login
A269021
Number of permutations of [2n] containing an increasing subsequence of length n.
3
1, 2, 23, 588, 24553, 1438112, 108469917, 9996042284, 1086997811325, 136102249609224, 19269396089593156, 3042212958893941456, 529708789768374664407, 100813134967124531098768, 20816198414187782633783462, 4634136282168760818748363080
OFFSET
0,2
LINKS
Alois P. Heinz and Vaclav Kotesovec, Table of n, a(n) for n = 0..41 (terms 0..30 from Alois P. Heinz)
M. Kauers and C. Koutschan, Some D-finite and some possibly D-finite sequences in the OEIS, arXiv:2303.02793 [cs.SC], 2023.
FORMULA
a(n) = A214152(2n,n).
a(n) = (2n)! - A269042(n).
a(n) ~ 16^n * (n-1)! / (Pi * exp(2)). - Vaclav Kotesovec, Mar 27 2016
Conjectured recurrence: -64*(1 + n)^2*(2 + n)^2*(3 + n)*(1 + 2*n)^2*(3 + 2*n)^2*(5 + 2*n)^2*(549760 + 3266000*n + 7264534*n^2 + 8663374*n^3 + 6333869*n^4 + 3012795*n^5 + 952323*n^6 + 198469*n^7 + 26156*n^8 + 1968*n^9 + 64*n^10)*a(n) + 16*(2 + n)^2*(3 + n)*(3 + 2*n)^2*(5 + 2*n)^2*(-5543040 - 487964*n + 78563984*n^2 + 229526554*n^3 + 325846005*n^4 + 284054698*n^5 + 165789363*n^6 + 67385886*n^7 + 19359535*n^8 + 3917758*n^9 + 545913*n^10 + 49788*n^11 + 2672*n^12 + 64*n^13)*a(n+1) - 4*(3 + n)*(5 + 2*n)^2*(-250467360 - 946158512*n - 562569136*n^2 + 3271711596*n^3 + 9313604242*n^4 + 12741784568*n^5 + 11118771121*n^6 + 6753094929*n^7 + 2966908118*n^8 + 959068672*n^9 + 228837227*n^10 + 39928763*n^11 + 4969164*n^12 + 419248*n^13 + 21568*n^14 + 512*n^15)*a(n+2) + 2*(-1300242000 - 6360099840*n - 10812498240*n^2 - 778719870*n^3 + 27672902302*n^4 + 55047935941*n^5 + 60004107039*n^6 + 43766004538*n^7 + 22820793074*n^8 + 8747566435*n^9 + 2488583381*n^10 + 523718876*n^11 + 80260596*n^12 + 8677944*n^13 + 624800*n^14 + 26752*n^15 + 512*n^16)*a(n+3) - 3*(4 + n)*(8 + 3*n)*(10 + 3*n)*(-15900 - 61278*n - 68928*n^2 + 48699*n^3 + 204716*n^4 + 233810*n^5 + 143536*n^6 + 52389*n^7 + 11324*n^8 + 1328*n^9 + 64*n^10)*a(n+4) = 0. - Manuel Kauers and Christoph Koutschan, Mar 01 2023
EXAMPLE
a(1) = 2: 12, 21.
a(2) = 23: all 4! permutations of {1,2,3,4} with the exception of 4321.
MAPLE
h:= proc(l) (n-> 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))(nops(l))
end:
g:= (n, i, l)-> `if`(n=0 or i=1, h([l[], 1$n])^2, `if`(i<1, 0,
add(g(n-i*j, i-1, [l[], i$j]), j=0..n/i))):
a:= n-> `if`(n=0, 1, (2*n)!-g(2*n, n-1, [])):
seq(a(n), n=0..16);
MATHEMATICA
h[l_] := Function[n, Total[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}]][Length[l]];
g[n_, i_, l_] := If[n == 0 || i == 1, h[Join[l, Table[1, {n}]]]^2, If[i < 1, 0, Sum[g[n - i*j, i - 1, Join[l, Table[i, {j}]]], {j, 0, n/i}]]];
a[n_] := If[n == 0, 1, (2n)! - g[2n, n-1, {}]];
Table[a[n], {n, 0, 16}] (* Jean-François Alcover, Apr 01 2017, translated from Maple *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Feb 17 2016
STATUS
approved