|
|
A217324
|
|
Number of self-inverse permutations in S_n with longest increasing subsequence of length 4.
|
|
2
|
|
|
1, 4, 19, 69, 265, 929, 3356, 11626, 41117, 142206, 499836, 1734328, 6099193, 21282265, 75125770, 263906332, 936517637, 3313246237, 11827430209, 42139231729, 151339387003, 542857007499, 1961171657524, 7079621540798, 25720257983591, 93396276789196
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
4,2
|
|
COMMENTS
|
Also the number of Young tableaux with n cells and 4 rows.
|
|
LINKS
|
|
|
FORMULA
|
|
|
EXAMPLE
|
a(4) = 1: 1234.
a(5) = 4: 12354, 12435, 13245, 21345.
a(6) = 19: 123654, 124365, 125436, 125634, 126453, 132465, 132546, 143256, 145236, 153426, 163452, 213465, 213546, 214356, 321456, 341256, 423156, 523416, 623451.
|
|
MAPLE
|
a:= proc(n) option remember; `if`(n<4, 0, `if`(n=4, 1,
((2+n)*(30*n^5+199*n^4-374*n^3-1537*n^2-406*n+408)*a(n-1)
-4*(n-1)*(n-2)*(120*n^4+46*n^3-471*n^2+371*n+204)*a(n-3)
+(n-1)*(285*n^5-262*n^4-2755*n^3-1520*n^2+820*n-48)*a(n-2)
-48*(n-1)*(n-3)*(3*n+7)*(5*n+4)*(n-2)^2*a(n-4))/
((n-4)*(5*n-1)*(3*n+4)*(n+4)*(n+3)*(n+2))))
end:
seq(a(n), n=4..40);
|
|
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, Function[p, h[p]*x^If[p == {}, 0, p[[1]]]][Join[l, Array[1&, n]]], Sum[g[n - i*j, i - 1, Join[l, Array[i&, j]]], {j, 0, n/i}]];
a[n_] := a[n] = Coefficient[g[n, n, {}], x, 4];
Table[Print[n, " ", a[n]]; a[n], {n, 4, 40}]
(* or: *)
MotzkinNumber = DifferenceRoot[Function[{y, n}, {(-3n-3)*y[n] + (-2n-5)*y[n+1] + (n+4)*y[n+2] == 0, y[0] == 1, y[1] == 1}]];
a[n_] := CatalanNumber[Quotient[n+1, 2]]*CatalanNumber[Quotient[n+2, 2]] - MotzkinNumber[n];
Table[a[n], {n, 4, 40}]
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|