Bijections, multisets, Stirling and Catalan numbers

MATH-260 counted permutations, subsets and lattice paths. This lesson builds the next layer: compositions and multisets, the two kinds of Stirling numbers, the Bell numbers and the Catalan numbers. Each family answers a natural question about distributing objects, and each comes with recurrences that are proved by thinking about one special element. Together they fill in most of what Gian-Carlo Rota called the twelvefold way, a table of the basic ways to put balls into boxes.

Compositions and multisets

A composition of \(n\) into \(k\) parts is an ordered list of positive integers \((a_1, \ldots, a_k)\) with sum \(n\). Write \(n\) as a row of \(n\) dots; a composition corresponds to choosing \(k - 1\) of the \(n - 1\) gaps between dots to cut. So the number of compositions of \(n\) into \(k\) parts is \(\binom{n-1}{k-1}\), and the total number of compositions of \(n\) is \(\sum_k \binom{n-1}{k-1} = 2^{n-1}\), since each gap is cut or not. For \(n = 4\) the eight compositions are 4, 3+1, 1+3, 2+2, 2+1+1, 1+2+1, 1+1+2 and 1+1+1+1.

If zero parts are allowed, a weak composition of \(n\) into \(k\) parts corresponds, by adding 1 to every part, to a composition of \(n + k\) into \(k\) parts. Hence there are \(\binom{n+k-1}{k-1}\) of them. This is the stars and bars count from MATH-260 seen as a bijection.

A multiset of size \(n\) from a set of \(k\) types is a selection in which repetition is allowed and order does not matter, such as choosing 12 doughnuts from 5 kinds. Recording how many of each type are chosen gives a weak composition of \(n\) into \(k\) parts, so the number of multisets is \[\Big(\!\!\binom{k}{n}\!\!\Big) = \binom{n+k-1}{n}.\] The notation, read k multichoose n, is due to Richard Stanley. The multiset count also equals the number of nondecreasing sequences \(1 \le b_1 \le \cdots \le b_n \le k\); the bijection \(b_i \mapsto b_i + i - 1\) turns them into strictly increasing sequences from \(1\) to \(n + k - 1\), that is, \(n\)-subsets of an \((n + k - 1)\)-set.

Set partitions and Stirling numbers of the second kind

A partition of a set \(X\) is a collection of nonempty, pairwise disjoint subsets, called blocks, whose union is \(X\). The Stirling number of the second kind \(S(n, k)\) is the number of partitions of an \(n\)-element set into exactly \(k\) blocks. For example \(S(4, 2) = 7\): the partitions of \(\{1, 2, 3, 4\}\) into two 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\}\) and \(\{1,4\}\{2,3\}\).

Theorem. \(S(n, k) = k\,S(n - 1, k) + S(n - 1, k - 1)\) for \(n, k \ge 1\), with \(S(0, 0) = 1\) and \(S(n, 0) = S(0, k) = 0\) otherwise.

Proof. Look at where the element \(n\) goes. Either \(n\) is alone in its block: removing that block leaves a partition of \(\{1, \ldots, n - 1\}\) into \(k - 1\) blocks, giving \(S(n - 1, k - 1)\) choices. Or \(n\) shares its block: removing \(n\) leaves a partition of \(\{1, \ldots, n - 1\}\) into \(k\) blocks, and \(n\) could have been in any of the \(k\) blocks, giving \(k\,S(n - 1, k)\). The two cases are disjoint and exhaustive.

Two values are easy: \(S(n, 1) = 1\) and \(S(n, n) = 1\). Also \(S(n, 2) = 2^{n-1} - 1\), since a partition into two blocks is determined by the block containing element 1, which is \(\{1\}\) together with any proper subset of the remaining \(n - 1\) elements, giving \(2^{n-1} - 1\) choices. And \(S(n, n - 1) = \binom{n}{2}\), since exactly one block has two elements.

Surjections. The number of functions from an \(n\)-set onto a \(k\)-set is \(k!\,S(n, k)\): a surjection is a partition of the domain into \(k\) blocks (the preimages) together with an assignment of the \(k\) blocks to the \(k\) values. Lesson 3 will find an explicit formula for surjections by inclusion and exclusion, which in turn gives an explicit formula for \(S(n, k)\).

Powers as falling factorials. Every function from an \(n\)-set to an \(x\)-set has an image of some size \(k\), and counting functions by image gives \[x^n = \sum_{k=0}^{n} S(n, k)\, x(x - 1)\cdots(x - k + 1).\] For instance \(x^3 = x + 3x(x - 1) + x(x - 1)(x - 2)\). This identity, proved first for positive integers \(x\), holds as a polynomial identity, because two polynomials agreeing at infinitely many points are equal. It is used in the calculus of finite differences to sum powers.

Bell numbers

The Bell number \(B_n\) is the total number of partitions of an \(n\)-set: \(B_n = \sum_k S(n, k)\). The first values are \(B_0 = 1\), then 1, 2, 5, 15, 52, 203, 877, 4140. They satisfy \[B_{n+1} = \sum_{k=0}^{n} \binom{n}{k} B_k.\] Proof: in a partition of \(\{1, \ldots, n + 1\}\), let the block containing \(n + 1\) have \(n - k\) other elements, chosen in \(\binom{n}{n-k} = \binom{n}{k}\) ways; the remaining \(k\) elements are partitioned in \(B_k\) ways. The numbers are named after Eric Temple Bell, who wrote about them in the 1930s, though they appear in Japanese work on incense games from the seventeenth century, where the 52 partitions of a 5-set were drawn as diagrams called genji-ko. Lesson 5 shows that \(\sum B_n x^n/n! = e^{e^x - 1}\).

Stirling numbers of the first kind

Every permutation of a finite set splits into disjoint cycles. The permutation of \(\{1, \ldots, 6\}\) sending \(1 \to 3 \to 5 \to 1\), \(2 \to 6 \to 2\) and fixing 4 has cycle notation \((1\,3\,5)(2\,6)(4)\), with three cycles. The unsigned Stirling number of the first kind \(c(n, k)\) counts permutations of an \(n\)-set with exactly \(k\) cycles. So \(c(n, n) = 1\) (only the identity), \(c(n, 1) = (n - 1)!\) (the cyclic orders) and \(\sum_k c(n, k) = n!\).

Theorem. \(c(n, k) = (n - 1)\,c(n - 1, k) + c(n - 1, k - 1)\).

Proof. Again follow the element \(n\). If \(n\) is a fixed point, it forms a cycle by itself and the rest is a permutation of \(n - 1\) elements with \(k - 1\) cycles. Otherwise, delete \(n\) from its cycle, joining its predecessor directly to its successor; this gives a permutation of \(n - 1\) elements with \(k\) cycles, and \(n\) can be reinserted after any of the \(n - 1\) elements, so each such permutation arises \(n - 1\) times.

The first kind numbers are the coefficients of the rising factorial: \[x(x + 1)(x + 2)\cdots(x + n - 1) = \sum_{k} c(n, k)\, x^k.\] Induction from the recurrence proves it, since multiplying by \(x + n - 1\) either raises the power of \(x\) (a new cycle) or multiplies by \(n - 1\). Setting \(x = 1\) recovers \(n!\). The average number of cycles of a random permutation is the harmonic number \(H_n = 1 + \frac12 + \cdots + \frac1n\), about \(\ln n\), obtained by differentiating at \(x = 1\).

Catalan numbers

The Catalan number \(C_n = \frac{1}{n+1}\binom{2n}{n}\) counts many structures: \(1, 1, 2, 5, 14, 42, 132, 429, \ldots\) MATH-260 met them as lattice paths. Here is the cleanest definition. A Dyck path of semilength \(n\) is a sequence of \(n\) up-steps \(U = (1, 1)\) and \(n\) down-steps \(D = (1, -1)\) from height 0 back to height 0 that never goes below the axis.

Theorem. The number of Dyck paths of semilength \(n\) is \(\frac{1}{n+1}\binom{2n}{n}\).

Proof by the reflection principle. There are \(\binom{2n}{n}\) paths with \(n\) up-steps and \(n\) down-steps. Call one bad if it dips below the axis, that is, touches height \(-1\). For a bad path, reflect the part after its first visit to height \(-1\) in the line \(y = -1\), swapping \(U\) and \(D\). The original path ended at height 0, one unit above the line, so the reflected path ends at height \(-2\): it has \(n - 1\) up-steps and \(n + 1\) down-steps. Conversely, every path with \(n - 1\) up-steps and \(n + 1\) down-steps must reach height \(-1\), and reflecting after its first visit there recovers a bad path. This bijection shows there are \(\binom{2n}{n+1}\) bad paths, so the good ones number \[\binom{2n}{n} - \binom{2n}{n+1} = \binom{2n}{n}\Big(1 - \frac{n}{n+1}\Big) = \frac{1}{n+1}\binom{2n}{n}.\] The argument is usually credited to Désiré André, 1887, though his original proof was a different counting argument.

The Catalan recurrence. Every nonempty Dyck path returns to the axis for the first time after \(2i + 2\) steps for some \(i \ge 0\). It decomposes as \(U P_1 D P_2\), where \(P_1\) is a Dyck path of semilength \(i\) (lifted one unit) and \(P_2\) is a Dyck path of semilength \(n - 1 - i\). So \[C_n = \sum_{i=0}^{n-1} C_i C_{n-1-i}, \qquad C_0 = 1.\] This first-return decomposition is the template for every Catalan family; lesson 4 solves the recurrence with generating functions and recovers the closed formula.

Other Catalan families. Balanced strings of \(n\) pairs of brackets (replace \(U\) by an opening and \(D\) by a closing bracket). Binary trees with \(n\) internal nodes (left subtree, right subtree, like \(P_1\) and \(P_2\)). Ways to fully parenthesize a product of \(n + 1\) factors, which is how Eugène Catalan met them in 1838. Triangulations of a convex polygon with \(n + 2\) sides by noncrossing diagonals, studied by Euler and Segner in the 1750s: fix one side, and the triangle on it splits the polygon into two smaller polygons. Noncrossing partitions of an \(n\)-set, and permutations of \(1, \ldots, n\) avoiding the pattern 231, which are exactly those sortable by a single stack, as Donald Knuth showed in 1968. Ming Antu found the Catalan numbers in China in the 1730s, independently of Europe.

from itertools import product, permutations
from math import comb, factorial

N = 8
S2 = [[0] * (N + 1) for _ in range(N + 1)]; S2[0][0] = 1
c1 = [[0] * (N + 1) for _ in range(N + 1)]; c1[0][0] = 1
for n in range(1, N + 1):
    for k in range(1, n + 1):
        S2[n][k] = k * S2[n - 1][k] + S2[n - 1][k - 1]
        c1[n][k] = (n - 1) * c1[n - 1][k] + c1[n - 1][k - 1]
print("S(n,k) rows:")
for n in range(1, 8):
    print("  n=%d" % n, S2[n][1:n + 1])
print("c(n,k) rows:")
for n in range(1, 7):
    print("  n=%d" % n, c1[n][1:n + 1], "sum =", sum(c1[n]), "= n!", factorial(n))

bell = [1]
for n in range(N):
    bell.append(sum(comb(n, k) * bell[k] for k in range(n + 1)))
print("Bell numbers:", bell)
print("row sums of S agree:", all(sum(S2[n]) == bell[n] for n in range(N + 1)))

def set_partitions(xs):
    if not xs:
        yield []
        return
    first, rest = xs[0], xs[1:]
    for p in set_partitions(rest):
        for i in range(len(p)):
            yield p[:i] + [[first] + p[i]] + p[i + 1:]
        yield [[first]] + p

counts = {}
for p in set_partitions(list(range(6))):
    counts[len(p)] = counts.get(len(p), 0) + 1
print("brute force S(6,k):", [counts[k] for k in range(1, 7)])

def cycles(perm):
    seen, cyc = set(), 0
    for i in range(len(perm)):
        if i not in seen:
            cyc += 1
            while i not in seen:
                seen.add(i); i = perm[i]
    return cyc

tally = [0] * 7
for p in permutations(range(6)):
    tally[cycles(p)] += 1
print("brute force c(6,k):", tally[1:])

def dyck_count(n):
    good = 0
    for steps in product((1, -1), repeat=2 * n):
        h = 0
        for t in steps:
            h += t
            if h < 0:
                break
        else:
            good += h == 0
    return good

cat = [comb(2 * n, n) // (n + 1) for n in range(11)]
print("Catalan:", cat)
print("Dyck paths by brute force, n = 0..7:", [dyck_count(n) for n in range(8)])
rec = [1]
for n in range(1, 11):
    rec.append(sum(rec[i] * rec[n - 1 - i] for i in range(n)))
print("first-return recurrence agrees:", rec == cat)

def stack_sortable(p):
    stack, out = [], []
    for x in p:
        while stack and stack[-1] < x:
            out.append(stack.pop())
        stack.append(x)
    out += reversed(stack)
    return out == sorted(p)
print("stack-sortable permutations, n = 1..7:", [sum(stack_sortable(p) for p in permutations(range(n))) for n in range(1, 8)])
print("multisets of 12 from 5 kinds:", comb(12 + 5 - 1, 12))

S(n,k) rows:
  n=1 [1]
  n=2 [1, 1]
  n=3 [1, 3, 1]
  n=4 [1, 7, 6, 1]
  n=5 [1, 15, 25, 10, 1]
  n=6 [1, 31, 90, 65, 15, 1]
  n=7 [1, 63, 301, 350, 140, 21, 1]
c(n,k) rows:
  n=1 [1] sum = 1 = n! 1
  n=2 [1, 1] sum = 2 = n! 2
  n=3 [2, 3, 1] sum = 6 = n! 6
  n=4 [6, 11, 6, 1] sum = 24 = n! 24
  n=5 [24, 50, 35, 10, 1] sum = 120 = n! 120
  n=6 [120, 274, 225, 85, 15, 1] sum = 720 = n! 720
Bell numbers: [1, 1, 2, 5, 15, 52, 203, 877, 4140]
row sums of S agree: True
brute force S(6,k): [1, 31, 90, 65, 15, 1]
brute force c(6,k): [120, 274, 225, 85, 15, 1]
Catalan: [1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796]
Dyck paths by brute force, n = 0..7: [1, 1, 2, 5, 14, 42, 132, 429]
first-return recurrence agrees: True
stack-sortable permutations, n = 1..7: [1, 2, 5, 14, 42, 132, 429]
multisets of 12 from 5 kinds: 1820

Every brute-force count agrees with its recurrence. The stack-sortable permutations give the Catalan numbers again, an example of how a single sequence links apparently unrelated problems. The doughnut count, 1,820, is the number of multisets of size 12 from 5 kinds.