A145870 Number of involutions of length 2n which are invariant under the reverse-complement map and have no decreasing subsequences of length 8.

1, 2, 6, 20, 75, 301, 1287, 5762, 26875, 129520, 642452, 3264834, 16950089, 89646090, 482012650, 2629809994, 14537429823, 81313943942, 459705628930, 2624247237560, 15113949789357, 87755911422989, 513357330465591, 3023830805847910, 17925386942479025

Offset: 0

Author

Eric S. Egge, Oct 22 2008

Keywords

• nonn

Comments

a(n) is also the number of involutions of length 2n+1 which are invariant under the reverse-complement map and have no decreasing subsequences of length 8.

Crossrefs

Cf. A000108, A001006.

Programs

Mathematica

Array[Cat, 21, 0];
For[i = 0, i < 21, ++i, Cat[i] = (1/(i + 1))*Binomial[2*i, i]];
Array[Mot, 21, 0];
For[i = 0, i < 21, ++i, Mot[i] = Sum[Binomial[i, 2*j]*Cat[j], {j, 0, Floor[i/2]}]];
Table[Sum[ Binomial[n, j]*Cat[Floor[(j + 1)/2]]*Cat[Ceiling[(j + 1)/2]]* Mot[n - j],
{j, 0, n}], {n, 0, 15}]

Formula

a(n) = Sum_{j=0..n} C(n,j) * A000108(floor((j+1)/2)) * A000108(ceiling((j+1)/2)) * A001006(n-j), where C(n,j) = n!/(j!*(n-j)!), A000108(n) = Catalan(n) and A001006(n) = Motzkin(n).

From Vaclav Kotesovec, Feb 18 2015: (Start)

Recurrence: (n+3)*(n+5)*(n+6)*(192*n^2 + 992*n + 1321)*a(n) = 4*(192*n^5 + 3392*n^4 + 21897*n^3 + 64596*n^2 + 84418*n + 35925)*a(n-1) + 2*(n-1)*(3264*n^4 + 28000*n^3 + 74185*n^2 + 47329*n - 41250)*a(n-2) - 4*(n-2)*(n-1)*(3648*n^3 + 30272*n^2 + 73819*n + 38895)*a(n-3) - 105*(n-3)*(n-2)*(n-1)*(192*n^2 + 1376*n + 2505)*a(n-4).

a(n) ~ 7^(n+9/2) / (4 * Pi^(3/2) * n^(9/2)). (End)

Extensions

More terms from Vaclav Kotesovec, Feb 18 2015