login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001250 Number of alternating permutations of order n.
(Formerly M1235 N0472)
33
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

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 11 04:33 EDT 2020. Contains 335609 sequences. (Running on oeis4.)