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

Comments

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

Links

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

Formula

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

Example

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

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 *)

Crossrefs

Column k=3 of A047884.

Cf. A001006, A001405, A182172.

Sequence in context: A369399 A108898 A291887 * A263781 A119901 A106934

Adjacent sequences: A217320 A217321 A217322 * A217324 A217325 A217326

Keyword

nonn,easy

Author

Alois P. Heinz, Sep 30 2012

Status

approved