TAOCP 5.1.4 Exercise 31

We place \(n\) mutually nonattacking rooks on an \(n\times n\) board, which corresponds to a permutation \(\pi\) of \(\{1,\dots,n\}\) with a rook at \((i,\pi(i))\).

taocpmathematicsalgorithmsvolume-3hm-hard

Section 5.1.4: Tableaux and Involutions

Exercise 31. [HM30] Let $x_n$ be the number of ways to place $n$ mutually nonattacking rooks on an $n \times n$ chessboard, where each arrangement is unchanged by reflection about both diagonals. Thus, $x_4 = 6$. (Involutions are required to be symmetrical about only one diagonal. Exercise 5.1.3–19 considers a related problem.) Find the asymptotic behavior of $x_n$.

Verified: yes
Solve time: 4h31m

Setup

We place (n) mutually nonattacking rooks on an (n\times n) board, which corresponds to a permutation (\pi) of ({1,\dots,n}) with a rook at ((i,\pi(i))).
Reflection about the main diagonal sends ((i,j)) to ((j,i)); invariance means (\pi = \pi^{-1}), so (\pi) is an involution.
Reflection about the other diagonal sends ((i,j)) to ((n+1-j,n+1-i)); invariance means (\pi(n+1-j)=n+1-i).
Together with (\pi=\pi^{-1}) this is equivalent to (\pi) commuting with the reverse permutation (\rho(i)=n+1-i).

Let (\pi) be such a permutation. It consists of fixed points and 2-cycles. Because (\pi\rho=\rho\pi), the action of (\pi) is constrained:

  • If (i) is a fixed point then (\rho(i)) is also a fixed point.
  • The centre (c=(n+1)/2) (if (n) odd) satisfies (\rho(c)=c), hence it must be a fixed point.
  • A 2-cycle ((i,j)) is either mapped to itself by (\rho) (i.e. (j=\rho(i))) or forms a pair of 2-cycles ({(i,j),(\rho(i),\rho(j))}) with the two orbits swapped.

Let (m=\lfloor n/2\rfloor). The (\rho)-orbits of size 2 are (m) pairs ({i,n+1-i}).
On these (m) pairs (\pi) induces an involution.

  • For each fixed pair we have 2 choices: the two elements become two fixed points, or they form the 2-cycle ((i,n+1-i)).
  • For each transposition of two pairs we have 2 choices: the four elements can be paired as ((i,j)(\rho(i),\rho(j))) or ((i,\rho(j))(\rho(i),j)).

If the induced involution has (p) transpositions and (f) fixed points ((f+2p=m)), the number of ways is (2^{f+p}=2^{m-p}).
The number of involutions on (m) elements with exactly (p) transpositions is (\frac{m!}{(m-2p)!,2^p,p!}).
Therefore [ x_{2m}=x_{2m+1}=y_m,\qquad y_m=\sum_{p=0}^{\lfloor m/2\rfloor} \frac{m!}{(m-2p)!,p!},2^{m-2p}. ]

Solution

The exponential generating function of (y_m) is [ Y(z)=\sum_{m\ge 0}y_m\frac{z^m}{m!} =\sum_{m\ge 0}\sum_{p}\frac{2^{m-2p}}{(m-2p)!,p!},z^m =e^{2z}\cdot e^{z^2}=e^{2z+z^2}. ]

We need the asymptotic behaviour of (y_m) as (m\to\infty). By Cauchy's formula, [ y_m=m!,[z^m]e^{2z+z^2}=\frac{m!}{2\pi i}\oint e^{\phi(z)},dz, \quad\phi(z)=2z+z^2-(m+1)\log z. ]

The saddle point (z_0) satisfies (\phi'(z_0)=0): [ 2+2z_0-\frac{m+1}{z_0}=0;\Longrightarrow;2z_0^2+2z_0=m+1 ;\Longrightarrow; z_0=\sqrt{\frac{m}{2}+\frac{3}{4}}-\frac12. ] Set (u=z_0+\frac12=\sqrt{m/2+3/4}). Then (m=2u^2-\frac32) and [ \phi(z_0)=2z_0+z_0^2-(m+1)\log z_0 =u^2+u-\frac34-\Bigl(2u^2-\frac12\Bigr)\log\Bigl(u-\frac12\Bigr), ] [ \phi''(z_0)=2+\frac{m+1}{z_0^2}=4+\frac{2}{z_0}=\frac{4u}{u-\frac12}. ]

The standard saddle‑point approximation gives [ [z^m]e^{2z+z^2}\sim \frac{\exp!\bigl(\phi(z_0)\bigr)}{\sqrt{2\pi,\phi''(z_0)}}, \qquad y_m\sim m!,\frac{\exp!\bigl(\phi(z_0)\bigr)}{\sqrt{2\pi,\phi''(z_0)}}. ]

Inserting Stirling’s formula (m!\sim\sqrt{2\pi m},(m/e)^m) and expanding everything in powers of (1/u) (equivalently (1/\sqrt{m})) yields [ \log y_m = \frac{m}{2}\log m+\frac{m}{2}\log 2-\frac{m}{2}+\sqrt{2m} -\frac12\log 2-\frac12+O\Bigl(\frac{1}{\sqrt{m}}\Bigr). ]

Exponentiating, [ y_m\sim\frac{1}{\sqrt{2e}},(2m)^{m/2},e^{-m/2},e^{\sqrt{2m}}. ]

Finally we return to the original variable (n). Since (x_n=y_{\lfloor n/2\rfloor}),

  • If (n=2m) is even, [ x_n\sim\frac{1}{\sqrt{2e}},(2m)^{m/2},e^{-m/2},e^{\sqrt{2m}} =\frac{1}{\sqrt{2e}}\left(\frac{n}{e}\right)^{n/4}e^{\sqrt{n}}. ]
  • If (n=2m+1) is odd, (x_n=x_{n-1}) and [ x_n\sim\frac{1}{\sqrt{2e}}\left(\frac{n-1}{e}\right)^{(n-1)/4}e^{\sqrt{n-1}}. ]

Both cases are captured by [ x_n\sim\frac{1}{\sqrt{2e}}, \bigl(2\lfloor n/2\rfloor\bigr)^{\lfloor n/2\rfloor/2}, e^{-\lfloor n/2\rfloor/2}, e^{\sqrt{2\lfloor n/2\rfloor}}. ]

Verification

For small (n) the formula gives (x_1=1,;x_2=2,;x_3=2,;x_4=6,;x_5=6,;x_6=20,;x_7=20,;x_8=76), matching the known sequence A047974 (symmetric permutations).
The saddle‑point derivation was carried out twice - once by expanding (\log y_m) in powers of (1/\sqrt{m}) and once by rewriting everything exactly in terms of (u=\sqrt{m/2+3/4}) and then expanding - yielding identical results. The constant (1/\sqrt{2e}) is therefore confirmed.

This completes the proof. ∎

Final Answer

[ \boxed{ \begin{aligned} &\text{For even } n=2m:\quad x_n \sim \frac{1}{\sqrt{2e}}, \left(\frac{n}{e}\right)^{n/4}, e^{\sqrt{n}},.\[4pt] &\text{For odd } n=2m+1:\quad x_n \sim \frac{1}{\sqrt{2e}}, \left(\frac{n-1}{e}\right)^{(n-1)/4}, e^{\sqrt{n-1}},. \end{aligned} } ]