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,2

Comments

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

Links

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

Formula

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

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

Crossrefs

Column k=4 of A047884.

Cf. A001006, A005817, A182172.

Sequence in context: A100185 A357251 A291888 * A129019 A167247 A267192

Adjacent sequences: A217321 A217322 A217323 * A217325 A217326 A217327

Keyword

nonn,easy

Author

Alois P. Heinz, Sep 30 2012

Status

approved