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

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.

Links

Table of n, a(n) for n=0..24.

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

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). - Vaclav Kotesovec, Feb 18 2015

a(n) ~ 7^(n+9/2) / (4 * Pi^(3/2) * n^(9/2)). - Vaclav Kotesovec, Feb 18 2015

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}]

Crossrefs

Sequence in context: A150166 A150167 A150168 * A134957 A052889 A263901

Adjacent sequences: A145867 A145868 A145869 * A145871 A145872 A145873

Keyword

nonn

Author

Eric S. Egge, Oct 22 2008

Extensions

More terms from Vaclav Kotesovec, Feb 18 2015

Status

approved