TAOCP 5.1.3 Exercise 19

An \(n \times n\) chessboard has rows and columns indexed \(1,2,\dots,n\).

taocpmathematicsalgorithmsvolume-3math-hard

Section 5.1.3: Runs

Exercise 19. ▶ [M26] (I. Kaplansky and J. Riordan, 1946.) (a) In how many ways can $n$ nonattacking rooks, no two in the same row or column, be placed on an $n \times n$ chessboard, so that exactly $k$ lie below the main diagonal? (b) In how many ways can $k$ nonattacking rooks be placed below the main diagonal of an $n \times n$ chessboard?

For example, Fig. 4 shows one of the 15619 ways to put eight nonattacking rooks on a standard chessboard with exactly three rooks in the unshaded portion below the main diagonal, together with one of the 1050 ways to put three nonattacking rooks on a triangular board.

Verified: yes
Solve time: 27m39s

Setup

An (n \times n) chessboard has rows and columns indexed (1,2,\dots,n). The main diagonal consists of the cells ((i,i)). A cell is below the main diagonal when its row index is strictly greater than its column index, i.e. ((i,j)) with (1\le j < i \le n).
Nonattacking rooks are placed so that no two share a row or a column.

Part (a) asks for the number of ways to place (n) nonattacking rooks (exactly one in each row and each column) such that exactly (k) of them lie below the main diagonal.
Part (b) asks for the number of ways to place (k) nonattacking rooks (not necessarily one per row/column, but still no two in the same row or column) with all of them below the main diagonal.

Solution

(a) (n) rooks on the full board

Placing (n) nonattacking rooks on an (n\times n) board is equivalent to choosing a permutation (p) of ({1,2,\dots,n}): the rook in row (i) is placed in column (p(i)).
The condition “exactly (k) rooks below the main diagonal” means exactly (k) indices (i) satisfy (i > p(i)), i.e. (p(i) < i).

The number of permutations of (n) with exactly (k) indices (i) such that (p(i) < i) is the Eulerian number (\left\langle {n \atop k} \right\rangle). This can be seen by noting that (p(i) < i) is equivalent to (i > p(i)); if we take the inverse permutation (q = p^{-1}), then (q(j) = i) and the inequality becomes (q(j) > j). Thus the number of indices with (p(i) < i) equals the number of excedances of the inverse permutation. The distribution of excedances over all permutations is well known to be the Eulerian numbers (which also count descents). Alternatively, one can verify directly that these numbers satisfy the recurrence [ a(n,k) = (k+1),a(n-1,k) + (n-k),a(n-1,k-1) ] with the boundary conditions (a(0,0)=1), (a(n,0)=1) for (n\ge 0), and (a(n,k)=0) for (k\ge n), which is exactly the recurrence (2) given in the text for (\left\langle {n \atop k} \right\rangle).

[ \boxed{\left\langle {n \atop k} \right\rangle} ]

(b) (k) rooks strictly below the diagonal

Let (r(n,k)) be the number of ways to place (k) nonattacking rooks on the board [ B = {(i,j) \mid 1\le j < i \le n}. ] We derive a recurrence by considering the last row, row (n). Row (n) contains the cells ((n,1),(n,2),\dots,(n,n-1)).

  • Case 1: No rook is placed in row (n).
    Then all (k) rooks are placed in the first (n-1) rows, which form the board (B' = {(i,j) \mid 1\le j < i \le n-1}). This gives (r(n-1,k)) ways.

  • Case 2: A rook is placed in row (n).
    First place (k-1) nonattacking rooks in the board (B') (rows (1,\dots,n-1)); there are (r(n-1,k-1)) ways to do this. These rooks occupy (k-1) distinct columns, all of which lie in ({1,\dots,n-2}) because the highest column available in (B') is (n-2).
    To extend this to a placement of (k) rooks in (B) with one rook in row (n), we must choose a column for the rook in row (n) from the columns ({1,\dots,n-1}) that are not already used. There are ((n-1) - (k-1) = n-k) available columns. Every such choice yields a valid placement because the new rook is in row (n) (so it is below the diagonal) and its column is distinct from the others. Hence this case contributes ((n-k),r(n-1,k-1)) ways.

Combining the two cases we obtain the recurrence [ r(n,k) = r(n-1,k) + (n-k),r(n-1,k-1),\qquad n\ge 2, ] with the initial conditions (r(1,0)=1) and (r(1,k)=0) for (k>0).

This recurrence together with the boundary conditions uniquely determines (r(n,k)). It is satisfied by the Stirling numbers of the second kind (\left{ {n \atop m} \right}) after a change of index.
Recall that (\left{ {n \atop m} \right}) counts partitions of an (n)-set into (m) nonempty subsets and obeys [ \left{ {n \atop m} \right} = m\left{ {n-1 \atop m} \right} + \left{ {n-1 \atop m-1} \right},\qquad \left{ {0 \atop 0} \right}=1,;\left{ {n \atop 0} \right}=0;(n>0). ] Define (a(n,k) = \left{ {n \atop n-k} \right}). Then [ a(n,k) = (n-k)\left{ {n-1 \atop n-k} \right} + \left{ {n-1 \atop n-k-1} \right} = (n-k),a(n-1,k-1) + a(n-1,k), ] which matches the recurrence for (r(n,k)). The initial conditions also agree: (a(1,0)=\left{ {1 \atop 1} \right}=1), (a(1,k)=0) for (k>0). Therefore [ r(n,k) = \left{ {n \atop n-k} \right}. ]

[ \boxed{\left{ {n \atop n-k} \right}} ]

Verification

  • Part (a) for (n=3): The permutations of ({1,2,3}) with (k) rooks below the diagonal are
    (k=0): (123) (1 way)
    (k=1): (132, 213, 231, 321) (4 ways)
    (k=2): (312) (1 way)
    These are exactly the Eulerian numbers (\left\langle {3 \atop 0} \right\rangle=1), (\left\langle {3 \atop 1} \right\rangle=4), (\left\langle {3 \atop 2} \right\rangle=1).

  • Part (b) for (n=4, k=2): Manual count gives 7 ways. The Stirling number (\left{ {4 \atop 2} \right}=7) matches.
    For (n=8, k=3): the recurrence yields (r(8,3)=1050), which coincides with (\left{ {8 \atop 5} \right}=1050) and agrees with the example in the exercise statement (“1050 ways to put three nonattacking rooks on a triangular board”).

  • The recurrence for part (a) is exactly the one given in the text (Equation (2)), and the symmetry (\left\langle {n \atop k} \right\rangle = \left\langle {n \atop n-1-k} \right\rangle) corresponds to the fact that a permutation with (k) rooks below the diagonal has (n-1-k) rooks above the diagonal (fixed points lie on the diagonal and are not counted in either category).

This completes the proof. ∎

Notes

The answers are expressed in terms of the standard combinatorial numbers introduced in the text: (\left\langle {n \atop k} \right\rangle) for Eulerian numbers and (\left{ {n \atop k} \right}) for Stirling numbers of the second kind. The derivations rely only on elementary combinatorial reasoning and the standard recurrences for these numbers.