%gessel64.tex: The number of 1...d-avoiding permutations of length d+r for SYMBOLIC d but numeric r 
%Plain TeX
%begin macros
\input eplain
\def\L{{\cal L}}
\baselineskip=14pt
\parskip=10pt
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
 0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
 height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\W{{\cal W}}
\def\P{{\cal P}}
\def\Q{{\cal Q}}
\def1円{{\overline{1}}}
\def2円{{\overline{2}}}
\parindent=0pt
\overfullrule=0in
\def\Tilde{\char126\relax}
\def\frac#1#2{{#1 \over #2}}
%\headline={\rm \ifodd\pageno \RightHead \else \LeftHead \fi}
%\def\RightHead{\centerline{
%Title
%}}
%\def\LeftHead{ \centerline{Doron Zeilberger}}
%end macros
\bf
\centerline
{
The Number of 1...d-Avoiding Permutations of Length d+r for SYMBOLIC d but Numeric r 
}
\rm
\bigskip
\centerline
{\it By Shalosh B. EKHAD, Nathaniel SHAR, and Doron ZEILBERGER}
\bigskip
\qquad \qquad 
{\it Dedicated to Ira Martin GESSEL (b. April 9, 1951), on his millionth$_2$ birthday}
\bigskip
{\bf 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 {\it 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 \quad .
Hence the number of permutations of length googol+30ドル$ {\it avoiding} an increasing subsequence of length googol is
$(googol+30)!$ {\it minus} the above small number.
{\bf Counting the ``Bad Guys''}
Recall that thanks to Robinson-Schensted ([Rob][Sc]), the number of permutations of length $n$ that 
do {\bf not} contain an increasing subsequence of length $d$ is given by
$$
G_d(n):=\sum_{ {\lambda \vdash n} \atop {\#rows(\lambda)<d} } f_{\lambda}^2 \quad ,
$$
where $\lambda$ denotes a typical {\it Young diagram}, and $f_\lambda$ is the number of
{\it Standard Young tableaux} whose {\it shape} is $\lambda$.
Hence the number of permutations of length $n$ that {\bf do} contain an increasing subsequence of length $d$ is
$$
B_d(n):=\sum_{ {\lambda \vdash n} \atop {\#rows(\lambda) \geq d} } f_{\lambda}^2 \quad .
$$
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 {\it Hook Length formula} (see [Wiki]) tells you that if $\lambda$ is a Young diagram
then
$$
f_{\lambda}= \frac{n!}{\prod_{c \in \lambda} h(c)} \quad,
$$
where the product is over all the $n$ cells of the Young diagram, and the {\it hook-lenght}, $h(c),ドル of
a cell $c=(i,j),ドル is $(\lambda_i -i)+ (\lambda'_j -j)+1,ドル where $\lambda'$ is the {\it conjugate} diagram, where
the rows become columns and vice-versa.
Let $r$ be a fixed integer, then for {\it symbolic} $d,ドル valid for $d \geq r-1,ドル any
Young diagram with at least $d$ rows, and with $d+r$ cells, can be written, for some Young diagram 
$\mu=(\mu_1, \dots, \mu_r),ドル with $\leq r$ cells,
(where we add zeros to the end if the number of parts of $\mu$ is less than $r$)
as
$$
\lambda=(1+\mu_1, \dots, 1+\mu_r, 1^{d-r+r'} )\quad ,
$$
where $r'=r-&#124;\mu&#124;$. For such a shape $\lambda,ドル with {\it at least} $d$ rows,
$$
\prod_{c \in \lambda} h(c)= \left ( ,円 \prod_{c \in \mu} h(c) ,円 \right ) \cdot ( (d+r'+\mu_1)(d+r'-1+\mu_2) \cdots (d+r'-r+1+\mu_r) ) \cdot (d-r+r')! \quad .
$$
Hence $f_{\lambda},ドル that is $(d+r)!$ divided by the above, is a certain specific number times a certain polynomial in $d$.
Since, for a specific, {\it numeric}, $r,ドル there are only {\it 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 {\it explicit} {\bf polynomial} 
expression, in the variable $d,ドル for $B_d(d+r),ドル the number of permutations of length $d+r$ that {\it 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 {\it symbolic} $d \geq r-1$.
{\bf ${\bf B_d(d+r)}$ for r from 0 to 30}
$$
B_d(d)= 1 \quad ,
$$
$$
B_d(d+1)= {d}^{2}+1 \quad ,
$$
$$
B_d(d+2)= \frac{1}{2} ,円 {d}^{4}+{d}^{3}+ \frac{1}{2},円{d}^{2}+d+3 \quad ,
$$
$$
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 \quad ,
$$
$$
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
\quad ,
$$
$$
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 \quad .
$$
For $B_d(d+r)$ for $r$ from 6ドル$ up to 30ドル,ドル see \hfill\break 
{\tt http://www.math.rutgers.edu/\~{}zeilberg/tokhniot/oGessel64a} .
{\bf Sequences}
The sequence $G_3(n)$ is the greatest {\it celeb} in the kingdom of combinatorial sequences
[the subject of an entire book([St]) by Ira Gessel's 
illustrious {\it academic father}, Richard Stanley],
the super-famous {\bf 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,
{\bf A005802}. $G_5(n)$ is {\bf A047889}, 
$G_6(n)$ is {\bf A047890},
$G_7(n)$ is {\bf A052399 },
$G_8(n)$ is {\bf A072131},
$G_9(n)$ is {\bf A072132},
$G_{10}(n)$ is {\bf A072133},
$G_{11}(n)$ is {\bf A072167},
but $G_d(n)$ for $d \geq 12$ are absent (for a good reason, one must stop somewhere!).
Also the {\it flattened version} of the 
{\it double-sequence}, $\{G_{d}(n)\},ドル for 1ドル \leq d \leq n \leq 45$ is {\bf A047887}.
Using the polynomials $B_d(d+r),ドル 
we computed the first 2ドルd+1$ terms of $G_d(n)$ for $d \leq 30$. See \hfill\break 
{\tt http://www.math.rutgers.edu/\~{}zeilberg/tokhniot/oGessel64b} .
But this method can only go up to 2ドルd+1$ terms of the sequence $G_d(n),ドル and of course, the first
$d-1$ terms are trivial, namely $d!$ (and the $d$-th term is $d!-1$). 
Can we find the first 100ドル$ terms (or whatever) for the sequences
$G_d(n)$ for $d$ up to 20ドル,ドル and beyond, {\bf efficiently?}
{\bf 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,ドル {\it canonized} in the {\it bible} ([W], p. 996, Eq. (5)).
Here it is: 
$$
\sum_{n \geq 0} \frac{G_d(n)}{n!^2} ,円 x^{2n} = ,円 \det (I_{&#124;i-j&#124;}(2x))_{i,j=1, \dots, d} \quad ,
$$
in which $I_{\nu}(t)$ is (the modified Bessel function)
$$
I_\nu (t) = \sum_{j=0}^{\infty} \frac{ (\frac{1}{2} ,円 t)^{2j+\nu}} {j!(j+\nu)!} \quad .
$$
Can we use this to compute the first 100ドル$ terms of, say, $G_{20}(n)$?
While computing {\it numerical} determinants is very fast, computing {\it 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 \times d$
matrix with {\it polynomial entries}. If you use the {\it 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 2ドルN$. But a little cleverness can make things more efficient. The Maple package
{\tt Gessel64}, available free of charge from
{\tt http://www.math.rutgers.edu/\~{}zeilberg/tokhniot/Gessel64} \quad ,
accompanying this article, has a procedure {\tt 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.
\verbatim
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:
&#124;endverbatim
In the above code, procedure {\tt 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:
{\tt Iv:=proc(v,t,N) local j: add(t**(2*j+v)/j!/(j+v)!,j=0..trunc((N-v)/2)+1): end: } \quad .
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ドル \leq d \leq 20,ドル and could have gone much further.
See {\tt http://www.math.rutgers.edu/\~{}zeilberg/tokhniot/oGessel64c} \quad .
{\bf HAPPY 64th BIRTHDAY, IRA!}
{\bf References}
[B] Rabbi Levi Ben Gerson, {\it Sefer Maaseh Hoshev}, Avignon, 1321.
[G] I. Gessel, {\it Symmetric functions and P-recursiveness},
Journal of Combinatorial Theory Series A {\bf 53} (1990), 257-285; \quad 
{\tt http://people.brandeis.edu/\~{}gessel/homepage/papers/dfin.pdf} \quad .
[Rob] G. de B. Robinson, {\it On the representations of $S_n$}, Amer. J. Math. {\bf 60} (1938), 745-760.
[Rot] G. Rote, {\it Division-Free Algorithms for the Determinant and Pfaffian: Algebraic and Combinatorial Approaches}, 
{\it Computational Discrete Mathematics: Advanced Lectures} (2001), 119-135.
[Sc] C. E. Schensted, {\it Largest increasing and decreasing subsequences}, Canad. J. Math {\bf 13} (1961), 179-191.
[Sl] N.J.A. Sloane, {\it The On-Line Encyclopedia of Integer Sequences}; {\tt http://oeis.org} \quad .
[St] R. P. Stanley, {\it ``Catalan Numbers''}, Cambridge University Press, 2015.
[Wiki] The Wikipedia Foundation, {\it Hook Length Formula}; \hfill\break
{\tt http://en.wikipedia.org/wiki/Hook\_length\_formula} \quad .
[W] H. S. Wilf, {\it Mathematics, an experimental science}, in: 
``Princeton Companion to Mathematics'', (W. Timothy Gowers, ed.), Princeton University Press, 2008, 991-1000; \hfill\break
{\tt http://www.math.rutgers.edu/\~{}zeilberg/akherim/HerbMasterpieceEM.pdf} \quad .
\bigskip
\hrule
\bigskip
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.
\bigskip
\hrule
\bigskip
Nathaniel Shar, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen
Rd., Piscataway, NJ 08854-8019, USA. \hfill \break
nshar at math dot rutgers dot edu \quad ; \quad {\tt http://www.math.rutgers.edu/\~{}nbs48/} \quad .
\bigskip
\hrule
\bigskip
Doron Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen
Rd., Piscataway, NJ 08854-8019, USA. \hfill \break
zeilberg at math dot rutgers dot edu \quad ; \quad {\tt http://www.math.rutgers.edu/\~{}zeilberg/} \quad .
\bigskip
\hrule
\bigskip
Published in The Personal Journal of Shalosh B. Ekhad and Doron Zeilberger \hfill \break
{ \tt http://www.math.rutgers.edu/\~{}zeilberg/pj.html} \quad .
\bigskip
\hrule
\bigskip
{\bf April 9, 2015}
\end
</div><div class="naked_ctrl">
<form action="/index.cgi/contrast" method="get" name="gate">
<p><a href="http://altstyle.alfasado.net">AltStyle</a> によって変換されたページ <a href="https://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimTeX/gessel64.tex">(-&gt;オリジナル)</a>
/ <label>アドレス: <input type="text" name="naked_post_url" value="https://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimTeX/gessel64.tex" size="22" /></label> <label>モード: <select name="naked_post_mode">
<option value="default">デフォルト</option>
<option value="speech">音声ブラウザ</option>
<option value="ruby">ルビ付き</option>
<option value="contrast" selected="selected">配色反転</option>
<option value="larger-text">文字拡大</option>
<option value="mobile">モバイル</option>
</select>
<input type="submit" value="表示" />
</p>
</form>
</div>