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
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 *)
a[0]:=1; a[1]:=1; a[n_]:=a[n]=1/(n (n-1)) Sum[a[n-1-k] a[k] k, {k, 1, n-1}]; Join[{a[0], a[1]}, Map[2 #! a[#]&, Range[2, 24]]] (* Oliver Seipel, May 27 2024 *)
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]
(Python)
from sympy import bernoulli, euler
def A001250(n): return 1 if n<2 else abs(((1<<n+1)-1<<n+1)*bernoulli(n+1)//(n+1) if n&1 else euler(n))<<1 # Chai Wah Wu, Nov 13 2024
CROSSREFS
The version for permutations of prime indices is A345164.
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).
Cf. A000041, A003242, A032020, A056986, A261962, A325534, A325535, A335452, A344652, A344740, A345165.
Row sums of A104345.
KEYWORD
nonn
AUTHOR
EXTENSIONS
Edited by Max Alekseyev, May 04 2012
a(0)=1 prepended by Alois P. Heinz, Nov 29 2015
STATUS
approved