|
%I #30 Mar 07 2023 03:06:50
%S 1,2,23,588,24553,1438112,108469917,9996042284,1086997811325,
%T 136102249609224,19269396089593156,3042212958893941456,
%U 529708789768374664407,100813134967124531098768,20816198414187782633783462,4634136282168760818748363080
%N Number of permutations of [2n] containing an increasing subsequence of length n.
%H Alois P. Heinz and Vaclav Kotesovec, <a href="/A269021/b269021.txt">Table of n, a(n) for n = 0..41</a> (terms 0..30 from Alois P. Heinz)
%H M. Kauers and C. Koutschan, <a href="https://arxiv.org/abs/2303.02793">Some D-finite and some possibly D-finite sequences in the OEIS</a>, arXiv:2303.02793 [cs.SC], 2023.
%F a(n) = A214152(2n,n).
%F a(n) = (2n)! - A269042(n).
%F a(n) ~ 16^n * (n-1)! / (Pi * exp(2)). - _Vaclav Kotesovec_, Mar 27 2016
%F 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
%e a(1) = 2: 12, 21.
%e a(2) = 23: all 4! permutations of {1,2,3,4} with the exception of 4321.
%p h:= proc(l) (n-> add(i, i=l)!/mul(mul(1+l[i]-j+add(`if`(
%p l[k]>=j, 1, 0), k=i+1..n), j=1..l[i]), i=1..n))(nops(l))
%p end:
%p g:= (n, i, l)-> `if`(n=0 or i=1, h([l[], 1$n])^2, `if`(i<1, 0,
%p add(g(n-i*j, i-1, [l[], i$j]), j=0..n/i))):
%p a:= n-> `if`(n=0, 1, (2*n)!-g(2*n, n-1, [])):
%p seq(a(n), n=0..16);
%t 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]];
%t 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}]]];
%t a[n_] := If[n == 0, 1, (2n)! - g[2n, n-1, {}]];
%t Table[a[n], {n, 0, 16}] (* _Jean-François Alcover_, Apr 01 2017, translated from Maple *)
%Y Cf. A010050, A214152, A269042.
%K nonn
%O 0,2
%A _Alois P. Heinz_, Feb 17 2016
|
