|
|
A000757
|
|
Number of cyclic permutations of [n] with no i -> i+1 (mod n).
(Formerly M4521 N1915)
|
|
25
|
|
|
1, 0, 0, 1, 1, 8, 36, 229, 1625, 13208, 120288, 1214673, 13469897, 162744944, 2128047988, 29943053061, 451123462673, 7245940789072, 123604151490592, 2231697509543361, 42519034050101745, 852495597142800376
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,6
|
|
REFERENCES
|
Ch. A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC, Boca Raton, Florida, 2002, pp. 182, 183, Table 5.6.
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).
R. P. Stanley, Space Programs Summary. Jet Propulsion Laboratory, California Institute of Technology, Pasadena, California, Vol. 37-40-4 (1966), pp. 208-214.
R. P. Stanley, Enumerative Combinatorics I, Chap. 2, Exercise 8, p. 88.
N. Ya. Vilenkin, Combinatorics, pp. 56-57, Q_n = a(n), n >= 3. Academic Press, 1971. On the Merry Go-Round.
|
|
LINKS
|
R. P. Stanley, Permutations with no runs of length 2, Space Programs Summary. Jet Propulsion Laboratory, California Institute of Technology, Pasadena, California, Vol. 37-40-4 (1966), pp. 208-214. [Annotated scanned copy]
|
|
FORMULA
|
a(n) = (-1)^n + Sum_{k=0..n-1} (-1)^k*binomial(n, k)*(n-k-1)!;
e.g.f.: (1 - log(1 - x)) / e^x;
a(n) = (n-3) * a(n-1) + (n-2) * (2*a(n-2) + a(n-3)).
a(n) = (n-2) * a(n-1) + (n-1) * a(n-2) - (-1)^n, if n > 0.
a(n) = n-th forward difference of [1, 1, 1, 2, 6, 24, ...] (factorials A000142 with 1 prepended). - Michael Somos, Mar 28 2011
a(n) = Sum_{j=3..n} (-1)^(n-j)*D(j-1), n >= 3, with the derangements numbers (subfactorials) D(n) = A000166(n).
a(n) ~ exp(-1)*(n-1)! * (1 - 1/n + 1/n^3 + 1/n^4 - 2/n^5 - 9/n^6 - 9/n^7 + 50/n^8 + 267/n^9 + 413/n^10 + ...), numerators are A000587. - Vaclav Kotesovec, Jul 03 2016
|
|
EXAMPLE
|
a(4)=1 because from the 4!/4=6 circular permutations of n=4 elements (1,2,3,4), (1,4,3,2), (1,3,4,2),(1,2,4,3), (1,4,2,3) and (1,3,2,4) only (1,4,3,2) has no successor pair (i,i+1). Note that (4,1) is also a successor pair. - Wolfdieter Lang, Jan 21 2008
a(3) = 1 = 2! - 3*1! + 3*0! - 1. a(4) = 1 = 3! - 4*2! + 6*1! - 4*0! + 1. - Michael Somos, Mar 28 2011
G.f. = 1 + x^3 + x^4 + 8*x^5 + 36*x^6 + 229*x^7 + 1625*x^8 + 13208*x^9 + ...
|
|
MATHEMATICA
|
|
|
PROG
|
(PARI) {a(n) = if( n<0, 0, (-1)^n + sum( k=0, n-1, (-1)^k * binomial( n, k) * (n - k - 1)!))}; /* Michael Somos, Jun 21 2002 */
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|