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

-1, -1, 0, 1, 6, 29, 150, 841, 5166, 34649, 252750, 1995181, 16962726, 154624469, 1505035350, 15583997521, 171082318686, 1985148989489, 24279125761950, 312193418011861, 4210755676649046, 59445878286889709, 876726137720576550, 13483686390543382201

Offset

0,5

Comments

a(n) mod 10 for n >= 2 is the periodic sequence repeat: 0, 1, 6, 9.

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

From Petros Hadjicostas, Aug 07 2019: (Start)

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.

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.

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é.

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.

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.

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").

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)).

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: +-++--+.

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 -).

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.

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.

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

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.

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].

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.

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.

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).

(End)

References

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

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

John Cerkan, Table of n, a(n) for n = 0..482

Data (data.bnf.fr), Désiré André (1840-1918).

Désiré André, Mémoire 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, Annales scientifiques de l'École Normale Supérieure, Serie 3, Vol. 1 (1884), 121-134.

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.

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.

F. Morley, A generating function for the number of permutations with an assigned number of sequences, 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]

Eugen Netto, Lehrbuch der Combinatorik, 1901, Annotated scanned copy of pages 112-113 only.

Eugen Netto, Lehrbuch der Combinatorik, Verlag von B. G. Teubner, Leipzig, 1901 (archived copy of the whole book).

Eric Weisstein's MathWorld, Polylogarithm.

Formula

E.g.f.: (1 - 2*cos(x)) / (1 - sin(x)).

a(n) ~ n! * 2*n*(2/Pi)^(n+2). - Vaclav Kotesovec, Oct 08 2013

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

Example

G.f. = -1 - x + x^3 + 6*x^4 + 29*x^5 + 150*x^6 + 841*x^7 + 5166*x^8 + 34649*x^9 + ...
a(3) = 1 with permutation 123. a(4) = 6 with permutations 1243, 1342, 1432, 2341, 2431, 3421.
From Petros Hadjicostas, Aug 07 2019: (Start)
We elaborate on the example above. For the permutations of [3], we have the following sign sequences:
123 -> ++;  132 --> +-; 213 -> -+; 213 -> 213; 231 -> +-; 312 -> -+; 321 --> --.
Thus, 123 and 321 are quasi-alternate and a(3) = 2/2 = 1.
For the permutations of [4] we have:
1234 -> +++ (neither alternate nor quasi-alternate);
1243 -> ++- (quasi-alternate);
1324 -> +-+ (alternate);
1342 -> ++- (quasi-alternate);
1423 -> +-+ (alternate);
1432 -> +-- (quasi-alternate);
2134 -> -++ (quasi-alternate);
2143 -> -+- (alternate);
2314 -> +-+ (alternate);
2341 -> ++- (quasi-alternate);
2413 -> +-+ (alternate);
2431 -> +-- (quasi-alternate);
3124 -> -++ (quasi-alternate);
3142 -> -+- (alternate);
3214 -> --+ (quasi-alternate);
3241 -> -+- (alternate);
3412 -> +-+ (alternate);
3421 -> +-- (quasi-alternate);
4123 -> -++ (quasi-alternate);
4132 -> -+- (alternate);
4213 -> --+ (quasi-alternate);
4231 -> -+- (alternate);
4312 -> --+ (quasi-alternate);
4321 -> --- (neither alternate nor quasi-alternate).
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").
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).
(End)

Maple

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

Mathematica

a[ n_] := If[ n < 0, 0, n! SeriesCoefficient[ (1 - 2 Cos[x]) / (1 - Sin[x]), {x, 0, n}]; (* Michael Somos, Aug 28 2013 *)
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 *)
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 *)

Prog

(PARI) x='x+O('x^99); Vec(serlaplace((1-2*cos(x))/(1-sin(x))))
(Python)
from mpmath import polylog, j, mp
mp.dps=20
def a(n): return -1 if n==0 else int(2*abs(polylog(-n - 1, j)) - 4*abs(polylog(-n, j)))
print([a(n) for n in range(23)])  # Indranil Ghosh, Jul 02 2017
(Python)
from itertools import count, islice, accumulate
def A000708_gen(): # generator of terms
    yield -1
    blist = (0, 1)
    for n in count(2):
        yield -2*blist[-1]+(blist:=tuple(accumulate(reversed(blist), initial=0)))[-1]
A000708_list = list(islice(A000708_gen(), 40)) # Chai Wah Wu, Jun 09-11 2022

Crossrefs

Apart from initial terms, equals (1/2)*A001758. A diagonal of A008970.

Cf. A000111, A001250, A008303, A059427.

Sequence in context: A292034 A108982 A059724 * A027248 A192481 A020090

Adjacent sequences: A000705 A000706 A000707 * A000709 A000710 A000711

Keyword

sign

Author

N. J. A. Sloane

Extensions

More terms from Barbara Haas Margolius (margolius(AT)math.csuohio.edu), Mar 12 2001

Corrected and extended by T. D. Noe, Oct 25 2006

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

Status

approved