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

1, 3, 11, 31, 92, 253, 709, 1936, 5336, 14587, 40119, 110202, 304137, 840597, 2332469, 6487762, 18106906, 50667263, 142194843, 400057791, 1128408337, 3190023641, 9038202201, 25659417876, 72987714502, 207983161609, 593665226069, 1697230353691, 4859461136196

Offset: 3

Author

Alois P. Heinz, Sep 30 2012

Keywords

• nonn
• easy

Comments

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

Examples

			a(3) = 1: 123.
a(4) = 3: 1243, 1324, 2134.
a(5) = 11: 12543, 13254, 14325, 14523, 15342, 21354, 21435, 32145, 34125, 42315, 52341.
		

Links

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

Crossrefs

Column k=3 of A047884.

Cf. A001006, A001405, A182172.

Programs

Maple

a:= proc(n) option remember; `if`(n<3, 0, `if`(n=3, 1,
      ((n+1)*(6*n^3-5*n^2-7*n-24)*a(n-1)
       +n*(n-1)*(21*n^2-28*n-109)*a(n-2)
       -2*(n-1)*(n-2)*(12*n^2+11*n-3)*a(n-3)
       -12*(3*n+5)*(n-1)*(n-2)*(n-3)*a(n-4))/
      ((n-3)*(3*n+2)*(n+2)*(n+1))))
    end:
seq(a(n), n=3..40);

Mathematica

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_] := MotzkinNumber[n] - Binomial[n, Quotient[n, 2]];
Table[a[n], {n, 3, 40}] (* Jean-François Alcover, Oct 27 2021, from 2nd formula *)

Formula

a(n) = A182172(n,3) - A182172(n,2) = A001006(n) - A001405(n).