A267436 Number of self-inverse permutations of [2n] with longest increasing subsequence of length n.

1, 1, 5, 31, 265, 2446, 26069, 294386, 3628517, 46938514, 645978814, 9265791393, 139408562319, 2174338555026, 35259402634616, 590187761512336, 10209739522685893, 181678453872654154, 3326776921054665350, 62485419303819431072, 1203772979032614462448

Offset

0,3

Comments

Also the number of 2n-length words w over n-ary alphabet {a1,a2,...,an} such that for every prefix z of w we have #(z,a1) >= #(z,a2) >= ... >= #(z,an) >= 1, where #(z,x) counts the letters x in word z. The a(2) = 5 words of length 4 over alphabet {a,b} are: aaab, aaba, abaa, aabb, abab.

Links

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

Formula

a(n) = A047884(2n,n).

Example

a(2) = 5: 1432, 2143, 3214, 3412, 4231.

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]), 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..25);

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_] := If[n == 0 || i == 1, h[Join[l, Table[1, {n}]]], Sum[g[n - i*j, i - 1, Join[l, Table[i, {j}]]], {j, 0, n/i}]];
a[n_] := g[n, n, {n}];
a /@ Range[0, 25] (* Jean-François Alcover, Jan 02 2021, after Alois P. Heinz *)

Crossrefs

Cf. A047884, A267433, A293128.

Sequence in context: A000556 A320512 A125598 * A294215 A294216 A058892

Adjacent sequences: A267433 A267434 A267435 * A267437 A267438 A267439

Keyword

nonn

Author

Alois P. Heinz, Jan 15 2016

Status

approved