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

Author

Eric S. Egge, Oct 21 2008

Keywords

• nonn

Programs

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

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

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

Extensions

Added more terms, Joerg Arndt, Feb 18 2015