Skip to content
Tutorials Center
My learning

Topics

Lesson 31 of 36 ยท Applications

Stirling Numbers

Understand Stirling numbers: partitions of a set into blocks (second kind), permutations by cycles (first kind), surjections and Bell numbers, with recurrences and checks.

Stirling numbers count two fundamental structures that binomial coefficients cannot: ways to split a labeled set into groups, and ways to arrange items into cycles. They also connect to polynomial bases and to the number of surjective functions. Both families satisfy a Pascal-like recurrence that you can build a table from, and both are easy to verify by brute force.

Stirling numbers of the second kind: S(n, k)

S(n, k) is the number of ways to split n labeled objects into exactly k non-empty, unordered groups. For example S(4, 2) = 7: four singletons-plus-triples (4 ways) and three pairs-plus-pairs.

Recurrence. Look at object n. Either it is alone in its group (S(n-1, k-1) ways to arrange the others into k-1 groups) or it joins one of the k groups made from the others (k * S(n-1, k) ways):

S(n, k) = k S(n-1, k) + S(n-1, k-1), S(n,n) = 1, S(n,0) = 0 for n > 0.

Bell numbers. B_n = sum_k S(n, k) counts all set partitions: 1, 1, 2, 5, 15, 52, 203, ..., with exponential generating function e^(e^x - 1) as in EGFs.

Surjections. The number of onto functions from an n-set to a k-set is k! * S(n,k): partition the domain into k groups, then decide which codomain element each group maps to.

Python Set partitions: recurrence vs brute force

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For 6 objects the counts by block number are 1, 31, 90, 65, 15, 1 (total 203, the Bell number). The generator set_partitions inserts the first element either as a singleton or into each existing block of a partition of the rest, which mirrors the recurrence. The last two lines both print 6, 36, 150, 540, 1806: surjections from n objects onto 3 objects, by formula and by listing every function.

Stirling numbers of the first kind: c(n, k)

The unsigned first-kind number c(n, k) counts permutations of n objects with exactly k cycles. The permutation (1 2 3)(4 5) has two cycles. c(n, 1) = (n-1)! because a single cycle through all elements can be arranged in (n-1)! ways (circular arrangements of n items).

Recurrence. Insert object n into a permutation of n-1: either as a new fixed point (own cycle), or right after any of the n-1 existing elements inside a cycle:

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

The row sums are n!, since every permutation has some number of cycles. They also appear as polynomial coefficients:

x (x+1)(x+2)...(x+n-1) = sum_k c(n, k) x^k.

Python Cycles of permutations and the rising factorial

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

All three computations give 24, 50, 35, 10, 1 for n = 5: 24 five-cycles, 50 permutations with two cycles, and so on up to the identity (1). The polynomial x^5 + 10x^4 + 35x^3 + 50x^2 + 24x shows the same numbers as coefficients. Row sums check out: c(6, k) adds to 720 = 6!.

Seeing the structure

flowchart TD
    N["Object n"] --> A["Alone / own cycle: S(n-1,k-1) or c(n-1,k-1)"]
    N --> B["Joins existing structure"]
    B --> B1["Second kind: k choices of block"]
    B --> B2["First kind: n-1 choices of position in a cycle"]

Both recurrences differ only in how many places the new object can be inserted.

Quantity Counts Row sum
S(n,k) set partitions into k blocks Bell number B_n
c(n,k) permutations with k cycles n!
k! S(n,k) surjections n -> k

Connections

  • Bases of polynomials: x^n = sum S(n,k) x(x-1)...(x-k+1) (falling factorials), the inverse relation of the first kind (with signs).
  • Surjections and inclusion-exclusion: k! S(n,k) = sum (-1)^j binom(k,j) (k-j)^n.
  • Programming: the number of ways to assign n jobs to indistinguishable servers using exactly k of them is S(n, k).

"Second kind = groups, first kind = cycles." If the groups are labeled (named boxes), multiply by k! for the second kind; for cycles, remember a cycle has no starting point.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is S(4, 2), the number of ways to split 4 labeled objects into 2 non-empty groups?

    Four splits of type 1+3 and three of type 2+2 give 7.
  2. 2. Which recurrence holds for Stirling numbers of the second kind?

    Object n either forms its own block or joins one of the k blocks of the others.
  3. 3. How many functions from a 5-element set ONTO a 2-element set?

    2! * S(5,2) = 2 * 15 = 30.
  4. 4. What is the sum over k of c(n,k), the unsigned first-kind numbers?

    Every permutation of n items has some number of cycles, so the row sums to n!.

Summary

  • S(n,k): partitions of an n-set into k blocks; recurrence k S(n-1,k) + S(n-1,k-1); row sums are Bell numbers; k! S(n,k) counts surjections.
  • c(n,k): permutations with k cycles; recurrence (n-1) c(n-1,k) + c(n-1,k-1); row sums are n!; the coefficients of x(x+1)...(x+n-1).
  • Always confirm tables with brute-force enumeration for small n.

Next: Combinatorics in Algorithms