Home > Discussions > Combinatorics

Note: this page uses MathJax for formatting, so may take a few seconds to load.

Note: this page uses MathJax for formatting, so may take a few seconds to load.

Adventures with Generating Functions V

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

- The previous article: Adventures with Generating Functions IV: Rook Paths
- The first article: Adventures with Generating Functions I: An Infinite Sum

Fifth Adventure: Rook Meanders

Khang Tran
Recall that a Rook path is a sequence of moves of a chess Rook starting at $(0,0)$ and moving right or up at each step, ending at $(m,n)$, where $m$ and $n$ are nonnegative integers.

A rook meander is a sequence of points in the plane starting at $(0,0)$ and ending at $(m,n)$, where each point $(x,y)$ is a pair of nonnegative integers, and at each step, $x$ changes and $|m-x|$ decreases, or $y$ changes and $|n-y|$ decreases. A rook meander represents a path that a chess Rook may take in moving from $(0,0)$ to $(m,n)$, getting closer to the goal square at each step.

For example, $(0,0)$, $(5,0)$, $(5,1)$, $(3,1)$, $(3,6)$, $(3,4)$ is a Rook meander.

This discussion is a series of exercises about Rook meanders.

**Exercise 1.** Let $a(m,n)$ be the number of Rook meanders from $(0,0)$ to $(m,n)$. It is a good counting problem to obtain the explicit formula
\[
a(m,n)=\left\{
\begin{array}{l}
\sum_{j=1}^m\sum_{k=1}^n\binom{j+k}{j}\binom{m-1}{j-1}\binom{n-1}{k-1}2^{j+k-2},\quad \mbox{for} \; m,n>0\\
3^{m-1}, \quad \mbox{for} \;n=0\\
3^{n-1}, \quad \mbox{for} \;m=0\\
1, \quad \mbox{for} \;m=n=0.
\end{array}
\right.
\]
This produces the following table of values.
\begin{array}{rrrrrr}
1 & 1 & 3 & 9 & 27 & 81\\
1 & 2 & 8 &30 &108 &378 \\
3 & 8 &38 &164 &666 &2592 \\
9 & 30 &164 &794 &3560 &15126 \\
27 & 108 &666 &3560 &17390 &79748 \\
81 & 378 &2592 &15126 &79748 &391538
\end{array}
You may want to check some small values by hand.

We next observe a recurrence relation. Let $a(n)$ be the number of meander paths from $0$ to $n$ for the $1$-dimensional Rook. We will show the recurrence \[ a(n)=2\sum_{k=1}^{n-1}a(k)+a(0) \] by forming two meander paths to $n$ from a meander path to $k$, for $1\le k < n$.

The first path is obtained by shifting the $j$-th cell, where $k+1\le j\le(2k-1),$ to the $(j+2n-2k)$-th cell and adding a final move from $k$ to $n$. Let $i$ be the current location of the Rook in the path to $k$. If $i < k$, the next step to $k$ is $j$, where $i < j < 2k-i$. The corresponding step to $n$ is from $i$ to $j$, where $i < j\le k$ or $2n-k< j< 2n-i$. If $i > k$, we apply the same argument by interchanging $i$ and $2k-i$ in the range for $j$. Since $|n-j| < |n-i|$ in either case, we obtain a path to $n$ whose final step is from $k$ to $n$.

Conversely, suppose we have a path to $n$ whose final step is from $k$ to $n$. Due to the final step, the $j$-th cell, where $k < j \le 2n-k$, will not appear in the path to $n$. Thus we can remove the final step and shift the $(j+2n-2k)$-th cell, $k+1\le j \le (2k-1)$, back to the $j$-th cell to obtain a path to $k$.

The second path is obtained by shifting the $j$-th cell, where $k \le j \le (2k-1)$, to the $(j+2n-2k)$-th cell and adding a final move from $2n-k$ to $n$. With a similar argument, we obtain a path to $n$ whose final step is from $2n-k$ to $n$. When $k=0$, we only obtain the first path since we cannot shift $j=0$ to $j=2n$ in the second construction.

It is straightforward to derive a similar recurrence formula for a higher-dimensional Rook by applying the argument to each dimension. In particular, the recurrence for the $2$-dimensional Rook is \[ a(m,n)=2\sum_{k=1}^{m-1}a(k,n)+2\sum_{k=1}^{n-1}a(m,k)+a(m,0)+a(n,0). \]

**Exercise 2.** Prove that a generating function for the doubly infinite sequence is
\[
\sum_{m=0}^{\infty}\sum_{n=0}^{\infty}a(m,n)x^my^n=\frac{1/4}{1-\frac{2x}{1-x}-\frac{2y}{1-y}}
+\frac{1/6}{1-3x}+\frac{1/6}{1-3y}+\frac{5}{12}.
\]
**Exercise 3.** From this, prove the recurrence formula
\[
a(m,n)=3a(m-1,n)+3a(m,n-1)-5a(m-1,n-1), \mbox{ for $m,n > 1$}.
\]
The diagonal sequence is
\[
\{b(n)\}=\{a(n,n)\}=\{1, 2, 38, 794, 17390, 391538, 8976566,\ldots\}.
\]
**Exercise 4.** Show that the generating function for the diagonal sequence is
\[
\sum_{n=0}^{\infty}b(n)t^n=\frac{5}{6}+\frac{\sqrt{1-t}}{6\sqrt{1-25t}}.
\]
**Exercise 5.** Show that this gives the recurrence formula
\[
b(n) = \frac{(26 n - 14) b(n - 1) - (25 n - 50) b(n - 2)}{n}, \quad n \geq 2, \quad b(0) = 1, \,
b(1) = 2.
\]
**Exercise 6.** Use the generating function to show that the asymptotic growth rate of the diagonal sequence is
\[
b(n) \sim \sqrt{1 - (1/24)} 25^n/(6 \sqrt{\pi n}).
\]