Easy Problemscountingcombinatoricsgrid

Permutations with K Inversions

An inversion in a permutation of the numbers 1 through n is a pair of positions where a larger value sits before a smaller one. Count how many permutations of 1 through n contain exactly k inversions.

Do this lesson first: climbing stairs

Example input

n = 7, k = 5, so the question is how many orderings of 1 through 7 hold exactly 5 inversions

Expected output

169

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[r][k] is the number of permutations of 1 through r + 1 that contain exactly k inversions, an inversion being a pair of positions holding values in the wrong order, larger before smaller. THE ROW INDEX IS ONE LESS THAN n, and getting that straight is the single thing most likely to make every number on this page look wrong. Row 0 is n = 1, row 1 is n = 2, row r is n = r + 1, and the table therefore declares size rows rather than size + 1, because n = 0 answers nothing anybody asked. It is not the only 2D table in this course that offsets an index, so treat no row gutter as self-evident: read the row heading on whatever page you are on before trusting the numbers down the side. The cost of missing it is concrete: at n = 7 the bottom row is row 6, and a reader who takes row 6 for n = 6 reads 169 where the answer for n = 6 is the 71 one row up. Two numbers name the state, how many values are being permuted and how many inversions they have to hold, so the table is a grid even though there is no input array anywhere on this page; that much it shares with binomial-coefficient and ways-to-partition-a-set. THE SHAPE IS WHERE IT PARTS COMPANY WITH THEM. Those two declare a square and skip the half above the diagonal, as do nth-row-of-pascals-triangle and min-sum-in-a-triangle: measured, four of the eight 2D tables authored before this one are lower-triangular in exactly that way, all four skipping the cells with column greater than row, and a dot on one of them means a position that does not exist. This table is a FULL RECTANGLE with every declared cell live and not a single dot, and its width does not grow with n past 12 columns. The cell holds a count and nothing about which orderings achieved it.

dp[r][k] = sum over j = 0 to min(k, r) of dp[r - 1][k - j]

Take the largest of the n values and ask where it ended up. Nothing outranks it, so every inversion it belongs to is an inversion with something to its RIGHT, one for each value sitting after it. Put it last and it contributes none. Slide it one position forward and it contributes one. Put it at the very front and all n - 1 of the others are to its right, so it contributes n - 1. That is n placements contributing 0, 1, up to n - 1 inversions, one value of j apiece. NOW THE PART THAT MAKES IT A RECURRENCE. Delete the largest value and what is left is a permutation of the other n - 1, in the same relative order, holding exactly the inversions it held before: none of them involved the largest value, so none of them is disturbed by where it sat. So if the largest contributed j, the rest have to supply the remaining k - j between them, and the row holding permutations of n - 1 values already counts the ways to do that. Mind which row that is: this cell lives in row n - 1, so the row it reads is row n - 2, one above it, and in the table's own coordinates that is simply dp[r - 1][k - j]. The correspondence runs both ways with nothing left over. From a permutation of n you read off one j and one permutation of the rest; from a j and a permutation of the rest you rebuild exactly one permutation of n. So the counts add, and they add over a WINDOW rather than a pair, which is the whole difference between this page and the three Pascal-shaped tables it sits near. TWO SEPARATE THINGS CAP THE WINDOW and both are real. j cannot exceed the number of positions the largest value can move forward through, which is n - 1, and in table coordinates n - 1 is the ROW INDEX r. j also cannot exceed k, because the rest of the permutation cannot supply a negative number of inversions to make up the difference. So j runs 0 to min(k, r) and the window is min(k, r) + 1 cells wide. It is a SUM rather than a min or a max because this is a counting problem: every placement really happens, across different permutations, and the total of them is what is wanted rather than the best of them. That is the same distinction count-all-paths-in-a-grid, two problems up this file, draws against min-cost-path.

THE WHOLE OF ROW 0 IS GIVEN, all of it, not merely its first cell. Row 0 is n = 1 and there is no row above it, so nothing in it could be summed from anywhere. dp[0][0] = 1, because the one ordering of a single value has no inversion: an inversion needs two positions to disagree and there is only one position. dp[0][k] = 0 for every k from 1 to the right edge, because one value cannot be out of order with anything. At n = 7 that is 12 given cells, one per declared column. COLUMN 0 IS GIVEN ON EVERY ROW TOO, value 1, and that is a choice with a reason on each side. The value itself is not in doubt: exactly one permutation of any n has no inversions at all, the sorted one. What is in doubt is whether to compute it, and the arithmetic settles that. The window for column 0 is min(0, r) + 1 = 1 cell wide, so the recurrence would copy dp[r - 1][0] across and call it a step, and a one-term sum restates a value rather than deriving one. Saying the sorted permutation out loud says strictly more. At n = 7 that is 6 further given cells, one per row past the first, so 18 of the table's 84 cells are given and the other 66 are summed. THE TABLE IS CUT OFF ON THE RIGHT, AND THE CUT IS A PROOF RATHER THAN A NOTE. A permutation of n values holds at most n(n - 1)/2 inversions, which is 21 at n = 7, so a complete table would need 22 columns; this one declares 12, numbered 0 through 11. Here is why nothing surviving is damaged. Every cell dp[r][k] reads only cells dp[r - 1][k - j] with j at least 0, so every cell it reads sits in its own column or a column to its LEFT. No cell anywhere in this table ever reads a column to its right. Removing columns 12 and beyond therefore removes cells that no remaining cell could ever have consulted, and every cell left on screen holds exactly the value it would hold in the full 22-column table. The answer cell, column 5, is nowhere near the cut. NOW THE HONEST HALF: the rows themselves are incomplete, visibly so at the bottom. At n = 7 five of the seven rows shown are complete, n = 1 through n = 5, whose largest inversion counts are 0, 1, 3, 6 and 10 and all fit inside column 11. The other two are truncated, n = 6 running to 15 and n = 7 to 21. What that costs you is a picture rather than a value: every complete row is symmetric about its middle, 1, 4, 9, 15, 20, 22, 20, 15, 9, 4, 1 at n = 5, because reversing a permutation turns each of its inversions into a non-inversion and back, so k and n(n - 1)/2 - k always tie. A cut row shows that symmetry only up to where it stops. As it happens neither cut hides its row's peak: n = 6's twin 101s sit at columns 7 and 8 and n = 7's twin 573s at columns 10 and 11, both pairs on screen, and what falls off the right edge is only the descent back to a single 1. THE FILL ORDER is row-major, left to right within each row, and the window makes the ordering requirement weaker rather than stronger. Every cell a computed cell reads lies in the row DIRECTLY above it, never in its own row, so finishing each row before starting the next is the whole of what the recurrence needs; within a row the order is free, because no cell in a row depends on another cell in the same row.

Tabulation, one row-major sweep, and what is worth pricing on this page is the WINDOW. THE NUMBERS AT n = 7, all measured off the emitted trace: 84 declared cells, all 84 live, 18 given and 66 summed, and those 66 sums read 262 cells between them and perform 196 additions. The window width is not uniform across them either: 16 cells read 2, 14 read 3, 12 read 4, 10 read 5, 8 read 6 and 6 read 7. Seven is the widest fan on the page and it occurs only in the bottom row, at columns 6 through 11, where min(k, 6) has stopped growing. The answer cell is not one of the seven-wide ones: dp[6][5] reads 6 cells, since min(5, 6) + 1 = 6. FAN-IN RATHER THAN PAIRING is the structural point, and it is worth stating carefully. Every one of those up to seven dependencies lies in the row directly above, spread across up to seven consecutive columns, so the arrows into a cell converge from a row rather than arriving as a fixed pair. What that LOOKS like is a separate question and has to come from the geometry rather than from the word fan. 2D cells are 60px wide and 58px tall and a 2D arrow is drawn straight from one centre to the next, so the seven arms into a bottom-row cell arrive at 0.0, 46.0, 64.2, 72.1, 76.4, 79.1 and 80.8 degrees off vertical. They spread across most of a right angle, but they are not evenly spread: they bunch towards the horizontal, because every extra column of reach adds 60px of width against no extra height at all, so the first sideways step alone accounts for 46 of those 80.8 degrees. The vertical arm is also much the shortest of the seven. It spans 58px centre to centre and the renderer trims 20px at the source and 22px at the tip to clear the digits, leaving 16px of drawn line, against 322.6px for the widest arm. COST. Every computed cell sums at most min(k, n - 1) + 1 cells and the snippet's table holds (n - 1) x k of them, so the sweep is O(n x k x min(k, n)) time, which is the looser O(n^2 k) whenever k is the larger of the two. Space is O(n k), and since a cell only ever reads the row above, one rolling row of k + 1 numbers reduces that to O(k). A GENUINELY CHEAPER RECURRENCE EXISTS and it is deliberately in variations rather than smuggled into the snippet above, because it is a different recurrence and this page is about this one. Measured across the slider's four sizes, the shipped sweep reads 50, 130, 200 and 262 cells where a two-operations-per-cell prefix form would do 36, 80, 110 and 132, a factor of 1.389, 1.625, 1.818 and 1.985. So at every size this page can show, the refinement saves under a factor of two, and the reason is arithmetic rather than luck: the factor is the average window width divided by 2, and the average window is only 3.97 cells at n = 7. It grows with min(k, n), which the 12-column cap holds down here, not with n on its own. MEMOIZATION does strictly less work than the sweep, as it does on binomial-coefficient and for the same reason: the answer is ONE cell, so part of this table lies outside the cone of cells that reaches it. How large a part is worth measuring rather than assuming, because it is not the same story at every size. A memoized recursion from dp[n - 1][5] only ever descends into columns 0 through 5, and it fills 17, 24, 31 and 37 cells across sizes 4 to 7 against the sweep's 28, 55, 72 and 84, a factor of 1.647, 2.292, 2.323 and 2.270. So 11 of the 28 cells sit outside the cone at the slider's minimum, which is 39 per cent and NOT most of them, against roughly 56 per cent at each of the other three sizes. The factor is not monotone in n either: it peaks at n = 6 and comes back down at 7. The surplus is not waste, though. The extra cells ARE the other answers, every inversion count rather than only k = 5, which is the same generality argument the counting tables in the basic tier make for keeping a table they can otherwise beat.

Time O(n × k × min(k, n)) to fill the table, since each of the (n - 1) × k computed cells sums a window of at most min(k, n - 1) + 1 cells; O(n^2 k) as a loose boundSpace O(n × k), reducible to O(k) with one rolling row

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.

THE WHOLE OF ROW 0 IS GIVEN, all of it, not merely its first cell. Row 0 is n = 1 and there is no row above it, so nothing in it could be summed from anywhere. dp[0][0] = 1, because the one ordering of a single value has no inversion: an inversion needs two positions to disagree and there is only one position. dp[0][k] = 0 for every k from 1 to the right edge, because one value cannot be out of order with anything. At n = 7 that is 12 given cells, one per declared column. COLUMN 0 IS GIVEN ON EVERY ROW TOO, value 1, and that is a choice with a reason on each side. The value itself is not in doubt: exactly one permutation of any n has no inversions at all, the sorted one. What is in doubt is whether to compute it, and the arithmetic settles that. The window for column 0 is min(0, r) + 1 = 1 cell wide, so the recurrence would copy dp[r - 1][0] across and call it a step, and a one-term sum restates a value rather than deriving one. Saying the sorted permutation out loud says strictly more. At n = 7 that is 6 further given cells, one per row past the first, so 18 of the table's 84 cells are given and the other 66 are summed. THE TABLE IS CUT OFF ON THE RIGHT, AND THE CUT IS A PROOF RATHER THAN A NOTE. A permutation of n values holds at most n(n - 1)/2 inversions, which is 21 at n = 7, so a complete table would need 22 columns; this one declares 12, numbered 0 through 11. Here is why nothing surviving is damaged. Every cell dp[r][k] reads only cells dp[r - 1][k - j] with j at least 0, so every cell it reads sits in its own column or a column to its LEFT. No cell anywhere in this table ever reads a column to its right. Removing columns 12 and beyond therefore removes cells that no remaining cell could ever have consulted, and every cell left on screen holds exactly the value it would hold in the full 22-column table. The answer cell, column 5, is nowhere near the cut. NOW THE HONEST HALF: the rows themselves are incomplete, visibly so at the bottom. At n = 7 five of the seven rows shown are complete, n = 1 through n = 5, whose largest inversion counts are 0, 1, 3, 6 and 10 and all fit inside column 11. The other two are truncated, n = 6 running to 15 and n = 7 to 21. What that costs you is a picture rather than a value: every complete row is symmetric about its middle, 1, 4, 9, 15, 20, 22, 20, 15, 9, 4, 1 at n = 5, because reversing a permutation turns each of its inversions into a non-inversion and back, so k and n(n - 1)/2 - k always tie. A cut row shows that symmetry only up to where it stops. As it happens neither cut hides its row's peak: n = 6's twin 101s sit at columns 7 and 8 and n = 7's twin 573s at columns 10 and 11, both pairs on screen, and what falls off the right edge is only the descent back to a single 1. THE FILL ORDER is row-major, left to right within each row, and the window makes the ordering requirement weaker rather than stronger. Every cell a computed cell reads lies in the row DIRECTLY above it, never in its own row, so finishing each row before starting the next is the whole of what the recurrence needs; within a row the order is free, because no cell in a row depends on another cell in the same row.

row r: holds n = r + 1 values, so row 0 is n = 1

0

1

2

3

4

5

6

7

8

9

10

11

0

1

0

1

0

2

1

2

1

0

3

1

3

5

6

5

3

1

0

4

1

4

9

15

20

22

20

15

9

4

1

0

5

1

5

14

29

49

71

90

101

90

71

49

6

1

6

20

49

98

169

259

359

455

531

573

column k: how many inversions, so the cell counts permutations of r + 1 values with exactly k of them

permutations-with-k-inversions.ts

1function permutationsWithKInversions(n, k) {
2 const dp = Array.from({ length: n }, () => new Array(k + 1).fill(0));
3 dp[0][0] = 1;
4 for (let r = 1; r < n; r++) {
5 dp[r][0] = 1;
6 for (let c = 1; c <= k; c++) {
7 let total = 0;
8 for (let j = 0; j <= Math.min(c, r); j++) {
9 total += dp[r - 1][c - j];
10 }
11 dp[r][c] = total;
12 }
13 }
14 return dp[n - 1][k];
15}

Base caseComputedBeing readAnswer

The code, the trap, the variations

permutations-with-k-inversions.ts

1function permutationsWithKInversions(n, k) {
2 const dp = Array.from({ length: n }, () => new Array(k + 1).fill(0));
3 dp[0][0] = 1;
4 for (let r = 1; r < n; r++) {
5 dp[r][0] = 1;
6 for (let c = 1; c <= k; c++) {
7 let total = 0;
8 for (let j = 0; j <= Math.min(c, r); j++) {
9 total += dp[r - 1][c - j];
10 }
11 dp[r][c] = total;
12 }
13 }
14 return dp[n - 1][k];
15}

Where people go wrong

The window width. There are THREE ways to get the width itself wrong, they fail in completely different registers, and they are worth ranking rather than lumping together; then there is a fourth mistake that is not about the width at all, and it is the one this table protects you from least. TWO OF THE FOUR CAN FAIL SILENTLY, which is the ranking that matters. USING min(k, n) WHERE THE TRUTH IS min(k, n - 1). This grants the largest value one more position than it has, and it is loud rather than subtle: measured, it reports 11, 41, 105 and 224 across n = 4 to 7 against the true 3, 22, 71 and 169, wrong at every size by a factor of 3.667, 1.864, 1.479 and 1.325, and the first cell it gets wrong is dp[1][2], where it claims one ordering of two values holds two inversions. Nothing about it looks fine at small n; it has already failed by the second row. USING min(k, n - 2) IS THE DANGEROUS ONE, and it is dangerous at every size rather than at some of them. It reports 0, 3, 22 and 71 across the same four sizes, and ALL FOUR are the correct answer for the next size down: measured, that variant's bottom row is exactly the true row for n - 1, cell for cell, at every one of n = 4, 5, 6 and 7. The 0 it reports at n = 4 is no exception, because a permutation of 3 values cannot hold 5 inversions, so 0 is the right answer to the question it has quietly substituted. This is not a table that looks broken; it is a table that looks perfect and answers a question one size down. A spot check anywhere lands on a number it has seen before and is reassured by it, which is why the independent check behind this page runs every size the slider offers rather than one. FORGETTING THE min WITH k ALTOGETHER, so j runs to n - 1 and the sum reaches for a negative column. This one is not a wrong-number bug at all, and saying it is would be wrong. Every out-of-range term is a term the true sum did not want, so if reading past the left edge contributes nothing the table is unchanged; in JavaScript dp[r - 1][-1] is undefined instead, so total += undefined poisons that cell to NaN. Measured, the NaN reaches the reported answer at n = 5, 6 and 7 but not at n = 4, where the poisoned cells happen to sit outside the answer's cone. It is a crash-shaped mistake, not a plausible-numbers one. READING THE TWO AXES THE WRONG WAY ROUND is the fourth mistake, the one that is not about the window at all, and the second of the four that can fail silently. This table gives you less protection against it than the triangular pages do. On binomial-coefficient a swapped lookup lands above the diagonal, on a dot, and tells you so at once. Here every cell of the rectangle is live, so a swap lands on a real number: at n = 7 the answer is dp[6][5] = 169 and the transposed cell dp[5][6] = 90, which is a perfectly good count of something else, the orderings of 6 values with 6 inversions.

Replace the window sum with a prefix-sum step, dp[r][k] = dp[r][k - 1] + dp[r - 1][k] - dp[r - 1][k - r - 1].
Two operations per cell instead of a fresh window sum, so the fill drops from O(n k min(k, n)) to O(n k). The identity is just the window telescoping: the window at column k and the window at column k - 1 overlap in all but their two ends, so one add brings in the new right end and one subtract drops the old left end, with the subtracted term omitted when its column is off the table. Nothing about the state, the bases or the fill order moves. What DOES change is the picture, which is why this is a variation rather than the shipped snippet: a cell now reads its own left neighbour as well as the row above, so the arrows stop fanning and the provenance of a value is no longer visible as one step per placement of the largest value. Measured, the saving over this page's four sizes is a factor of 1.389, 1.625, 1.818 and 1.985, so it is real but modest until min(k, n) grows well past what a 12-column table can show.
Ask for the number of permutations with AT MOST k inversions rather than exactly k.
The recurrence, the bases and the sweep are all untouched; only what you read at the end changes, from one highlighted cell to the running total of its row from column 0 to column k. The sweep was already computing every term of that total, which is the generality argument made concrete. This one costs nothing at all, and it is worth being exact about why rather than inventing a price for it. Filling exactly columns 0 through k is what the k = 5 question already required, so the column bound does not move; the rolling-row reduction still applies, since the row being totalled is the row the rolling row holds; and no cell reads a column to its right, so no dependency changes either. The read at the end is the whole of the difference, which makes this the cheapest variation on the page.
Count permutations of n with exactly k inversions modulo a prime p, the usual competitive-programming form.
The recurrence does not change at all: still the same window of the row above. Only the write changes, taking a % p after the sum, which keeps every cell below p. Shape, bases, fill order and the dependency fan are all untouched. The one thing to watch is the prefix-sum variation above, which subtracts: under a modulus that subtraction can go negative, so it needs a + p before the % rather than after it. The plain window sum has no such hazard, which is a small argument for the slower form that this page's cost section does not otherwise make.

Paths in a Grid with Obstacles Max A's using Special Keyboard