login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001758 Number of quasi-alternating permutations of length n.
(Formerly M2027 N0800)
5

%I M2027 N0800 #97 Feb 03 2023 01:33:55

%S 0,2,12,58,300,1682,10332,69298,505500,3990362,33925452,309248938,

%T 3010070700,31167995042,342164637372,3970297978978,48558251523900,

%U 624386836023722,8421511353298092,118891756573779418,1753452275441153100,26967372781086764402

%N Number of quasi-alternating permutations of length n.

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

%C From _Petros Hadjicostas_, Aug 08 2019: (Start)

%C 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 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 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 Thus, here a(n) is the number of permutations of [n] with n-2 such "séquences" ("alternate runs").

%C 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 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 (End)

%D L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 261.

%D F. N. David and D. E. Barton, Combinatorial Chance, Charles Griffin, 1962.

%D E. Netto, Lehrbuch der Combinatorik. 2nd ed., Teubner, Leipzig, 1927, p. 113.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H T. D. Noe, <a href="/A001758/b001758.txt">Table of n, a(n) for n = 2..100</a>

%H Data (data.bnf.fr), <a href="https://data.bnf.fr/fr/14523527/desire_andre/#documents-about ">Désiré André (1840-1918)</a>.

%H 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 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 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 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 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 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 E.g.f.: 2 * (1 + x + (1 - 2*cos(x)) / (1 - sin(x))). - _Michael Somos_, Aug 28 2012

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

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

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

%p 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 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 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 Table[4 Abs[PolyLog[-n-1, I]] - 8 Abs[PolyLog[-n, I]], {n, 2, 23}] (* _Jean-François Alcover_, Jul 01 2017 *)

%o (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 (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 Essentially the same as 2*A000708.

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

%Y Cf. A001759, A001760, A001250.

%Y See A008970 for formulas.

%K nonn,easy,nice

%O 2,2

%A _N. J. A. Sloane_

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

%E Edited by _N. J. A. Sloane_, Aug 27 2012

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 06:44 EDT 2024. Contains 371265 sequences. (Running on oeis4.)