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

1, 1, 1, 2, 7, 36, 182, 1196, 8699, 76840, 704834, 7570716, 84889638, 1085246904, 14322115212, 211595659320, 3216832016019, 53984412657360, 928559550102410, 17440458896525180, 334876925319944690, 6960292943873805976, 147563833511292247796, 3362366089440205308072

Offset

0,4

Comments

a(0) = 1 by convention.

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

Links

Alois P. Heinz, Table of n, a(n) for n = 0..200

D. Chebikin, Variations on descents and inversions in permutations, The Electronic J. of Combinatorics, 15 (2008), #R132.

Formula

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

Example

a(2) = 1: 12.
a(3) = 2: 123, 321.
a(4) = 7: 1234, 1432, 2431, 3214, 3421, 4213, 4312.

Maple

b:= proc(u, o) option remember; expand(`if`(u+o=0, 1,
       add(b(o+j-1, u-j)*x, j=1..u)+
       add(b(o-j, u-1+j),   j=1..o)))
    end:
a:= n-> coeff(b(n, 0), x, ceil(n/2)):
seq(a(n), n=0..25);

Mathematica

b[u_, o_] := b[u, o] = Expand[If[u + o == 0, 1,
     Sum[b[o + j - 1, u - j]*x, {j, u}] +
     Sum[b[o - j, u - 1 + j], {j, o}]]];
a[n_] := Coefficient[b[n, 0], x, Ceiling[n/2]];
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Aug 31 2021, after Alois P. Heinz *)

Crossrefs

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

Cf. A145876.

Sequence in context: A060814 A192816 A302895 * A378787 A249691 A129261

Adjacent sequences: A302902 A302903 A302904 * A302906 A302907 A302908

Keyword

nonn

Author

Alois P. Heinz, Apr 15 2018

Status

approved