Ferkans — Interactive Telecom Tutor

Why Advanced Counting?

In Chapters 2 and 3 we developed the basic counting toolkit — permutations, combinations, and multinomial coefficients. These suffice when the objects we count are drawn from a single set and placed into a single structure. But many problems in probability and combinatorics require us to count partitions of a set into an unspecified number of blocks, or to enumerate permutations by their cycle structure. Stirling numbers and Bell numbers are the tools for these richer counting problems. They also preview the generating function technique that we will use systematically when we study probability generating functions in Chapter 9.

Definition:
Stirling Number of the Second Kind

For non-negative integers $n$ and $k$ , the Stirling number of the second kind, denoted $S(n, k)$ or $\left\{\begin{smallmatrix} n \\ k \end{smallmatrix}\right\}$ , is the number of ways to partition a set of $n$ elements into exactly $k$ non-empty, unordered subsets (called blocks).

By convention, $S(0, 0) = 1$ (the empty set has exactly one partition — the empty partition) and $S(n, 0) = 0$ for $n \geq 1$ .

The notation $\left\{\begin{smallmatrix} n \\ k \end{smallmatrix}\right\}$ is due to Knuth. The alternative $S(n,k)$ is more common in probability texts.

Theorem: Recurrence for Stirling Numbers of the Second Kind

For $n \geq 1$ and $1 \leq k \leq n$ : $S(n, k) = k \cdot S(n-1, k) + S(n-1, k-1)$ with boundary conditions $S(n, n) = 1$ and $S(n, 1) = 1$ for all $n \geq 1$ .

Consider element $n$ . Either it forms a singleton block (contributing $S(n-1, k-1)$ partitions of the remaining elements into $k-1$ blocks), or it is inserted into one of the $k$ existing blocks of a partition of $\{1, \ldots, n-1\}$ into $k$ blocks (contributing $k \cdot S(n-1, k)$ partitions).

Proof

Case 1: element $n$ is a singleton

If $\{n\}$ is one of the $k$ blocks, then the remaining $n-1$ elements must be partitioned into $k-1$ non-empty blocks. The number of such partitions is $S(n-1, k-1)$ .

Case 2: element $n$ joins an existing block

If $\{n\}$ is not a singleton, remove $n$ from its block. The remaining $n-1$ elements form a partition into $k$ non-empty blocks (the block from which we removed $n$ is still non-empty since $n$ was not alone). There are $S(n-1, k)$ such partitions, and element $n$ can be placed into any of the $k$ blocks. This gives $k \cdot S(n-1, k)$ .

Combine

Since the two cases are mutually exclusive and exhaustive: $S(n, k) = S(n-1, k-1) + k \cdot S(n-1, k). \qquad \square$

Example: Computing Small Stirling Numbers

Compute $S(4, 2)$ — the number of ways to partition $\{1, 2, 3, 4\}$ into exactly 2 non-empty blocks.

Solution

List all partitions

The partitions of $\{1,2,3,4\}$ into 2 blocks are: $\{\{1\}, \{2,3,4\}\}$ , $\{\{2\}, \{1,3,4\}\}$ , $\{\{3\}, \{1,2,4\}\}$ , $\{\{4\}, \{1,2,3\}\}$ , $\{\{1,2\}, \{3,4\}\}$ , $\{\{1,3\}, \{2,4\}\}$ , $\{\{1,4\}, \{2,3\}\}$ .

Count and verify

There are $S(4,2) = 7$ partitions. We can verify with the recurrence: $S(4,2) = 2 \cdot S(3,2) + S(3,1) = 2 \cdot 3 + 1 = 7$ . $\checkmark$

Theorem: Explicit Formula for Stirling Numbers of the Second Kind

For $0 \leq k \leq n$ : $S(n, k) = \frac{1}{k!} \sum_{j=0}^{k} (-1)^{k-j} \binom{k}{j} j^n$

The factor $k!$ accounts for the fact that blocks are unordered. The alternating sum is an inclusion-exclusion over surjections from $[n]$ onto $[k]$ : we count all functions, subtract those missing at least one value in $[k]$ , add back those missing at least two, and so on.

Proof

Count surjections via inclusion-exclusion

Let $A_i$ be the set of functions $f: [n] \to [k]$ that do not map any element to $i$ . The number of surjections from $[n]$ onto $[k]$ is: $\left|\overline{A_1} \cap \cdots \cap \overline{A_k}\right| = \sum_{j=0}^{k} (-1)^j \binom{k}{j}(k-j)^n$

Relate surjections to partitions

Each surjection $f: [n] \to [k]$ defines an ordered partition $(f^{-1}(1), \ldots, f^{-1}(k))$ into $k$ non-empty blocks. Since blocks are unordered in $S(n,k)$ , each unordered partition corresponds to $k!$ surjections. Therefore: $S(n, k) = \frac{1}{k!}\sum_{j=0}^{k}(-1)^j\binom{k}{j}(k-j)^n = \frac{1}{k!}\sum_{j=0}^{k}(-1)^{k-j}\binom{k}{j}j^n \qquad \square$

Definition:
Unsigned Stirling Number of the First Kind

The unsigned Stirling number of the first kind, denoted $\left[\begin{smallmatrix} n \\ k \end{smallmatrix}\right]$ or $c(n, k)$ , is the number of permutations of $[n] = \{1, 2, \ldots, n\}$ that have exactly $k$ disjoint cycles.

The signed Stirling number of the first kind is $s(n, k) = (-1)^{n-k} c(n, k)$ .

Theorem: Recurrence for Unsigned Stirling Numbers of the First Kind

For $n \geq 1$ and $1 \leq k \leq n$ : $c(n, k) = (n-1) \cdot c(n-1, k) + c(n-1, k-1)$ with $c(0, 0) = 1$ and $c(n, 0) = 0$ for $n \geq 1$ .

Consider element $n$ in a permutation of $[n]$ . Either $n$ forms a fixed point (a cycle of length 1), contributing $c(n-1, k-1)$ from the remaining elements, or $n$ is inserted into an existing cycle of a permutation of $[n-1]$ with $k$ cycles. There are $n-1$ positions where $n$ can be inserted (after any of the $n-1$ elements in that permutation), giving $(n-1) \cdot c(n-1, k)$ .

Proof

Case 1: $n$ is a fixed point

If $(n)$ is a cycle of length 1, the remaining $n-1$ elements form a permutation with $k-1$ cycles. There are $c(n-1, k-1)$ such permutations.

Case 2: $n$ is inserted into an existing cycle

Remove $n$ from its cycle by connecting its predecessor directly to its successor. This yields a permutation of $[n-1]$ with $k$ cycles. There are $c(n-1, k)$ such permutations, and $n$ can be inserted after any of the $n-1$ elements, giving $(n-1) \cdot c(n-1, k)$ choices.

Combine

$c(n, k) = c(n-1, k-1) + (n-1) \cdot c(n-1, k). \qquad \square$ $

Example: Permutations of $[3]$ by Cycle Structure

List all permutations of $\{1, 2, 3\}$ and classify them by number of cycles. Verify the values $c(3, 1)$ , $c(3, 2)$ , $c(3, 3)$ .

Solution

Enumerate

The 6 permutations in cycle notation:

3 cycles: $(1)(2)(3)$ — the identity. Count: 1.
2 cycles: $(12)(3)$ , $(13)(2)$ , $(1)(23)$ . Count: 3.
1 cycle: $(123)$ , $(132)$ . Count: 2.

Verify

$c(3, 3) = 1$ , $c(3, 2) = 3$ , $c(3, 1) = 2$ . Check: $1 + 3 + 2 = 6 = 3!$ . $\checkmark$

Recurrence check: $c(3, 2) = 2 \cdot c(2, 2) + c(2, 1) = 2 \cdot 1 + 1 = 3$ . $\checkmark$

Duality Between Stirling Numbers

The two kinds of Stirling numbers satisfy an orthogonality relation. If we define $s(n,k) = (-1)^{n-k} c(n,k)$ , then: $\sum_{j=k}^{n} s(n,j) \cdot S(j,k) = \delta_{nk}, \qquad \sum_{j=k}^{n} S(n,j) \cdot s(j,k) = \delta_{nk}$ In matrix form, the matrices of signed Stirling numbers of the first and second kind are inverses of each other.

Definition:
Bell Number

The Bell number $B_n$ is the total number of partitions of a set of $n$ elements into non-empty, unordered subsets: $B_n = \sum_{k=0}^{n} S(n, k)$ By convention, $B_0 = 1$ .

The first few Bell numbers are: $B_0 = 1$ , $B_1 = 1$ , $B_2 = 2$ , $B_3 = 5$ , $B_4 = 15$ , $B_5 = 52$ .

Theorem: Bell Number Recurrence

For $n \geq 1$ : $B_n = \sum_{k=0}^{n-1} \binom{n-1}{k} B_k$

Consider element $n$ . It belongs to some block of size $j$ where $1 \leq j \leq n$ . Choose the $j-1$ other elements of that block from the remaining $n-1$ in $\binom{n-1}{j-1}$ ways, then partition the other $n-j$ elements in $B_{n-j}$ ways. Summing over $j$ and substituting $k = n - j$ gives the formula.

Proof

Condition on the block containing element $n$

Let the block containing $n$ have size $j$ , where $1 \leq j \leq n$ . We must choose $j - 1$ companions for $n$ from $\{1, \ldots, n-1\}$ in $\binom{n-1}{j-1}$ ways, then partition the remaining $n - j$ elements arbitrarily in $B_{n-j}$ ways.

Sum over block sizes

$B_n = \sum_{j=1}^{n} \binom{n-1}{j-1} B_{n-j} = \sum_{k=0}^{n-1} \binom{n-1}{k} B_k$ $where we substituted$ k = n - j $.$ \qquad \square$

Theorem: Exponential Generating Function of Bell Numbers

The exponential generating function (EGF) of the Bell numbers is: $\sum_{n=0}^{\infty} B_n \frac{x^n}{n!} = e^{e^x - 1}$

The EGF for set partitions factors as the exponential of the EGF for non-empty subsets. Since the EGF for a single non-empty subset is $e^x - 1$ , the composition gives $\exp(e^x - 1)$ . This is a fundamental instance of the exponential formula in enumerative combinatorics.

Proof

EGF for $S(n,k)$

The EGF for the number of partitions into exactly $k$ blocks is $\frac{(e^x - 1)^k}{k!}$ , because each block is a non-empty subset (EGF: $e^x - 1$ ) and blocks are unordered (divide by $k!$ ).

Sum over $k$

$\sum_{n=0}^{\infty} B_n \frac{x^n}{n!} = \sum_{k=0}^{\infty} \frac{(e^x - 1)^k}{k!} = e^{e^x - 1}. \qquad \square$ $

Definition:
Integer Partition

An integer partition of a positive integer $n$ is a way of writing $n$ as a sum of positive integers, where the order of summands does not matter. Each summand is called a part. The number of integer partitions of $n$ is denoted $p(n)$ .

For example, the partitions of 5 are: $5$ , $4+1$ , $3+2$ , $3+1+1$ , $2+2+1$ , $2+1+1+1$ , $1+1+1+1+1$ , so $p(5) = 7$ .

Integer partitions are distinct from set partitions. The set $\{1,2,3,4,5\}$ has $B_5 = 52$ set partitions, but the integer 5 has only $p(5) = 7$ integer partitions. Integer partitions count how many objects go in each block; set partitions also track which objects go where.

Historical Note: Euler and the Theory of Partitions

18th–20th century

Leonhard Euler initiated the systematic study of integer partitions in the 1740s. His key insight was to encode partitions via generating functions: the number of partitions of $n$ is the coefficient of $x^n$ in the product $\prod_{k=1}^{\infty} \frac{1}{1 - x^k}$ . This observation opened the door to an entire branch of combinatorics and number theory. A century and a half later, Hardy and Ramanujan (1918) established the celebrated asymptotic formula $p(n) \sim \frac{1}{4n\sqrt{3}} e^{\pi\sqrt{2n/3}}$ using the circle method — one of the landmarks of analytic number theory.

Theorem: Generating Function for Integer Partitions

The ordinary generating function for the partition function $p(n)$ is: $\sum_{n=0}^{\infty} p(n)\, x^n = \prod_{k=1}^{\infty} \frac{1}{1 - x^k}, \qquad |x| < 1$

Each factor $\frac{1}{1 - x^k} = 1 + x^k + x^{2k} + \cdots$ corresponds to choosing how many parts of size $k$ appear in the partition: 0, 1, 2, and so on. The product over all $k$ generates all possible combinations of part sizes.

Proof

Expand each factor

Write $\frac{1}{1-x^k} = \sum_{m_k=0}^{\infty} x^{k \cdot m_k}$ , where $m_k$ counts the number of parts equal to $k$ .

Take the product

$\prod_{k=1}^{\infty} \frac{1}{1-x^k} = \sum_{m_1, m_2, \ldots \geq 0} x^{1 \cdot m_1 + 2 \cdot m_2 + 3 \cdot m_3 + \cdots}$ $The coefficient of$ x^n $is the number of sequences$ (m_1, m_2, \ldots) $of non-negative integers with$ \sum_{k=1}^{\infty} k \cdot m_k = n $. Each such sequence encodes a partition of$ n $.$ \qquad \square$

,

Generating Functions: A Preview

The generating functions we encountered for Bell numbers and integer partitions are instances of a powerful general technique: encode a counting sequence $\{a_n\}$ as the coefficients of a formal power series $A(x) = \sum a_n x^n$ (ordinary GF) or $A(x) = \sum a_n x^n/n!$ (exponential GF). Algebraic operations on power series — multiplication, composition, differentiation — then correspond to combinatorial operations on the underlying structures.

In Chapter 9 we will formalize this idea in the probabilistic setting: the probability generating function $G_X(z) = \mathbb{E}[z^X]$ and the moment generating function $M_X(t) = \mathbb{E}[e^{tX}]$ will let us derive distributions of sums of independent random variables, prove the central limit theorem, and establish large deviation bounds.

Stirling number of the second kind

$S(n,k)$ : the number of partitions of an $n$ -element set into exactly $k$ non-empty, unordered subsets.

Related: Bell number, set partition

Stirling number of the first kind

$c(n,k)$ (unsigned): the number of permutations of $[n]$ with exactly $k$ cycles.

Bell number

$B_n = \sum_{k=0}^{n} S(n,k)$ : the total number of partitions of an $n$ -element set.

set partition

A collection of non-empty, pairwise disjoint subsets (blocks) of a set $S$ whose union is $S$ .

Related: Bell number

integer partition

A representation of a positive integer $n$ as an unordered sum of positive integers. The number of such representations is $p(n)$ .

Related: set partition

Quick Check

What is $S(4, 3)$ ?

3

6

7

4

Correction:

6

Correct. $S(4,3) = 3 \cdot S(3,3) + S(3,2) = 3 \cdot 1 + 3 = 6$ . Equivalently, choose which 2 of the 4 elements share a block: $\binom{4}{2} = 6$ .

Quick Check

What is $B_4$ ?

14

15

16

52

Correction:

15

Correct. $B_4 = 1 + 7 + 6 + 1 = 15$ .

Common Mistake: Set Partitions vs. Integer Partitions

Mistake:

Confusing the number of set partitions of $[n]$ (counted by $B_n$ ) with the number of integer partitions of $n$ (counted by $p(n)$ ).

Correction:

Set partitions care about which elements go into each block; integer partitions care only about the sizes of the blocks. For $n = 5$ : $B_5 = 52$ set partitions but only $p(5) = 7$ integer partitions.

Key Takeaway

Stirling numbers of the second kind $S(n,k)$ count set partitions into $k$ blocks; Stirling numbers of the first kind $c(n,k)$ count permutations with $k$ cycles. Both satisfy simple recurrences that parallel Pascal's identity. Bell numbers $B_n$ sum over all $k$ and admit the elegant EGF $e^{e^x - 1}$ . Integer partitions $p(n)$ have the Euler product generating function $\prod(1-x^k)^{-1}$ .

Advanced Counting

Why Advanced Counting?

Definition: Stirling Number of the Second Kind

Theorem: Recurrence for Stirling Numbers of the Second Kind

Case 1: element $n$ is a singleton

Case 2: element $n$ joins an existing block

Combine

Example: Computing Small Stirling Numbers

List all partitions

Count and verify

Theorem: Explicit Formula for Stirling Numbers of the Second Kind

Count surjections via inclusion-exclusion

Relate surjections to partitions

Definition: Unsigned Stirling Number of the First Kind

Theorem: Recurrence for Unsigned Stirling Numbers of the First Kind

Case 1: $n$ is a fixed point

Case 2: $n$ is inserted into an existing cycle

Combine

Example: Permutations of [3][3][3] by Cycle Structure

Enumerate

Verify

Duality Between Stirling Numbers

Definition: Bell Number

Theorem: Bell Number Recurrence

Condition on the block containing element $n$

Sum over block sizes

Theorem: Exponential Generating Function of Bell Numbers

EGF for $S(n,k)$

Sum over $k$

Definition: Integer Partition

Historical Note: Euler and the Theory of Partitions

Theorem: Generating Function for Integer Partitions

Expand each factor

Take the product

Generating Functions: A Preview

Stirling number of the second kind

Stirling number of the first kind

Bell number

set partition

integer partition

Quick Check

Quick Check

Common Mistake: Set Partitions vs. Integer Partitions

Key Takeaway

Definition:
Stirling Number of the Second Kind

Definition:
Unsigned Stirling Number of the First Kind

Example: Permutations of $[3]$ by Cycle Structure

Definition:
Bell Number

Definition:
Integer Partition