A001758 Number of quasi-alternating permutations of length n.

0, 2, 12, 58, 300, 1682, 10332, 69298, 505500, 3990362, 33925452, 309248938, 3010070700, 31167995042, 342164637372, 3970297978978, 48558251523900, 624386836023722, 8421511353298092, 118891756573779418, 1753452275441153100, 26967372781086764402

Offset: 2

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

Comments

The number of permutations of [n] with n-2 sequences (see Comtet).

From Petros Hadjicostas, Aug 08 2019: (Start)

We clarify the word "sequences" used above because it may not be standard. On pp. 260-261 of his book, Comtet (1974) defines a so-called "sequence" in a permutation b of [n]. Using one-line notation (not cycle notation), write b = (b_1, b_2, ..., b_n) for the elements of a permutation of [n]. A maximal list of indices of length l (where l >= 2) is called a "sequence" in the permutation b if it is of the form {i, i+1, ..., i+l-1} for some integer i (with 1 <= i <= n-l+1) such that b_i < b_{i+1} < ... < b_{i+l-1} or b_i > b_{i+1} > ... > b_{i+l-1}. (The word "maximal" means that in the first case, b_{i-1} > b_i and b_{i+l} < b_{i+l-1}, while in the second case, b_{i-1} < b_i and b_{i+l} > b_{i+l-1}, provided that b_{i-1} and b_{i+l} can be defined.) The assumption l >= 2 is important; i.e., these so-called "sequences" should have length >= 2.

Comtet (1974) has borrowed this confusing terminology about "séquences" in permutations from André (see links to some of his papers below). André actually uses the term "séquence" for the list of terms (b_i, b_{i+1}, ..., b_{i+l-1}) rather than the index set {i, i+1, ..., i+l-1}.

Some authors today use the term "alternate runs" (or just "runs") to discuss these so-called "séquences" defined by Comtet and André but we must have l >= 2.

Thus, here a(n) is the number of permutations of [n] with n-2 such "séquences" ("alternate runs").

For an extensive discussion of these so-called "séquences" in permutations ("alternate runs"), maxima and minima in a permutation, alternate and quasi-alternate permutations, and other related information, see the four papers by André, or see my comments for sequence A000708 (which equals one-half of the current sequence).

David and Barton (1962, p. 154) call these "séquences" "runs up" if they are ascending and "runs down" if they are descending. In modern terminology, "runs up" are ascending runs of length >= 2 while "runs down" are descending runs of length >= 2. Thus, a modern terminology for these "séquences" is "ascending or descending runs of length >= 2".

(End)

Examples

			G.f. = 2*x^3 + 12*x^4 + 58*x^5 + 300*x^6 + 1682*x^7 + 10332*x^8 + 69298*x^9 + ...
		

References

• L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 261.
• F. N. David and D. E. Barton, Combinatorial Chance, Charles Griffin, 1962.
• E. Netto, Lehrbuch der Combinatorik. 2nd ed., Teubner, Leipzig, 1927, p. 113.
• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• T. D. Noe, Table of n, a(n) for n = 2..100
• Data (data.bnf.fr), Désiré André (1840-1918).
• Désiré André, Sur les permutations alternées, J. Math. Pur. Appl., 7 (1881), 167-184.
• Désiré André, Étude sur les maxima, minima et séquences des permutations, Ann. Sci. Ecole Norm. Sup., 3, no. 1 (1884), 121-135.
• Désiré André, Mémoire sur les permutations quasi-alternées, Journal de mathématiques pures et appliquées 5e série, tome 1 (1895), 315-350.
• Désiré André, Mémoire sur les séquences des permutations circulaires, Bulletin de la S. M. F., tome 23 (1895), pp. 122-184.
• E. Estanave, Sur les coefficients des développements en séries de tang x, séc x et d'autres fonctions. Caractères de périodicité que présentent les chiffres des unités de ces coefficients, Bulletin de la S.M.F., 30 (1902), pp. 220-226. See p. 223.

Crossrefs

Essentially the same as 2*A000708.

The diagonal P(n, n-2) of A059427.

Cf. A001759, A001760, A001250.

See A008970 for formulas.

Programs

Maple

seq(i!*coeff(series((tan(t)+sec(t))^2-4*(tan(t)+sec(t)),t,35),t,i),i=2..24); # Barbara Haas Margolius (margolius(AT)math.csuohio.edu), Mar 12 2001

Mathematica

With[{nn=30}, Join[{1}, Drop[CoefficientList[Series[(Tan[x]+Sec[x])^2- 4(Tan[x]+Sec[x]),{x,0,nn}],x] Range[0,nn]!,3]]] (* Harvey P. Dale, Oct 01 2011 *)
a[ n_] := If[ n < 0, 0, n! SeriesCoefficient[ (u (u - 4) /. u -> Tan[x] + Sec[x]) + 3 + 2 x, {x, 0, n}]]; (* Michael Somos, Oct 24 2015 *)
Table[4 Abs[PolyLog[-n-1, I]] - 8 Abs[PolyLog[-n, I]], {n, 2, 23}] (* Jean-François Alcover, Jul 01 2017 *)

PARI

{a(n) = my(A); if( n<0, 0, A = x * O(x^n); 2 * n! * polcoeff( 1 + x + (1 - 2 * cos(x + A)) / (1 - sin(x + A)), n))}; /* Michael Somos, Aug 28 2012 */

PARI

x='x+O('x^99); concat(0, Vec(serlaplace(2*(1+x+(1-2*cos(x))/(1-sin(x)))))) \\ Altug Alkan, Jul 01 2017

Formula

E.g.f.: 3 + 2*x + u(x)^2 - 4*u(x) where u(x) = tan(x) + sec(x). - Barbara Haas Margolius (margolius(AT)math.csuohio.edu), Mar 12 2001

E.g.f.: 2 * (1 + x + (1 - 2*cos(x)) / (1 - sin(x))). - Michael Somos, Aug 28 2012

Asymptotics: a(n) ~ 8*(2/Pi)^(n+1)*((n+1)/Pi-1)*n!.

a(n) = A001250(n+1) - 2*A001250(n). - Barbara Haas Margolius (margolius(AT)math.csuohio.edu), Mar 12 2001

Extensions

More terms from Larry Reeves (larryr(AT)acm.org), Feb 01 2001

Edited by N. J. A. Sloane, Aug 27 2012