The cells a permutation must miss

A permutation of five objects can be drawn as five dots on a five-by-five grid, one in every row and one in every column: the dot in row $i$ sits in the column of the place object $i$ goes to. A derangement is then a permutation with no dot on the diagonal, and the hat problem is the question of how many permutations miss five particular cells.

Nothing about the counting needed those cells to be the diagonal. Forbid any cells at all — a person who will not take two particular hats, a task that two workers cannot do, a guest who refuses three seats — and ask how many permutations avoid them. The question is the same question, and inclusion–exclusion answers it the same way.

What makes the answer computable is that it depends on the board through one list of numbers and nothing else. Those numbers have a name taken from chess, and they carry more structure than the problem that introduced them.

One condition per forbidden cell #

The derangement count came from one bad event per object: object $i$ lands in place $i$. Here there is one bad event per forbidden cell: the permutation puts a dot in that cell. A permutation avoids the board exactly when none of the bad events happens, which is the shape inclusion–exclusion counts.

So take every set of forbidden cells, count the permutations that use all of them, and add those counts with alternating signs by the size of the set. A set of cells can be used by a permutation only if no two share a row or a column, since a permutation has one dot per row and per column. Such a set is a placement of non-attacking rooks: rooks on a chessboard attack along rows and columns, so a set of cells that a permutation can use simultaneously is exactly a set of rooks none of which threatens another.

A placement of $k$ rooks fixes $k$ rows of the permutation. The other $n - k$ rows can be filled in $(n - k)!$ ways, so every placement is contained in exactly $(n-k)!$ permutations. Write $r_k$ for the number of placements of $k$ rooks on the forbidden cells. Then inclusion–exclusion gives

$$\#\{\text{permutations avoiding the board}\} = \sum_{k=0}^{n} (-1)^k \, r_k \, (n-k)!.$$

The numbers $r_0, r_1, r_2, \ldots$ are the board’s rook numbers. They depend only on which cells are forbidden, and once they are known the count is a finite sum of a kind already met in the bracketing argument: each partial sum overshoots or undershoots in turn.

The table the count comes from #

It is worth seeing the sum laid out, because the terms are enormous next to the answer and it is not obvious that they should cancel so completely.

The running total falls below zero at the second step, which is the first sign that the individual terms mean nothing on their own. A single permutation that uses three forbidden cells appears three times in the $r_1$ term, three times in the $r_2$ term (once for each pair of its three cells), and once in the $r_3$ term. With signs, that is $3 - 3 + 1 = 1$ subtracted from its single appearance in the first term, leaving zero. Every permutation that touches the board at all is cancelled to zero in the same way, by the binomial identity that $\sum (-1)^k \binom{m}{k} = 0$ for $m \ge 1$.

For the diagonal board the table becomes the familiar one. Any $k$ diagonal cells are non-attacking, so $r_k = \binom{n}{k}$, and the sum is the derangement formula $\sum (-1)^k \binom{n}{k}(n-k)! = n! \sum (-1)^k / k!$. The hat problem is the case where the rook numbers are as simple as they can be.

How many cells a permutation hits #

Avoiding the board is the event of hitting zero forbidden cells, and the same rook numbers give the chance of hitting any other number. The count of people who get their own hat did this for the diagonal; for a general board the formula is

$$e_j = \sum_{k \ge j} (-1)^{k-j} \binom{k}{j} \, r_k \, (n-k)!,$$

the number of permutations that use exactly $j$ forbidden cells. The binomial coefficient is the correction for a permutation that hits $k$ cells being counted once for every $j$ of them.

For the eight-cell board the six values are $20, 39, 38, 16, 6$ and $1$ for $j = 0$ to $5$, and they add to $120$ as they must. The average number of hits is $192/120 = 1.6$, which is the eight forbidden cells times the chance $1/5$ that a random permutation uses any particular one — the first rook number times $(n-1)!$, divided by $n!$. That average needs nothing but $r_1$. The chance of hitting none needs every rook number, which is the difference between a mean and a distribution.

The single permutation that hits five forbidden cells is worth finding, because it shows how dense this board is. Five cells with no two in a row or column is a complete permutation lying entirely inside the board — and $r_5 = 1$ says there is exactly one such. It sends the five rows to columns $2, 4, 3, 1, 5$ in turn, and it is forced: the bottom row has only its corner forbidden, which fixes column $5$, and each choice after that leaves exactly one forbidden cell available in some other row, until all five are placed.

A polynomial that multiplies #

Collect the rook numbers into a polynomial, $R(x) = r_0 + r_1 x + r_2 x^2 + \cdots$. The polynomial is not a notational convenience. It turns a structural fact about boards into multiplication.

When two groups of forbidden cells share no row and no column, a rook in one can never attack a rook in the other. A placement of $k$ rooks on the whole board is then a placement of $j$ rooks on the first block and $k - j$ on the second, chosen independently, so

$$r_k = \sum_j r_j(\text{first}) \, r_{k-j}(\text{second}),$$

which is exactly the rule for multiplying polynomials. The same rule is what makes generating functions work in general: a polynomial is a device for making independent choices multiply.

There is a second rule for boards that do not split. Pick any forbidden cell. A placement either avoids that cell, in which case it is a placement on the board with the cell deleted, or uses it, in which case the rest is a placement on the board with that cell’s row and column removed. So $R(x) = R_{\text{deleted}}(x) + x \, R_{\text{struck}}(x)$. Every board reduces, one cell at a time, to boards of a single cell, whose polynomial is $1 + x$. Between the product rule and this one, a rook polynomial can be computed by hand for boards far larger than a search would comfortably enumerate — though not, as the last section explains, for every board quickly.

The product board and the eight-cell board have something else in common, which the two figures reveal only if they are compared. Both are avoided by exactly $20$ of the $120$ permutations, although their rook numbers differ in the last two places. Equal counts do not require equal rook numbers: the count is one alternating sum of them, and different lists can have the same sum.

Two boards that look nothing alike #

The converse question is the more interesting one. If two boards have the same rook numbers, they are avoided by the same number of permutations of every size into which both fit, because the count is built from the rook numbers and nothing else. So which boards share rook numbers?

Boards that differ by rearranging rows, rearranging columns, or swapping rows with columns share them for an obvious reason: those operations do not change which cells attack which. The interesting cases are boards that are genuinely different shapes.

Boards of this shape — columns of cells standing on a common base, heights never decreasing — are called Ferrers boards, after the dot diagrams of partitions. For them the question has a complete answer, found by Jay Goldman, John Joichi and Dennis White in 1975. With heights $h_1 \le h_2 \le \cdots \le h_n$,

$$\sum_k r_k \, x(x-1)\cdots(x-n+k+1) = \prod_{i=1}^{n} (x + h_i - i + 1),$$

so the rook numbers are determined by the multiset of values $h_i - i$, and two Ferrers boards share rook numbers exactly when those multisets agree. For the two boards in the figure the values are $\{-1, -2, -3, -2, -1\}$ and $\{-1, -1, -2, -2, -3\}$: the same five numbers in a different order.

The factorisation is proved by counting one thing two ways. Take $x$ extra rows below the board and count the ways to put one rook in every column of the enlarged board with no two in a row. Filling the columns from shortest to tallest, column $i$ has $x + h_i$ cells and $i - 1$ of its rows are already taken, which gives the product. Alternatively, sort placements by how many rooks sit on the original board; $k$ rooks there leave $n - k$ columns to fill from the $x$ new rows, in $x(x-1)\cdots$ ways, which gives the sum.

Rooks that split a set #

The simplest Ferrers board with a non-trivial answer is the staircase, with column heights $0, 1, 2, \ldots, n-1$. Its rook numbers are a famous triangle in disguise.

A Stirling number of the second kind $S(n, j)$ counts the ways to split $n$ labelled objects into $j$ non-empty groups, and the correspondence with rooks is direct. Label the columns and the rows by the objects $1$ to $n$ so that the column of object $j$ contains cells for exactly the objects smaller than $j$. A rook in column $j$ and the row of object $i < j$ means “put $j$ in the same group as $i$, as its next member”. No two rooks in a column means each object has at most one immediate predecessor; no two in a row means each has at most one immediate successor. So a placement strings the objects into chains, each chain is a group, and $k$ rooks join $n$ singletons into $n - k$ groups.

With heights $h_i = i - 1$, every factor in the Goldman–Joichi–White product is just $x$, and the identity becomes

$$x^n = \sum_j S(n, j)\, x(x-1)\cdots(x-j+1),$$

the standard expansion of a power in falling factorials. A statement about set partitions, one about polynomials and one about rooks on a staircase are the same statement, and counting the colourings of a graph runs on the same expansion.

A band of forbidden cells #

The diagonal is a band of width one. Widen it: forbid object $i$ from places $i$ and $i+1$, or from $i$, $i+1$ and $i+2$. The rook numbers of a band are no longer binomial coefficients, but the count still settles as the board grows.

The limits are $e^{-1} \approx 0.368$, $e^{-2} \approx 0.135$ and $e^{-3} \approx 0.050$. They have the same explanation as the Poisson count of fixed points. A band of width $w$ contains about $nw$ cells, and a random permutation hits each with chance $1/n$, so it hits about $w$ of them on average. The hits are only weakly dependent, and the number of them behaves like a Poisson count with mean $w$, whose chance of being zero is $e^{-w}$.

The approach is not equally fast for every width, and the difference is visible in the exact values at fourteen. The width-one band is within $10^{-12}$ of $1/e$, as derangements always are. The width-two band stands at $0.13498$ against $e^{-2} \approx 0.13534$, and the width-three band at $0.04910$ against $0.04979$ — still more than one per cent short. A wider band packs more of its cells into the same few rows and columns, so its hits interfere with each other more, and the Poisson picture takes longer to become accurate.

The width-two band is also the start of a problem with a history. If the band wraps round, so that the last object is also forbidden from the first place, the board describes guests at a round table who refuse to sit beside two particular people. That is the problem Lucas posed about couples at dinner, and the corner cell that makes the band wrap turns out to be the whole of its difficulty.

Where the rooks came from #

The chessboard language is not decoration; it is how the subject was organised. Irving Kaplansky and John Riordan introduced rook polynomials in a paper of 1946, “The problem of the rooks and its applications”, precisely to bring the scattered problems of forbidden positions under one roof. Derangements, the dinner-table problem of couples, and the counting of Latin rectangles had each been solved separately in the nineteenth and early twentieth centuries, each with its own ingenious argument. Kaplansky and Riordan observed that every one of them was inclusion–exclusion over a board, and that the only problem-specific work was finding the board’s rook numbers.

That division of labour is the reason the method has lasted. The inclusion–exclusion step is the same for every board and never needs to be re-derived; all the ingenuity goes into the rook numbers, where the product rule, the deletion rule and the Ferrers factorisation each do a piece of it. Riordan’s textbook of 1958 made the approach standard, and by then the rook polynomial had become an object studied for its own sake — the Goldman–Joichi–White theorem is about rook numbers with no permutation in sight.

What a board of rooks cannot settle #

Which boards are rook-equivalent in general. The Ferrers criterion is complete for boards of that shape and says nothing about any other. Two arbitrary boards with the same rook numbers can be found by search, and the figures find some, but no simple test on the cells of a general board decides it.

That the band limits are exactly $e^{-w}$. The curves are exact up to fourteen and flat to the eye by eight. The limit itself rests on a Poisson approximation that holds because the forbidden cells are spread thinly, one band across the whole board; the argument is a theorem about sums of weakly dependent events, and no finite computation reaches the limit.

Where the sum’s size comes from. The inclusion–exclusion table shows terms of hundreds cancelling to twenty. It does not show why the cancellation is total, which is the binomial identity in the text: every permutation that touches the board is counted with weights summing to zero.

Still open: counting avoidance quickly #

The count of permutations avoiding a board is the permanent of a matrix of zeroes and ones — ones in the allowed cells — the determinant’s sum with every sign set to plus, and the same quantity that bounds the number of Latin squares. Rook numbers are one route to it, and for special boards they are fast: Ferrers boards have the product formula, bands have recurrences, and the diagonal has $n!/e$ rounded.

For an arbitrary board, every known method is exponential. The best general formula, Herbert Ryser’s of 1963, takes on the order of $2^n n$ steps, and in 1979 Leslie Valiant showed that computing the permanent of a zero–one matrix is as hard as any counting problem in a precise sense. Whether the number of permutations avoiding an arbitrary board can be computed in time polynomial in its size is open — a fast method would collapse a large part of complexity theory, and no proof rules one out.

A count carried by one list #

The diagonal made inclusion–exclusion look like a formula for one problem. With the diagonal replaced by an arbitrary board, it becomes a machine whose only input is a list: the numbers of ways to place non-attacking rooks on the forbidden cells. Everything the answer knows about the board passes through that list.

The list turned out to have structure of its own — it multiplies over separate blocks, it is shared by boards of different shapes exactly when a simple multiset agrees, and on the staircase it is the triangle of Stirling numbers. And the width of a forbidden band sets the limit the answer approaches, $e^{-w}$, of which the hat problem’s $1/e$ is only the first.