Combinatorics

Just enough combinatorics to get by. Each section is builds on the previous ones, so read in order.

Rule of product

This is the simplest and most basic rule of combinatorics. It states that if there are $n$ possible ways of doing action 1 and $m$ possible ways of doing action 2, then there are $nm$ possible ways of doing both action 1 and action 2.

For example, if I have $4$ shirts and $3$ trousers, then there are $4 \cdot 3 = 12$ possible combinations of clothes I can choose from.

This can be visualized as counting the leaves of the following tree (if you'll excuse the sloppy ASCII art):

   Shirts represented as S1, S2, S3, S4.
   Trousers represented as T1, T2, T3.
   (Though I think they call them "pants" in the USA)

   -------------------------------
   |         |         |         |
   S1        S2        S3        S4
   |         |         |         |
   -------   -------   -------   -------
   |  |  |   |  |  |   |  |  |   |  |  |
   T1 T2 T3  T1 T2 T3  T1 T2 T3  T1 T2 T3

Each leaf represents a possible choice of clothes and every choice is represented by one leaf. The number of leaves is $4 \cdot 3$ and thus such is the number of choice of clothes too.

Permutations (or: queues)

Given $n$ people, how many different ways are there of ordering them in a queue? This can be solved using the rule of product: we can choose $n$ people for the first place, $n-1$ people for the second place, $n-2$ for the third and so on, up to the $n$th place where we can only place the one person remaining. So the number of possible queues of $n$ people is $n(n-1)(n-2)...2\cdot1 = n!$

Each such queue is called a permutation of $n$ elements. This can also be visualized as a tree.

A slightly more general problem is that of forming queues of $k$ people from a total of $n$ people. It can also be solved using the rule of product (and visualized as a tree the same way). The number of such queues is $P^n_k = n(n-1)(n-2)...(n-k+1)$. There are $k$ factors in this product, one for each place in the queue; a nicer way of expressing it is $P^n_k = \frac{n!}{(n-k)!}$. Note that setting $k = n$ recovers our previous result.

Combinations (or: subsets)

How many subsets of $k$ elements are there in a set of $n$ elements? Let's say we want to count all subsets of size 2 of set $S = \{a,b,c,d\}$. An attempt of doing this using the product rule would yield $4\cdot3$ subsets: $4$ choices for the first element and $3$ choices for the second element, right? Not quite: we are counting the same subset $\{a,b\}$ and $\{b,a\}$ twice. What we have done is no different to counting permutations, in which the order does matter. Noting this gets us closer to the solution. We know that there are $P^n_k$ permutations of size $k$ from $n$ elements. Counting permutations is like counting subsets, except for the fact that every subset gets counted many times… namely $k!$ times, once for each possible way of rearranging said subset.

So the number of possible subsets can be obtained by dividing $P^n_k$ by $k!$. To sum up, $C^n_k = \frac{P^n_k}{k!} = \frac{n!}{k!(n-k)!}$ is the number of subsets of size $k$ in a set of size $n$.

$C^n_k$ is also denoted as $n \choose k$ and called a binomial coefficient. It has many nice properties and uses besides combinatorics.

Reordering classes of objects (or: scrabble)

Given $n$ letters, how many words can we form with them? It would be tempting to answer $n!$ right away, the number of permutations of $n$ elements, but this is true only if all letters are different. To put it another way, if given letters $EOHLL$, we wouldn't want to count the word $HELLO$ once for every way we can reorder both letters $L$, since they are the same word. This is more clearly understood by imagining a game of scrabble: there are two physically different tiles with the letter $L$ on them, but we don't care which comes first.

To generalize: let's say we are given $n$ scrabble tiles (I avoid saying “$n$ letters” here). There are $n_i$ tiles with letter $i$ for $i=1..k$, where $k$ is the number of letters in the alphabet (so $\sum_{i=0}^k n_i = n$). Then there are $\frac{n!}{n_1!n_2!...n_k!}$ words you could possibly form. In other words, we first calculate the total number of permutations and then correct the repeated counts by dividing by each of the $n_i!$ permutations of the same letter.

Choosing from classes of objects (or: voting)

How many possible outcomes are there to an election, if there are $n$ candidates and $k$ voters?

In this problem, votes cast to the same candidate are indistinguishable. To be as clear as possible, if we have candidates A and B and two voters, John and Peter, the following are considered the same:

  • John votes for A and Peter votes for B.
  • Peter votes for A and John votes for B.
  • Peter votes for B and John votes for A.
  • John votes for B and Peter votes for A.

We don't care about who voted for whom or the order in which they voted. We only care about the fact that A received one vote and B received one vote. This is what happens in an election, after all.

This can be visualized using $k$ dots (votes) and $n-1$ sticks that separate the votes into $n$ sets, like this:

    Candidates: C1, C2, C3, C4, separated by sticks. There are n=4 candidates, and thus n-1=3 sticks.
    Votes: k=10 voters, represented as dots.

    This represents an outcome in which candidate 1 has 2 votes, candidate 2 has 3 votes, etc.

    C1    C2     C3     C4 
   ..  | ...   |      | .....     

Note that every possible outcome of the election is represented by an arrangement of sticks and dots, and every possible such arrangement represents an outcome. So counting such arrangements is equivalent to counting election outcomes. And we already know how to count these kinds of arrangements. It's a reordering of classes of elements, a scrabble-like problem in which there are two kinds of letters (sticks and dots).

Let's calculate. There are $n-1$ sticks and $k$ dots, so we have $n-1+k$ scrabble tiles… I mean objects we must rearrange. There are $(n-1+k)!$ such rearrangements. But, to account for repeated elements, we must divide by $(n-1)!$ and by $k!$, too. To sum up:

$$ \frac{(n-1+k)!}{(n-1)!k!} = \frac{(n-1+k)!}{(n-1+k-k)! k!} = {n-1+k \choose k} $$

is the number of possible outcomes of an election with $n$ candidates and $k$ voters.

This result can be used to count domino tiles. How come? Imagine an election with $n=7$ candidates (numbers 0 to 6) and $k=2$ voters (since a tile has 2 sides). Each possible outcome of this election is written in a domino tile. So there are ${n-1+k \choose k} = {7-1+2 \choose 2} = {8 \choose 2} = \frac{8!}{2!\cdot 6!} = \frac{8 \cdot 7}{2} = 28$ possible domino tiles.

Partitions

Given $n$ people, how many ways are there to divide them into $k$ groups?

The answer depends on whether the people and the groups are distinguishable or not.

People Groups Example
Distinguishable Distinguishable Each of $n$ people choose one of $k$ buses, each of which has a different destination
Indistinguishable Distinguishable Each of $n$ clones board into one of $k$ buses, each of which has a different destination
Distinguishable Indistinguishable Each of $n$ people choose one of $k$ buses, all of which go to the same destination
Indistinguishable Indistinguishable Each of $n$ clones board into one of $k$ buses, all of which go to the same destination

Distinguishable people and distinguishable groups

The answer for distinguishable people and distinguishable groups is simply $k^n$, because of the rule of product: the first person has $k$ buses to choose from, the second person also has $k$ choices, etc.

What if we require each group to have at least one member? (I'm not sure, but I thing it might be related to the Stirling number of the second kind plus some shuffling. I'm not writing a definite formula here since I haven't proved it).

Indistinguishable people and distinguishable groups

If people are indistinguishable, let's represent them as $n$ dots and let's use $k-1$ sticks to separate them

  n=14 people (dots).
  k=3 buses, so k-1=2 sticks.
  
  Some possible divisions:
  .....|........|.   (5 in bus 1, 8 in bus 2, 1 in bus 3) 
  .....|.........|   (nobody in bus 3)
  ||..............   (everybody in bus 3)

Each possible reordering of sticks and dots represents an assignment of people into buses. We already had this! There are ${k-1+n \choose n}$ such reorderings.

Note that dots and sticks can only be used when dots are indistinguishable and groups are distinguishable.

What if we make the requirement none of the buses can be empty? This can also be answered by reasoning with dots and sticks. But instead of rearranging said dots and sticks, we lay all $n$ dots in a line and choose without repetition $k-1$ of the $n-1$ spaces between the dots to insert the $k-1$ sticks. Each such choice defines exactly one arrangement in which none of the buses is empty, and any such arrangement can be represented this way. So, if buses can't be empty, there are $C^{n-1}_{k-1} = {n-1 \choose k-1}$ possible distributions.

Distinguishable people and indistinguishable groups

What would it mean that people are distinguishable but buses are not? Imagine we have people A, B and C and buses 1 and 2. Then, the following should be considered the same:

  • A, B board bus 1 and C boards bus 2.
  • C boards bus 1 and A, B board bus 2.

While the following should be counted as two different events:

  • A, B board bus 1 and C boards bus 2.
  • A, C boards bus 1 and B board bus 2.

If empty buses are not allowed, the answer is the Stirling number of the second kind $S(n,k) = \{{n \atop k}\} = \frac{1}{k!}\sum_{j=0}^{k}(-1)^{k-j}{k \choose j}j^n$.

If empty buses are allowed, the answer can be obtained by considering situations in which exactly 1, 2, … up to $k$ buses are not empty, and summing over all these situations, so: $\sum_{i=1}^k S(n,i)$

Indistinguishable people and indistinguishable groups

To be done…