cp's OEIS Frontend

A217323 Number of self-inverse permutations in S_n with longest increasing subsequence of length 3.

%I A217323 #22 Oct 27 2021 09:27:05
%S A217323 1,3,11,31,92,253,709,1936,5336,14587,40119,110202,304137,840597,
%T A217323 2332469,6487762,18106906,50667263,142194843,400057791,1128408337,
%U A217323 3190023641,9038202201,25659417876,72987714502,207983161609,593665226069,1697230353691,4859461136196
%N A217323 Number of self-inverse permutations in S_n with longest increasing subsequence of length 3.
%C A217323 Also the number of Young tableaux with n cells and 3 rows.
%H A217323 Alois P. Heinz, <a href="/A217323/b217323.txt">Table of n, a(n) for n = 3..1000</a>
%F A217323 a(n) = A182172(n,3) - A182172(n,2) = A001006(n) - A001405(n).
%e A217323 a(3) = 1: 123.
%e A217323 a(4) = 3: 1243, 1324, 2134.
%e A217323 a(5) = 11: 12543, 13254, 14325, 14523, 15342, 21354, 21435, 32145, 34125, 42315, 52341.
%p A217323 a:= proc(n) option remember; `if`(n<3, 0, `if`(n=3, 1,
%p A217323       ((n+1)*(6*n^3-5*n^2-7*n-24)*a(n-1)
%p A217323        +n*(n-1)*(21*n^2-28*n-109)*a(n-2)
%p A217323        -2*(n-1)*(n-2)*(12*n^2+11*n-3)*a(n-3)
%p A217323        -12*(3*n+5)*(n-1)*(n-2)*(n-3)*a(n-4))/
%p A217323       ((n-3)*(3*n+2)*(n+2)*(n+1))))
%p A217323     end:
%p A217323 seq(a(n), n=3..40);
%t A217323 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 A217323 a[n_] := MotzkinNumber[n] - Binomial[n, Quotient[n, 2]];
%t A217323 Table[a[n], {n, 3, 40}] (* _Jean-François Alcover_, Oct 27 2021, from 2nd formula *)
%Y A217323 Column k=3 of A047884.
%Y A217323 Cf. A001006, A001405, A182172.
%K A217323 nonn,easy
%O A217323 3,2
%A A217323 _Alois P. Heinz_, Sep 30 2012