cp's OEIS Frontend

A001758 Number of quasi-alternating permutations of length n.

%I A001758 M2027 N0800 #101 Jul 30 2024 01:49:44
%S A001758 0,2,12,58,300,1682,10332,69298,505500,3990362,33925452,309248938,
%T A001758 3010070700,31167995042,342164637372,3970297978978,48558251523900,
%U A001758 624386836023722,8421511353298092,118891756573779418,1753452275441153100,26967372781086764402
%N A001758 Number of quasi-alternating permutations of length n.
%C A001758 The number of permutations of [n] with n-2 sequences (see Comtet).
%C A001758 From _Petros Hadjicostas_, Aug 08 2019: (Start)
%C A001758 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.
%C A001758 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}.
%C A001758 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.
%C A001758 Thus, here a(n) is the number of permutations of [n] with n-2 such "séquences" ("alternate runs").
%C A001758 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).
%C A001758 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".
%C A001758 (End)
%D A001758 L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 261.
%D A001758 F. N. David and D. E. Barton, Combinatorial Chance, Charles Griffin, 1962.
%D A001758 E. Netto, Lehrbuch der Combinatorik. 2nd ed., Teubner, Leipzig, 1927, p. 113.
%D A001758 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A001758 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A001758 T. D. Noe, <a href="/A001758/b001758.txt">Table of n, a(n) for n = 2..100</a>
%H A001758 Data (data.bnf.fr), <a href="https://data.bnf.fr/fr/14523527/desire_andre/#documents-about ">Désiré André (1840-1918)</a>.
%H A001758 Désiré André, <a href="http://sites.mathdoc.fr/JMPA/PDF/JMPA_1881_3_7_A10_0.pdf">Sur les permutations alternées</a>, J. Math. Pur. Appl., 7 (1881), 167-184.
%H A001758 Désiré André, <a href="https://doi.org/10.24033/asens.235">Étude sur les maxima, minima et séquences des permutations</a>, Ann. Sci. Ecole Norm. Sup., 3, no. 1 (1884), 121-135.
%H A001758 Désiré André, <a href="http://sites.mathdoc.fr/JMPA/PDF/JMPA_1895_5_1_A7_0.pdf">Mémoire sur les permutations quasi-alternées</a>, Journal de mathématiques pures et appliquées 5e série, tome 1 (1895), 315-350.
%H A001758 Désiré André, <a href="https://doi.org/10.24033/bsmf.519">Mémoire sur les séquences des permutations circulaires</a>, Bulletin de la S. M. F., tome 23 (1895), pp. 122-184.
%H A001758 E. Estanave, <a href="https://doi.org/10.24033/bsmf.675">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</a>, Bulletin de la S.M.F., 30 (1902), pp. 220-226. See p. 223.
%F A001758 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
%F A001758 E.g.f.: 2 * (1 + x + (1 - 2*cos(x)) / (1 - sin(x))). - _Michael Somos_, Aug 28 2012
%F A001758 Asymptotics: a(n) ~ 8*(2/Pi)^(n+1)*((n+1)/Pi-1)*n!.
%F A001758 a(n) = A001250(n+1) - 2*A001250(n). - Barbara Haas Margolius (margolius(AT)math.csuohio.edu), Mar 12 2001
%e A001758 G.f. = 2*x^3 + 12*x^4 + 58*x^5 + 300*x^6 + 1682*x^7 + 10332*x^8 + 69298*x^9 + ...
%p A001758 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
%t A001758 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 *)
%t A001758 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 *)
%t A001758 Table[4 Abs[PolyLog[-n-1, I]] - 8 Abs[PolyLog[-n, I]], {n, 2, 23}] (* _Jean-François Alcover_, Jul 01 2017 *)
%o A001758 (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 */
%o A001758 (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
%Y A001758 Essentially the same as 2*A000708.
%Y A001758 The diagonal P(n, n-2) of A059427.
%Y A001758 Cf. A001759, A001760, A001250.
%Y A001758 See A008970 for formulas.
%K A001758 nonn,easy,nice
%O A001758 2,2
%A A001758 _N. J. A. Sloane_
%E A001758 More terms from Larry Reeves (larryr(AT)acm.org), Feb 01 2001
%E A001758 Edited by _N. J. A. Sloane_, Aug 27 2012