A145845 Number of permutations of length 2n+1 which are invariant under the reverse-complement map and have no decreasing subsequences of length 5.

1, 2, 7, 34, 208, 1504, 12283, 109778, 1050820, 10614856, 111978128, 1224261856, 13792583296, 159411938560, 1883550536707, 22687603653106, 277940485660012, 3456490397570392, 43565433620294908, 555752354850506312, 7167182317486700416, 93348781597357983232, 1226830676118851157712

Offset

0,2

Links

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

Formula

a(n) = sum(j=0, n, C(n,j)^2 * A005802(j)).

a(n) = sum(j=0, n, C(n,j)^2 * (1/((j+1)^2 (j+2))) * sum(i=0, j, C(2*i,i) * C(j+1,i+i) * C(j+2,i+1))) where C(n,j) = n!/(j!(n-j)!).

Recurrence: (n+2)^3*(3*n+1)*a(n) = 2*(30*n^4 + 67*n^3 + 29*n^2 - 10*n - 8)*a(n-1) - 64*(n-1)^2*n*(3*n+4)*a(n-2). - Vaclav Kotesovec, Feb 18 2015

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

Mathematica

Table[Sum[ Binomial[n, j]^2*(1/((j + 1)^2*(j + 2)))* Sum[Binomial[2*i, i]*Binomial[j + 1, i + 1]* Binomial[j + 2, i + 1], {i, 0, j}], {j, 0, n}], {n, 0, 20}]

Prog

(PARI) /* using formula given; this gives fractions! */
C=binomial;
a(n)=sum(j=0, n, C(n, j)^2 * (1/((j+1)^2*(j+2))) * sum(i=0, j, C(2*i, i)*C(j+1, i+i)*C(j+2, i+1)));
\\ Joerg Arndt, Feb 18 2015
(PARI) /* Using a(n) = sum(j=0, n, C(n, j)^2 * A005802(j)). */
f(n)= 2 * sum(k=0, n, binomial(2*k, k) * (binomial(n, k))^2 * (3*k^2+2*k+1-n-2*k*n)/((k+1)^2 * (k+2) * (n-k+1)));
vector(33, N, my(n=N-1); sum(j=0, n, f(j) * C(n, j)^2 ) )
\\ Joerg Arndt, Feb 18 2015

Crossrefs

Sequence in context: A075834 A011800 A112916 * A355292 A002720 A234239

Adjacent sequences: A145842 A145843 A145844 * A145846 A145847 A145848

Keyword

nonn

Author

Eric S. Egge, Oct 21 2008

Extensions

Added more terms, Joerg Arndt, Feb 18 2015

Status

approved