Basic Problemscountingpartitioncombinatorics

Ways to Partition a Set

Given a set of n distinct elements, count the number of ways to split it into exactly k non-empty, unordered subsets, known as the Stirling number of the second kind.

Do this lesson first: climbing stairs

Example input

n = 8 elements, k = 3 subsets, so the question is S(8, 3)

Expected output

966

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

dp[n][k] is the number of ways to split n distinct elements into exactly k non-empty, unordered subsets, so the cell holds a COUNT and nothing about which element went where. UNORDERED is the load-bearing word. The k subsets carry no labels and no order among themselves, so splitting three elements a, b, c into {a} and {b, c} is ONE partition however you write the two pieces down, not two. Two counts name the state, how many elements there are and how many subsets they have to fill, so the table is a grid even though there is no input array anywhere on this page. The nearest table in this course is binomial-coefficient's, and it is the same table SHAPE cell for cell: an (n + 1) by (n + 1) rectangle with everything above the diagonal skipped, the same two predecessors at every computed cell, the same row-major fill order, and the same base POSITIONS row for row, one per row down the left edge and one per row past the first on the diagonal, which is 17 of them at n = 8. Read that page first if you have not. TWO things then differ, and they are worth ranking rather than lumping together as one. The difference that matters to the algorithm is a single multiplication at each computed cell, and that multiplication is what this page is for. The difference that matters to anyone retyping the table is smaller and easier to get wrong: the positions match, but eight of the seventeen base VALUES at n = 8 do not, because past row 0 the left edge holds 0 here where it holds 1 there. dp[0][0] is 1 on both pages, and the diagonal is 1 on both; it is the eight left-edge cells below row 0 that disagree. basesAndOrder is where that edge is both explained and priced. pitfall prices the other mistake, the missing multiplication.

dp[n][k] = k * dp[n - 1][k] + dp[n - 1][k - 1]

Single out one particular element, say the last of the n, and ask what became of it. Either it ended up alone in a subset of its own, or it ended up sharing a subset with other elements. No partition is in both groups and none is outside them, so the two cases are disjoint and exhaustive and their counts add. TAKE THE ALONE CASE FIRST, because it is the one with no multiplier. If the singled-out element is by itself, the other n - 1 elements have to carry all of the remaining k - 1 subsets between them, and there are dp[n - 1][k - 1] ways for them to do that. Each of those arrangements yields exactly ONE partition of the n elements: bolt the lone element on as its own subset and you are finished, there is nothing left to choose. So this case contributes dp[n - 1][k - 1] as it stands. NOW THE OTHER CASE, WHICH IS WHERE THE COEFFICIENT COMES FROM. If the singled-out element is not alone, then pulling it out leaves every subset still non-empty, so the other n - 1 elements are already split into exactly k subsets, and there are dp[n - 1][k] ways for them to be. But that is NOT the number of partitions this case contributes, and assuming that it is is the mistake this page exists to prevent. Each of those k subsets is a home the element could have been dropped into. That is k choices, and each choice produces a DIFFERENT partition of the n elements, because the subsets are told apart by their contents and the element sits in a different one each time. Nothing is double counted either: given any partition in which the element is not alone, delete the element and you recover both the arrangement of the other n - 1 and which subset it came out of, uniquely. So the correspondence is k partitions of n to one arrangement of n - 1, in that direction, and the case contributes k × dp[n - 1][k]. WHY EXACTLY k, and not k! and not 2^k: the element goes into ONE subset, so it is a single choice among k, not a permutation of the subsets and not a selection of several of them. And the multiplier is the COLUMN index, the number of subsets, not the row index n. Both of those numbers are printed on the gutters right next to the cell, which is exactly why reaching for the wrong one is easy. It is a SUM between the two cases and a PRODUCT inside one of them because this is a counting problem: both cases really happen, across different partitions, and we want the total of them rather than the better of them. That is the same distinction binomial-coefficient draws against min-cost-path and it does not change here. What changes is that one of the two branches is not one outcome per arrangement but k of them.

BOTH outer edges are given, as on binomial-coefficient's triangle, and one of the two holds a DIFFERENT NUMBER here. That difference is worth stopping on rather than skimming. dp[0][0] = 1. There is exactly one way to split the empty set into zero subsets: take no subsets at all. It is 1 rather than 0 because an empty collection of subsets is a legitimate arrangement of nothing, and it is the seed the whole triangle is built from. dp[n][0] = 0 for every row past the first, and binomial-coefficient's matching edge is 1. BOTH ARE RIGHT, and the reason is that the two cells count different things. There, the cell counts selections, and choosing NOTHING out of n items is a real selection, the empty one, which always exists and there is exactly one of it. Here the cell counts partitions of a non-empty set into zero non-empty subsets, and zero subsets hold no elements between them, so there is nowhere for the n elements to go and no such arrangement exists at all. One way to choose nothing from anything; no way to split something into nothing. That 0 is not decorative either. Every computed cell in column 1 reads it, which is what pins the whole of column 1 to 1 all the way down: dp[n][1] = 1 × dp[n - 1][1] + 0. Copy that edge across as a 1, which is the likeliest slip for a reader arriving from the other page, and column 3 comes out 7, 32, 122, 423, 1389 across n = 4 to 8 in place of the true 6, 25, 90, 301, 966. dp[n][n] = 1 for every row: there is exactly one way to split n elements into n non-empty subsets, every element alone in its own. Both edges have to be GIVEN rather than summed, and that reason is arithmetic rather than convention. dp[n][0] would reach for dp[n - 1][-1], column -1, which is off the table altogether, and dp[n][n] would reach for dp[n - 1][n], which sits above the diagonal and does not exist. Every cell with 1 <= k <= n - 1 is computed, and each of those has exactly two live predecessors, never one. At n = 8 the rectangle declares 81 cells, 45 of them live: 17 given, one per row down the left edge and one per row past the first on the diagonal, and 28 summed. THE DOTS ARE NOT ZEROS, in the sense that nothing is ever written to them and no cell ever reads one. A position with column > row would be asking to fill more non-empty subsets than there are elements to fill them, which is not a hard question, it is not a question. Nothing could read one by accident either: a computed cell at (n, k) has k <= n - 1, so the two cells it reads, (n - 1, k) and (n - 1, k - 1), both have column at most n - 1 and therefore sit on or below row n - 1's own diagonal. Zero is even the mathematically correct value for those positions, since there are no such partitions, so unlike min-sum-in-a-triangle nothing here would be corrupted by a stray zero above the diagonal. They are dots because they are not part of the question. Filling row-major, left to right within each row, means both cells a computed cell reads are final before it reads them, which is the only ordering property the recurrence needs.

Tabulation, one row-major sweep, and as on binomial-coefficient's page the case for the table is NOT that it rescues an exponential, so it is worth saying plainly which case is being made. S(n, 3) has a closed form. Write out the inclusion and exclusion sum and it collapses to (3^n - 3 * 2^n + 3) / 6, two exponentiations, one multiplication and one division, and a closed form of that shape is what the independent check behind this page computes: four alternating terms and no table at all. Nothing here is being saved from blowing up by the grid. Four other arguments are the real ones, and two of them are worth more here than they are over there. EXACTNESS. Every cell of the sweep is a whole number times a whole number plus a whole number, so the arithmetic never leaves the integers and there is nothing to round anywhere in the pass. The closed form divides by k! at the end. Do not oversell that, though, because it was measured: the division is exact in JavaScript for every n up to 40 and the numerator stays a safe integer through n = 30, so at this page's sizes the sweep's advantage on this axis is a matter of principle rather than a wrong answer you can point at, and the rounding in the check is defensive rather than load-bearing. That is a weaker exactness story than binomial-coefficient's, where the factorial route really does return 253.00000000000003 for a value of 253. GENERALITY, which is worth MORE here. The sweep fills S(n, k) for every pair of counts up to the bottom row rather than only column 3, so one pass answers every question of this shape at once. It also hands over a second sequence for nothing: sum each row and you get the number of partitions into ANY number of subsets, which is the Bell numbers, measured as 1, 1, 2, 5, 15, 52, 203, 877, 4140 for rows 0 through 8. Pascal's rows sum to 2^n, which is 16, 32, 64, 128, 256 over this slider's range, so the same shape of table with one coefficient added takes the bottom row's total from 256 to 4140. That growth is what this page is really about, and the row itself shows it: 0, 1, 127, 966, 1701, 1050, 266, 28, 1 against Pascal's symmetric 1, 8, 28, 56, 70, 56, 28, 8, 1. Set the two tables cell against cell at n = 8 and they agree at only 10 of the 45 live cells, which are the nine diagonal cells plus one interior coincidence at dp[3][2], where both hold 3. SURVIVING A CHANGE. The in-row shortcut that makes a single row of Pascal's triangle cheap, C(n, k) = C(n, k - 1) * (n - k + 1) / k, has no counterpart here, because neighbouring entries of a Stirling row are not related by one multiply and divide; nth-row-of-pascals-triangle says exactly that about this problem. So the additive table is what still works when the arithmetic shifts, which is the argument that page makes for keeping a table it otherwise prices as the most expensive of its four options. COST. The triangle down to row n holds (n + 1)(n + 2) / 2 live cells, so the sweep is O(n^2) time and O(n^2) space; a cell only ever reads the row above it, so one rolling row is enough, and a sweep that only needs column k can stop there for O(n k). Memoization from dp[n][3] descends only into cells with column 3 or less and fills 4n - 9 of them, which is FEWER cells than the sweep writes. Measured, the sweep's live-cell count divided by the memoized recursion's runs 2.143 at n = 4, 1.909 at 5, 1.867 at 6, 1.895 at 7 and 1.957 at 8, so the factor is not monotone in n and its value at the slider's maximum is still below its value at the minimum. It does grow without bound eventually, since n^2 outruns 4n, but this slider does not reach far enough to show that. Those five ratios are shared with binomial-coefficient rather than measured independently of it, and they HAVE to be: the two tables have identical shapes, identical base positions and identical dependency arrows, so their cell counts cannot differ. Only the arithmetic inside each cell does. That page prints three of the five, 2.14 at n = 4, its lowest of 1.87 at n = 6 and 1.96 at n = 8, alongside a bound of 2.15 across the range; the two it does not print are the 1.909 at n = 5 and the 1.895 at n = 7. The surplus cells are not waste and they are not an argument against the sweep either: the extra cells ARE the other answers, which is the generality point above.

Time O(n^2) to fill the triangle down to row n, or O(n k) if the sweep stops at column kSpace O(n^2), reducible to O(k) with one rolling row that stops at column k

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

BOTH outer edges are given, as on binomial-coefficient's triangle, and one of the two holds a DIFFERENT NUMBER here. That difference is worth stopping on rather than skimming. dp[0][0] = 1. There is exactly one way to split the empty set into zero subsets: take no subsets at all. It is 1 rather than 0 because an empty collection of subsets is a legitimate arrangement of nothing, and it is the seed the whole triangle is built from. dp[n][0] = 0 for every row past the first, and binomial-coefficient's matching edge is 1. BOTH ARE RIGHT, and the reason is that the two cells count different things. There, the cell counts selections, and choosing NOTHING out of n items is a real selection, the empty one, which always exists and there is exactly one of it. Here the cell counts partitions of a non-empty set into zero non-empty subsets, and zero subsets hold no elements between them, so there is nowhere for the n elements to go and no such arrangement exists at all. One way to choose nothing from anything; no way to split something into nothing. That 0 is not decorative either. Every computed cell in column 1 reads it, which is what pins the whole of column 1 to 1 all the way down: dp[n][1] = 1 × dp[n - 1][1] + 0. Copy that edge across as a 1, which is the likeliest slip for a reader arriving from the other page, and column 3 comes out 7, 32, 122, 423, 1389 across n = 4 to 8 in place of the true 6, 25, 90, 301, 966. dp[n][n] = 1 for every row: there is exactly one way to split n elements into n non-empty subsets, every element alone in its own. Both edges have to be GIVEN rather than summed, and that reason is arithmetic rather than convention. dp[n][0] would reach for dp[n - 1][-1], column -1, which is off the table altogether, and dp[n][n] would reach for dp[n - 1][n], which sits above the diagonal and does not exist. Every cell with 1 <= k <= n - 1 is computed, and each of those has exactly two live predecessors, never one. At n = 8 the rectangle declares 81 cells, 45 of them live: 17 given, one per row down the left edge and one per row past the first on the diagonal, and 28 summed. THE DOTS ARE NOT ZEROS, in the sense that nothing is ever written to them and no cell ever reads one. A position with column > row would be asking to fill more non-empty subsets than there are elements to fill them, which is not a hard question, it is not a question. Nothing could read one by accident either: a computed cell at (n, k) has k <= n - 1, so the two cells it reads, (n - 1, k) and (n - 1, k - 1), both have column at most n - 1 and therefore sit on or below row n - 1's own diagonal. Zero is even the mathematically correct value for those positions, since there are no such partitions, so unlike min-sum-in-a-triangle nothing here would be corrupted by a stray zero above the diagonal. They are dots because they are not part of the question. Filling row-major, left to right within each row, means both cells a computed cell reads are final before it reads them, which is the only ordering property the recurrence needs.

row n: how many distinct elements there are to place

0

1

2

3

4

5

6

7

8

0

1

·

1

0

1

·

2

0

1

·

3

0

1

3

1

·

4

0

1

7

6

1

·

5

0

1

15

25

10

1

·

6

0

1

31

90

65

15

1

·

7

0

1

63

301

350

140

21

1

·

8

0

1

127

966

1701

1050

266

28

1

column k: how many non-empty subsets to fill, so the cell is S(n, k)

ways-to-partition-a-set.ts

1function waysToPartitionASet(n, k) {
2 const dp = Array.from({ length: n + 1 }, () => new Array(n + 1).fill(0));
3 dp[0][0] = 1;
4 for (let i = 1; i <= n; i++) {
5 dp[i][0] = 0;
6 dp[i][i] = 1;
7 for (let j = 1; j < i; j++) {
8 const joinExisting = j * dp[i - 1][j];
9 const startNew = dp[i - 1][j - 1];
10 dp[i][j] = joinExisting + startNew;
11 }
12 }
13 return dp[n][k];
14}

Base caseComputedBeing readAnswer

The code, the trap, the variations

ways-to-partition-a-set.ts

1function waysToPartitionASet(n, k) {
2 const dp = Array.from({ length: n + 1 }, () => new Array(n + 1).fill(0));
3 dp[0][0] = 1;
4 for (let i = 1; i <= n; i++) {
5 dp[i][0] = 0;
6 dp[i][i] = 1;
7 for (let j = 1; j < i; j++) {
8 const joinExisting = j * dp[i - 1][j];
9 const startNew = dp[i - 1][j - 1];
10 dp[i][j] = joinExisting + startNew;
11 }
12 }
13 return dp[n][k];
14}

Where people go wrong

Dropping the coefficient. Write dp[n][k] = dp[n - 1][k] + dp[n - 1][k - 1], which is binomial-coefficient's recurrence, and everything about the picture stays right: same triangle, same two arrows, same bases, nothing thrown, whole numbers throughout. What you get is Pascal's triangle SHIFTED one row down and one column right, not Pascal's triangle in place, because this page's left edge is 0 where Pascal's is 1. Measured, the broken table holds exactly C(n - 1, k - 1) at every cell with 1 <= k <= n <= 10. Three things let it survive a glance, and the numbers are what make the point. FIRST, it is not wrong everywhere. Of the 45 live cells at n = 8 it gets 24 right, and those 24 are precisely column 0, column 1 and the diagonal, the cells whose value is forced to a 0 or a 1 anyway. All 21 cells with 2 <= k <= n - 1 are wrong. The first cell it gets wrong is dp[3][2], where it says 2 and the truth is 3, so it has already failed AT n = 3, not somewhere past it. SECOND, the wrong answers are a recognisable sequence rather than obvious garbage: column 3 comes out 3, 6, 10, 15, 21 across n = 4 to 8, which are the triangular numbers, against the true 6, 25, 90, 301, 966. THIRD, and worst, one of the wrong answers is a right answer from next door. The broken table returns 6 at n = 5, and 6 is the correct value of S(4, 3), so a spot check at a single size can land on a number it has seen before and be reassured by it. The other two mistakes are about which index goes where, and both are worth measuring rather than waving at. Put the coefficient on the OTHER term, dp[n][k] = k * dp[n - 1][k - 1] + dp[n - 1][k], and column 3 comes out 10, 25, 46, 73, 106 across n = 4 to 8: wrong at four of the five sizes and exactly right at n = 5, where it returns 25. That is why the independent check behind this page runs every size the slider offers rather than one. Use the ROW index as the multiplier instead of the column and it is wrong everywhere and wildly so, 9, 71, 580, 5104, 48860 over the same range. And reading the two axes the wrong way round puts you in the empty half: S(8, 3) is dp[8][3], the 966, while dp[3][8] is a dot, because splitting 3 elements into 8 non-empty subsets is not a small number, it is not a thing at all.

Ask for the number of ways to split the n elements into ANY number of non-empty subsets rather than exactly k.
Nothing about the recurrence, the bases or the fill order moves; only what you read at the end does, switching from one highlighted cell to the SUM of the bottom row. Those totals are the Bell numbers, measured as 1, 1, 2, 5, 15, 52, 203, 877, 4140 for rows 0 through 8, and the sweep was already computing every term of the sum. That is the generality argument made concrete, and it is the same relationship nth-row-of-pascals-triangle has with binomial-coefficient: one cell against a whole row of the same table. It also keeps the rolling-row space reduction alive, since the final row is exactly what the rolling row holds, but it kills the option of stopping the sweep at column k, because now every column of the bottom row is part of the answer.
Return S(n, k) modulo a prime p, the usual competitive-programming form.
The recurrence does not change: still the column index times the cell above, plus the cell up and to the left. Only the write changes, taking a % p after the addition, which keeps every cell below p and removes the overflow question entirely. Shape, bases, fill order and dependency arrows are all untouched. This is also the variation that makes the table clearly worth having over the closed form, which divides by k! at the end: dividing modulo p means multiplying by the modular inverse of k!, real extra machinery to get right, while the additive table needs a multiply, a plus and a percent.
Count distributions into k LABELLED boxes with none left empty, which is the number of surjections from an n-element set onto a k-element set.
Naming the subsets turns each partition into k! distinct distributions, so the answer is k! * S(n, k), which is 36, 150, 540, 1806, 5796 across n = 4 to 8 against this page's 6, 25, 90, 301, 966. The interesting part is that the labelled table has a recurrence of its own and it is a different SHAPE of arithmetic: T(n, k) = k * (T(n - 1, k) + T(n - 1, k - 1)), one factor over a bracketed sum, verified against k! * S(n, k) for every k up to 6 and n up to 10. That is the form painting-fence and count-derangements narrate, and it is NOT the same quantity as k * T(n - 1, k) + T(n - 1, k - 1); the same triangle and the same two arrows admit both, which is why a page has to be explicit about where the bracket goes. The shape and fill order are unchanged and the left edge stays 0, but the diagonal moves: T(n, n) = n!, so it runs 1, 1, 2, 6, 24, 120, 720, 5040, 40320 instead of all 1s. One more thing falls out of it. The 5796 at n = 8 is exactly the alternating sum the check behind this page forms before dividing by 3!, and that is not a coincidence: inclusion and exclusion counts the LABELLED distributions, and the division by k! is precisely what turns labelled boxes back into unordered subsets.

Minimum Perfect Squares Binomial Coefficient