A001250 Number of alternating permutations of order n. (Formerly M1235 N0472)

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

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.

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

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, and Nadir Murru, Some combinatorial properties of the Hurwitz series ring arXiv:1710.05665 [math.NT], 2017.

D. Berry, J. Broom, D. Dixon, and A. Flaherty, Umbral Calculus and the Boustrophedon Transform, 2013.

C. K. Cook, M. R. Bacon, and R. A. Hillman, Higher-order Boustrophedon transforms for certain well-known sequences, Fib. Q., 55(3) (2017), 201-208.

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_{k=0..n-1} A109449(n-1,k)*A000111(k). - 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 + ...
From Gus Wiseman, Jun 21 2021: (Start)
The a(0) = 1 through a(4) = 10 permutations:
  ()  (1)  (1,2)  (1,3,2)  (1,3,2,4)
           (2,1)  (2,1,3)  (1,4,2,3)
                  (2,3,1)  (2,1,4,3)
                  (3,1,2)  (2,3,1,4)
                           (2,4,1,3)
                           (3,1,4,2)
                           (3,2,4,1)
                           (3,4,1,2)
                           (4,1,3,2)
                           (4,2,3,1)
(End)

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 *)
Table[Length[Select[Permutations[Range[n]], And@@(!(OrderedQ[#]||OrderedQ[Reverse[#]])&/@Partition[#, 3, 1])&]], {n, 8}] (* Gus Wiseman, Jun 21 2021 *)

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
(Python)
from itertools import accumulate, islice
def A001250_gen(): # generator of terms
    yield from (1, 1)
    blist = (0, 2)
    while True:
        yield (blist := tuple(accumulate(reversed(blist), initial=0)))[-1]
A001250_list = list(islice(A001250_gen(), 40)) # Chai Wah Wu, Jun 09-11 2022

Crossrefs

Cf. A000111. A diagonal of A010094.

Cf. A001251, A001252, A001253, A010026, A211318, A260786.

The version for permutations of prime indices is A345164.

The version for compositions is A025047, ranked by A345167.

The version for patterns is A345194.

A049774 counts permutations avoiding adjacent (1,2,3).

A344614 counts compositions avoiding adjacent (1,2,3) and (3,2,1).

A344615 counts compositions avoiding the weak adjacent pattern (1,2,3).

A344654 counts partitions without a wiggly permutation, ranked by A344653.

A345170 counts partitions with a wiggly permutation, ranked by A345172.

A345192 counts non-wiggly compositions, ranked by A345168.

Cf. A000041, A003242, A032020, A056986, A261962, A325534, A325535, A335452, A344652, A344740, A345165.

Row sums of A104345.

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