Partition four labeled students into two nonempty teams, without naming the teams. There are seven possibilities: four have a singleton and a triple, while three divide the students into two pairs. Naming the teams red and blue doubles the count to fourteen. The students remain labeled throughout; only the blocks are unlabeled. This distinction separates set partitions from both assignments to named boxes and integer partitions of the number four.
Predict
Predict the role of the last student. In a partition of n labels into k blocks, that student either belongs to a block containing someone else or is alone. In the first case, removing the student leaves k blocks and there are k places to reinsert them. In the second case, removing their singleton leaves k−1 blocks. These two operations are reversible and the cases cannot overlap.
Experiment
Build the triangular array from its boundary values.
n
S(n, 1)
S(n, 2)
S(n, 3)
S(n, 4)
1
1
0
0
0
2
1
1
0
0
3
1
3
1
0
4
1
7
6
1
Verify S(4, 2)=2·3+1 and S(4, 3)=3·1+3. The coefficients multiplying previous entries represent actual choices of an existing block.
Understand
The Stirling number of the second kind S(n, k) counts partitions of an n-element labeled set into k nonempty unlabeled blocks. Set S(0, 0)=1, S(n, 0)=0 for n>0, and S(n, k)=0 for k>n. The last-element decomposition proves S(n, k)=kS (n−1, k)+S(n−1, k−1). A surjection to k named targets determines its nonempty fibers, and labeling the blocks of a partition determines the surjection. Thus the number of surjections is k!S(n, k). Inclusion–exclusion on missing target labels gives the independent formula k!S(n, k)=Σ_j(−1)^j C(k, j)(k−j)^n, with the empty-domain case interpreted by the actual function count.
Apply
The same fiber argument proves an important polynomial basis identity. For a nonnegative integer x, count all x^n functions from n labels to x labels. If the image has k elements, first form the partition into fibers in S(n, k) ways, then assign distinct target labels to those k blocks in (x)_k=x(x−1)…(x−k+1) ways. Therefore x^n=Σ_k S(n, k)(x)_k. Since both sides are polynomials and agree at every nonnegative integer x, they agree as polynomial expressions. This connects combinatorial classification with a change of basis in algebra.
Continue
Test a tempting but incorrect answer C(n, k) for the partition count: choosing k representatives does not determine how the remaining labels are grouped. Nor can every allocation count be divided by k! when empty boxes are allowed, because permuting empty boxes can create stabilizers of different sizes. The nonempty-block condition makes the labeling count uniform. Later exponential generating functions will package all set partitions into exp (exp (z)−1), with a proof of why unlabeled components of labeled objects lead to that expression.
Drafts save locally as you type. Reveal worked solutions when useful; the site remembers that exposure. Automatic matches check the requested answer, while written arguments require review against the rubric.
Find S(5, 2), the number of partitions into two nonempty unlabeled blocks.
Integers, fractions and finite decimals are accepted. Expressions such as sqrt(2) are not parsed by this checker.
Count surjections from a four-element set to a three-element labeled set.
Integers, fractions and finite decimals are accepted. Expressions such as sqrt(2) are not parsed by this checker.
Prove S(n, k)=k S(n−1, k)+S(n−1, k−1).
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Why does multiplying S(n, k) by k! count surjections?
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Prove S(n, 2)=2^(n−1)−1 for n≥1.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Prove x^n=Σ S(n, k)(x)_k for nonnegative integer x.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Reflect and continue
Before marking this lesson complete, explain one key idea without the worked solution and identify a condition that matters. Marking complete records participation, not independent mastery.
