REFINED ASYMPTOTICS AND EXPLICIT RECURRENCES FOR THE NUMBERS OF YOUNG TABLEAUX IN THE (k, l) HOOK FOR k + l ≤ 5

SHALOSH B. EKHAD AND AMITAI REGEV

The Input: the Sequences S_{k,l}^{(z)}(n)

Recall that a Young Shape (alias Ferrers diagram) λ = (λ_{1}, λ_{2}, …) is an arrangement of leftjustified rows of boxes, with λ_{1} boxes in the first row, λ_{2} boxes in the second row, etc. If the total number of boxes is n, we write λ ⊢ n. The set of shapes λ with n cells with the property that λ_{k+1} ≤ l is denoted by H(k, l; n). Recall also that a Standard Young Tableau (SYT) of shape λ ⊢ n is any way of placing the integers from 1 to n inside the n boxes in such a way that all rows and all columns are increasing. There is a well-known, explicit, formula for f^{λ}, the number of SYTs of a given shape λ, due to Young and Frobenius, as well as a more elegant reformulation, called the hook-length formula, due to Frame, Robinson, and Thrall. In [2], Regev and Berele studied the sequences

S_{k,l}^{(z)}(n) = ∑_{λ∈H(k,l;n)}(f^{λ})^{z} ,

and obtained explicit leading asymptotics for general (k, l) as well as general (real) z. Except for (k, l) ∈ {(1, 0), (2, 0), (4, 0), (1, 1)} (when z = 1) and (k, l) ∈ {(1, 0), (2, 0), (1, 1), (∞, ∞)} (for z = 2), there are no known “nice” expressions for S_{k,l}^{(z)}(n) in terms of n. Of course, using the Young-Frobenius formula one can always express it as a multi-sum of hypergeometric terms, but, in general with k + l − 1 sigma signs. The next best thing to a closed-form formula is a linear recurrence. It follows from the Fundamental Theorem of Wilf-Zeilberger theory ([3]) that for any specific (k, l) and positive integer z, the sequence A(n) = S_{k,l}^{(z)}(n) is holonomic (alias P -recursive), in other words it satisfies a (homogeneous) linear recurrence equation with polynomial coefficients. This means that there exists a positive integer L, and polynomials p_{0}(n), …, p_{L}(n) such that

∑_{i=0}^{L} p_{i}(n)A(n + i) = 0 , n ≥ 0 .

Furthermore there exist algorithms for computing these recurrences, but they are rather slow for multi-sums. Since we know a priori that such a recurrence exists, we may just as well find it empirically by asking the computer to compute the first 60 (or whatever) terms and then guess the recurrence by undetermined coefficients. This is done by the command listtorec in Bruno Salvy and Paul Zimmermann’s Maple package gfun (but we prefer to have our own version). While there is a “theoretical” possibility that the guessed recurrence is not the “right” one, this is very unlikely, and besides, using the recurrence one can extend the sequence very fast, and check whether the continuation matches, and if it does (say for the next 20 terms), then this is a semi-rigorous proof, good enough for us. We know that we have the option to find a fully rigorous proof by the multivariable Zeilberger algorithm [1] (that alas, will take much longer, and for larger (k, l) may not terminate in a reasonable amount of time) but why bother?.

Date: July 30, 2010.

The beauty of knowing a linear recurrence is that one can use the Poincaré-Birkhoff-Trjitzinsky method to derive higher-order asymptotics for the sequence. This method, described in [4], is fully implemented in Doron Zeilberger’s Maple package

http://www.math.rutgers.edu/~zeilberg/tokhniot/AsyRec .

The drawback of that method is that it does not output the constant factor, that must be determined empirically, in general. Luckily, thanks to [2], we know that constant exactly (expressed in terms of π), and this enables the computation of very refined asymptotics of the sequences S_{k,l}^{(z)}(n) for the most interesting cases z = 1 and z = 2, and for k + l ≤ 5.

The Output: Recurrences and asymptotics for S_{k,l}^{(1)}(n) and S_{k,l}^{(2)}(n) for k + l ≤ 5

All the necessary algorithms have been implemented in the self-contained Maple package HOOKER, kindly written by Doron Zeilberger, and available from

http://www.math.rutgers.edu/~zeilberg/tokhniot/HOOKER .

Detailed output files, with lots of terms in the sequences, and asymptotics to order 10, can be viewed in the webpage of this article:

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/hooker.html .

Here we only list (for the record) the output for (k, l) ∈ {(2, 1), (2, 2)} and z = 1, 2, and even for these, we only list the first few terms, the annihilating operator and the refined asymptotics to order 3. Below N denotes the shift-operator in n, so, for example, the annihilating operator for the Fibonacci sequence is N^{2} − N − 1 and for n! is N − n − 1. (k, l) = (2, 1), z = 1

1, 2, 4, 10, 26, 71, 197, 554, 1570, 4477, 12827, 36895, 106471, 308114, 893804, 2598314, 7567466, 22076405,

64498427, 188689685

3 \frac{n + 2}{n + 3} − \frac{n (n + 2) N}{(n + 3) (n + 1)} − \frac{(9 + 11 n + 3 n^{2}) N^{2}}{(n + 3) (n + 1)} + N^{3}

1/4 3^{n}\sqrt{n^{−1}} (1 − 3/16 n^{−1} + \frac{1}{512} n^{−2} + \frac{135}{8192} n^{−3}) \sqrt{3}\frac{1}{\sqrt{π}}

(k, l) = (2, 1), z = 2

1, 2, 6, 24, 120, 695, 4403, 29540, 206244, 1483371, 10919271, 81896661, 623810421,
4813777566, 37561178658, 295907998908, 2350767037116

−9 \begin{matrix}(n + 2) & 2 \\ (n + 3) & 2 \end{matrix} + \frac{(19 n^{2} + 40 n + 18) (n + 2)^{2} N}{(n + 3)^{2} (n + 1)^{2}}

−\frac{(45 + 148 n + 159 n^{2} + 70 n^{3} + 11 n^{4}) N^{2}}{(n + 3)^{2} (n + 1)^{2}} + N^{3}

\frac{9}{128} 9^{n} (1 + 3/4 n^{−1} + \frac{53}{32} n^{−2} + \frac{261}{64} n^{−3}) \sqrt{3}n^{−2}π^{−1}

(k, l) = (2, 2), z = 1

1, 2, 4, 10, 26, 76, 232, 764, 2578, 9076, 32264, 117448, 428936, 1589680, 5897504, 22101304, 82851218,

312935236, 1182083272, 4491680504, 17067914056, 65167445872

REFINED ASYMPTOTICS AND EXPLICIT RECURRENCES FOR THE NUMBERS OF YOUNG TABLEAUX IN THE (k, l) HOOK FOR k+l ≤ 5 3

128 \frac{n (n − 1)}{(n + 5) (n + 4)} − 32 \frac{(−1 + 4 n + 6 n^{2}) N}{(n + 5) (n + 4)} +

8 \frac{(4 + 21 n + 11 n^{2}) N^{2}}{(n + 5) (n + 4)} − 4 \frac{(−24 − 7 n + n^{2}) N^{3}}{(n + 5) (n + 4)} − 2 \frac{(3 n + 10) N^{4}}{n + 4} + N^{5}

1/4 \frac{4^{n}}{π n}

(for more refined asymptotics see the webpage). (k, l) = (2, 2), z = 2

1, 2, 6, 24, 120, 720, 5040, 40320, 361116, 3540600, 37207368, 411988896, 4747167568,
56428884512, 687793860000, 8559142303296, 108400653865572

−512 \frac{(2 n − 1) (n − 1) n}{(n + 5) (n + 4)^{2}} + 16 \frac{(231 n + 711 n^{2} + 164 n^{4} + 588 n^{3} − 2) N}{(n + 5) (n + 1) (n + 4)^{2}}

−16 \frac{(1146 n^{2} + 545 n^{3} + 1003 n + 94 n^{4} + 296) N^{2}}{(n + 5) (n + 1) (n + 4)^{2}} +4 \frac{(2030 n^{2} + 85 n^{4} + 688 n^{3} + 2501 n + 996) N^{3}}{(n + 5) (n + 1) (n + 4)^{2}}

−4 \frac{(87 n^{3} + 8 n^{4} + 525 n + 336 n^{2} + 250) N^{4}}{(n + 5) (n + 1) (n + 4)^{2}} + N^{5}

1/32 16^{n} (n^{−1})^{7/2} (1 + \frac{33}{8} n^{−1} + \frac{2145}{128} n^{−2} + \frac{81723}{1024} n^{−3}) π^{−3/2}

References

[1] M. Apagodu and D. Zeilberger Multi-Variable Zeilberger and Almkvist-Zeilberger Algorithms and the Sharpening of Wilf-Zeilberger Theory , Adv. Appl. Math. 37(2006)(Special Regev issue), 139-152 .

[2] A. Berele and A. Regev Asymptotics of Young Tableaux in the (k, l) hook, to appear in: Contemporary Mathematics v. ???(AMS) (201?), C. Polcino Milies, ed., http://arxiv.org/abs/1007.3833v1 .

[3] H. Wilf and D. Zeilberger An algorithmic proof theory for hypergeometric (ordinary and “q”) multisum/integral identities, Invent. Math. 108 (1992), 575-633.

[4] J. Wimp and D. Zeilberger Resurrecting the asymptotics of linear recurrences, J. Math. Anal. Appl. 111, 162-177 (1985)

Shalosh B. Ekhad c/o Doron Zeilberger, Mathematics Department, Rutgers University (New Brunswick), Piscataway, NJ, USA.

E-mail address: c/o zeilberg@math.rutgers.edu

Amitai Regev, Department of Mathematics, Weizmann Instiute of Science, Rehovot, Israel

E-mail address: amitai.regev@weizmann.ac.il