|
| |
|
|
A001250
|
|
Number of alternating permutations of order n.
(Formerly M1235 N0472)
|
|
37
|
|
|
|
1, 1, 2, 4, 10, 32, 122, 544, 2770, 15872, 101042, 707584, 5405530, 44736512, 398721962, 3807514624, 38783024290, 419730685952, 4809759350882, 58177770225664, 740742376475050, 9902996106248192, 138697748786275802, 2030847773013704704, 31029068327114173810
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
For n>1, a(n) is the number of permutations of order n with the length of longest run equal 2.
Boustrophedon transform of the Euler numbers (A000111). [Berry et al., 2013] - N. J. A. Sloane, Nov 18 2013
Number of inversion sequences of length n where all consecutive subsequences i,j,k satisfy i >= j < k or i < j >= k. a(4) = 10: 0010, 0011, 0020, 0021, 0022, 0101, 0102, 0103, 0112, 0113. - Alois P. Heinz, Oct 16 2019
|
|
|
REFERENCES
|
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 261.
C. K. Cook, M. R. Bacon, and R. A. Hillman, Higher-order Boustrophedon transforms ..., Fib. Q., 55 (No. 3, 2017), 201-208.
F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 262.
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
|
Max Alekseyev and Alois P. Heinz, Table of n, a(n) for n = 0..500 (terms n=1..100 from Max Alekseyev)
Max A. Alekseyev, On the number of permutations with bounded run lengths, arXiv:1205.4581 [math.CO], 2012-2013.
Désiré André, 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, Ann. Sci. Ecole Norm. Sup., 3, no. 1 (1884), 121-135.
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.
Désiré André, Mémoire sur les séquences des permutations circulaires, Bulletin de la S. M. F., tome 23 (1895), pp. 122-184.
Stefano Barbero, Umberto Cerruti, Nadir Murru, Some combinatorial properties of the Hurwitz series ring arXiv:1710.05665 [math.NT], 2017.
D. Berry, J. Broom, D. Dixon, A. Flaherty, Umbral Calculus and the Boustrophedon Transform, 2013.
C. Davis, Problem 4755, Amer. Math. Monthly, 64 (1957) 596; solution by W. J. Blundon, 65 (1958), 533-534.
Chandler Davis, Problem 4755: A Permutation Problem, Amer. Math. Monthly, 64 (1957) 596; solution by W. J. Blundon, 65 (1958), 533-534. [Denoted by P_n in solution.] [Annotated scanned copy]
S. Kitaev, Multi-avoidance of generalized patterns, Discrete Math., 260 (2003), 89-100. (See p. 100.)
S. T. Thompson, Problem E754: Skew Ordered Sequences, Amer. Math. Monthly, 54 (1947), 416-417. [Annotated scanned copy]
Eric Weisstein's World of Mathematics, Alternating Permutation
|
|
|
FORMULA
|
a(n) = coefficient of x^(n-1)/(n-1)! in power series expansion of (tan(x) + sec(x))^2 = (tan(x)+1/cos(x))^2.
a(n) = coefficient of x^n/n! in power series expansion of 2*(tan(x) + sec(x)) - 2 - x. - Michael Somos, Feb 05 2011
For n>1, a(n) = 2 * A000111(n). - Michael Somos, Mar 19 2011
a(n) = 4*|Li_{-n}(i)|-[n=1] = sum_{m=0...n/2} (-1)^m*2^{1-k}*sum_{j=0...k} binomial(k,j)*(-1)^j*(k-2*j)^(n+1)/k - [n=1], where k = k(m) = n+1-2*m and [n=1] equals 1 if n=1 and zero else; Li denotes the polylogarithm (and i^2 = -1). - M. F. Hasler, May 20 2012
From Sergei N. Gladkovskii, Jun 18 2012: (Start)
Let E(x) = 2/(1-sin(x))-1 (essentially the e.g.f.), then
E(x) = -1 + 2*(-1/x + 1/(1-x)/x- x^3/((1-x)*((1-x)*G(0) + x^2))) where G(k)= (2*k+2)*(2*k+3)-x^2+(2*k+2)*(2*k+3)*x^2/G(k+1); (continued fraction, Euler's 1st kind, 1-step).
E(x) = -1 + 2*( -1/x + 1/(1-x)/x- x^3/((1-x)*((1-x)*G(0) + x^2)) ) where G(k)= 8*k+6-x^2/(1 + (2*k+2)*(2*k+3)/G(k+1)); (continued fraction, Euler's 2nd kind, 2-step).
E(x) = (tan(x) + sec(x))^2 = -1 + 2/(1-x*G(0)) where G(k)= 1 - x^2/(2*(2*k+1)*(4*k+3) - 2*x^2*(2*k+1)*(4*k+3)/(x^2 - 4*(k+1)*(4*k+5)/G(k+1))); (continued fraction, 3rd kind, 3-step).
(End).
G.f.: conjecture: 2*T(0)/(1-x) -1, where T(k) = 1 - x^2*(k+1)*(k+2)/(x^2*(k+1)*(k+2) - 2*(1-x*(k+1))*(1-x*(k+2))/Q(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Nov 19 2013
a(n) ~ 2^(n+3) * n! / Pi^(n+1). - Vaclav Kotesovec, Sep 06 2014
a(n) = sum(A109449(n-1,k)*A000111(k): k = 0..n-1). - Reinhard Zumkeller, Sep 17 2014
|
|
|
EXAMPLE
|
1 + x + 2*x^2 + 4*x^3 + 10*x^4 + 32*x^5 + 122*x^6 + 544*x^7 + 2770*x^8 + ...
|
|
|
MAPLE
|
# With Eulerian polynomials:
A := (n, x) -> `if`(n<2, 1/2/(1+I)^(1-n), add(add((-1)^j*binomial(n+1, j)*(m+1-j)^n, j=0..m)*x^m, m=0..n-1)):
A001250 := n -> 2*(I-1)^(1-n)*exp(I*(n-1)*Pi/2)*A(n, I);
seq(A001250(i), i=0..22); # Peter Luschny, May 27 2012
# second Maple program:
b:= proc(u, o) option remember;
`if`(u+o=0, 1, add(b(o-1+j, u-j), j=1..u))
end:
a:= n-> `if`(n<2, 1, 2)*b(n, 0):
seq(a(n), n=0..30); # Alois P. Heinz, Nov 29 2015
|
|
|
MATHEMATICA
|
a[n_] := 4*Abs[PolyLog[-n, I]]; a[0] = a[1] = 1; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Jan 09 2016, after M. F. Hasler *)
|
|
|
PROG
|
(PARI) {a(n) = local(v=[1], t); if( n<0, 0, for( k=2, n+3, t=0; v = vector( k, i, if( i>1, t += v[k+1 - i]))); v[3])} /* Michael Somos, Feb 03 2004 */
(PARI) {a(n) = if( n<0, 0, n! * polcoeff( (tan(x + x * O(x^n)) + 1 / cos(x + x * O(x^n)))^2, n))} /* Michael Somos, Feb 05 2011 */
(PARI) A001250(n)=sum(m=0, n\2, my(k); (-1)^m*sum(j=0, k=n+1-2*m, binomial(k, j)*(-1)^j*(k-2*j)^(n+1))/k>>k)*2-(n==1) \\ M. F. Hasler, May 19 2012
(PARI) A001250(n)=4*abs(polylog(-n, I))-(n==1) \\ M. F. Hasler, May 20 2012
(Sage) # Algorithm of L. Seidel (1877)
def A001250_list(n) :
R = [1]; A = {-1:0, 0:2}; k = 0; e = 1
for i in (0..n) :
Am = 0; A[k + e] = 0; e = -e
for j in (0..i) : Am += A[k]; A[k] = Am; k += e
if i > 1 : R.append(A[-i//2] if i%2 == 0 else A[i//2])
return R
A001250_list(22) # Peter Luschny, Mar 31 2012
(PARI)
x='x+O('x^66);
egf=2*(tan(x)+1/cos(x))-2-x;
Vec(serlaplace(egf))
/* Joerg Arndt, May 28 2012 */
(Haskell)
a001250 n = if n == 1 then 1 else 2 * a000111 n
-- Reinhard Zumkeller, Sep 17 2014
|
|
|
CROSSREFS
|
Cf. A000111. A diagonal of A010094.
Cf. A001251, A001252, A001253, A010026, A211318, A260786.
Sequence in context: A176006 A263664 A263665 * A013032 A098830 A121277
Adjacent sequences: A001247 A001248 A001249 * A001251 A001252 A001253
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
N. J. A. Sloane
|
|
|
EXTENSIONS
|
Edited by Max Alekseyev, May 04 2012
a(0)=1 prepended by Alois P. Heinz, Nov 29 2015
|
|
|
STATUS
|
approved
|
| |
|
|
