A217324 Number of self-inverse permutations in S_n with longest increasing subsequence of length 4.

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

Offset: 4

Author

Alois P. Heinz, Sep 30 2012

Keywords

• nonn
• easy

Comments

Also the number of Young tableaux with n cells and 4 rows.

Examples

			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.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 4..1000

Crossrefs

Column k=4 of A047884.

Cf. A001006, A005817, A182172.

Programs

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}]
(* Jean-François Alcover, Oct 27 2021, after Alois P. Heinz in A047884 and second formula *)

Formula

a(n) = A182172(n,4)-A182172(n,3) = A005817(n)-A001006(n).