cp's OEIS Frontend

A047890 Number of permutations in S_n with longest increasing subsequence of length <= 5.

%I A047890 #67 Apr 29 2025 08:12:39
%S A047890 1,1,2,6,24,120,719,5003,39429,344837,3291590,33835114,370531683,
%T A047890 4285711539,51990339068,657723056000,8636422912277,117241501095189,
%U A047890 1639974912709122,23570308719710838,347217077020664880,5231433025400049936,80466744544235325387
%N A047890 Number of permutations in S_n with longest increasing subsequence of length <= 5.
%H A047890 Alois P. Heinz, <a href="/A047890/b047890.txt">Table of n, a(n) for n = 0..735</a>
%H A047890 F. Bergeron and F. Gascon, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL3/CYT/cyt.html">Counting Young tableaux of bounded height</a>, J. Integer Sequences, Vol. 3 (2000), #00.1.7.
%H A047890 Alin Bostan, Andrew Elvey Price, Anthony John Guttmann, Jean-Marie Maillard, <a href="https://arxiv.org/abs/2001.00393">Stieltjes moment sequences for pattern-avoiding permutations</a>, arXiv:2001.00393 [math.CO], 2020.
%H A047890 Shalosh B. Ekhad, Nathaniel Shar, and Doron Zeilberger, <a href="http://arxiv.org/abs/1504.02513">The number of 1...d-avoiding permutations of length d+r for SYMBOLIC d but numeric r</a>, arXiv:1504.02513, 2015.
%H A047890 Ira M. Gessel, <a href="http://dx.doi.org/10.1016/0097-3165(90)90060-A">Symmetric functions and P-recursiveness</a>, J. Combin. Theory Ser. A 53 (1990), no. 2, 257-285.
%H A047890 Permutation Pattern Avoidance Library (PermPAL), <a href="https://permpal.com/perms/name/012345/">012345</a>
%H A047890 Nathaniel Shar, <a href="https://pdfs.semanticscholar.org/98e3/71b675789ed6ec4f9c9cd82e2dee9ca79399.pdf">Experimental methods in permutation patterns and bijective proof</a>, PhD Dissertation, Mathematics Department, Rutgers University, May 2016.
%H A047890 <a href="/index/Y#Young">Index entries for sequences related to Young tableaux.</a>
%F A047890 a(n) ~ 9 * 5^(2*n + 25/2) / (512 * n^12 * Pi^2). - _Vaclav Kotesovec_, Sep 10 2014
%p A047890 h:= proc(l) local n; n:=nops(l); add(i, i=l)! /mul(mul(1+l[i]-j
%p A047890       +add(`if`(l[k]>=j, 1, 0), k=i+1..n), j=1..l[i]), i=1..n)
%p A047890     end:
%p A047890 g:= proc(n, i, l)
%p A047890       `if`(n=0 or i=1, h([l[], 1$n])^2, `if`(i<1, 0,
%p A047890        add(g(n-i*j, i-1, [l[], i$j]), j=0..n/i)))
%p A047890     end:
%p A047890 a:= n-> g(n, 5, []):
%p A047890 seq(a(n), n=0..30);  # _Alois P. Heinz_, Apr 10 2012
%p A047890 # second Maple program
%p A047890 a:= proc(n) option remember; `if`(n<6, n!, ((-375+400*n+843*n^2
%p A047890        +322*n^3+35*n^4)*a(n-1) +225*(n-1)^2*(n-2)^2*a(n-3)
%p A047890        -(259*n^2+622*n+45)*(n-1)^2*a(n-2))/ ((n+6)^2*(n+4)^2))
%p A047890     end:
%p A047890 seq(a(n), n=0..30);  # _Alois P. Heinz_, Sep 26 2012
%t A047890 h[l_] := With[{n = Length[l]}, Sum[i, {i, l}]!/Product[Product[1+l[[i]]-j+Sum[If[l[[k]] >= j, 1, 0], {k, i+1, n}], {j, 1, l[[i]]}], {i, 1, n}]]; g[n_, i_, l_] := If[n == 0 || i == 1, h[Join[l, Array[1&, n]]]^2, If[i<1, 0, Sum[g[n-i*j, i-1, Join[l, Array[i&, j]]], {j, 0, n/i}]]]; a[n_, k_] := If[k >= n, n!, g[n, k, {}]]; Table[a[n, 5], {n, 1, 30}] (* _Jean-François Alcover_, Mar 10 2014, after _Alois P. Heinz_ *)
%Y A047890 A column of A047888. Cf. A005802, A052399.
%Y A047890 Column k=5 of A214015.
%K A047890 nonn,easy
%O A047890 0,3
%A A047890 Eric Rains (rains(AT)caltech.edu), _N. J. A. Sloane_
%E A047890 More terms from _Naohiro Nomoto_, Mar 01 2002
%E A047890 More terms from _Alois P. Heinz_, Apr 10 2012