Math 262A: Lecture 5

In this Lecture and the next, we will explore the analogue of Stirling’s formula for a certain generalization of $N!$ . This generalization is based on the combinatorial interpretation of $N!$ as the number of permutations of $1,\dots,N$ , i.e. as the cardinality of the symmetric group $\mathrm{S}(N).$ A permutation $\pi \in \mathrm{S}(N)$ is said to have an increasing subsequence of length $k$ at positions $1 \leq i_1 < \dots i_k \leq N$ if $\pi(i_1) < \dots \pi(i_k).$ If instead $\pi(i_1) > \dots > \pi(i_k)$ , then we say that $\pi$ has a decreasing subsequence of length $k$ at these positions.

Definition 1: Given positive integers $d,N \in \mathbb{N},$ we define $N!_d$ to be the number of permutations in $\mathrm{S}(N)$ that have no decreasing subsequence of length $d+1.$

Exercise 1: Show that if one changes the word “decreasing” to “increasing” in Definition 1, the number $N!_d$ stays the same.

For example, in the case $d=1,$ we have $N!_1=1$ for all $N\in \mathbb{N},$ corresponding to the fact that the identity permutation is the unique permutation with no decreasing subsequence of length $2.$ The case $d=2$ is non-trivial: computing $N!_2$ means counting permutations in $\mathrm{S}(N)$ with no decreasing subsequence of length $3,$ and the number of these is not immediately obvious. This enumeration problem seems to have been first addressed by Donald Knuth.

Theorem (Knuth): For all $N \in \mathbb{N},$ we have $N!_2 = \frac{1}{N+1}{2N \choose N}.$

The sequence

$\mathrm{Cat}_N = \frac{1}{N+1}{2N \choose N}, \quad N \in \mathbb{N}$

is the sequence of Catalan numbers, and it is ubiquitous in combinatorics.

Exercise 2: Prove Knuth’s theorem.

Apart from the cases $d=1,2,$ there is no simple explicit formula which gives $N!_d$ for all values of $N$ (of course, when $N \leq d,$ we simply have $N!_d=N!$ ). Asymptotic algebraic combinatorics is supposed to deal with cases such as this by supplying useful asymptotic formulas, even when no exact formula is available. The problem we set ourselves is thus to find the analogue of Stirling’s formula for this combinatorial generalization of the factorial:

Problem 1: Given an arbitrary but fixed $d \in \mathbb{N},$ give an $N \to \infty$ asymptotic approximation to $N!_d.$

Exercise 3: Combine Knuth’s theorem and Stirling’s formula to obtain to solve Problem 1 in the case $d=2.$

Problem 1 was first solved by Amitai Regev in this paper, and it uses some surprisingly sophisticated mathematics, namely something called Mehta’s integral. A simpler proof was given thirty years later by yours truly in this paper, and this is the argument we will present. The starting point of both arguments is the same, namely a certain bijection called the Robinson-Schensted-Knuth correspondence.

The RSK correspondence is a bijection between $\mathrm{S}(N)$ and pairs of standard Young tableaux of the same shape. Young diagrams and Young tableaux are objects of fundamental importance in algebraic combinatorics. Given a natural number $N,$ a partition of $N$ is a decomposition of $N$ into a sum of natural numbers (the “parts” of the partition) which are less than or equal to $N,$ without regard for the order of the summands. For example, the partitions of $N=3$ are

$3,\ 2+1,\ 1+1+1.$

Notice that ignoring the order of the summands is the same thing as picking a particular order. There are two canonical choices: write the parts in weakly decreasing order as above (English convention), or in weakly increasing order (French convention). We are using the English convention.

Let $\mathbf{Y}(N)$ denote the set of partitions of $N,$ and set

$\mathbf{Y} = \bigsqcup_{N =1}^\infty \mathbf{Y}(N).$

The set $\mathbf{Y}$ is called Young’s lattice, because it carries a partial order introduced by Alfred Young which makes it into a lattice. This partial order emerges when we graphically encode partitions as Young diagrams: this means that we write the first part $\lambda_1$ of a given partition $\lambda$ as a row of latex $\lambda_1$ cells, then the second part $\lambda_2$ as a second row of cells under the first row, etc. (it’s probably best if you just look at a picture). The partial order on $\mathbf{Y}$ is then just containment of diagrams: we define $\mu \leq \lambda$ if and only if $\mu$ fits inside $\lambda$ (again, it’s probably best if you just look at a picture). From now on, we identify partitions with their Young diagrams.

Let $\lambda \in \mathbf{Y}(N)$ be a Young diagram with $N$ cells. A standard Young tableau of shape $\lambda$ is a walk in Young’s lattice which starts at the diagram $\Box$ , ends at $\lambda,$ and in which each step consists of adding a single cell. One can encode such a walk by writing the numbers $1,\dots,N$ in the cells of $\lambda$ corresponding to the order in which they were added; by construction, in any such filling the numbers will be increasing along rows and columns (again, best to just look at a picture). The number of standard Young tableau of shape $\lambda$ is called the dimension of $\lambda$ and denoted $\dim \lambda.$

Theorem 2 (RSK correspondence): There is a bijective correspondence between permutations $\pi \in \mathrm{S}(N)$ and pairs $(P,Q)$ of standard Young tableaux of the same shape $\lambda \in \mathbf{Y}(N).$ This correspondence has the following properties: if $\pi$ corresponds to $(P,Q)$ , then $\pi^{-1}$ corresponds to $(Q,P)$ ; if $\pi$ corresponds to $(P,Q)$ , then the maximal length of a decreasing subsequence in $\pi$ is the number of rows in the common shape $\lambda$ of $P$ and $Q,$ and the maximal length of a longest increasing subsequence in $\pi$ is the number of columns in $\lambda.$

For a Young diagram $\lambda,$ let $\ell(\lambda)$ denote the number of rows in $\lambda$ . The RSK correspondence gives us the following formula.

Corollary 1: We have

$N!_d = \sum\limits_{\substack{ \lambda \in \mathbf{Y}(N) \\ \ell(\lambda) \leq d}} (\dim \lambda)^2.$

Corollary 1 will play the same role in our asymptotic analysis of $N!_d$ that Euler’s integral

$N! = \int_0^\infty x^N e^{-x} \mathrm{d}x$

played in the asymptotic analysis of $N!.$ Although Corollary 1 gives us a sum representation of $N!_d$ rather than an integral representation, we shall see that this sum may naturally be viewed as a Riemann sum for a certain (multidimensional) integral. This is enabled by the following explicit formula for the dimension of a given Young diagram.

Theorem 3 (Frobenius’ formula): For any $\lambda \in \mathbf{Y}(N)$ and any $m \geq \ell(\lambda),$ we have

$\dim \lambda = \frac{N!}{\prod_{i=1}^m (m-i + \lambda_i)} \prod\limits_{1 \leq i < j \leq m}(\lambda_i - \lambda_j + j-i).$

Combining Corollary 1 and Theorem 3 gives us a complicated but explicit formula for $N!_d.$ It is not clear that this is helpful, since even in the case $d=2$ it seems non-trivial to evaluate this sum to get the Catalan number $\mathrm{Cat}_N$ (try it, or at least try writing down this sum). However, there is another way to look at things: before we start plugging in complicated products and trying to figure out what to do with them, we can step back and consider the symmetries in the problem.

Here is a “symmetry first” approach to obtaining Knuth’s formula for $N!_2$ using the RSK correspondence in conjunction with Frobenius’ formula. Let $\pi \in \mathrm{S}(N)$ be a permutation with no decreasing subsequence of length $3,$ and let $(P,Q)$ be the pair of standard Young tableaux associated to $\pi$ by RSK. The diagram $\lambda \in \mathbf{Y}(N)$ on which both $P,Q$ are built has $N$ cells and at most $2$ rows. Take the tableau $Q,$ and replace each of its entries $i$ with $N+i$ so that the entries of this augmented $Q$ are the numbers $N+1,\dots,2N.$ Now take this augmented $Q,$ rotate it clockwise through $180^\circ$ degrees, and glue it to $P$ (you should probably draw yourself a picture). You are now looking at a standard Young tableaux of shape $R(2,N),$ where $R(a,b)$ denotes the rectangular Young diagram with $a$ rows, each of length $b.$ This process is clearly reversible (make sure you understand both why and how), and so we have a bijection between permutations in $\mathrm{S}(N)$ with no decreasing subsequence of length $3$ and standard Young tableaux of shape $R(2,N).$ It seems like it shouldn’t be too hard to do the single computation of evaluating $\dim R(2,N)$ using Frobenius’ formula, and presumably the result of this computation will be $\mathrm{Cat}_N.$ Before we check this, observe that even before applying the Frobenius formula we have discovered an interesting peculiarity of the universe.

Theorem 4: For any $N \in \mathbb{N},$ the number of permutations in $\mathrm{S}(N)$ with no decreasing subsequence of length $3$ is equal to the number of involutions in $\mathrm{S}(2N)$ whose longest decreasing subsequence has length exactly $2$ and whose longest increasing subsequence has length exactly $N.$

Proof: This follows from the first property of RSK, i.e. the one about switching $P$ and $Q$ (think about it). — Q.E.D.

Now, combining the above trick with the Frobenius formula, we get

$N!_2 = \dim R(2,N) = \frac{(2N)!}{(N-1+2)!(N-2+2)!} (N-N+2-1) = \frac{(2N)!}{(N+1)!N!} = \mathrm{Cat}_N,$

so we’ve recovered Knuth’s theorem in quite an appealing way.

Let’s not get too excited — the above trick is not going to work for evaluating $N!_d$ when with $d > 2.$ Indeed, a Young diagram with $3$ rows need not be self-complementary, in that one can’t necessarily glue it to a rotated copy of the same diagram to get a rectangle (draw yourself a counterexample). But perhaps this is true most of the time — that is, maybe for large $N$ most diagrams with $N$ cells and at most a fixed number $d$ of rows are indeed self-complementary. This sort of thing is very much the spirit of asymptotic algebraic combinatorics, and in fact something along these lines turns out to be true in this case. We’ll see why next lecture.