login
Number of permutations of [n] having exactly ceiling(n/2)-1 alternating descents.
4

%I #20 Aug 31 2021 07:41:32

%S 1,1,1,2,7,36,182,1196,8699,76840,704834,7570716,84889638,1085246904,

%T 14322115212,211595659320,3216832016019,53984412657360,

%U 928559550102410,17440458896525180,334876925319944690,6960292943873805976,147563833511292247796,3362366089440205308072

%N Number of permutations of [n] having exactly ceiling(n/2)-1 alternating descents.

%C a(0) = 1 by convention.

%C Index i is an alternating descent of permutation p if either i is odd and p(i) > p(i+1), or i is even and p(i) < p(i+1).

%H Alois P. Heinz, <a href="/A302905/b302905.txt">Table of n, a(n) for n = 0..200</a>

%H D. Chebikin, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v15i1r132">Variations on descents and inversions in permutations</a>, The Electronic J. of Combinatorics, 15 (2008), #R132.

%F a(n) = A145876(n,ceiling(n/2)) for n > 0.

%e a(2) = 1: 12.

%e a(3) = 2: 123, 321.

%e a(4) = 7: 1234, 1432, 2431, 3214, 3421, 4213, 4312.

%p b:= proc(u, o) option remember; expand(`if`(u+o=0, 1,

%p add(b(o+j-1, u-j)*x, j=1..u)+

%p add(b(o-j, u-1+j), j=1..o)))

%p end:

%p a:= n-> coeff(b(n, 0), x, ceil(n/2)):

%p seq(a(n), n=0..25);

%t b[u_, o_] := b[u, o] = Expand[If[u + o == 0, 1,

%t Sum[b[o + j - 1, u - j]*x, {j, u}] +

%t Sum[b[o - j, u - 1 + j], {j, o}]]];

%t a[n_] := Coefficient[b[n, 0], x, Ceiling[n/2]];

%t Table[a[n], {n, 0, 25}] (* _Jean-François Alcover_, Aug 31 2021, after _Alois P. Heinz_ *)

%Y Bisections give: A302904 (even part), A302903 (odd part).

%Y Cf. A145876.

%K nonn

%O 0,4

%A _Alois P. Heinz_, Apr 15 2018