Stirling Number Calculator: Blocks, Cycles, and Which Kind You Need
About the Author
Marko Šinko
Co-Founder & Lead Developer, AI Math Calculator
Any Stirling number calculator has to settle one question before it can give you a number: which kind? At n = 4 and k = 2 the second kind says 7 and the first kind says 11, and both are correct — they are counting different things. The second kind, written S(4,2), counts the ways to split four labelled items into two unlabelled groups. The first kind, c(4,2), counts the permutations of four items that break into exactly two cycles.
Almost everyone who searches for this arrives wanting the second kind, because that is the one that shows up in set partitions, surjections, Bell numbers and the standard combinatorics curriculum. The first kind turns up later, in falling factorials and in the analysis of shuffles. Get the two mixed up and every downstream number is wrong by a factor that grows with n.
The Seven Ways to Split Four People
Take four people — 1, 2, 3 and 4 — and put them into two non-empty teams. The teams have no names, no captain, no order. Here is the complete list:
Shape 3 + 1 — four of them
Shape 2 + 2 — three of them
Seven altogether, and the arithmetic on the 2+2 group is the interesting half: choosing who joins person 1 gives three options, and that is the entire count — because once you name person 1’s partner, the other pair is forced. Trying to compute it as “choose 2 of 4” gives 6, which double counts every split. That factor of 2 is the first place a combination calculator will lead you astray here: nCr counts labelled selections, and Stirling numbers of the second kind do not label the blocks.
The 3+1 group is the reverse case — there, choosing which single person sits alone gives 4 with no correction needed, because the two blocks have different sizes and so cannot be confused with each other. Equal block sizes are exactly when the division kicks in, and that asymmetry is why no single binomial expression covers S(n,k).
One Decision Per Element Builds the Whole Triangle
The recurrence is the tool that actually gets used, and it comes from asking one question about the last element:
S(n,k) = k · S(n−1,k) + S(n−1,k−1)
c(n,k) = (n−1) · c(n−1,k) + c(n−1,k−1)
For the second kind: element n is either alone in its own block, in which case the other n−1 elements formed k−1 blocks, or it joined a block that already existed, in which case the other n−1 elements formed all k blocks and there were k of them to choose from. Two disjoint cases, no overlap, and S(4,2) = 2·S(3,2) + S(3,1) = 2·3 + 1 = 7 lands on the seven partitions listed above.
The first kind uses the same skeleton with a different multiplier, and that difference is worth a moment. Element n can be inserted immediately after any of the n−1 earlier elements inside whatever cycle that element sits in — n−1 slots, not k. So the first kind grows faster, and the gap widens with n rather than staying constant:
| n | S(n,2) | c(n,2) | Ratio c/S |
|---|---|---|---|
| 3 | 3 | 3 | 1.0 |
| 4 | 7 | 11 | 1.6 |
| 6 | 31 | 274 | 8.8 |
| 10 | 511 | 1,026,576 | 2,009 |
At n = 3 the two families agree, which is why a homework problem checked only against small cases can hide the error completely. By n = 10 the first kind is two thousand times larger. Both triangles are laid out in the calculator above with the target cell and its two parent cells highlighted, so the recurrence is something you can trace rather than trust.
Blocks or Cycles: Telling the Two Kinds Apart
The cleanest way to see the difference is to take one set partition and count how many permutations it corresponds to. Split {1,2,3,4} as {1,2,3}{4}. As a partition that is one object. As a permutation you also have to decide how the block of three cycles: 1→2→3→1 or 1→3→2→1. Two cyclic orders, so one partition becomes two permutations. A block of size m admits (m−1)! cyclic orders — which is where the factorial hiding inside the first kind comes from.
Run that over the whole list: the four partitions of shape 3+1 each give 2 permutations, and the three of shape 2+2 each give 1 (a 2-cycle has only one cyclic order). Total 4×2 + 3×1 = 11, which is c(4,2) exactly. That is not a coincidence or an identity to memorise — it is what the first kind means.
There is also a third notation in circulation, and it trips people up in print rather than in counting. The signed Stirling numbers of the first kind, s(n,k) = (−1)n−k c(n,k), are the coefficients that expand a falling factorial into ordinary powers. Nothing is being counted by a negative number; the sign is bookkeeping so the algebra comes out right. If a source writes s(4,2) = 11 and another writes s(4,2) = −11, both are using a standard convention and neither is wrong.
Which Balls-in-Boxes Question Are You Asking?
Most wrong answers in this area are not arithmetic errors — they are the wrong question. Four different counts hide behind “put n things into k groups”, depending on whether the things and the groups are distinguishable. This table is the one worth keeping:
| Items | Groups | Count | n=4, k=2 |
|---|---|---|---|
| Distinct | Identical | S(n,k) | 7 |
| Distinct | Labelled | k! · S(n,k) | 14 |
| Identical | Identical | partitions of n into k parts | 2 |
| Identical | Labelled | C(n−1, k−1) | 3 |
Same n, same k, four answers between 2 and 14. The third row — identical items into identical groups — is 2 because only the sizes matter: 3+1 or 2+2. The fourth row is the stars-and-bars count, 3 because you are choosing where to cut a row of four identical balls into two non-empty runs. Only the top row is a Stirling number of the second kind.
A practical test: if renaming the groups changes your answer, you want a labelled row. Handing four different tasks to two identical anonymous committees is the top row. Handing them to Committee A and Committee B is the second. This is the same distinction that separates a permutation calculator from a combination calculator, one level up: it is not the items being ordered, it is the containers.
Onto Functions Are Just k! × S(n,k)
Row two of that table is where Stirling numbers of the second kind earn their place in computer science. A surjection from an n-element set onto a k-element set is precisely a partition into k blocks plus an assignment of the blocks to the k target values, so the count is k! · S(n,k). For n = 4, k = 2 that is 2 · 7 = 14 onto functions — and you can sanity check it directly: 24 = 16 functions total, minus the 2 constant ones that miss a value, gives 14.
Turn that around and you get the closed form the calculator above traces term by term:
Read it as inclusion–exclusion over which target values go unused. Count all kn functions, subtract the ones that miss at least one value, add back the ones double-subtracted for missing two, and so on. Then divide by k! to forget the labels. For S(4,2): (1/2)·(24 − 2·14 + 1·04) = (16 − 2)/2 = 7.
This formula is exact but a poor way to compute anything large. It needs k+1 terms of alternating sign with the biggest one around kn, so in floating point the cancellation destroys precision fast — by around n = 20 a double-precision implementation is returning nonsense for mid-range k. The recurrence has no subtraction at all for the second kind, which is why every serious library builds the triangle instead. Related sequence tools run into the same trade-off; the Catalan number calculator has a clean product formula, but a recurrence relation calculator is the more robust route once the numbers stop fitting in a double.
Where a Stirling Number Calculator Beats Hand Work
Building the triangle by hand is fine up to about n = 8. After that the numbers get long and the errors compound silently, since one wrong cell corrupts every cell below and to the right of it. Some landmarks for scale:
- S(10,5) = 42,525 — still a plausible hand computation, ten rows of arithmetic.
- B(10) = 115,975 — the Bell number, the whole row added up: every way to partition ten items into any number of groups.
- B(20) ≈ 5.17 × 1013 — more partitions of a 20-element set than there are seconds in 1.6 million years.
- S(50,12) is a 46-digit number — exact integer arithmetic is not optional here, and a spreadsheet using doubles will silently lose the low digits.
The calculator computes with arbitrary-precision integers for exactly that reason, and it shows the row distribution because the shape is genuinely surprising. Split a 50-element set at random and the most likely number of blocks is not 2 or 3 but 16. The peak of S(n,k) tracks n / W(n), where W is the Lambert function — about 17.5 at n = 50, and noticeably higher than the n / ln n figure of 12.8 that a quick estimate suggests. The first kind peaks near ln n instead: a random shuffle of 52 cards splits into 4 cycles more often than any other number, and 4.54 on average, rather than one big loop.
Four Slips That Produce the Wrong Stirling Number
Treating S(0,0) as 0. It is 1. There is exactly one way to partition the empty set: use no blocks. Every recurrence in the subject depends on this base case, and an implementation that returns 0 there produces a triangle that is wrong in its entirety. The same goes for c(0,0) = 1. But S(n,0) = 0 for every n above 0, which looks inconsistent until you read it as “no blocks cannot hold anything”.
Multiplying by k! when the groups are anonymous. This is the single most common error, and it is easy to catch: ask whether swapping the contents of group 1 and group 2 gives you a different arrangement. If it does not, no k! belongs in the answer. Sorting four students into two unnamed study pairs is 3 ways, not 6.
Confusing set partitions with integer partitions. “Partitions of 4” means 5 (4, 3+1, 2+2, 2+1+1, 1+1+1+1) when the items are identical, and 15 — the Bell number B(4) — when they are distinct. A set calculator works on labelled elements, which is the Stirling case; integer partitions ignore identity entirely.
Reading a signed table as a count. If a table shows −225 at n = 6, k = 3, that is s(6,3) with the (−1)n−k convention attached, and the count is 225. Signed values appear in generating function work and in falling-factorial expansions; unsigned values appear whenever something is being counted. The standard reference on both families spells out the conventions, and the sequences themselves are catalogued as OEIS A008277 for the second kind and A132393 for the unsigned first kind — useful for checking any row you have computed by hand against a published table.
