A302691 Number of broken alternating permutations of n things.

0, 0, 1, 2, 7, 26, 117, 594, 3407, 21682, 151853, 1160026, 9600567, 85566378, 817099909, 8322907298, 90074979487, 1032183177314, 12485056392285, 158964674218410, 2125201153260167, 29764791617545690, 435823661971532981, 6658895050949717362, 105979606291488794607

Offset: 0

Author

Michael De Vlieger, Apr 11 2018

Keywords

• nonn

Comments

A permutation of {1,2,...,n} is said to be a "broken alternating permutation" if it is an alternating permutation (cf. A000111) except at one point. See El Hilany and Rau for precise definition and an explicit formula.

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..484
• D. Chebikin, Variations on descents and inversions in permutations, The Electronic J. of Combinatorics, 15 (2008), #R132.
• Boulos El Hilany, Johannes Rau, Signed counts of real simple rational functions, arXiv:1712.05639 [math.AG], 2017, Proposition 6.4, p. 19.

Crossrefs

Cf. A000111.

Column k=2 of A145876.

Programs

Maple

b:= proc(u, o, t) option remember;
      `if`(u+o=0, t, add(b(o+j-1, u-j, t), j=1..u)+
      `if`(t=0,      add(b(o-j, u-1+j, 1), j=1..o), 0))
    end:
a:= n-> b(n, 0$2):
seq(a(n), n=0..25);  # Alois P. Heinz, Apr 14 2018
# second Maple program:
egf:= (cos(x)-sin(x)+x-1)/(sin(x)-1):
a:= n-> n! * coeff(series(egf, x, n+1), x, n):
seq(a(n), n=0..25);  # Alois P. Heinz, Apr 16 2018

Mathematica

b[u_, o_, t_] := b[u, o, t] = If[u + o == 0, t, Sum[b[o + j - 1, u - j, t], {j, 1, u}] + If[t == 0, Sum[b[o - j, u - 1 + j, 1], {j, 1, o}], 0]];
a[n_] := b[n, 0, 0];
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Apr 19 2018, after Alois P. Heinz *)

Formula

a(n) ~ (4 - Pi) * 2^(n + 5/2) * n^(n + 3/2) / (exp(n) * Pi^(n + 3/2)). - Vaclav Kotesovec, Apr 14 2018

E.g.f.: (cos(x)-sin(x)+x-1)/(sin(x)-1). - Alois P. Heinz, Apr 16 2018

Extensions

a(13)-a(24) from Alois P. Heinz, Apr 14 2018