In this Lecture and the next, we will explore the analogue of Stirling’s formula for a certain generalization of . This generalization is based on the combinatorial interpretation of
as the number of permutations of
, i.e. as the cardinality of the symmetric group
A permutation
is said to have an increasing subsequence of length
at positions
if
If instead
, then we say that
has a decreasing subsequence of length
at these positions.
Definition 1: Given positive integers we define
to be the number of permutations in
that have no decreasing subsequence of length
Exercise 1: Show that if one changes the word “decreasing” to “increasing” in Definition 1, the number stays the same.
For example, in the case we have
for all
corresponding to the fact that the identity permutation is the unique permutation with no decreasing subsequence of length
The case
is non-trivial: computing
means counting permutations in
with no decreasing subsequence of length
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 we have
The sequence
is the sequence of Catalan numbers, and it is ubiquitous in combinatorics.
Exercise 2: Prove Knuth’s theorem.
Apart from the cases there is no simple explicit formula which gives
for all values of
(of course, when
we simply have
). 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 give an
asymptotic approximation to
Exercise 3: Combine Knuth’s theorem and Stirling’s formula to obtain to solve Problem 1 in the case
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 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
a partition of
is a decomposition of
into a sum of natural numbers (the “parts” of the partition) which are less than or equal to
without regard for the order of the summands. For example, the partitions of
are
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 denote the set of partitions of
and set
The set 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
of a given partition
as a row of latex
cells, then the second part
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
is then just containment of diagrams: we define
if and only if
fits inside
(again, it’s probably best if you just look at a picture). From now on, we identify partitions with their Young diagrams.
Let be a Young diagram with
cells. A standard Young tableau of shape
is a walk in Young’s lattice which starts at the diagram
, ends at
and in which each step consists of adding a single cell. One can encode such a walk by writing the numbers
in the cells of
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
is called the dimension of
and denoted
Theorem 2 (RSK correspondence): There is a bijective correspondence between permutations and pairs
of standard Young tableaux of the same shape
This correspondence has the following properties: if
corresponds to
, then
corresponds to
; if
corresponds to
, then the maximal length of a decreasing subsequence in
is the number of rows in the common shape
of
and
and the maximal length of a longest increasing subsequence in
is the number of columns in
For a Young diagram let
denote the number of rows in
. The RSK correspondence gives us the following formula.
Corollary 1: We have
Corollary 1 will play the same role in our asymptotic analysis of that Euler’s integral
played in the asymptotic analysis of Although Corollary 1 gives us a sum representation of
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 and any
we have
Combining Corollary 1 and Theorem 3 gives us a complicated but explicit formula for It is not clear that this is helpful, since even in the case
it seems non-trivial to evaluate this sum to get the Catalan number
(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 using the RSK correspondence in conjunction with Frobenius’ formula. Let
be a permutation with no decreasing subsequence of length
and let
be the pair of standard Young tableaux associated to
by RSK. The diagram
on which both
are built has
cells and at most
rows. Take the tableau
and replace each of its entries
with
so that the entries of this augmented
are the numbers
Now take this augmented
rotate it clockwise through
degrees, and glue it to
(you should probably draw yourself a picture). You are now looking at a standard Young tableaux of shape
where
denotes the rectangular Young diagram with
rows, each of length
This process is clearly reversible (make sure you understand both why and how), and so we have a bijection between permutations in
with no decreasing subsequence of length
and standard Young tableaux of shape
It seems like it shouldn’t be too hard to do the single computation of evaluating
using Frobenius’ formula, and presumably the result of this computation will be
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 the number of permutations in
with no decreasing subsequence of length
is equal to the number of involutions in
whose longest decreasing subsequence has length exactly
and whose longest increasing subsequence has length exactly
Proof: This follows from the first property of RSK, i.e. the one about switching and
(think about it). — Q.E.D.
Now, combining the above trick with the Frobenius formula, we get
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 when with
Indeed, a Young diagram with
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
most diagrams with
cells and at most a fixed number
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.
Exercise 4: Using the Frobenius and Stirling formulas, show that for fixed and
we have
Use this computation to conjecture an asymptotic formula for
2 Comments