A214015 -id:A214015 - cp's OEIS frontend

A217677 Number of permutations in S_n containing an increasing subsequence of length 10.

1, 101, 6063, 284431, 11592572, 433386000, 15343169775, 524963196399, 17597634740010, 583499409451862, 19269396089593156, 636977450902768356, 21156201514272916444, 708006643310351350076, 23925259865186482138965, 817728884509460388159381

Offset: 10

Alois P. Heinz, Oct 10 2012

nonn

Alois P. Heinz, Table of n, a(n) for n = 10..200

Cf. A000142, A072133, A214015, A214152.

b:= proc(n) option remember;
      `if`(n<5, n!, ((-1110790863+(1520978576+(1772290401+(607308786+
       (101671498+(9464664+(500874+(14124+165*n)*n)*n)*n)*n)*n)*n)*n)*b(n-1)
       -(1129886062*n+559908333*n^2+111239576*n^3+10655238*n^4+8778*n^6
       +491700*n^5 +353895381)*(n-1)^2*b(n-2) +(258011271+234066216*n
       +58221266*n^2+5463876*n^3 +172810*n^4)*(n-1)^2*(n-2)^2*b(n-3)
       -9*(4070430+1504292*n+117469*n^2)* (n-1)^2*(n-2)^2*(n-3)^2*b(n-4)
       +893025*(n-1)^2*(n-2)^2*(n-3)^2*(n-4)^2*b(n-5)) /
       ((n+20)^2*(n+8)^2*(n+18)^2*(n+14)^2))
    end:
a:= n-> n! -b(n):
seq(a(n), n=10..30);

a(n) = A214152(n,10) = A000142(n)-A072133(n) = A000142(n)-A214015(n,9).

A072167 T_10(n) in the notation of Bergeron et al., u_10(n) in the notation of Gessel: Related to Young tableaux of bounded height.

Original entry on oeis.org

1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916799, 479001478, 6227012074, 87177809092, 1307651456625, 20921799763626, 355647213494682, 6400805686152436, 121585553747301448, 2430677026538811240

Offset: 1

Jesse Carlsson (j.carlsson(AT)physics.unimelb.edu.au), Jun 29 2002

nonn

In general, column k > 1 of A214015 is asymptotic to (Product_{j=1..k} j!) * k^(2*n + k^2/2) / (Pi^((k-1)/2) * 2^((k-1)*(k+2)/2) * n^((k^2-1)/2)). - Vaclav Kotesovec, Sep 10 2014

Vaclav Kotesovec, Table of n, a(n) for n = 1..500
F. Bergeron and F. Gascon, Counting Young tableaux of bounded height, J. Integer Sequences, Vol. 3 (2000), #00.1.7.
Shalosh B. Ekhad, Nathaniel Shar, and Doron Zeilberger, The number of 1...d-avoiding permutations of length d+r for SYMBOLIC d but numeric r, arXiv:1504.02513 [math.CO], 2015.
Ira M. Gessel, Symmetric functions and P-recursiveness, J. Combin. Theory Ser. A 53 (1990), no. 2, 257-285.
Nathaniel Shar, Experimental methods in permutation patterns and bijective proof, PhD Dissertation, Mathematics Department, Rutgers University, May 2016.

Cf. A052399 for T_6(n), A047890 for T_5(n), A047889 for T_4(n).

Column k=10 of A214015.

h:= proc(l) local n; n:=nops(l); add(i, i=l)! / mul(mul(1+l[i]-j
       +add(`if`(l[k]>=j, 1, 0), k=i+1..n), j=1..l[i]), i=1..n)
    end:
g:= proc(n, i, l) option remember;
      `if`(n=0, h(l)^2, `if`(i<1, 0, `if`(i=1, h([l[], 1$n])^2,
       g(n, i-1, l)+ `if`(i>n, 0, g(n-i, i, [l[], i])))))
    end:
a:= n-> g(n, 10, []):
seq(a(n), n=0..25); # Vaclav Kotesovec, Sep 10 2014, after Alois P. Heinz

RecurrenceTable[{-7372800*(-4 + n)^2*(-3 + n)^2*(-2 + n)^2*(-1 + n)^2*(15 + 2*n)*a[-5 + n] + 256*(-3 + n)^2*(-2 + n)^2*(-1 + n)^2*(11018760 + 4743323*n + 577824*n^2 + 21076*n^3)*a[-4 + n]-8*(-2 + n)^2*(-1 + n)^2*(2488711560 + 2208119423*n + 580006399*n^2 + 64938154*n^3 + 3273732*n^4 + 61160*n^5)*a[-3 + n] + 4*(-1 + n)^2*(8002290720 + 21962910556*n + 10433770264*n^2 + 2088552609*n^3 + 215646686*n^4 + 12084237*n^5 + 349536*n^6 + 4092*n^7)*a[-2 + n]-2*(-45705600000 + 64584000000*n + 68412531600*n^2 + 22314826244*n^3 + 3672058745*n^4 + 350428790*n^5 + 20286926*n^6 + 704088*n^7 + 13497*n^8 + 110*n^9)*a[-1 + n] + (9 + n)^2*(16 + n)^2*(21 + n)^2*(24 + n)^2*(25 + n)*a[n]==0,a[1]==1,a[2]==2,a[3]==6,a[4]==24,a[5]==120},a,{n,1,20}] (* Vaclav Kotesovec, Sep 10 2014 *)

a(n) ~ 546852789 * 2^(2*n + 26)* 5^(2*n + 55) / (n^(99/2) * Pi^(9/2)). - Vaclav Kotesovec, Sep 10 2014

Recurrence: (n+9)^2*(n + 16)^2*(n + 21)^2*(n + 24)^2*(n + 25)*a(n) = 2*(110*n^9 + 13497*n^8 + 704088*n^7 + 20286926*n^6 + 350428790*n^5 + 3672058745*n^4 + 22314826244*n^3 + 68412531600*n^2 + 64584000000*n - 45705600000)*a(n-1) - 4*(n-1)^2*(4092*n^7 + 349536*n^6 + 12084237*n^5 + 215646686*n^4 + 2088552609*n^3 + 10433770264*n^2 + 21962910556*n + 8002290720)*a(n-2) + 8*(n-2)^2*(n-1)^2*(61160*n^5 + 3273732*n^4 + 64938154*n^3 + 580006399*n^2 + 2208119423*n + 2488711560)*a(n-3) - 256*(n-3)^2*(n-2)^2*(n-1)^2*(21076*n^3 + 577824*n^2 + 4743323*n + 11018760)*a(n-4) + 7372800*(n-4)^2*(n-3)^2*(n-2)^2*(n-1)^2*(2*n + 15)*a(n-5). - Vaclav Kotesovec, Sep 10 2014

cp's OEIS Frontend

A217677 Number of permutations in S_n containing an increasing subsequence of length 10.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Formula