A230071 Sum over all permutations without double ascents on n elements and each permutation contributes 2 raised to the power of the number of double descents.

0, 0, 2, 6, 26, 130, 782, 5474, 43794, 394146, 3941462, 43356082, 520272986, 6763548818, 94689683454, 1420345251810, 22725524028962, 386333908492354, 6954010352862374, 132126196704385106, 2642523934087702122, 55493002615841744562, 1220846057548518380366

Offset

0,3

Links

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

R. Ehrenborg and J. Jung, Descent pattern avoidance, Adv. in Appl. Math., 49 (2012) 375-390.

Formula

E.g.f.: (exp(x)+exp(-x)-2)/(1-x).

a(n) = closest integer to (e-2+1/e)*n! for n > 3.

a(n) = (2-n)*a(n-3) + a(n-2) + n*a(n-1) for n > 2.

a(n) = 2*A080227(n).

a(n) = sum(0<=k<n, (-1)^(n-k-1)*binomial(n,k)*A002627(k)). - Peter Luschny, May 30 2014

0 = a(n)*(+a(n+1) - a(n+2) - 3*a(n+3) + a(n+4)) + a(n+1)*(+a(n+1) + a(n+2) - 2*a(n+3)) + a(n+2)*(+a(n+2) + a(n+3) - a(n+4)) + a(n+3)*(+a(n+3)) if n>=0. - Michael Somos, May 30 2014

Example

For n=3 the a(3)= 6 since the 4 permutations 132, 213, 231, 312 all contribute 1 and 321 contributes 2 to the sum. Note when n=4, the permutation 4321 contributes 4 since it has two double descents.
G.f. = 2*x^2 + 6*x^3 + 26*x^4 + 130*x^5 + 782*x^6 + 5474*x^7 + 43794*x^8 + ...

Maple

a := proc(n) if n < 2 then 0 elif n = 2 then 2 else (2-n)*a(n-3)+a(n-2)+n*a(n-1) fi end: seq(a(n), n=0..9); # Peter Luschny, May 30 2014

Mathematica

a[0] = 0; a[n_] := a[n] = n a[n-1] + (-1)^n + 1;
Array[a, 23, 0] (* Jean-François Alcover, Jul 08 2019, after A080227 *)

Crossrefs

Cf. A000166, A002627, A080227, A055596, A227918.

Sequence in context: A306041 A345870 A123872 * A030937 A030827 A030947

Adjacent sequences: A230068 A230069 A230070 * A230072 A230073 A230074

Keyword

nonn

Author

Richard Ehrenborg, Oct 08 2013

Extensions

a(0) and a(1) prepended, partially edited. - Peter Luschny, May 30 2014

Status

approved