Enumerative Combinatorics#
⎕IO←1
How to Count#
Enumerative Combinatorics is, in essence, the study of counting. Of course, we all (hopefully) know how to count, but in this chapter we’ll be using much more insightful techniques than you were taught as a child.
Let’s start with a simple example. Say we have a group of people - Alice, Bob, and Charlie - and we ask them to pick their favourite from a group of colours - red, green, blue, and yellow. How many different ways can our hypothetical gang pick these colours? Well, Alice has 4×4×4 ←→ 4*3 ←→ 64
possibilities. This holds in general. Say we have k
people and n
colours, there are n*k
ways for them to pick their favourite colours.
Consider another problem: we have a bookshelf nicely filled with 4×3×2×1 ←→ 24
ways to rearrange the books. Such a rearrangement of items is called a permutation, so we can say that there are '📕📘📗📙'
, a permutation of the books might be '📗📙📘📕'
.
Our calculation to count the permutations nicely generalises - if we have k×(k-1)×(k-2)×...×2×1 ←→ ×/⍳k
permutations of them. In combinatorics, this quantity is used all the time, so it gets its own name: the factorial. APL has factorial built in as monadic !
:
4×3×2×1
×/⍳4
!4
24
24
24
!0
is defined as
×/⍳0
!0
1
1
In traditional mathematical notation, the factorial is written postfix:
Now let’s consider a slightly more restricted scenario. We still want to put 7×6×5×4 ←→ 840
arrangments of 7×6×5×4×3×2×1 ←→ !7
and chop off the trailing 3×2×1 ←→ !3
, which we can do by dividing them: 7×6×5×4 ←→ (!7)÷!3 ←→ (!7)×!7-4
. Since an arrangement of all our books is a permutation, an arrangement of only some of them is a partial permutation or '📕📘📗📙'
, a '📙📘'
. In general, we only want the first n-k
terms. This tells us that there are (!n)÷!n-k
These are the kinds of problems we’re concerned with in enumerative combinatorics. Over the remainder of this chapter, we’ll be returning to these problems as well as many more. Once we’ve covered enough ground, we’re going to see a unified framework for looking at all sorts of counting problems called ‘The Twelvefold Way’. At this point, we’ll also look not just at counting all the possibilities for a problem, but also algorithms for generating them all.
Important
Enumerative combinatorics is the study of counting finite structures.
The factorial:
!k ←→ ×/⍳k ←→ k×(k-1)×(k-2)×...×2×1
, .A permutation is a rearrangement of a set.
There are
!n
permutations of an element set.A
-permutation is an arrangement of exactly elements of a set.There are
(!n)÷!n-k
-permutations of an element set.