Enumerative Combinatorics

Table of contents
Balls and Boxes
Counting Orderings
Counting Subsets
Types of Functions
Counting Surjections
Inclusion-Exclusion
Application of Inclusion-Exclusion - Counting Surjections
Counting Set Partitions: Stirling Numbers
Stars and Bars
Generating Functions
Integer Partitions
Catalan Numbers

Example 1

Suppose we have $k$ labelled balls (i.e., they are labelled with the integers $1, ..., k$ ), and $n$ labelled boxes (i.e. they are labelled with the integers $1, ..., n$ ) How many different ways are there to distribute the balls in the boxes, if every ball has to go in a box, and every box can hold arbitrarily many balls?
The answer to this problem is $n^{k}$ . For the first of the $k$ balls, there are $n$ choices for where to put the ball. For the second ball, there are again $n$ choices. If we repeat this for each of the $k$ balls, we will find that each ball has a choice of $n$ boxes. Therefore, the total amount of ways to arrange the balls is $n \times n \times ... \times n$ , $k$ times ( $= n^{k}$ ).

Like before, suppose we have $k$ labelled balls and $n$ labelled boxes, with the new conditions that $n = k$ and that each of the $n$ boxes has a capacity $1$ . How many ways are there to distribute the balls into the boxes?

Solution

Apply the same strategy of considering each ball individually and in order. For the first ball, there are $n$ choices of where to place it. No matter which of the $n$ boxes we choose, the second ball will have $n - 1$ choices for its placement, and so on, down to $1$ choice for the $k t h$ ball.
This gives the answer $n \cdot (n - 1) \cdot ...2 \cdot 1 = i = 1 \prod n i$
This expression comes up regularly

definition factorial

Let $n$ be a positive integer. We define the factorial of $n$ , denoted $n!$ , to be the product of positive integers at most $n$ . That is, $n! = 1 \cdot 2 \cdot ... \cdot (n - 1) \cdot n = i = 1 \prod n i$
We also define $0! = 1$

How many ways are there to choose 3 distinct objects out of a total of 10?

Solution

Using the previous strategy, there are 10 choices for the first object. No matter which of the 10 was chosen, there are then 9 choices for the second, and 8 for the third. This would give the answer as $10 \cdot 9 \cdot 8 = \frac{10 !}{7 !}$
However, we have overcounted—this is the number of of ways we can pick 3 objects if these objects are labelled. Therefore, we know how much we have overcounted by—the number of permutations of the 3 objects. The correct answer, factoring in the permutations, is $\frac{10 \cdot 9 \cdot 8}{3 \cdot 2 \cdot 1} = \frac{10 !}{7 ! 3 !} = 120$

proposition

Let $n$ be a positive integer, and let $k \leq n$ be a nonnegative integer. The number of ways to distribute $k$ unlabelled balls into $n$ labelled $c a p a c i t y - 1$ boxes is $\frac{n \cdot ( n - 1 ) \cdot ... \cdot ( n - ( k - 1 ))}{k \cdot ( k - 1 ) \cdot ... \cdot 2 \cdot 1} = \frac{n !}{k ! ( n - k )!}$

definition n choose k

Let $n \geq k$ be positive integers. We define n choose k, written $(k n)$ , to be the quantity $\frac{n !}{k ! ( n - k )!}$ . The value $(k n)$ is also called a “binomial coefficient.”

Notes on $(k n)$ :

$(k n) = (n - k n)$
$(0 n) = (n n) = 1$
We can write out all the binomial coefficients using “Pascal’s Triangle”

proposition

$(k n) = (k n - 1) + (k - 1 n - 1)$
There are 2 ways to prove this:

Proof 1

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

Proof 2

Suppose we want to choose $k$ things out of $n$ choices. We can choose the first one, then choose $k - 1$ things out of $n - 1$ choices, or we can not choose the first one, and choose $k$ things out of $n - 1$ choices.

Now consider that you are allowed to choose any number of objects—i.e. distribute 10 labelled balls into 2 labelled boxes with arbitrary capacity: “chosen” and “not chosen.” There is another way to present this—there are 10 unlabelled balls, and there are 11 labelled boxes—one for each of the balls (each with capacity 1), and one “not chosen” box (with capacity $\infty$ ). We have already shown that for labelled balls and labelled boxes with arbitrary capacity, the answer is $n^{k}$ —in this case, the answer is $2^{10}$ (Note that one of these options is to choose none of the balls).

We can also answer this in a different way—it is the number of 0 ball choices ( $(0 10) = 1$ ), plus the number of 1 ball choices ( $(1 10) = 10$ ) plus the number of 2 ball choices ( $(2 10) = 45$ ) and so on. From this, we can derive a formula: $2^{n} = k = 0 \sum n (k n)$

theorem Binomial Theorem

Let $n$ be a positive integer. Then: $(a + b)^{n} = k = 0 \sum n (k n) a^{k} b^{n - k}$

Example $(a + b)^{4} = a^{4} + 4 a^{3} b + 6 a^{2} b^{2} + 4 a b^{3} + b^{4}$

Proof

Specifying any term of $(a + b) (a + b) ... (a + b)$ consists of choosing, for each factor, either the $a$ or the $b$ . There are $(k n)$ ways to choose $k$ $a$ s and $n - k$ $b$ s.

proposition

Suppose we have $n$ labelled boxes, and $n$ balls— $k_{1}$ labelled with colour $c_{1}$ , $k_{2}$ labelled with colour $c_{2}$ , and so on up to $k_{r}$ labelled with colour $c_{r}$ , where $k_{1} + k_{2} + ... + k_{r} = n$ . Then the number of distinct ways to distribute the balls among the boxes is $\frac{n !}{k _{1} ! k _{2} ! ... k _{r} !}$

We give this quantity a symbol in analogy with binomial coefficients: $(k _{1} , k _{2} , ... , k _{r} n)$ , and call it a multinomial coefficient:

theorem Multinomial Theorem

Let $n$ be a positive integer. Then $(a_{1} + ... + a_{r})^{n} = k_{1} + ... + k_{r} = n \sum (k _{1} , ... , k _{r} n) a_{1}^{k_{1}} ... a_{r}^{k_{r}}$

Recall that if $K$ and $N$ are sets, a function $f : K \to N$ assigns a single element of $N$ to each element of $K$ . There are some important classes of functions:

definition Injective

A function $f : K \to N$ is injective or one-to-one if it takes each value at most once. That is, we never have $f (k_{1}) = f (k_{2})$ for $k_{1} \neq = k_{2}, k_{1}, k_{2} \in K$
It is only possible to have such a function if $K$ has at most as many elements as $N$ , i.e $∣ K ∣ \leq ∣ N ∣$

definition Surjective

A function $f : K \to N$ is surjective or onto if it takes each value at least once—i.e. if every $n \in N$ is equal to $f (k)$ for some $k \in K$ .
It is only possible to have such a function if $K$ has at least as many elements as $N$ , i.e. $∣ K ∣ \geq ∣ N ∣$

definition Bijective

A function $f : K \to N$ that is both injective and surjective is called bijective.
It is only possible to have such a function if $∣ K ∣ = ∣ N ∣$ .

Note

A function is bijective if and only if it has an inverse—A function $f : K \to N$ is bijective if and only if there exists a function $g : N \to K$ such that $f \circ g = i d_{N}$ , and $g \circ f = i d_{K}$ , where $i d_{n} : N \to N$ and $i d_{K} : K \to K$ are the identity functions.

Example

Here is a bijection $f$ from $K = {1, 2, 3}$ to $N = {A, B, C}$ :
$f (1) = A, f (2) = C, f (3) = B$

Notation

For brevity, we will denote ${1, ..., k}$ and ${1, ..., n}$ as $[k]$ and $[n]$ respectively. Note that 0 is not included, and $[0]$ is the empty set $\emptyset$

We have counted functions $[k] \to [n]$ (there are $n^{k}$ of them), as well as injective functions ( $\frac{n !}{( n - k )!}$ , assuming $k \leq n$ , and 0 otherwise), and bijective functions ( $n!$ assuming $n = k$ , otherwise 0). What about surjective functions?

Surjective functions are harder to count. Let’s define $Surj (k, n)$ to be the number.

Example

Let $n = 4$ and $k = 2$ . We could put 3 balls in one box and 1 ball in another (8 ways), or we could put 2 balls in each box (6 ways).

Example

250 students are taking Combinatorics, and 350 students are taking Algebra. How many students are taking at least one of the 2? The answer could be anywhere from 250 (every Combinatorics student also takes algebra) to 600 (no student takes both). To get the right answer, we need to subtract the number of students taking both to avoid double-counting them: $∣ A_{1} \cup A_{2} ∣ = ∣ A_{1} ∣ + ∣ A_{2} ∣ - ∣ A_{1} \cap A_{2} ∣$

Now what about $∣ A_{1} \cup A_{2} \cup A_{3} ∣$ ? Concretely:
Suppose 250 students are taking Combinatorics, 300 are taking Analysis, and 250 are taking Algebra. How many students in total are taking at least one of the three? To count, we could add $250 + 300 + 350 = 900$ , but clearly we have overcounted, as some students will have been counted more than once.

How much did we overcount by? Suppose 140 students do both Combinatorics and Algebra, 225 students do both Algebra and Analysis, and 175 students do both Analysis and Combinatorics. Furthermore, suppose 125 students are taking all 3 modules. So we have counted 125 students 3 times, and $15 + 100 + 50 = 140 + 224 + 175 - 3 \cdot 125 = 165$ students twice. Overall, we have overcounted by $165 + 125 \cdot 2 = 415$ , so the total number of students is $900 - 415 = 485$ .

theorem inclusion-Exclusion Theorem

Let $A_{1}, ..., A_{r}$ be sets. Then
$∣ A_{1} \cup ... \cup A_{r} ∣ = I \subseteq {1, ..., r}, I \neq = \emptyset \sum (- 1)^{∣ I ∣ - 1} ∣ i \in I ⋂ A_{i} ∣$

Proof

We need to see why each element of $A_{1} \cup ... \cup A_{r}$ gets counted exactly once in total on the right side. Let $J \subseteq {1, ..., r}$ be the set of $A_{i}$ s containing element $x$ (in other words, the set of modules a student $x$ is enrolled in). Then $x$ gets counted as $+ 1$ in term $I$ for all $I \subseteq J$ with an odd number of elements, and $x$ gets counted as $- 1$ in term $I$ for all nonempty $I \subseteq J$ with an even number of elements.

Overall, $x$ gets counted
$(1 ∣ J ∣) - (2 ∣ J ∣) + (3 ∣ J ∣) - (4 ∣ J ∣) + ... + (- 1)^{∣ J ∣ + 1} (∣ J ∣ ∣ J ∣)$
This is the same as
$(0 ∣ J ∣) + k = 0 \sum ∣ J ∣ (- 1)^{k + 1} (k ∣ J ∣) = (0 ∣ J ∣) + 0^{∣ J ∣}$
Where the last equality is by expanding $(- 1 + 1)^{∣ J ∣}$ using the binomial theorem. Thus, $x$ gets counted altogether $(0 ∣ J ∣) = 1$ time.

Back to the problem of counting surjections $[k] \to [n]$ . We have discovered it may be easier to count functions that are not surjections, but how can we break up this set as much as possible?

How can a function fail to be surjective? It must miss some element $i \in [n]$ —so the set of non-surjective functions is precisely the union, over $i \in [n]$ , of functions that miss $i$ .

Define $A_{i}$ to be the set of functions missing $i$ . Now lets try to apply inclusion-exclusion. $A_{i}$ is the set of functions $[k] \to [n] \ {i}$ , so $∣ A_{i} ∣ = (n - 1)^{k}$ .

We also need to calculate $∣ A_{i} \cap A_{j} ∣$ . $A_{i} \cap A_{j}$ is the set of functions $[k] \to [n] \ {i, j}$ , so $∣ A_{i} \cap A_{j} ∣ = (n - 2)^{k}$

We can calculate any term of the inclusion exclusion formula: $∣ ⋂_{i \in I} A_{i} ∣ = (n - ∣ I ∣)^{k}$ . So the number of non-surjections $[k] \to [n]$ is
$I \subseteq [n], I \neq = \emptyset \sum (- 1)^{∣ I ∣ + 1} (n - ∣ I ∣)^{k}$
Subtracting this from the total number of functions gives $Surj (k, n)$ :
$Surj (k, n) = n^{k} - I \subseteq [n], I \neq = \emptyset \sum (- 1)^{∣ I ∣ + 1} (n - ∣ I ∣)^{k} = I \subseteq [n] \sum (- 1)^{∣ I ∣} (n - ∣ I ∣)^{k}$

We can simplify this formula (to remove having to sum over a very large set) by grouping terms with the same size $I$ , as follows:
$Surj (k, n) = I \subseteq [n] \sum (- 1)^{∣ I ∣} (n - ∣ I ∣)^{k} = m = 0 \sum n I \subseteq [n], ∣ I ∣ = m \sum (- 1)^{∣ I ∣} (n - ∣ I ∣)^{k}$ $= m = 0 \sum n I \subseteq [n], ∣ I ∣ = m \sum (- 1)^{m} (n - m)^{k}$
$= m = 0 \sum n (- 1)^{m} (n - m)^{k} I \subseteq [n], ∣ I ∣ = m \sum 1$
$= m = 0 \sum N (- 1)^{m} (n - m)^{k} (m n)$
To check, let’s use the example from before:
$Surj (4, 2) = 2^{4} (0 2) - 1^{4} (1 2) + 0^{4} (2 2) = 16 - 2 + 0 = 14$
We can also see that if $k = 1$ and $n > 1$ , then
$0 = Surj (k, n) = m = 0 \sum n (- 1)^{m} (n - M) (m n)$
Using $(m n) = (n - m n)$ and the substitution $j = n - m$ gives
$0 = (- 1)^{n} j = 0 \sum n (- 1)^{j} j (j n)$

What if we count surjections, but with unlabelled boxes. This can be interpreted as counting the ways of dividing $[k]$ into $n$ nonempty pieces. These numbers $S (k, n)$ are called the Stirling numbers of the second kind. If we think this through carefully, each surjection gets counted exactly $n!$ times, giving the formula:
$S (k, n) = \frac{1}{n !} m = 0 \sum n (- 1)^{m} (n - m)^{k} (m n)$
Similarly to the binomial coefficients, we can make observations by writing the Stirling numbers out in a triangle

proposition

$S (k, n) = S (k - 1, n - 1) + n S (k - 1, n)$

Proof

Does $1 \in [k]$ form a singleton block? If yes, there are $K (k - 1, n - 1)$ ways to partition the rest of the set. If no, removing $1$ yields a partition of $[k] \ {1} = {2, ..., k}$ into $n$ pieces, and $1$ must have come from one of these pieces.

Notes

If we allowed empty parts, we would be partitioning $[k]$ into at most $n$ parts, which would form a summation.

Notation

For $k \geq o$ , define the Bell numbers $B_{k} = \sum_{n = 0}^{k} S (k, n)$ . That is, $B_{k}$ is the number of ways to partition $[k]$ into any number of parts.
The first few Bell numbers are $1, 1, 2, 5, 15, 52, 203, 877, 4140, ...$

proposition

$B_{k} = n = 0 \sum k - 1 (n k - 1) B_{n}$

Proof

I’m lazy I’ll do it later

If we have $k$ unlabelled balls, and $n$ labelled boxes (of arbitrary capacity), how many ways can we distribute the balls?

Example

Let $k = 3$ and $n = 3$ . The ways to arrange the balls are:
3 | 0 | 0 2 | 1 | 0 2 | 0 | 1 1 | 2 | 0 1 | 1 | 1
1 | 0 | 2 0 | 3 | 0 0 | 2 | 1 0 | 1 | 2 0 | 0 | 3

Which is the same as $x^{3}, x^{2} y, x^{2} z, x y^{2} x yz, x z^{2}, y^{3}, y^{2} z, y z^{2}, z^{3}$

Note that we get a recursion $C_{k, n} = \sum_{i = 0}^{k} F_{k - i, n - 1}$

This example can be redrawn as follows:
* * *|| |*| ||* *|**| *|*|*|
*|| |*| ||* |*| ||***

They are sequences of 5 symbols, with 2 bars and 3 stars. That is, choose 3 stars out of 5 slots.

proposition

There are $(n - 1 n + ( k - 1 ))$ ways to distribute the balls.

definition Ordinary and Exponential Generating Functions

Let $(a_{n})_{n \geq 0}$ be a sequence of numbers. The formal power series
$n = 0 \sum \infty a_{n} x^{n}$
is called the ordinary generating function of $(a_{n})_{n \geq o}$ , and the formal power series
$n = 0 \sum \infty a_{n} \frac{x ^{n}}{n !}$
is called the exponential generating function of $(a_{n})_{n \geq 0}$
Where “formal” means we haven’t checked whether the power series has a nonzero radius of convergence.

Example

Let $f_{n}$ denote the $n$ th Fibonacci number, defined by $f_{0} = f_{1} = 1$ and $f_{n} = f_{n - 1} + f_{n - 2}$ for $n \geq 2$ .
The generating function $F (x)$ for the Fibonacci numbers is as follows:
$F (x) = 1 + x + 2 x^{2} + 3 x^{3} + 5 x^{4} + 8 x^{5} + 13 x^{6} + 21 x^{7} + ...$
Note what happens when $F (x)$ is multiplied by $x$ and $x^{2}$ .
$x F (x) = x + x^{2} + 2 x^{3} + 3 x^{4} + 5 x^{5} + 8 x^{6} + 13 x^{7} + ...$
$x^{2} F (x) = x^{2} + x^{3} + 2 x^{4} + 3 x^{5} + 5 x^{6} + 8 x^{7} + ...$
Using the recursion we see that $1 + x F (x) + x^{2} F (x) = F (x)$ . We can solve for $F (x)$ to get $F (x) = \frac{1}{1 - x - x ^{2}}$ .

Note: I am so confused what the fuck is this shit

Let $k \leq n$ be positive integers. How many ways are there to divide $n$ unlabelled balls into $k$ unlabelled boxes so that each box gets a ball? Now all that matters is the number of balls in each box. This is the number of ways to write the integer $n$ as a sum of $k$ positive integers (without caring about the order). We call this number $p_{k} (n)$ .

Example

There are 8 partitions of 10 into 3 parts:
$8 + 1 + 1, 7 + 2 + 1, 6 + 3 + 1, 6 + 2 + 2, 5 + 4 + 1, 5 + 3 + 2, 4 + 4 + 2, 4 + 3 + 3$

If we allow any number of boxes, we get $p (n)$ , the number of partitions of $n$ .

Example

There are 7 partitions of 5:
$5, 4 + 1, 3 + 2, 3 + 1 + 1, 2 + 2 + 1, 2 + 1 + 1 + 1, 1 + 1 + 1 + 1 + 1$

There are no good formulas for $p (n)$ or $p_{k} (n)$

definition Conjugate Partition

Let $λ$ be a partition of $n$ . The conjugate partition $λ^{T}$ of $λ$ is the partition corresponding to the reflection of the Ferrers diagram of $λ$ over the diagonal

Example $4 + 1$ is conjugate to $2 + 1 + 1 + 1$ . $3 + 1 + 1$ is conjugate to itself

proposition

The number of partitions of $n$ into at most $k$ parts is equal to the number of partitions of $n$ into parts of size at most $k$

Example

The partitions of 7 into at most 3 pieces:
$7, 6 + 1, 5 + 2, 4 + 3, 5 + 1 + 1, 4 + 2 + 1, 3 + 3 + 1, 3 + 2 + 2$
The partitions of 7 into parts of size at most 3:
$3 + 3 + 1, 3 + 2 + 1, 3 + 2 + 1 + 1, 3 + 1 + 1 + 1 + 1, 2 + 2 + 2 + 1, 2 + 2 + 1 + 1 + 1, 2 + 1 + 1 + 1 + 1 + 1, 1 + 1 + 1 + 1 + 1 + 1 + 1$

Proof

The two sets of partitions are related by conjugation

proposition

The number of partitions of $n$ into distinct off parts is equal to the number of self-conjugate partitions of $n$

proposition The number of partitions of $n$ into odd parts is equal to the number of partitions of $n$ into distinct parts

Example

Let $n = 8$
Odd parts: $7 + 1, 5 + 3, 5 + 1 + 1 + 1, 3 + 3 + 1 + 1, 3 + 1 + 1 + 1 + 1 + 1, 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1$
Distinct parts: $8, 7 + 1, 6 + 2, 5 + 3, 5 + 2 + 1, 4 + 3 + 1$

Proof $(1 + x^{i}) = \frac{1 - x ^{2 i}}{1 - x ^{i}}$ , we have $n \geq 0 \sum p_{d i s t in c t} (n) x^{n} = i \geq 1 \prod (1 + x^{i}) = i \geq 1 \prod \frac{1 - x ^{2 i}}{1 - x ^{1}}$ $= \frac{( 1 - x ^{2} ) ( 1 - x ^{4} ) ( 1 - x ^{6} ) ...}{( 1 - x ) ( 1 - x ^{2} ) ( 1 - x ^{3} ) ...}$ $= \frac{1}{( 1 - x ) ( 1 - x ^{3} ) ( 1 - x ^{5} ) ...} = n \geq 0 \sum p_{o dd} (n) x^{n}$

Using

definition Triangulation

A triangulation of a regular $n$ -gon is a collection of non-crossing diagonals that divide the $n$ -gon into triangles.

definition Catalan Number

The $n$ th Catalan number $C_{n}$ is the number of triangulations of a regular $(n + 2)$ -gon.

definition Balanced Sequence

A balanced sequence of $n$ opening and $n$ closing parenthesis is a sequence such that every close-parenthesis has a matching open-parenthesis