|
%I #25 Oct 27 2021 09:27:21
%S 1,4,19,69,265,929,3356,11626,41117,142206,499836,1734328,6099193,
%T 21282265,75125770,263906332,936517637,3313246237,11827430209,
%U 42139231729,151339387003,542857007499,1961171657524,7079621540798,25720257983591,93396276789196
%N Number of self-inverse permutations in S_n with longest increasing subsequence of length 4.
%C Also the number of Young tableaux with n cells and 4 rows.
%H Alois P. Heinz, <a href="/A217324/b217324.txt">Table of n, a(n) for n = 4..1000</a>
%F a(n) = A182172(n,4)-A182172(n,3) = A005817(n)-A001006(n).
%e a(4) = 1: 1234.
%e a(5) = 4: 12354, 12435, 13245, 21345.
%e a(6) = 19: 123654, 124365, 125436, 125634, 126453, 132465, 132546, 143256, 145236, 153426, 163452, 213465, 213546, 214356, 321456, 341256, 423156, 523416, 623451.
%p a:= proc(n) option remember; `if`(n<4, 0, `if`(n=4, 1,
%p ((2+n)*(30*n^5+199*n^4-374*n^3-1537*n^2-406*n+408)*a(n-1)
%p -4*(n-1)*(n-2)*(120*n^4+46*n^3-471*n^2+371*n+204)*a(n-3)
%p +(n-1)*(285*n^5-262*n^4-2755*n^3-1520*n^2+820*n-48)*a(n-2)
%p -48*(n-1)*(n-3)*(3*n+7)*(5*n+4)*(n-2)^2*a(n-4))/
%p ((n-4)*(5*n-1)*(3*n+4)*(n+4)*(n+3)*(n+2))))
%p end:
%p seq(a(n), n=4..40);
%t 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}]];
%t 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}]];
%t a[n_] := a[n] = Coefficient[g[n, n, {}], x, 4];
%t Table[Print[n, " ", a[n]]; a[n], {n, 4, 40}]
%t (* or: *)
%t 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}]];
%t a[n_] := CatalanNumber[Quotient[n+1, 2]]*CatalanNumber[Quotient[n+2, 2]] - MotzkinNumber[n];
%t Table[a[n], {n, 4, 40}]
%t (* _Jean-François Alcover_, Oct 27 2021, after _Alois P. Heinz_ in A047884 and second formula *)
%Y Column k=4 of A047884.
%Y Cf. A001006, A005817, A182172.
%K nonn,easy
%O 4,2
%A _Alois P. Heinz_, Sep 30 2012
|
