|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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
|
|
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
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|