A267433 Number of permutations of [2n] with longest increasing subsequence of length n.

1, 1, 13, 381, 17557, 1100902, 87116283, 8312317976, 927716186325, 118504614869214, 17044414451764396, 2725298085020712539, 479491040778079234419, 92050364310704637832186, 19146538134094625864605786, 4289203871330156652985437480

Offset

0,3

Links

Alois P. Heinz and Vaclav Kotesovec, Table of n, a(n) for n = 0..74 (terms 0..55 from Alois P. Heinz)

Formula

a(n) = A047874(2n,n) = A126065(2n,n).

a(n) ~ 16^n * (n-1)! / (Pi * exp(2)). - Vaclav Kotesovec, Mar 27 2016

Example

a(2) = 13: 1432, 2143, 2413, 2431, 3142, 3214, 3241, 3412, 3421, 4132, 4213, 4231, 4312.

Maple

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:= (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-> g(n$2, [n]):
seq(a(n), n=0..20);

Mathematica

h[l_] := With[{n = Length[l]}, 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}]];
g[n_, i_, 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_] := g[n, n, {n}];
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Mar 29 2017, translated from Maple *)

Crossrefs

Cf. A047874, A126065, A230341, A267436.

Sequence in context: A279306 A134498 A329554 * A142122 A370379 A302700

Adjacent sequences: A267430 A267431 A267432 * A267434 A267435 A267436

Keyword

nonn

Author

Alois P. Heinz, Jan 15 2016

Status

approved