A227918 Sum over all permutations beginning and ending with ascents, and without double ascents on n elements and each permutation contributes 2 to the power of the number of double descents.

1, 0, 5, 22, 137, 956, 7653, 68874, 688745, 7576192, 90914309, 1181886014, 16546404201, 248196063012, 3971137008197, 67509329139346, 1215167924508233, 23088190565656424, 461763811313128485, 9697040037575698182, 213334880826665360009, 4906702259013303280204, 117760854216319278724901

Offset

2,3

Links

Table of n, a(n) for n=2..24.

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

Formula

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

Closest integer to (e - 4 + 4/e)*n! for n > 7.

a(n) = n*a(n-1) + 1 + 4*(-1)^n.

Conjecture: a(n) -n*a(n-1) -a(n-2) +(n-2)*a(n-3) = 0. - R. J. Mathar, Jul 17 2014

Example

a(4) = 5 since the sum is over the five permutations 1324, 1423, 2314, 2413 and 3412, and each of them contribute 1 to the sum, since none of them has a double descent.

Mathematica

a[2] = 1; a[n_] := n*a[n - 1] + 1 + 4 (-1)^n;  Table[a[n], {n, 2, 20}] (* Wesley Ivan Hurt, May 04 2014 *)

Crossrefs

Cf. A000166, A230071, A055596.

Sequence in context: A221539 A372139 A028561 * A009638 A346410 A121942

Adjacent sequences: A227915 A227916 A227917 * A227919 A227920 A227921

Keyword

nonn

Author

Richard Ehrenborg, Oct 08 2013

Status

approved