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

3769987628815905643852921525646105664146833823621994801456991357113502936781270538054719048039675278 0769193354371721350001524610578097700045972792823897290959624203896101981952929640805170129282073883 4740018807571147534091229951249435913149171795302592312477456091277812321956212802204785578598020255 5625008802850838455586257402947256848380647181479993222566420025908679106917004348077812428261510240 6340176300585397517990032393036653951304924586489968650809789292291489270968710994809677050176596751 0725956202350750841376095024046396844968511243494784162014881795337835528626142808150073111101283361 0980701571937952824136796425017224636196853995950587943259043687431653922927840572864396105085190223 2582799067810378389890635196322425667467335158890500820128768331750855469963050322432973194472331947 0989825934469696079344723053679001130033667827524966034661782064851068214182454731365743413486729730 0631055444127725930013792836515384850702346797298406803049230145697433567004811555984158378611125895 0145768901348725550726037527669812626353266837685037397408862767082018239579392663024131792105407280 4788720840618514463465035392103884394981202007834724110094447116613439128758285044269471808502083275 6629374247928521501786839409853287740758570056230853738462527374534709641735458487560816949365616486 0695626913029699922648102091615529949414940648588048836485372758775808743231365617459515329190972398 7074543946415578728439994306071279654045146432379557541358408978156863172980419720839292761025261752 6805876626590163265795592248178664681630980893821587688413815206609216082514983787883386977226071420 21649147728993592578961422177700294482596740993986519357246959930668146505085270714475561150113747221 20887870047753358177316206263356927955729458754686550644432634687680282027976402772772483836117105473 48145611509228154510472000404130614639780926417137329939732465722014680564902839930824306834920414545 13874753600055252092001136814571329384587325582468487887244395295245585419188646792764252832159962029 69411649544372131053235387439446875434698793735121412796400236965732584484687219982898355145980291977 86269234486135973112564250247007239135280355775712267954726019033893771378762777423669196575295174512 96452587669725726144832740371782822308006170531910099265678141483622517144014107716217010098383839968 84507804590244720667406593929564134591547805793634468523934454328906756758701209765471514880572370759 09084331736216302289075177161806402089083889989467334293366576755423738845099552628279269937176915588 59427835870444539800644480052821630922331779937023228656305272974159931977365064817849361860909445301 08120140577436690007140701570599484176861047461052826774744899246746666909264578067076243923453088561 96698778069217767194382941365732112039412879713531991598317675682505439845424625600438225076973116586 49130213308514799728830764637172129004065611907475610401713008790972891409020362658741946509891832165 77016676670060012096109989093803820108650038852207775655317011335432185883307209708526943588264818977 37757381491860736859345865582855966329016368188788860428833268391323270593913089901528577501918097456 34879121424762765606213101234688450096506147759256582735622079237519547939943470930166182921645804027 12542798143388641167614178301190598174793878806944301625322109937912755282207791779022466004479258408 24462949592761349881316543422038699183826473525107075809508274778093413168220963984409028566362293900 40215415882419358649518674355414801095047413826040824566345129789426039221842088797052981439573736696 50223307930886494490895506612422266377009758720488022558779513425100432348926430427665125944987693089 42245751122706284028982754337386885459391626543570555162051612664363788373280457226691660908679569539 27163081562519904030045933274931742332018704568957075002591805894557106029373427199758644919233869688 59038428977769800021296515522194835877177597740437988812991749584835721786755293502620149338987031222 32518225184081589902714463624365018242747599082635817593737724580337688809342550695342366935036425354 91880914435376674876432270204764414065561382212425100253695336680109353578878041405262772638139124792 83216406483941960286265199599663254512526642623538896318838417766536461292705936611493062590853978024 18629266233934211681736693714241352634384615108485320700947811487618744149158225668175169324385259284 55634363409372944818437842421507459176260334046758894630063276039591166623100092626550628336007090706 43413326647797799377122631843882036054772111620148059377505229785356202259250047229187386576746999449 47405347907659143618050579417087497652165460185477043345636632204978226001800424273526341460220242548 683728799179065030083029494514450905531725089967903293290935500874548539339178735194085694882107486318 798833745852508207772876776458002804430766991660626376067637977770235404212193344610052823762990072265 783070820234545141480898874637486106893816774598214664007156038886731975384257202382 .

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-Schenstead ([R][Sc]), the number of permutations of length n that do not contain an increasing sequence of length d is given by

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

where λ denotes a typical Young diagram.

Hence the number of permutations of length n that do contain an increasing sequence 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 c of the Young diagram and h(c) is its hook length. If c = (i, j), then h(c) = (λ_{i} − i) + (λ′_{j} − j) + 1, where λ′ is the conjuagate 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 d + r cells can be written, for some Young diagram μ with ≤ r cells as μ = (μ_{1}, …, μ_{r}) (where we add zeros to the end if the number of parts of μ is less than r)

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

where r′ = r − |μ|. For such a λ, 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 s 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 larger than r − 1.

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

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) = 47 + \frac{1}{24} d^{8} + \frac{1}{2} d^{7} + \frac{395}{6} d + \frac{247}{6} d^{2} + \frac{29}{24} d^{4} + 9 d^{3} + \frac{25}{12} d^{6} + \frac{19}{6} d^{5} ,

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

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 superfamous A000108 in Neil Sloane’s legendary database ([Sl]). G_{4}(n) is also 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 no longer there (for a good reason, enough is enough!). 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 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), 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_{2}0(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 determinants 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 of 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 procdure SeqIra(k,N) that computes the first N terms of G_{k}(n), using the following clever implementation of Gessel’s famous formula

SeqIra:=proc(k,N) local gu,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:
gu:=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(gu,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 .

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

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

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

[Wiki] The Wikipedia Foundation, Hook Length Formula, http://en.wikipedia.org/wiki/Hook length formula [W] H. 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.

March 27, 2015