login
Number of broken alternating permutations of n things.
2

%I #21 Apr 19 2018 15:59:51

%S 0,0,1,2,7,26,117,594,3407,21682,151853,1160026,9600567,85566378,

%T 817099909,8322907298,90074979487,1032183177314,12485056392285,

%U 158964674218410,2125201153260167,29764791617545690,435823661971532981,6658895050949717362,105979606291488794607

%N Number of broken alternating permutations of n things.

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

%H Alois P. Heinz, <a href="/A302691/b302691.txt">Table of n, a(n) for n = 0..484</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.

%H Boulos El Hilany, Johannes Rau, <a href="https://arxiv.org/abs/1712.05639">Signed counts of real simple rational functions</a>, arXiv:1712.05639 [math.AG], 2017, Proposition 6.4, p. 19.

%F a(n) ~ (4 - Pi) * 2^(n + 5/2) * n^(n + 3/2) / (exp(n) * Pi^(n + 3/2)). - _Vaclav Kotesovec_, Apr 14 2018

%F E.g.f.: (cos(x)-sin(x)+x-1)/(sin(x)-1). - _Alois P. Heinz_, Apr 16 2018

%p b:= proc(u, o, t) option remember;

%p `if`(u+o=0, t, add(b(o+j-1, u-j, t), j=1..u)+

%p `if`(t=0, add(b(o-j, u-1+j, 1), j=1..o), 0))

%p end:

%p a:= n-> b(n, 0$2):

%p seq(a(n), n=0..25); # _Alois P. Heinz_, Apr 14 2018

%p # second Maple program:

%p egf:= (cos(x)-sin(x)+x-1)/(sin(x)-1):

%p a:= n-> n! * coeff(series(egf, x, n+1), x, n):

%p seq(a(n), n=0..25); # _Alois P. Heinz_, Apr 16 2018

%t 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]];

%t a[n_] := b[n, 0, 0];

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

%Y Cf. A000111.

%Y Column k=2 of A145876.

%K nonn

%O 0,4

%A _Michael De Vlieger_, Apr 11 2018

%E a(13)-a(24) from _Alois P. Heinz_, Apr 14 2018