The computer-aided discovery of a theorem about Young tableaux

Herbert S. Wilf^{1} University of Pennsylvania Philadelphia, PA 19104-6395

                                    wilf@central.cis.upenn.edu

Abstract

Recently [4] a relationship was discovered between the number of permutations of n letters that have no increasing subsequence of length > k, on the one hand, and the number of Young tableaux of n cells whose first row is of length ≤ k, on the other. The proof seemed quite unmotivated and artificial. Here we describe the sequence of events that led to the discovery, via computer algebra, of this relationship.

Here we give an account of how the main result of [4] was found, since in the paper itself there is no clue, but the sequence of events was fairly interesting. The main theorem was essentially discovered by Mathematica, and I only slowly realized exactly what it was that had been discovered. The theorem relates the counting sequences for two difficult combinatorial problems, neither of which has been solved in a very explicit sense, though a great deal is known about them.

The first problem concerns the increasing subsequences of permutations. A permutation σ of n letters has an increasing subsequence of length k if there are positions 1 ≤ i_{1} < i_{2} < ⋯ < i_{k} ≤ n such that σ(i_{1}) < σ(i_{2}) < ⋯ < σ(i_{k}). Thus the permutation

σ = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 5 & 3 & 8 & 7 & 1 & 4 & 2 & 6 \end{matrix} )

has increasing subsequences of length 3, at positions {2, 6, 8} as well as at positions {5, 6, 8} and {5, 7, 8}. Let u_{k}(n) be the number of permutations of n letters that have no increasing subsequence of length > k. Here is a table of values of {u_{k}(n)} for 0 ≤ n ≤ 7, 1 ≤ k ≤ 6.

k=1:  1 1 1 1 1  1  1  1
k=2:  1 1 2 5 14 42 132 429
k=3:  1 1 2 6 23 103 513 2761
k=4:  1 1 2 6 24 119 694 4582
k=5:  1 1 2 6 24 120 719 5003
k=6:  1 1 2 6 24 120 720 5039

The second problem in this story is about Young tableaux. We let y_{k}(n) be the number of standard Young tableaux of n cells, whose first row is of length ≤ k. That is, the partition

1 Supported by the Office of Naval Research of the integer n that underlies the tableau has no part larger than k. Here is a table of values of {y_{k}(n)} for 0 ≤ n ≤ 8, k = 2, 4, 6, 8, 10.

k=2:  1 1 2 3 6 10 20 35 70
k=4:  1 1 2 4 10 25 70 196 588
k=6:  1 1 2 4 10 26 76 231 756
k=8:  1 1 2 4 10 26 76 232 764
k=10:  1 1 2 4 10 26 76 232 764

The generating function for the numbers u_{k}(n) was found by Ira Gessel [1], in 1990. If we write

U_{k}(x) = ∑_{n≥0} u_{k}(n)\frac{x^{2n}}{n!^{2}} ,

then Gessel found that U_{k}(x) has the beautiful determinantal form

U_{k}(x) = det (I_{|i−j|}(2x))_{i,j=1}^{k},

in which the I_{ν} are the modified Bessel functions

I_{ν}(x) = ∑_{r≥0} \frac{(\frac{x}{2})^{ν+2r}}{r!(ν + r)!}.

My own involvement with these matters began simply with a wish to see what these generating functions looked like. I asked Mathematica to put U_{6}(x) on my screen, with the Bessel functions being unevaluated primitives. I regretted that almost immediately, since Mathematica replied with the following:

BesselI(0,2 x)ˆ 6 - 5 BesselI(0,2 x)ˆ 4 BesselI(1,2 x)ˆ 2 + 6 BesselI(0,2 x)ˆ 2 BesselI(1,2 x)ˆ 4 - BesselI(1,2 x)ˆ 6 + 8 BesselI(0,2 x)ˆ 3 BesselI(1,2 x)ˆ 2 BesselI(2,2 x) - 12 BesselI(0,2 x) BesselI(1,2 x)ˆ 4 BesselI(2,2 x)

- 4 BesselI(0,2 x)ˆ 4 BesselI(2,2 x)ˆ 2 + 8 BesselI(1,2 x)ˆ 4 BesselI(2,2 x)ˆ 2 + 4 BesselI(0,2 x)ˆ 2 BesselI(2,2 x)ˆ 4

- 4 BesselI(1,2 x)ˆ 2 BesselI(2,2 x)ˆ 4 - 6 BesselI(0,2 x)ˆ 2 BesselI(1,2 x)ˆ 3 BesselI(3,2 x) + 4 BesselI(1,2 x)ˆ 5 BesselI(3,2 x) + 12 BesselI(0,2 x)ˆ 3 BesselI(1,2 x) BesselI(2,2 x) BesselI(3,2 x) - 14 BesselI(0,2 x)ˆ 2 BesselI(1,2 x) BesselI(2,2 x)ˆ 2 BesselI(3,2 x) - 2 BesselI(1,2 x)ˆ 3 BesselI(2,2 x)ˆ 2 BesselI(3,2 x) - 4 BesselI(0,2 x) BesselI(1,2 x) BesselI(2,2 x)ˆ 3 BesselI(3,2 x) + 4 BesselI(1,2 x) BesselI(2,2 x)ˆ 4 BesselI(3,2 x) - 3 BesselI(0,2 x)ˆ 4 BesselI(3,2 x)ˆ 2 + BesselI(0,2 x)ˆ 2 BesselI(1,2 x)ˆ 2 BesselI(3,2 x)ˆ 2 - 4 BesselI(1,2 x)ˆ 4 BesselI(3,2 x)ˆ 2 + 16 BesselI(0,2 x) BesselI(1,2 x)ˆ 2 BesselI(2,2 x) BesselI(3,2 x)ˆ 2 + 2 BesselI(0,2 x)ˆ 2 BesselI(2,2 x)ˆ 2 BesselI(3,2 x)ˆ 2 + 4 BesselI(0,2 x) BesselI(2,2 x)ˆ 3 BesselI(3,2 x)ˆ 2 - BesselI(2,2 x)ˆ 4 BesselI(3,2 x)ˆ 2 - 2 BesselI(1,2 x)ˆ 3 BesselI(3,2 x)ˆ 3

- 12 BesselI(0,2 x) BesselI(1,2 x) BesselI(2,2 x) BesselI(3,2 x)ˆ 3 - 4 BesselI(1,2 x)BesselI(2,2 x)ˆ 2 BesselI(3,2 x)ˆ 3 + 3 BesselI(0,2 x)ˆ 2 BesselI(3,2 x)ˆ 4 + 4 BesselI(1,2 x)ˆ 2 BesselI(3,2 x)ˆ 4 + 2 BesselI(2,2 x)ˆ 2 BesselI(3,2 x)ˆ 4

- BesselI(3,2 x)ˆ 6 + 4 BesselI(0,2 x) BesselI(1,2 x)ˆ 4 BesselI(4,2 x) - 12 BesselI(0,2 x)ˆ 2 BesselI(1,2 x)ˆ 2 BesselI(2,2 x) BesselI(4,2 x) - 4 BesselI(1,2 x)ˆ 4 BesselI(2,2 x) BesselI(4,2 x) + 4 BesselI(0,2 x)ˆ 3 BesselI(2,2 x)ˆ 2 BesselI(4,2 x) + 16 BesselI(0,2 x) BesselI(1,2 x)ˆ 2 BesselI(2,2 x)ˆ 2 BesselI(4,2 x) - 8 BesselI(0,2 x) BesselI(2,2 x)ˆ 4 BesselI(4,2 x) + 8 BesselI(0,2 x)ˆ 3 BesselI(1,2 x) BesselI(3,2 x) BesselI(4,2 x) - 4 BesselI(0,2 x) BesselI(1,2 x)ˆ 3 BesselI(3,2 x) BesselI(4,2 x)

- 16 BesselI(0,2 x)ˆ 2 BesselI(1,2 x) BesselI(2,2 x) BesselI(3,2 x) BesselI(4,2 x)

- 4 BesselI(1,2 x)ˆ 3 BesselI(2,2 x) BesselI(3,2 x) BesselI(4,2 x) + 8 BesselI(0,2 x) BesselI(1,2 x) BesselI(2,2 x)ˆ 2 BesselI(3,2 x) BesselI(4,2 x) + 4 BesselI(1,2 x) BesselI(2,2 x)ˆ 3 BesselI(3,2 x) BesselI(4,2 x) + 8 BesselI(0,2 x) BesselI(1,2 x)ˆ 2 BesselI(3,2 x)ˆ 2 BesselI(4,2 x)

- 4 BesselI(0,2 x)ˆ 2 BesselI(2,2 x) BesselI(3,2 x)ˆ 2 BesselI(4,2 x) + 8 BesselI(1,2 x)ˆ 2 BesselI(2,2 x) BesselI(3,2 x)ˆ 2 BesselI(4,2 x) + 4 BesselI(0,2 x) BesselI(2,2 x)ˆ 2 BesselI(3,2 x)ˆ 2 BesselI(4,2 x) - 4 BesselI(2,2 x)ˆ 3 BesselI(3,2 x)ˆ 2 BesselI(4,2 x)

- 8 BesselI(0,2 x) BesselI(1,2 x) BesselI(3,2 x)ˆ 3 BesselI(4,2 x) - 4 BesselI(1,2 x) BesselI(2,2 x) BesselI(3,2 x)ˆ 3 BesselI(4,2 x) + 4 BesselI(2,2 x) BesselI(3,2 x)ˆ 4 BesselI(4,2 x) - 2 BesselI(0,2 x)ˆ 4 BesselI(4,2 x)ˆ 2 + 2 BesselI(0,2 x)ˆ 2 BesselI(1,2 x)ˆ 2 BesselI(4,2 x)ˆ 2 + 2 BesselI(1,2 x)ˆ 4 BesselI(4,2 x)ˆ 2 + 4 BesselI(0,2 x)ˆ 2 BesselI(2,2 x)ˆ 2 BesselI(4,2 x)ˆ 2 - 8 BesselI(1,2 x)ˆ 2 BesselI(2,2 x)ˆ 2 BesselI(4,2 x)ˆ 2 + 4 BesselI(2,2 x)ˆ 4 BesselI(4,2 x)ˆ 2 - 4 BesselI(1,2 x)ˆ 3 BesselI(3,2 x) BesselI(4,2 x)ˆ 2 - 2 BesselI(1,2 x) BesselI(2,2 x)ˆ 2 BesselI(3,2 x) BesselI(4,2 x)ˆ 2 + 2 BesselI(0,2 x)ˆ 2 BesselI(3,2 x)ˆ 2 BesselI(4,2 x)ˆ 2 + 4 BesselI(1,2 x)ˆ 2 BesselI(3,2 x)ˆ 2 BesselI(4,2 x)ˆ 2 + 4 BesselI(0,2 x) BesselI(2,2 x) BesselI(3,2 x)ˆ 2 BesselI(4,2 x)ˆ 2 - 4 BesselI(2,2 x)ˆ 2 BesselI(3,2 x)ˆ 2 BesselI(4,2 x)ˆ 2

- 2 BesselI(1,2 x) BesselI(3,2 x)ˆ 3 BesselI(4,2 x)ˆ 2 + 4 BesselI(1,2 x)ˆ 2 BesselI(2,2 x) BesselI(4,2 x)ˆ 3 - 4 BesselI(0,2 x) BesselI(2,2 x)ˆ 2 BesselI(4,2 x)ˆ 3 - 4 BesselI(0,2 x) BesselI(1,2 x) BesselI(3,2 x) BesselI(4,2 x)ˆ 3 + 4 BesselI(1,2 x) BesselI(2,2 x) BesselI(3,2 x) BesselI(4,2 x)ˆ 3 + BesselI(0,2 x)ˆ 2 BesselI(4,2 x)ˆ 4 - BesselI(1,2 x)ˆ 2 BesselI(4,2 x)ˆ 4 - 2 BesselI(1,2 x)ˆ 5 BesselI(5,2 x) + 8 BesselI(0,2 x) BesselI(1,2 x)ˆ 3 BesselI(2,2 x) BesselI(5,2 x)

- 6 BesselI(0,2 x)ˆ 2 BesselI(1,2 x) BesselI(2,2 x)ˆ 2 BesselI(5,2 x) - 6 BesselI(1,2 x)ˆ 3 BesselI(2,2 x)ˆ 2 BesselI(5,2 x) + 4 BesselI(0,2 x) BesselI(1,2 x) BesselI(2,2 x)ˆ 3 BesselI(5,2 x) + 4 BesselI(1,2 x) BesselI(2,2 x)ˆ 4 BesselI(5,2 x)

- 6 BesselI(0,2 x)ˆ 2 BesselI(1,2 x)ˆ 2 BesselI(3,2 x) BesselI(5,2 x) + 6 BesselI(1,2 x)ˆ 4 BesselI(3,2 x) BesselI(5,2 x) + 4 BesselI(0,2 x)ˆ 3 BesselI(2,2 x) BesselI(3,2 x) BesselI(5,2 x) + 4 BesselI(0,2 x) BesselI(1,2 x)ˆ 2 BesselI(2,2 x) BesselI(3,2 x) BesselI(5,2 x)

- 10 BesselI(1,2 x)ˆ 2 BesselI(2,2 x)ˆ 2 BesselI(3,2 x) BesselI(5,2 x) - 4 BesselI(0,2 x) BesselI(2,2 x)ˆ 3 BesselI(3,2 x) BesselI(5,2 x)

- 2 BesselI(2,2 x)ˆ 4 BesselI(3,2 x) BesselI(5,2 x) - 2 BesselI(0,2 x)ˆ 2 BesselI(1,2 x) BesselI(3,2 x)ˆ 2 BesselI(5,2 x)

- 4 BesselI(1,2 x)ˆ 3 BesselI(3,2 x)ˆ 2 BesselI(5,2 x) + 8 BesselI(0,2 x) BesselI(1,2 x) BesselI(2,2 x) BesselI(3,2 x)ˆ 2 BesselI(5,2 x) + 10 BesselI(1,2 x) BesselI(2,2 x)ˆ 2 BesselI(3,2 x)ˆ 2 BesselI(5,2 x) - 2 BesselI(1,2 x)ˆ 2 BesselI(3,2 x)ˆ 3 BesselI(5,2 x)

- 4 BesselI(0,2 x) BesselI(2,2 x) BesselI(3,2 x)ˆ 3 BesselI(5,2 x) - 2 BesselI(2,2 x)ˆ 2 BesselI(3,2 x)ˆ 3 BesselI(5,2 x) + 2 BesselI(1,2 x) BesselI(3,2 x)ˆ 4 BesselI(5,2 x) + 4 BesselI(0,2 x)ˆ 3 BesselI(1,2 x) BesselI(4,2 x) BesselI(5,2 x)

- 8 BesselI(0,2 x) BesselI(1,2 x)ˆ 3 BesselI(4,2 x) BesselI(5,2 x)

- 4 BesselI(0,2 x)ˆ 2 BesselI(1,2 x) BesselI(2,2 x) BesselI(4,2 x) BesselI(5,2 x) + 12 BesselI(1,2 x)ˆ 3 BesselI(2,2 x) BesselI(4,2 x) BesselI(5,2 x) - 4 BesselI(1,2 x) BesselI(2,2 x)ˆ 3 BesselI(4,2 x) BesselI(5,2 x) + 4 BesselI(0,2 x) BesselI(1,2 x)ˆ 2 BesselI(3,2 x) BesselI(4,2 x) BesselI(5,2 x)

- 4 BesselI(0,2 x)ˆ 2 BesselI(2,2 x) BesselI(3,2 x) BesselI(4,2 x) BesselI(5,2 x)

- 8 BesselI(1,2 x)ˆ 2 BesselI(2,2 x) BesselI(3,2 x) BesselI(4,2 x) BesselI(5,2 x) + 4 BesselI(0,2 x) BesselI(2,2 x)ˆ 2 BesselI(3,2 x) BesselI(4,2 x) BesselI(5,2 x) + 4 BesselI(2,2 x)ˆ 3 BesselI(3,2 x) BesselI(4,2 x) BesselI(5,2 x) + 4 BesselI(0,2 x) BesselI(1,2 x) BesselI(3,2 x)ˆ 2 BesselI(4,2 x) BesselI(5,2 x)

- 4 BesselI(1,2 x) BesselI(2,2 x) BesselI(3,2 x)ˆ 2 BesselI(4,2 x) BesselI(5,2 x) - 2 BesselI(1,2 x)ˆ 3 BesselI(4,2 x)ˆ 2 BesselI(5,2 x) + 4 BesselI(0,2 x) BesselI(1,2 x) BesselI(2,2 x) BesselI(4,2 x)ˆ 2 BesselI(5,2 x)

- 2 BesselI(1,2 x) BesselI(2,2 x)ˆ 2 BesselI(4,2 x)ˆ 2 BesselI(5,2 x) - 2 BesselI(0,2 x)ˆ 2 BesselI(3,2 x) BesselI(4,2 x)ˆ 2 BesselI(5,2 x) + 2 BesselI(1,2 x)ˆ 2 BesselI(3,2 x) BesselI(4,2 x)ˆ 2 BesselI(5,2 x) - BesselI(0,2 x)ˆ 4 BesselI(5,2 x)ˆ 2 + 3 BesselI(0,2 x)ˆ 2 BesselI(1,2 x)ˆ 2 BesselI(5,2 x)ˆ 2 - BesselI(1,2 x)ˆ 4 BesselI(5,2 x)ˆ 2 - 4 BesselI(0,2 x) BesselI(1,2 x)ˆ 2 BesselI(2,2 x) BesselI(5,2 x)ˆ 2 + 2 BesselI(0,2 x)ˆ 2 BesselI(2,2 x)ˆ 2 BesselI(5,2 x)ˆ 2 + 2 BesselI(1,2 x)ˆ 2 BesselI(2,2 x)ˆ 2 BesselI(5,2 x)ˆ 2

- BesselI(2,2 x)ˆ 4 BesselI(5,2 x)ˆ 2 + 2 BesselI(1,2 x)ˆ 3 BesselI(3,2 x) BesselI(5,2 x)ˆ 2

- 4 BesselI(0,2 x) BesselI(1,2 x) BesselI(2,2 x) BesselI(3,2 x) BesselI(5,2 x)ˆ 2 + 2 BesselI(1,2 x) BesselI(2,2 x)ˆ 2 BesselI(3,2 x) BesselI(5,2 x)ˆ 2 + BesselI(0,2 x)ˆ 2 BesselI(3,2 x)ˆ 2 BesselI(5,2 x)ˆ 2

- BesselI(1,2 x)ˆ 2 BesselI(3,2 x)ˆ 2 BesselI(5,2 x)ˆ 2

That seemed somewhat unpromising, but I next asked Mathematica to factor the expression, if possible. It scrolled two screens past me rapidly, and when it came to rest there was a right parenthesis at the end of the expression. Upon tracing back to find the matching left parenthesis, I found it at the middle of the expression. What had happened was that the expression had been factored into two factors of the same size! I do not wish to subject readers here to the actual appearance of the screen at that moment, so instead we will do that with k = 4 instead of k = 6, and we will use conventional mathematical notation for the Bessel functions. In that case one finds that U_{4}(x) is

I_{0}(2 x)^{4} − 3 I_{0}(2 x)^{2} I_{1}(2 x)^{2} + I_{1}(2 x)^{4} + 4 I_{0}(2 x) I_{1}(2 x)^{2} I_{2}(2 x) − 2 I_{0}(2 x)^{2} I_{2}(2 x)^{2}
− 2 I_{1}(2 x)^{2} I_{2}(2 x)^{2} + I_{2}(2 x)^{4} − 2 I_{1}(2 x)^{3} I_{3}(2 x) + 4 I_{0}(2 x) I_{1}(2 x) I_{2}(2 x) I_{3}(2 x)
− 2 I_{1}(2 x) I_{2}(2 x)^{2} I_{3}(2 x) − I_{0}(2 x)^{2} I_{3}(2 x)^{2} + I_{1}(2 x)^{2} I_{3}(2 x)^{2}.

A request to factor the above brings the result

\begin{matrix}(I_{0}(2x)^{2} − I_{0}(2x)I_{1}(2x) − I_{1}(2x)^{2} + 2I_{1}(2x)I_{2}(2x) − I_{2}(2x)^{2} − I_{0}(2x)I_{3}(2x) + I_{1}(2x)I_{3}(2x))× \\ (I_{0}(2x)^{2} + I_{0}(2x)I_{1}(2x) − I_{1}(2x)^{2} − 2I_{1}(2x)I_{2}(2x) − I_{2}(2x)^{2} + I_{0}(2x)I_{3}(2x) + I_{1}(2x)I_{3}(2x)), \end{matrix}

which obviously demands explanation. Further, the explanation that is demanded consists of an analytical reason for the observed factorization of the determinant, and if possible, a combinatorial interpretation also.

First, examination of the factorization above shows that it is of the form (A − B)(A + B), which only deepens the puzzle. Further thought suggests that, while it is possible that the observed factorization depends on specific properties of the Bessel functions that are involved, it is much more likely that it is shared by any determinant of the form

det (a_{|i−j|})_{i,j=1}^{k}  (1)

i.e., by any Toeplitz determinant.

Hence we go back to Mathematica with the Toeplitz determinant (1), with k = 4, and discover that

\begin{aligned}det (a_{|i−j|})_{i,j=1}^{4} & = (a_{0}^{2} − a_{0}a_{1} − a_{1}^{2} + 2a_{1}a_{2} − a_{2}^{2} − a_{0}a_{3} + a_{1}a_{3}) \\ & (a_{0}^{2} + a_{0}a_{1} − a_{1}^{2} − 2a_{1}a_{2} − a_{2}^{2} + a_{0}a_{3} + a_{1}a_{3}) , \end{aligned}

which is again of the form (A−B)(A+B), and the factorization is revealed to be in the province of Toeplitz determinants, rather than of Bessel functions.

Now it does not take long to formulate and prove the following.

Lemma. If a_{0}, a_{1}, … is a given sequence, and a_{−i} = a_{i}, then we have

det (a_{i−j})_{i,j=1}^{2m} = det (a_{i−j} + a_{i+j−1})_{i,j=1}^{m} det (a_{i−j} − a_{i+j−1})_{i,j=1}^{m}.  (2)

Proof. In the determinant on the left, for each i = 1, 2, …, m, add row 2m + 1 − i to row i and leave the result in row i. Then for each j = 1, 2, …, m, subtract column j from column 2m + 1 − j and leave the result in column 2m + 1 − j. The result is a (2m) × (2m) matrix which

when partitioned into m × m blocks looks like ( \begin{matrix}A & 0 \\ B & C \end{matrix} ), where A and C are the two matrices

on the right side of (2) after reflecting A in its antidiagonal.

Hence we have found a factorization of the generating function U_{2k}(x) for permutations that have no increasing subsequence of length > 2k. It looks like this:

U_{2k}(x) = det (I_{|i−j|}(2x))_{i,j=1}^{2k}

= det (I_{|i−j|}(2x) + I_{|i+j−1|}(2x))_{i,j=1}^{k} det (I_{|i−j|}(2x) − I_{|i+j−1|}(2x))_{i,j=1}^{k} (3)

Next we would like to understand the combinatorial meaning, if any, of this factorization. For that purpose the theorem that is needed was already known. It had been obtained twenty years earlier by Basil Gordon [3] by carrying out the reduction of a Pfaffian of Gordon and Houten [2]. His theorem states that

Y_{2k}(x) = det (I_{|i−j|}(2x) + I_{|i+j−1|}(2x))_{i,j=1}^{k},

where Y_{k}(x) = ∑_{n} y_{k}(n)x^{n}/n! is, as above, the usual exponential generating function for Young tableaux whose first row is of length ≤ k. If we compare this with (3), we discover that the relation

U_{2k}(x) = Y_{2k}(x)Y_{2k}(−x) (k = 1, 2, …)

holds between the two generating functions. By matching the coefficients of like powers of x on both sides, we can get the relation between the two counting sequences, which turns out to be

\binom{2n}{n}u_{2k}(n) = ∑_{r} \binom{2n}{r}(−1)^{r}y_{2k}(r)y_{2k}(2n − r)  (n ≥ 0; k ≥ 1).  (4)

No direct combinatorial proof of (4) is known.

References

1. Ira M. Gessel, Symmetric functions and P-recursiveness, J. Combinatorial Theory A, 53 (1990), 257-285.

2. B. Gordon and L. Houten, Notes on plane partitions, II, J. Combinatorial Theory A, 4 (1968), 81-99.

3. B. Gordon, Notes on plane partitions, V, J. Combinatorial Theory B, 11 (1971), 157-168.

4. H. Wilf, Ascending subsequences of permutations and the shapes of tableaux, J. Comb. Theory A, 60 (1992), 155-157.