

A000708


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


7



1, 1, 0, 1, 6, 29, 150, 841, 5166, 34649, 252750, 1995181, 16962726, 154624469, 1505035350, 15583997521, 171082318686, 1985148989489, 24279125761950, 312193418011861, 4210755676649046, 59445878286889709, 876726137720576550
(list;
graph;
refs;
listen;
history;
text;
internal format)



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 n2 "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. 260261) 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 socalled "séquences" in permutations defined by Comtet and André are called "alternate runs" (or just "runs"). We discuss these socalled "sequences" below.
We clarify that a(n) is actually onehalf the number of permutations on [n] that have n2 "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 socalled "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 socalled "séquences" ("alternate runs") 78, 81, 125, 543, 36 (see p. 122 in André (1884)).
If in the above permutation we take the difference 87, 18, 21, 52, 45, 34, 63, 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 oneline notation, but not in cycle notation), we form the differences a_2  a_1, a_3  a_2, ..., a_n  a_{n1}, then we get a list of n1 signs (+ or ).
For n >= 2, André (1885) calls a permutation of [n] "alternate" if it has n  1 socalled "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] "quasialternate" if it has n  2 socalled "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 socalled "séquences" ("alternate signs") and 5 < 82 < 81; that is, it is neither alternate nor quasialternate. We can reach the same conclusion by looking at its corresponding list of signs ++++. The permutation is neither alternate nor quasialternate because we have one ++ and one .
On p. 316, André (1885) gives the following two examples of permutations of [8]: 31426587 and 32541768 (using oneline 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 quasialternate (because of a single ). Alternatively, the first one has n1 = 7 socalled "séquences" ("alternate runs")31, 14, 42, 26, 65, 58, 87while the second one has n2 = 6 socalled "séquences" ("alternate runs")32, 25, 541, 17, 76, 68.
Here 2*a(n) is the total number of quasialternate permutations of [n]. Actually, André (1884, 1885) uses P_{n,s} to denote the number of permutations of [n] with exactly s of his socalled "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 quasialternate permutations of [n].
Thus, P_{n,n1} = 2*A_n = 2*A000111(n) = A001250(n) for n >= 2 and P_{n,n2} = 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_{n1,s} + 2*P_{n1,s1} + (ns)*P_{n1,s2} 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 socalled "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é (18401918).
Désiré André, Mémoire sur les permutations alternées, J. Math. Pur. Appl., 7 (1881), 167184.
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), 121134.
Désiré André, Mémoire sur les permutations quasialternées, Journal de mathématiques pures et appliquées 5e série, tome 1 (1895), 315350.
M. 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. 220226.
F. Morley, A generating function for the number of permutations with an assigned number of sequences, Bull. Amer. Math. Soc. 4 (1897), 2328. [Discusses the socalled "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 = n1, where s is the number of the socalled "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 112113 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(n1, i))  4*abs(PolyLog(n, i)) for n > 0, with a(0) = 1.  JeanFranç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 quasialternate and a(3) = 2/2 = 1.
For the permutations of [4] we have:
1234 > +++ (neither alternate nor quasialternate);
1243 > ++ (quasialternate);
1324 > ++ (alternate);
1342 > ++ (quasialternate);
1423 > ++ (alternate);
1432 > + (quasialternate);
2134 > ++ (quasialternate);
2143 > + (alternate);
2314 > ++ (alternate);
2341 > ++ (quasialternate);
2413 > ++ (alternate);
2431 > + (quasialternate);
3124 > ++ (quasialternate);
3142 > + (alternate);
3214 > + (quasialternate);
3241 > + (alternate);
3412 > ++ (alternate);
3421 > + (quasialternate);
4123 > ++ (quasialternate);
4132 > + (alternate);
4213 > + (quasialternate);
4231 > + (alternate);
4312 > + (quasialternate);
4321 >  (neither alternate nor quasialternate).
Thus we have 10 = 2*A000111(4) = A001250(4) alternate permutations of [4] and 2*a(4) = 2*6 = 12 quasialternate permutations of [4]. The remaining 2 permutations (1234 and 4321) have each one socalled "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=2..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}] (* JeanFrançois Alcover, Feb 10 2016, after Paul Curtz *)
Table[If[n == 0, 1, 2 Abs[PolyLog[n1, I]]  4 Abs[PolyLog[n, I]]], {n, 0, 22}] (* JeanFrançois Alcover, Jul 01 2017 *)


PROG

(PARI) x='x+O('x^99); Vec(serlaplace((12*cos(x))/(1sin(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


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



