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
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