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
Keywords
Examples
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.
Links
- R. Ehrenborg and J. Jung, Descent pattern avoidance, Adv. in Appl. Math., 49 (2012) 375-390.
Programs
-
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 *)
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