|
| |
|
|
A000757
|
|
Number of cyclic permutations of [n] with no i->i+1 (mod n)
(Formerly M4521 N1915)
|
|
13
| |
|
|
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; internal format)
|
|
|
|
OFFSET
| 0,6
|
|
|
REFERENCES
| Ch. A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC, Boca Raton, Florida, 2002, p. 182 and p. 183, Table 5.6.
S. M. Jacob, The enumeration of the Latin rectangle of depth three..., Proc. London Math. Soc., 31 (1928), 329-336.
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.
|
|
|
FORMULA
| a(n) = (-1)^n + sum((-1)^k*binomial(n, k)*(n-k-1)!, k=0..n-1); e.g.f.: (1 - ln(1 - x)) / e^x; a(n) = (n-3) * a(n-1) + (n-2) * (2*a(n-2) + a(n-3)). - Michael Somos Jun 21 2002
a(n) = (n-2) * a(n-1) + (n-1) * a(n-2) - (-1)^n, n>0. a(n) = (-1)^n + A002741(n). - Michael Somos Jun 21 2002
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(((-1)^(n-j))*D(j-1),j=3..n), n>=3, with the derangements numbers (subfactorials) D(n)=A000166(n).
|
|
|
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. W. 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
|
|
|
MATHEMATICA
| a[n_] = (-1)^n + Sum[(-1)^k*n!/((n-k)*k!), {k, 0, n-1}]; Table[a[n], {n, 0, 21}] (* From Jean-François Alcover, Aug 30 2011, after M. Somos *)
|
|
|
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
| Cf. A000142, A002741.
Sequence in context: A001555 A032770 A032794 * A126756 A203297 A181072
Adjacent sequences: A000754 A000755 A000756 * A000758 A000759 A000760
|
|
|
KEYWORD
| nonn,easy,nice
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| Better description from Len Smiley (smiley(AT)math.uaa.alaska.edu)
Additional comments from Michael Somos, Jun 21, 2002
|
| |
|
|
