|
%I M1235 N0472 #144 Oct 30 2023 08:16:02
%S 1,1,2,4,10,32,122,544,2770,15872,101042,707584,5405530,44736512,
%T 398721962,3807514624,38783024290,419730685952,4809759350882,
%U 58177770225664,740742376475050,9902996106248192,138697748786275802,2030847773013704704,31029068327114173810
%N Number of alternating permutations of order n.
%C For n>1, a(n) is the number of permutations of order n with the length of longest run equal 2.
%C Boustrophedon transform of the Euler numbers (A000111). [Berry et al., 2013] - _N. J. A. Sloane_, Nov 18 2013
%C 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
%D L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 261.
%D F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 262.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Alois P. Heinz, <a href="/A001250/b001250.txt">Table of n, a(n) for n = 0..500</a> (terms n=1..100 from Max Alekseyev)
%H Max A. Alekseyev, <a href="http://arxiv.org/abs/1205.4581">On the number of permutations with bounded run lengths</a>, arXiv:1205.4581 [math.CO], 2012-2013.
%H Désiré André, <a href="http://sites.mathdoc.fr/JMPA/PDF/JMPA_1881_3_7_A10_0.pdf">Sur les permutations alternées</a>, J. Math. Pur. Appl., 7 (1881), 167-184.
%H Désiré André, <a href="https://doi.org/10.24033/asens.235">Étude sur les maxima, minima et séquences des permutations</a>, Ann. Sci. Ecole Norm. Sup., 3, no. 1 (1884), 121-135.
%H Désiré André, <a href="http://sites.mathdoc.fr/JMPA/PDF/JMPA_1895_5_1_A7_0.pdf">Mémoire sur les permutations quasi-alternées</a>, Journal de mathématiques pures et appliquées 5e série, tome 1 (1895), 315-350.
%H Désiré André, <a href="https://doi.org/10.24033/bsmf.519">Mémoire sur les séquences des permutations circulaires</a>, Bulletin de la S. M. F., tome 23 (1895), pp. 122-184.
%H Stefano Barbero, Umberto Cerruti, and Nadir Murru, <a href="https://arxiv.org/abs/1710.05665">Some combinatorial properties of the Hurwitz series ring</a> arXiv:1710.05665 [math.NT], 2017.
%H D. Berry, J. Broom, D. Dixon, and A. Flaherty, <a href="https://www.math.lsu.edu/system/files/DeAngelisProject2.pdf">Umbral Calculus and the Boustrophedon Transform</a>, 2013.
%H C. K. Cook, M. R. Bacon, and R. A. Hillman, <a href="https://www.fq.math.ca/Papers1/55-3/CookBaconHillman01222017.pdf">Higher-order Boustrophedon transforms for certain well-known sequences</a>, Fib. Q., 55(3) (2017), 201-208.
%H C. Davis, <a href="https://www.jstor.org/stable/2308848">Problem 4755</a>, Amer. Math. Monthly, 64 (1957) 596; <a href="https://www.jstor.org/stable/2308592">solution</a> by W. J. Blundon, 65 (1958), 533-534.
%H Chandler Davis, <a href="/A000111/a000111_2.pdf">Problem 4755: A Permutation Problem</a>, Amer. Math. Monthly, 64 (1957) 596; solution by W. J. Blundon, 65 (1958), 533-534. [Denoted by P_n in solution.] [Annotated scanned copy]
%H S. Kitaev, <a href="http://dx.doi.org/10.1016/S0012-365X(02)00452-1">Multi-avoidance of generalized patterns</a>, Discrete Math., 260 (2003), 89-100. (See p. 100.)
%H S. T. Thompson, <a href="/A260786/a260786.pdf">Problem E754: Skew Ordered Sequences</a>, Amer. Math. Monthly, 54 (1947), 416-417. [Annotated scanned copy]
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/AlternatingPermutation.html">Alternating Permutation</a>
%F 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.
%F a(n) = coefficient of x^n/n! in power series expansion of 2*(tan(x) + sec(x)) - 2 - x. - _Michael Somos_, Feb 05 2011
%F For n>1, a(n) = 2 * A000111(n). - _Michael Somos_, Mar 19 2011
%F 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
%F From _Sergei N. Gladkovskii_, Jun 18 2012: (Start)
%F Let E(x) = 2/(1-sin(x))-1 (essentially the e.g.f.), then
%F 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).
%F 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).
%F 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).
%F (End)
%F 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
%F a(n) ~ 2^(n+3) * n! / Pi^(n+1). - _Vaclav Kotesovec_, Sep 06 2014
%F a(n) = Sum_{k=0..n-1} A109449(n-1,k)*A000111(k). - _Reinhard Zumkeller_, Sep 17 2014
%e 1 + x + 2*x^2 + 4*x^3 + 10*x^4 + 32*x^5 + 122*x^6 + 544*x^7 + 2770*x^8 + ...
%e From _Gus Wiseman_, Jun 21 2021: (Start)
%e The a(0) = 1 through a(4) = 10 permutations:
%e () (1) (1,2) (1,3,2) (1,3,2,4)
%e (2,1) (2,1,3) (1,4,2,3)
%e (2,3,1) (2,1,4,3)
%e (3,1,2) (2,3,1,4)
%e (2,4,1,3)
%e (3,1,4,2)
%e (3,2,4,1)
%e (3,4,1,2)
%e (4,1,3,2)
%e (4,2,3,1)
%e (End)
%p # With Eulerian polynomials:
%p 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)):
%p A001250 := n -> 2*(I-1)^(1-n)*exp(I*(n-1)*Pi/2)*A(n,I);
%p seq(A001250(i), i=0..22); # _Peter Luschny_, May 27 2012
%p # second Maple program:
%p b:= proc(u, o) option remember;
%p `if`(u+o=0, 1, add(b(o-1+j, u-j), j=1..u))
%p end:
%p a:= n-> `if`(n<2, 1, 2)*b(n, 0):
%p seq(a(n), n=0..30); # _Alois P. Heinz_, Nov 29 2015
%t 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_ *)
%t Table[Length[Select[Permutations[Range[n]],And@@(!(OrderedQ[#]||OrderedQ[Reverse[#]])&/@Partition[#,3,1])&]],{n,8}] (* _Gus Wiseman_, Jun 21 2021 *)
%o (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 */
%o (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 */
%o (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
%o (PARI) A001250(n)=4*abs(polylog(-n,I))-(n==1) \\ _M. F. Hasler_, May 20 2012
%o (Sage) # Algorithm of L. Seidel (1877)
%o def A001250_list(n) :
%o R = [1]; A = {-1:0, 0:2}; k = 0; e = 1
%o for i in (0..n) :
%o Am = 0; A[k + e] = 0; e = -e
%o for j in (0..i) : Am += A[k]; A[k] = Am; k += e
%o if i > 1 : R.append(A[-i//2] if i%2 == 0 else A[i//2])
%o return R
%o A001250_list(22) # _Peter Luschny_, Mar 31 2012
%o (PARI)
%o x='x+O('x^66);
%o egf=2*(tan(x)+1/cos(x))-2-x;
%o Vec(serlaplace(egf))
%o /* _Joerg Arndt_, May 28 2012 */
%o (Haskell)
%o a001250 n = if n == 1 then 1 else 2 * a000111 n
%o -- _Reinhard Zumkeller_, Sep 17 2014
%o (Python)
%o from itertools import accumulate, islice
%o def A001250_gen(): # generator of terms
%o yield from (1,1)
%o blist = (0,2)
%o while True:
%o yield (blist := tuple(accumulate(reversed(blist),initial=0)))[-1]
%o A001250_list = list(islice(A001250_gen(),40)) # _Chai Wah Wu_, Jun 09-11 2022
%Y Cf. A000111. A diagonal of A010094.
%Y Cf. A001251, A001252, A001253, A010026, A211318, A260786.
%Y The version for permutations of prime indices is A345164.
%Y The version for compositions is A025047, ranked by A345167.
%Y The version for patterns is A345194.
%Y A049774 counts permutations avoiding adjacent (1,2,3).
%Y A344614 counts compositions avoiding adjacent (1,2,3) and (3,2,1).
%Y A344615 counts compositions avoiding the weak adjacent pattern (1,2,3).
%Y A344654 counts partitions without a wiggly permutation, ranked by A344653.
%Y A345170 counts partitions with a wiggly permutation, ranked by A345172.
%Y A345192 counts non-wiggly compositions, ranked by A345168.
%Y Cf. A000041, A003242, A032020, A056986, A261962, A325534, A325535, A335452, A344652, A344740, A345165.
%Y Row sums of A104345.
%K nonn
%O 0,3
%A _N. J. A. Sloane_
%E Edited by _Max Alekseyev_, May 04 2012
%E a(0)=1 prepended by _Alois P. Heinz_, Nov 29 2015
|
