# Lattice paths in Young diagrams

TK Waring

###### Abstract

Fill each box in a Young diagram with the number of paths from the bottom of
its column to the end of its row, using steps north and east. Then, any square
sub-matrix of this array starting on the south-east boundary has determinant
one. We provide a — to our knowledge — new bijective argument for this result.
Using the same ideas, we prove further identities involving these numbers,
which correspond to an integral orthonormal basis of the inner product space
with Gram matrix given by the array in question. This provides an explicit
answer to a question (listed as unsolved111In an addendum [Sta99, p. 584],
Stanley notes that Robin Chapman settled the existence problem stated in the
exercise. This argument doesn’t appear to be available anywhere, and in this
note we provide the required object explicitly.) raised in Exercise 6.27 c) of
Stanley’s Enumerative Combinatorics.

Here we consider a problem raised in Exercises 6.26 and 6.27 of [Sta99, p.
232]. These problems are solved (see [CRS71, §3 Theorem 2], [Rad97] and the
solutions on [Sta99, p. 267]), but here we give a concise bijective proof,
using the Lindström-Gessel-Viennot lemma.

Let $D$ be a Young diagram of a partition $\lambda$, and fill each box
$(i,j)\in D$ (numbering matrix-wise: down then across) with the number of
paths from $(\lambda^{\prime}_{j},j)$ to $(i,\lambda_{i})$, using steps north
and east, and staying within the diagram $D$. That is, $(i,j)$ is filled with
the number of paths from the lowest square in its column to the rightmost
square in its row. Call this number $D_{i,j}$. For example, with
$\lambda=(5,4,3,3)$: centertableaux

$\ytableau 16&7211\\\ 6311\\\ 321\\\ 111$ (1)

Then, the matrix formed by any square sub-array with a 1 in the lower right
has determinant 1. The same array of integers arises in discussions of so-
called ballot sequences [CRS71, §1], and of Young’s lattice of partitions
[Sta75, p. 223]. For instance, from the diagram in eq. 1 we have:

$\det\begin{pmatrix}16&7&2\\\ 6&3&1\\\ 3&2&1\end{pmatrix}=1.$

This result follows directly from the following lemma, due to Lindström-
Gessel-Viennot.

######  Lemma 1.

Let $G$ be a locally finite directed acyclic graph, and
$A=\\{a_{1},\dots,a_{n}\\}$ and $B=\\{b_{1},\dots,b_{n}\\}$ sets of source and
destination vertices, respectively. Write $e(a,b)$ for the number of paths
from $a$ to $b$ in $G$, and define a matrix $M$ by $M_{i,j}=e(a_{i},b_{j})$.
Then,

$\det M=\sum_{P=P_{1},\dots,P_{n}}\operatorname{sgn}(\sigma_{P}),$

where the sum is over the collection of $n$-tuples of vertex-disjoint paths
$(P_{1},\dots,P_{n})$ in $G$, where $\sigma_{P}$ is a permutation of $[n]$,
and $P_{i}$ is a path from $a_{i}$ to $b_{\sigma_{P}(i)}$.

###### Proof.

See [AZ03, Chapter 29]. ∎

To see this, let $G$ be the graph with the boxes of $D$ as vertices, and
directed edges from each box to its northern and eastern neighbours. Given a
square $n\times n$ sub-array as above, let $a_{1},\dots,a_{n}$ be the feet of
the columns of $D$ corresponding to the columns of $M$, and
$b_{1},\dots,b_{n}$ the ends of the rows. Any path system $P$ as above must
have $\sigma_{P}=\operatorname{id}$, as a pair of paths $a_{i}\to b_{j}$ and
$a_{j}\to b_{j}$ must share a vertex. Moreover, there is exactly one vertex-
disjoint tuple $P$ of paths with $\sigma_{p}=\operatorname{id}$. The 1 in the
lower right of $M$ forces the path $a_{n}\to b_{n}$ to be a hook up then
right. This implies the same of the path $a_{n-1}\to b_{n-1}$ and so forth.
The unique collection of paths in our running example is (poorly) rendered in
eq. 2.

$\ytableau\looparrowright&\rightarrow\rightarrow\rightarrow\rightarrow\\\
\uparrow\looparrowright\rightarrow\rightarrow\\\
\uparrow\uparrow\looparrowright\\\ \uparrow\uparrow\uparrow$ (2)

Exercise 6.27 offers an extension, which is also resolved by our method.
Suppose that $D$ is self-conjugate (ie $\lambda=\lambda^{\prime}$), and let
$n$ be the size of the Durfee square of the diagram $D$ — that is, the largest
$n$ such that $\lambda_{n}\geq n$. Let $x_{1},\dots,x_{n}$ be a basis for a
real vector space $V$, and define an inner product on $V$ by

$\langle x_{i},x_{j}\rangle=D_{i,j}.$

We exhibit an integral orthonormal basis for $V$. If
$G_{k}=\det[D_{i,j}]_{k\leq i,j\leq n}$ is the Gram determinant, then, using
Cramer’s rule, the result of applying the Gram-Schmidt process to the vectors
$x_{n},x_{n-1},\dots$ (in that order) is a basis $y_{n},\dots,y_{1}$ of $V$
given by:

$G_{j-1}\cdot y_{j}=\det\begin{pmatrix}x_{j}&\langle
j,j+1\rangle&\dots&\langle j,n\rangle\\\ x_{j+1}&\langle
j+1,j+1\rangle&\dots&\langle j+1,n\rangle\\\ \vdots&\vdots&&\vdots\\\
x_{n}&\langle n,j+1\rangle&\dots&\langle
n,n\rangle\end{pmatrix}=\det\begin{pmatrix}x_{j}&D_{j,j+1}&\dots&D_{j,n}\\\
x_{j+1}&D_{j+1,j+1}&\dots&D_{j+1,n}\\\ \vdots&\vdots&&\vdots\\\
x_{n}&D_{n,j+1}&\dots&D_{n,n}\end{pmatrix}$

Observe that the matrix in the formal determinant given here is the
$(n-j+1)\times(n-j+1)$ submatrix of the Durfee square of $D$, with the first
column replaced by $x_{j},\dots,x_{n}$. As such, the above result implies that
the Gram determinant $G_{j-1}=1$, and as such the basis $y_{1},\dots,y_{n}$ is
integral. The norm of $y_{j}$ is $G_{j}/G_{j-1}=1$.

Using the above interpretation of determinants in terms of lattice paths, we
can derive the coefficients explicitly. Expanding our expression by cofactors,
we obtain an expression of the form
$y_{j}=\sum_{i=j}^{n}(-1)^{i-j}c_{ij}x_{i}$, with coefficients

$c_{ij}=\det\begin{pmatrix}D_{j,j+1}&\dots&D_{j,n}\\\ \vdots&&\vdots\\\
\widehat{D_{i,j+1}}&\dots&\widehat{D_{i,n}}\\\ \vdots&&\vdots\\\
D_{n,j+1}&\dots&D_{n,n}\end{pmatrix},$

where the hat denotes omitting that row. This is the path matrix from
$a_{j+1},\dots,a_{n}$ to $b_{j},\dots,\widehat{b_{i}},\dots,b_{n}$. For
example, with $j=1$ and $i=2$, using the tableau given above, $c_{ij}$ is the
path determinant of:

$\ydiagram[*(white)]{4,4,2,1}*[*(red)]{4+1,0,2+1}*[*(green)]{0,0,0,1+2}$

First observe that, again, we can restrict ourselves to tuples
$(P_{j},\dots,P_{n})$ with $\sigma_{P}=\operatorname{id}$, for the same reason
as above. Secondly, for any $k>i$, the path $P_{k}$ from $a_{k}\to b_{k}$ is
uniquely determined (indeed, it is the same hook described in the original
problem). For each $k<i$, the path $P_{k}:a_{k+1}\to b_{k}$ is determined by a
number $m_{k}$ so that it has the form:

$(\lambda^{\prime}_{k+1},k+1),\dots,(k+1,k+1),\dots,(k+1,m_{k}),(k,m_{k}),\dots,(k,\lambda_{k}),$

where $k+1\leq m_{k}\leq\lambda_{k}$ In the above example, we have
$m_{k}\in\\{2,3,4\\}$, corresponding to the paths:

$\ydiagram[*(cyan)]{1+4,1+1,1+1,1+1}*{5,4,3,3},\quad\ydiagram[*(cyan)]{2+3,1+2,1+1,1+1}*{5,4,3,3}\quad\text{and}\quad\ydiagram[*(cyan)]{3+2,1+3,1+1,1+1}*{5,4,3,3}$

Since $P_{k}$ cannot intersect $P_{k+1}$, we have $m_{k}<m_{k+1}$, and to
avoid going outside the Young diagram, we must have $m_{k}\leq\lambda_{k+1}$.
In fact, since $\lambda_{k}\geq\lambda_{k+1}$, applying the second requirement
to $m_{i-1}$ is sufficient. Therefore, the sequence $m_{j},\dots,m_{i-1}$ is
uniquely determined by an $(i-j)$-subset of $\\{j+1,\dots,\lambda_{i}\\}$.
Since any such a sequence determines a unique tuple $P_{j},\dots,P_{n}$, we
have:

$c_{ij}=\binom{\lambda_{i}-j}{i-j}.$

Explicitly, this give us the expansion:

$y_{j}=\sum_{i=j}^{n}(-1)^{i-j}\binom{\lambda_{i}-j}{i-j}x_{i}.$

In this example, we glossed over the requirement that $\lambda$ be self-
conjugate, which allows for the interpretation of the above as an inner
product. The argument goes through regardless, demonstrating the following
identity for $i\geq j$:

$\langle
y_{j},x_{i}\rangle=\sum_{k=j}^{n}(-1)^{j-k}D_{ki}\binom{\lambda_{k}-j}{k-j}=\delta_{ij}.$
(3)

Applied to the conjugate, we have:

$\langle
y_{j}^{\prime},x_{i}\rangle=\sum_{k=j}^{n}(-1)^{j-k}D_{ik}\binom{\lambda_{k}^{\prime}-j}{k-j}=\delta_{ij}.$

Combined, these identities determine the values $D_{ij}$ for $1\leq i,j\leq
n$. Cutting off initial rows or columns from the Young diagram $D$, the values
of $D_{ij}$ outside the Durfee square could also be computed.

This result reduces to, and provides a bijective proof of, the special cases
of Exercise 6.27 a) and b). If $\lambda=(2n+1,2n,\dots,2,1)$ then
$D_{ij}=C_{2n+2-i-j}$, and the orthonormal basis $y_{j}$ is:

$y_{j}=\sum_{i=j}^{n+1}(-1)^{i-j}\binom{2n+2-i-j}{i-j}x_{i},$

If we let primes denote the reflection $i^{\prime}=(n+1)-i$, we get $\langle
x_{i^{\prime}},x_{j^{\prime}}\rangle=C_{i^{\prime}+j^{\prime}}$ and,

$y_{j^{\prime}}=\sum_{i^{\prime}=0}^{j^{\prime}}(-1)^{j^{\prime}-i^{\prime}}\binom{i^{\prime}+j^{\prime}}{j^{\prime}-i^{\prime}}x_{i^{\prime}},$

as expected.

As a final example, if $\lambda=(n,n,\dots,n)$ is the partition of $n^{2}$,
then $D_{ij}=\binom{2n-i-j}{n-i}$, and $c_{ij}=\binom{n-j}{i-j}$. The identity
in question is:

$\langle
y_{j},x_{i}\rangle=\sum_{k=j}^{n}(-1)^{j-k}\binom{2n-i-k}{n-i}\binom{n-j}{k-j}=\delta_{ij}.$

Making the substitution $m=n-m$ on the indexes $i,j,k$, and extending the sum
with terms $=0$, this the sum is:

$\sum_{k}(-1)^{k-j}\binom{i+k}{i}\binom{j}{j-k}=\binom{i}{i-j},$ (4)

where we have used the following, which is [Knu97, §1.2.6 eq. 23]:

$\sum_{k}(-1)^{r-k}\binom{r}{k}\binom{s+k}{n}=\binom{s}{n-r}.$

Since we require that $j\geq i$ (opposite to eq. 3 after the substitution made
in eq. 4), this implies the claimed identity.

## References

  * [AZ03] M. Aigner and G. M. Ziegler.  Proofs from the Book.  Springer, 4 edition, 2003.
  * [CRS71] L. Carlitz, D. Roselle, and R. Scoville.  Some remarks on ballot-type sequences of positive integers.  Journal of Combinatorial Theory, Series A, 11(3):258–271, 1971\.
  * [Knu97] D. E. Knuth.  The Art of Computer Programming, Vol. 1: Fundamental Algorithms.  Addison-Wesley, third edition, 1997.
  * [Rad97] C. Radoux.  Nombres de Catalan généralisés.  Bulletin of the Beligan Mathematical Society, 4:289–292, 1997.
  * [Sta75] R. P. Stanley.  The Fibonacci lattice.  The Fibonacci Quarterly, 13(3):215–232, 1975.
  * [Sta99] R. P. Stanley.  Enumerative Combinatorics.  Cambridge University Press, 1999.