The Number of 1...d-Avoiding Permutations of Length d+r for SYMBOLIC d but Numeric r

By Shalosh B. EKHAD, Nathaniel SHAR, and Doron ZEILBERGER

Dedicated to Ira Martin GESSEL (b. April 9, 1951), on his millionth_{2} birthday

Preface: How many permutations are there of length googol+30 avoiding an increasing subsequence of length googol?

This number is way too big for our physical universe, but the number of permutations of length googol+30 that contain at least one increasing subsequence of length googol is a certain integer that

may be viewed in http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/gessel64.pdf.

Hence the number of permutations of length googol+30 avoiding an increasing subsequence of length googol is (googol + 30)! minus the above small number.

Counting the “Bad Guys”

Recall that thanks to Robinson-Schensted ([Rob][Sc]), the number of permutations of length n that do not contain an increasing subsequence of length d is given by

G_{d}(n) := ∑_{{λ⊢n \atop #rows(λ)<d}} f_{λ}^{2} ,

where λ denotes a typical Young diagram, and f_{λ} is the number of Standard Young tableaux whose shape is λ.

Hence the number of permutations of length n that do contain an increasing subsequence of length d is

B_{d}(n) := ∑_{{λ⊢n \atop #rows(λ)≥d}} f_{λ}^{2} .

Since the total number of permutations of length n is n! ([B]), if we know how to find B_{d}(n), we would know immediately G_{d}(n) = n! − B_{d}(n), at least if we leave n! alone as a factorial, rather than spell it out.

Recall that the Hook Length formula (see [Wiki]) tells you that if λ is a Young diagram then

f_{λ} = \frac{n!}{∏_{c∈λ} h(c)} ,

where the product is over all the n cells of the Young diagram, and the hook-lenght, h(c), of a cell c = (i, j), is (λ_{i} − i) + (λ′_{j} − j) + 1, where λ′ is the conjugate diagram, where the rows become columns and vice-versa.

Let r be a fixed integer, then for symbolic d, valid for d ≥ r − 1, any Young diagram with at least d rows, and with d + r cells, can be written, for some Young diagram μ = (μ_{1}, …, μ_{r}), with ≤ r cells, (where we add zeros to the end if the number of parts of μ is less than r) as

λ = (1 + μ_{1}, …, 1 + μ_{r}, 1^{d−r+r′}) ,

where r′ = r − |μ|. For such a shape λ, with at least d rows,

∏_{c∈λ} h(c) = ( ∏_{c∈μ} h(c) ) · ((d + r′ + μ_{1})(d + r′ − 1 + μ_{2}) ⋯ (d + r′ − r + 1 + μ_{r})) · (d − r + r′)! .

Hence f_{λ}, that is (d+r)! divided by the above, is a certain specific number times a certain polynomial in d. Since, for a specific, numeric, r, there are only finitely many Young diagrams with at most r cells, the computer can find all of them, compute the polynomial corresponding to each of them, square it, and add-up all these terms, getting an explicit polynomial expression, in the variable d, for B_{d}(d + r), the number of permutations of length d + r that contain an increasing subsequence of length d. As we said above, from this we can find G_{d}(d + r) = (d + r)! − B_{d}(d + r), valid for symbolic d ≥ r − 1.

B_{d}(d + r) for r from 0 to 30

B_{d}(d) = 1 ,
B_{d}(d + 1) = d^{2} + 1 ,

B_{d}(d + 2) = \frac{1}{2} d^{4} + d^{3} + \frac{1}{2} d^{2} + d + 3 ,

B_{d}(d + 3) = \frac{1}{6} d^{6} + d^{5} + \frac{5}{3} d^{4} + \frac{2}{3} d^{3} + \frac{19}{6} d^{2} + \frac{31}{3} d + 11 ,

B_{d}(d + 4) = \frac{1}{24} d^{8} + \frac{1}{2} d^{7} + \frac{25}{12} d^{6} + \frac{19}{6} d^{5} + \frac{29}{24} d^{4} + 9 d^{3} + \frac{247}{6} d^{2} + \frac{395}{6} d + 47 ,

B_{d}(d+5) = \frac{1}{120} d^{10}+\frac{1}{6} d^{9}+\frac{31}{24} d^{8}+\frac{14}{3} d^{7}+\frac{823}{120} d^{6}+\frac{67}{30} d^{5}+\frac{653}{24} d^{4}+\frac{959}{6} d^{3}+\frac{10459}{30} d^{2}+\frac{3981}{10} d+239 .

For B_{d}(d + r) for r from 6 up to 30, see

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

Sequences

The sequence G_{3}(n) is the greatest celeb in the kingdom of combinatorial sequences [the subject of an entire book([St]) by Ira Gessel’s illustrious academic father, Richard Stanley], the superfamous A000108 in Neil Sloane’s legendary database ([Sl]). G_{4}(n), while not in the same league as the Catalan sequence, is still moderately famous, A005802. G_{5}(n) is A047889, G_{6}(n) is A047890, G_{7}(n) is A052399 , G_{8}(n) is A072131, G_{9}(n) is A072132, G_{10}(n) is A072133, G_{11}(n) is A072167, but G_{d}(n) for d ≥ 12 are absent (for a good reason, one must stop somewhere!). Also the flattened version of the double-sequence, {G_{d}(n)}, for 1 ≤ d ≤ n ≤ 45 is A047887. Using the polynomials B_{d}(d + r), we computed the first 2d + 1 terms of G_{d}(n) for d ≤ 30. See

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

But this method can only go up to 2d + 1 terms of the sequence G_{d}(n), and of course, the first d − 1 terms are trivial, namely n!. Can we find the first 100 terms (or whatever) for the sequences G_{d}(n) for d up to 20, and beyond, efficiently?

Encore: Efficient Computer-Algebra Implementation of Ira Gessel’s AMAZING Determinant Formula

Recall Ira Gessel’s [G] famous expression for the generating function of G_{d}(n)/n!^{2}, canonized in the bible ([W], p. 996, Eq. (5)). Here it is:

∑_{n≥0} \frac{G_{d}(n)}{n!^{2}} x^{2n} = det(I_{|i−j|}(2x))_{i,j=1,...,d} ,

in which I_{ν}(t) is (the modified Bessel function)

I_{ν}(t) = ∑_{j=0}^{∞} \frac{(\frac{1}{2} t)^{2j+ν}}{j!(j + ν)!} .

Can we use this to compute the first 100 terms of, say, G_{20}(n)?

While computing numerical determinants is very fast, computing symbolic ones is a different story. First, do not get scared by the “infinite” power series. If we are only interested in the first N terms of G_{d}(n), then it is safe to truncate the series up to t^{2N}, and take the determinant of a d×d matrix with polynomial entries. If you use the vanilla determinant in a computer-algebra system such as Maple, it would be very inefficient, since the degree of the determinant is much larger than 2N. But a little cleverness can make things more efficient. The Maple package Gessel64, available free of charge from

http://www.math.rutgers.edu/~zeilberg/tokhniot/Gessel64 ,

accompanying this article, has a procedure SeqIra(k,N) that computes the first N terms of G_{k}(n), using a division-free algorithm (see [Rot]) over an appropriate ring to compute the determinant in Gessel’s famous formula.

SeqIra:=proc(k,N) local ira,t,i,j, R:
  R := table():
  R[`0`] := 0:
  R[`1`] := 1:
  R[`+`] := `+`:

  R[`-`] := `-`:
  R[`*`] := proc(p, q): return add(coeff(p*q, t, i)*t**i, i=0..2*N): end:
  R[`=`] := proc(p, q): return evalb(p = q): end:
  ira:=expand(LinearAlgebra[Generic][Determinant][R](Matrix([seq([seq(Iv(abs(i-j),t,2*N),
                                                                        j=1..k-1)],
                                                                   i=1..k-1)]))):
  [seq(coeff(ira,t,2*i)*i!**2,i=1..N)]:
end:

In the above code, procedure Iv(v,t,N) computes the truncated modified Bessel function that shows up in Gessel’s determinant, and it is short enough to reproduce here:

Iv:=proc(v,t,N) local j:  add(t**(2*j+v)/j!/(j+v)!,j=0..trunc((N-v)/2)+1):  end:  .

Using this procedure, the first-named author computed (in 4507 seconds) the first 100 terms of each of the sequences G_{d}(n) for 3 ≤ d ≤ 20, and could have gone much further.

See http://www.math.rutgers.edu/~zeilberg/tokhniot/oGessel64c .

HAPPY 64th BIRTHDAY, IRA! References

[B] Rabbi Levi Ben Gerson, Sefer Maaseh Hoshev, Avignon, 1321.

[G] I. Gessel, Symmetric functions and P-recursiveness, Journal of Combinatorial Theory Series A

53 (1990), 257-285; http://people.brandeis.edu/~gessel/homepage/papers/dfin.pdf .

[Rob] G. de B. Robinson, On the representations of S_{n}, Amer. J. Math. 60 (1938), 745-760.

[Rot] G. Rote, Division-Free Algorithms for the Determinant and Pfaffian: Algebraic and Combinatorial Approaches, Computational Discrete Mathematics: Advanced Lectures (2001), 119-135.

[Sc] C. E. Schensted, Largest increasing and decreasing subsequences, Canad. J. Math 13 (1961), 179-191.

[Sl] N.J.A. Sloane, The On-Line Encyclopedia of Integer Sequences; http://oeis.org .

[St] R. P. Stanley, “Catalan Numbers”, Cambridge University Press, 2015.

[Wiki] The Wikipedia Foundation, Hook Length Formula;

http://en.wikipedia.org/wiki/Hook length formula .

[W] H. S. Wilf, Mathematics, an experimental science, in: “Princeton Companion to Mathematics”, (W. Timothy Gowers, ed.), Princeton University Press, 2008, 991-1000;

http://www.math.rutgers.edu/~zeilberg/akherim/HerbMasterpieceEM.pdf .

Shalosh B. Ekhad, c/o D. Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

Nathaniel Shar, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

nshar at math dot rutgers dot edu ; http://www.math.rutgers.edu/~nbs48/ .

Doron Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

zeilberg at math dot rutgers dot edu ; http://www.math.rutgers.edu/~zeilberg/ .

Published in The Personal Journal of Shalosh B. Ekhad and Doron Zeilberger

( http://www.math.rutgers.edu/~zeilberg/pj.html) and arxiv.org.

April 9, 2015