login
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.
2

%I #21 Oct 02 2023 20:23:47

%S 1,0,5,22,137,956,7653,68874,688745,7576192,90914309,1181886014,

%T 16546404201,248196063012,3971137008197,67509329139346,

%U 1215167924508233,23088190565656424,461763811313128485,9697040037575698182,213334880826665360009,4906702259013303280204,117760854216319278724901

%N 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.

%H R. Ehrenborg and J. Jung, <a href="http://dx.doi.org/10.1016/j.aam.2012.08.004">Descent pattern avoidance</a>, Adv. in Appl. Math., 49 (2012) 375-390.

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

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

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

%F Conjecture: a(n) -n*a(n-1) -a(n-2) +(n-2)*a(n-3) = 0. - _R. J. Mathar_, Jul 17 2014

%e 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.

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

%Y Cf. A000166, A230071, A055596.

%K nonn

%O 2,3

%A _Richard Ehrenborg_, Oct 08 2013