login
A145870
Number of involutions of length 2n which are invariant under the reverse-complement map and have no decreasing subsequences of length 8.
0
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.
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 A374569
KEYWORD
nonn
AUTHOR
Eric S. Egge, Oct 22 2008
EXTENSIONS
More terms from Vaclav Kotesovec, Feb 18 2015
STATUS
approved