cp's OEIS Frontend

A000708 a(n) = E(n+1) - 2*E(n), where E(i) is the Euler number A000111(i).

%I A000708 M4188 N1745 #155 Jun 01 2025 00:53:15
%S A000708 -1,-1,0,1,6,29,150,841,5166,34649,252750,1995181,16962726,154624469,
%T A000708 1505035350,15583997521,171082318686,1985148989489,24279125761950,
%U A000708 312193418011861,4210755676649046,59445878286889709,876726137720576550,13483686390543382201
%N A000708 a(n) = E(n+1) - 2*E(n), where E(i) is the Euler number A000111(i).
%C A000708 a(n) mod 10 for n >= 2 is the periodic sequence repeat: 0, 1, 6, 9.
%C A000708 For n >= 2, a(n) is the number of permutations on [n] that have n-2 "sequences" (which are maximal monotone runs in Comtet terminology) and start increasing. - _Michael Somos_, Aug 28 2013
%C A000708 From _Petros Hadjicostas_, Aug 07 2019: (Start)
%C A000708 With regard to the comment by _Michael Somos_ above, a "sequence" in a permutation according to Ex. 13 (pp. 260-261) of Comtet (1974) is actually a "séquence" in a permutation according to André. He uses this terminology in several of his papers cited in the links below.
%C A000708 In the terminology of array A059427, these so-called "séquences" in permutations defined by Comtet and André are called "alternate runs" (or just "runs"). We discuss these so-called "sequences" below.
%C A000708 We clarify that a(n) is actually one-half the number of permutations on [n] that have n-2 "séquences" as defined by Comtet and André.
%C A000708 André (1884) defines a "maximum" of a permutation of [n] to be any number in the permutation that is greater than both of its neighbors, if it is an interior number, or greater than its single neighbor, if it is either at the beginning or at the end of the permutation.
%C A000708 André (1884) also defines a "minimum" of a permutation of [n] to be any number in the permutation that is less than both of its neighbors, if it is an interior number, or less than its single neighbor, if it is either at the beginning or at the end of the permutation.
%C A000708 A "séquence" in a permutation of [n] according to André and Comtet is a list of consecutive numbers in the permutation that begins with a maximum and ends with a minimum, or vice versa, but has no interior maxima and minima. As mentioned above, other authors call these so-called "séquences" "alternate runs" (or just "runs").
%C A000708 For example, in the permutation 78125436 of [8], we have three maxima, 8, 5, and 6; three minima, 7, 1, and 3; and the so-called "séquences" ("alternate runs") 78, 81, 125, 543, 36 (see p. 122 in André (1884)).
%C A000708 If in the above permutation we take the difference 8-7, 1-8, 2-1, 5-2, 4-5, 3-4, 6-3, we may form a word (list) of signs of consecutive differences: +-++--+.
%C A000708 In general, if in a permutation of [n], say a_1,a_2,...,a_n (written in one-line notation, but not in cycle notation), we form the differences a_2 - a_1, a_3 - a_2, ..., a_n - a_{n-1}, then we get a list of n-1 signs (+ or -).
%C A000708 For n >= 2, André (1885) calls a permutation of [n] "alternate" if it has n - 1 so-called "séquences" ("alternate runs"); i.e., if the corresponding list of signs alternates between + and -. See the documentation and references for sequences A000111 and A001250.
%C A000708 For n >= 2, André (1885) calls a permutation of [n] "quasi-alternate" if it has n - 2 so-called "séquences" ("alternate runs"); i.e., if the corresponding list of signs alternates between + and - except for a single ++ or a single --, but not both.
%C A000708 In the above example, the permutation 78125436 has 5 so-called "séquences" ("alternate signs") and 5 < 8-2 < 8-1; that is, it is neither alternate nor quasi-alternate. We can reach the same conclusion by looking at its corresponding list of signs +-++--+. The permutation is neither alternate nor quasi-alternate because we have one ++ and one --.
%C A000708 On p. 316, André (1885) gives the following two examples of permutations of [8]: 31426587 and 32541768 (using one-line notation for permutations). The first one has list of signs -+-+-+- while the second one has list of signs -+--+-+. The first one is alternate while the second one is quasi-alternate (because of a single --). Alternatively, the first one has n-1 = 7 so-called "séquences" ("alternate runs")--31, 14, 42, 26, 65, 58, 87--while the second one has n-2 = 6 so-called "séquences" ("alternate runs")--32, 25, 541, 17, 76, 68.
%C A000708 Here 2*a(n) is the total number of quasi-alternate permutations of [n]. Actually, André (1884, 1885) uses P_{n,s} to denote the number of permutations of [n] with exactly s of his so-called "séquences" ("alternate runs"). He uses the notation A_n to denote half the number of alternate permutations of [n] and B_n to denote half the number of quasi-alternate permutations of [n].
%C A000708 Thus, P_{n,n-1} = 2*A_n = 2*A000111(n) = A001250(n) for n >= 2 and P_{n,n-2} = 2*B_n = 2*a(n) for n >= 2.
%C A000708 We have P_{n,s} = A059427(n,s) for n >= 2 and s >= 1. See also p. 261 in Comtet (1974). They satisfy André's recurrence P_{n,s} = s*P_{n-1,s} + 2*P_{n-1,s-1} + (n-s)*P_{n-1,s-2} for n >= 3 and s >= 3 with P(n, 1) = 2 for n >= 2 and P(n, s) = 0 for s >= n.
%C A000708 The numbers Q(n,s) that count the circular permutations of [n] with exactly s so-called "séquences" ("alternate runs") appear in array A008303. They have also been studied by Désiré André (see the references there).
%C A000708 (End)
%D A000708 L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 261.
%D A000708 E. Netto, Lehrbuch der Combinatorik. 2nd ed., Teubner, Leipzig, 1927, p. 113.
%D A000708 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A000708 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A000708 John Cerkan, <a href="/A000708/b000708.txt">Table of n, a(n) for n = 0..482</a>
%H A000708 Data (data.bnf.fr), <a href="https://data.bnf.fr/fr/14523527/desire_andre/#documents-about ">Désiré André (1840-1918)</a>.
%H A000708 Désiré André, <a href="http://sites.mathdoc.fr/JMPA/PDF/JMPA_1881_3_7_A10_0.pdf">Mémoire sur les permutations alternées</a>, J. Math. Pur. Appl., 7 (1881), 167-184.
%H A000708 Désiré André, <a href="https://doi.org/10.24033/asens.235">Étude sur les maxima, minima et séquences des permutations</a>, Annales scientifiques de l'École Normale Supérieure, Serie 3, Vol. 1 (1884), 121-134.
%H A000708 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 A000708 E. Estanave, <a href="http://www.numdam.org/item?id=BSMF_1902__30__220_1">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.
%H A000708 F. Morley, <a href="http://dx.doi.org/10.1090/S0002-9904-1897-00451-7">A generating function for the number of permutations with an assigned number of sequences</a>, Bull. Amer. Math. Soc. 4 (1897), 23-28. [Discusses the so-called "séquences" of Désiré André. A shifted version of the current sequence appears in column r = 1 in the table on p. 24. His definition, however, of a "run" is highly not standard! The definition of the letter r in his paper is the number of triplets of adjacent numbers in the permutation that appear in order of magnitude (ascending or descending). He proves that in any permutation b of [n] we have r + s = n-1, where s is the number of the so-called "séquences" of André (i.e., number of "alternate runs"). Thus, r = 1 if and only s = n - 2. - _Petros Hadjicostas_, Aug 09 2019]
%H A000708 Eugen Netto, <a href="/A000708/a000708.pdf">Lehrbuch der Combinatorik</a>, 1901, Annotated scanned copy of pages 112-113 only.
%H A000708 Eugen Netto, <a href="/A000708/a000708.pdf">Lehrbuch der Combinatorik</a>, Verlag von B. G. Teubner, Leipzig, 1901 (archived copy of the whole book).
%H A000708 Eric Weisstein's MathWorld, <a href="https://mathworld.wolfram.com/Polylogarithm.html">Polylogarithm</a>.
%F A000708 E.g.f.: (1 - 2*cos(x)) / (1 - sin(x)).
%F A000708 a(n) ~ n! * 2*n*(2/Pi)^(n+2). - _Vaclav Kotesovec_, Oct 08 2013
%F A000708 a(n) = 2*abs(PolyLog(-n-1, i)) - 4*abs(PolyLog(-n, i)) for n > 0, with a(0) = -1. - _Jean-François Alcover_, Jul 02 2017
%e A000708 G.f. = -1 - x + x^3 + 6*x^4 + 29*x^5 + 150*x^6 + 841*x^7 + 5166*x^8 + 34649*x^9 + ...
%e A000708 a(3) = 1 with permutation 123. a(4) = 6 with permutations 1243, 1342, 1432, 2341, 2431, 3421.
%e A000708 From _Petros Hadjicostas_, Aug 07 2019: (Start)
%e A000708 We elaborate on the example above. For the permutations of [3], we have the following sign sequences:
%e A000708 123 -> ++; 132 --> +-; 213 -> -+; 213 -> 213; 231 -> +-; 312 -> -+; 321 --> --.
%e A000708 Thus, 123 and 321 are quasi-alternate and a(3) = 2/2 = 1.
%e A000708 For the permutations of [4] we have:
%e A000708   1234 -> +++ (neither alternate nor quasi-alternate);
%e A000708   1243 -> ++- (quasi-alternate);
%e A000708   1324 -> +-+ (alternate);
%e A000708   1342 -> ++- (quasi-alternate);
%e A000708   1423 -> +-+ (alternate);
%e A000708   1432 -> +-- (quasi-alternate);
%e A000708   2134 -> -++ (quasi-alternate);
%e A000708   2143 -> -+- (alternate);
%e A000708   2314 -> +-+ (alternate);
%e A000708   2341 -> ++- (quasi-alternate);
%e A000708   2413 -> +-+ (alternate);
%e A000708   2431 -> +-- (quasi-alternate);
%e A000708   3124 -> -++ (quasi-alternate);
%e A000708   3142 -> -+- (alternate);
%e A000708   3214 -> --+ (quasi-alternate);
%e A000708   3241 -> -+- (alternate);
%e A000708   3412 -> +-+ (alternate);
%e A000708   3421 -> +-- (quasi-alternate);
%e A000708   4123 -> -++ (quasi-alternate);
%e A000708   4132 -> -+- (alternate);
%e A000708   4213 -> --+ (quasi-alternate);
%e A000708   4231 -> -+- (alternate);
%e A000708   4312 -> --+ (quasi-alternate);
%e A000708   4321 -> --- (neither alternate nor quasi-alternate).
%e A000708 Thus we have 10 = 2*A000111(4) = A001250(4) alternate permutations of [4] and 2*a(4) = 2*6 = 12 quasi-alternate permutations of [4]. The remaining 2 permutations (1234 and 4321) each have one so-called "séquence" ("alternate run").
%e A000708 Thus, P_{n=4, s=1} = 2, P_{n=4, s=2} = 12, and P_{n=4, s=10} = 10 (see row n = 4 for array A059427).
%e A000708 (End)
%p A000708 seq(i! * coeff(series((1 + (tan(t) + sec(t))^2 - 4*(tan(t) + sec(t))) / 2, t, 35), t, i), i=0..24); # Barbara Haas Margolius (margolius(AT)math.csuohio.edu), Mar 12 2001
%t A000708 a[ n_] := If[ n < 0, 0, n! SeriesCoefficient[ (1 - 2 Cos[x]) / (1 - Sin[x]), {x, 0, n}]]; (* _Michael Somos_, Aug 28 2013 *)
%t A000708 nmax = 22; ee = Table[2^n*EulerE[n, 1] + EulerE[n], {n, 0, nmax+1}]; dd = Table[Differences[ee, n][[1]] // Abs, {n, 0, nmax+1}]; a[n_] := dd[[n+2]] - 2dd[[n+1]]; a[0] = -1; Table[a[n], {n, 0, nmax}] (* _Jean-François Alcover_, Feb 10 2016, after _Paul Curtz_ *)
%t A000708 Table[If[n == 0, -1, 2 Abs[PolyLog[-n-1, I]] - 4 Abs[PolyLog[-n, I]]], {n, 0, 22}] (* _Jean-François Alcover_, Jul 01 2017 *)
%o A000708 (PARI) x='x+O('x^99); Vec(serlaplace((1-2*cos(x))/(1-sin(x))))
%o A000708 (Python)
%o A000708 from mpmath import polylog, j, mp
%o A000708 mp.dps=20
%o A000708 def a(n): return -1 if n==0 else int(2*abs(polylog(-n - 1, j)) - 4*abs(polylog(-n, j)))
%o A000708 print([a(n) for n in range(23)])  # _Indranil Ghosh_, Jul 02 2017
%o A000708 (Python)
%o A000708 from itertools import count, islice, accumulate
%o A000708 def A000708_gen(): # generator of terms
%o A000708     yield -1
%o A000708     blist = (0,1)
%o A000708     for n in count(2):
%o A000708         yield -2*blist[-1]+(blist:=tuple(accumulate(reversed(blist),initial=0)))[-1]
%o A000708 A000708_list = list(islice(A000708_gen(),40)) # _Chai Wah Wu_, Jun 09-11 2022
%Y A000708 Apart from initial terms, equals (1/2)*A001758. A diagonal of A008970.
%Y A000708 Cf. A000111, A001250, A008303, A059427.
%K A000708 sign
%O A000708 0,5
%A A000708 _N. J. A. Sloane_
%E A000708 More terms from Barbara Haas Margolius (margolius(AT)math.csuohio.edu), Mar 12 2001
%E A000708 Corrected and extended by _T. D. Noe_, Oct 25 2006
%E A000708 Edited by _N. J. A. Sloane_, Aug 27 2012