Mathacadabra
Home > Discussions > Combinatorics
Note: this page uses MathJax for formatting, so may take a few seconds to load.


Adventures with Generating Functions IV

Note: This is the fourth article of a planned 5-part series.

Fourth Adventure: Rook Paths

How many paths can a Rook take in going from the lower-left corner to the upper-right corner of the $8 \times 8$ chess board? Assume that the Rook moves right or up at each step. One such Rook path is shown in the figure.

Rook Path

Consider Rook paths to any square on the board (with the Rook starting on a1 and moving up or right at every step). We make a table displaying the number of paths. The bottom-left entry is the number of Rook paths from a1 to a1, which is $1$. Each other entry is the sum of all the entries below or to the left of the given entry. The reason is that the Rook's last move must come from one of the squares represented by these entries. For example, the entry corresponding to the d3 square is $4+12+2+5+14=37$. You can fill out the table (by hand!) in a few minutes. The number of Rook paths from a1 to h8 is $470{,}010$. (The dots in the table indicate that we can generalize the problem to arbitrarily large chess boards.) \begin{array}{ccccccccc} \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ 64 & 320 & 1328 & 4864 & 16428 & 52356 & 159645 & 470010 & \ldots\\ 32 & 144 & 560 & 1944 & 6266 & 19149 & 56190 & 159645 & \ldots\\ 16 & 64 & 232 & 760 & 2329 & 6802 & 19149 & 52356 & \ldots\\ 8 & 28 & 94 & 289 & 838 & 2329 & 6266 & 16428 & \ldots\\ 4 & 12 & 37 & 106 & 289 & 760 & 1944 & 4864 & \ldots\\ 2 & 5 & 14 & 37 & 94 & 232 & 560 & 1328 & \ldots\\ 1 & 2 & 5 & 12 & 28 & 64 & 144 & 320 & \ldots\\ 1 & 1 & 2 & 4 & 8 & 16 & 32 & 64 & \ldots \end{array}

Let $a(m,n)$ be the number of Rook paths from $(0,0)$ to $(m,n)$, where $m$ and $n$ are nonnegative integers. The two-variable generating function for the doubly infinite sequence $\{a(m,n)\}$ is \[ \sum_{m=0}^{\infty}\sum_{m=0}^{\infty}a(m,n)s^mt^n=\frac{1}{1-\frac{s}{1-s}-\frac{t}{1-t}}. \] Can you explain why?

Rewriting this rational generating function as \[ \frac{1-s-t+st}{1-2s-2t+3st}, \] a finite-order recurrence formula is apparent: \begin{align*} &a(m,n)=2a(m,n-1)+2a(m-1,n)-3a(m-1,n-1), \quad m\geq 2 \; \mbox{or} \; n\geq 2;\\ &a(0,0)=1, \; a(0,1)=1, \; a(1,0)=1, \; a(1,1)=2. \end{align*} (We assume that $a(m,n)=0$ if either $m$ or $n$ is negative.) Can you explain why this recurrence formula holds by counting Rook paths?

Let $a_n=a(n,n)$, the $n$th element of the diagonal sequence. The sequence is \[ 1, 2, 14, 106, 838, 6802, 56190, 470010, \ldots. \] The sequence is A051708 in the On-Line Encyclopedia of Integer Sequences. We seek to find a formula for $a_n$.

A sequence is called $D$-finite if its generating function satisfies a linear differential equation with finitely many derivatives and polynomial coefficients. Equivalently, the sequence satisfies a linear recurrence relation with polynomial coefficients. Rational generating functions are $D$-finite, and the diagonal sequence of a $D$-finite sequence is $D$-finite. Therefore, the sequence $\{a_n\}$ is $D$-finite. In fact, the generating function is \[ f(x)=\sum_{n=0}^{\infty}a_nx^n=\frac{1}{2}\left(1+\frac{\sqrt{1-x}}{\sqrt{1-9x}}\right). \]

In order to prove this, we make the change of variables $t=x/s$ in the two-variable generating function. Now, to accommodate terms such as $s^5t^7$, we allow arbitrary integer exponents for $s$. (The exponents of $x$ are still nonnegative integers.) Thus, we represent $s^5t^7$ as $s^{-2}x^7$. The diagonal generating function is the coefficient of $s^0$, because no $s$ occurs in it. The generating function becomes \[ \frac{1}{2}\left(1+\frac{(1-x)s}{-2s^2+(3x+1)s-2x}\right). \]

We concentrate on the function \[ \frac{s}{-2s^2+(3x+1)s-2x}=\frac{s}{-2(s-\alpha)(s-\beta)}, \] where \[ \alpha=\frac{3x+1-\sqrt{(1-x)(1-9x)}}{4}, \; \beta=\frac{3x+1+\sqrt{(1-x)(1-9x)}}{4}. \] We put our function into partial fractions form: \[ \frac{1}{2(\beta-\alpha)}\left[\frac{\alpha}{s-\alpha}-\frac{\beta}{s-\beta}\right] =\frac{1}{2(\beta-\alpha)}\left[\frac{\alpha/s}{1-(\alpha/s)}+\frac{1}{1-(s/\beta)}\right]. \]

For $-1/9< x<1/9$, we expand the function in a Laurent series in the annulus $|\alpha|<|s|<|\beta|$, in powers of $\alpha/s$ and $s/\beta$, obtaining \[ \frac{1}{2(\beta-\alpha)}\left[\sum_{n=1}^\infty \left(\frac{\alpha}{s}\right)^n+\sum_{n=0}^\infty\left(\frac{s}{\beta}\right)^n\right]. \] The coefficient of $s^0$ in this expression is \[ \frac{1}{2(\beta-\alpha)}=\frac{1}{\sqrt{(1-x)(1-9x)}}. \] This establishes the generating function for $\{a_n\}$.

By inspection, $f(x)$ satisfies the first-order differential equation (with polynomial coefficients) \[ f'(x)(1-x)(1-9x)=4f(x)-2. \] We can read off a recurrence formula for $\{a_n\}$ by looking at the coefficient of $x^n$ in the above equation: \begin{align*} &a_0 = 1, \, a_1 = 2 \\ &a_n = \frac{(10 n -6) a_{n-1}-(9 n -18) a_{n-2}}{n}, \quad n \geq 2. \end{align*} A combinatorial proof of this recurrence formula was recently found by E. Y. Jin and M. E. Nebel.

How fast does the diagonal sequence $\{a_n\}$ grow? We will find the asymptotic growth rate (as $n \rightarrow \infty$). Remember that $a_n$, for $n \geq 1$, is the coefficient of $x^n$ in the generating function $\frac{1}{2}\sqrt{1-x}/\sqrt{1-9x}$ . We examine the generating function at the singularity $x=1/9$. Let $y=9x$ and $h(y)=\frac{1}{2}\sqrt{1-y/9}=h_0+h_1y+h_2y^2+\cdots$. Then $h_0+h_1+h_2+\cdots=h(1)=\sqrt{2}/3$. Suppose that $(1-y)^{-1/2}=s_0+s_1x+s_2x^2+\cdots$. Then \[ a_n=(h_0s_n+h_1s_{n-1}+\cdots+h_ns_0)9^n \sim h(1)s_n9^n, \] and, using using Stirling's approximation $n!\sim n^ne^{-n}\sqrt{2 \pi n}$, we have \[ s_n =\binom{-1/2}{n}(-1)^n \sim \frac{1}{\sqrt{\pi n}}. \] Therefore \[ a_n \sim \frac{\sqrt{2}}{3} \cdot\frac{9^n}{\sqrt{\pi n}}. \]

It is always pleasant to see $\pi$ appear in a formula unexpectedly.

The next article in the series: Adventures with Generating Functions V: Rook Meanders.