|
| |
|
|
A001250
|
|
Number of alternating permutations of order n.
(Formerly M1235 N0472)
|
|
17
|
|
|
|
1, 2, 4, 10, 32, 122, 544, 2770, 15872, 101042, 707584, 5405530, 44736512, 398721962, 3807514624, 38783024290, 419730685952, 4809759350882, 58177770225664, 740742376475050, 9902996106248192, 138697748786275802
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
For n>1, a(n) is the number of permutations of order n with the length of longest run equal 2.
|
|
|
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.
C. Davis, Problem 4755, Amer. Math. Monthly, 64 (1957) 596; solution by W. J. Blundon, 65 (1958), 533-534.
S. Kitaev, Multi-avoidance of generalized patterns, Discrete Math., 260 (2003), 89-100. (See p. 100.)
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, Table of n, a(n) for n = 1..100
Max A. Alekseyev, On the number of permutations with bounded runs length, arXiv, May 22, 2012.
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).
|
|
|
EXAMPLE
|
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=1, 1/2, 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=1..22); # Peter Luschny, May 27 2012
|
|
|
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, March 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 */
|
|
|
CROSSREFS
|
Cf. A000111. A diagonal of A010094.
Cf. A001251, A001252, A001253, A010026, A211318.
Sequence in context: A120017 A000736 A176006 * 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
|
|
|
STATUS
|
approved
|
| |
|
|
