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

Author

Richard Ehrenborg, Oct 08 2013

Keywords

• nonn

Examples

			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 + ...
		

Links

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

Crossrefs

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

Programs

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 *)

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<=kA002627(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

Extensions

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