A000757 Number of cyclic permutations of [n] with no i -> i+1 (mod n). (Formerly M4521 N1915)

1, 0, 0, 1, 1, 8, 36, 229, 1625, 13208, 120288, 1214673, 13469897, 162744944, 2128047988, 29943053061, 451123462673, 7245940789072, 123604151490592, 2231697509543361, 42519034050101745, 852495597142800376

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

Vincenzo Librandi, Table of n, a(n) for n = 0..200

Roland Bacher, Counting Packings of Generic Subsets in Finite Groups, Electr. J. Combinatorics, 19 (2012), #P7. - N. J. A. Sloane, Feb 06 2013

Bhadrachalam Chitturi and Krishnaveni K S, Adjacencies in Permutations, arXiv preprint arXiv:1601.04469 [cs.DM], 2016.

S. M. Jacob, The enumeration of the Latin rectangle of depth three..., Proc. London Math. Soc., 31 (1928), 329-336.

R. Moreno, L. M. Rivera, Blocks in Cycles and k-commuting Permutations, arXiv preprint arXiv:1306.5708 [math.CO], 2013.

Luis Manuel Rivera, Integer sequences and k-commuting permutations, arXiv preprint arXiv:1406.3081 [math.CO], 2014.

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

From Michael Somos, Jun 21 2002: (Start)

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) = (-1)^n + A002741(n). (End)

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) + a(n+1) = A000166(n). - Aaron Meyerowitz, Feb 08 2014

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

a[n_] := (-1)^n + Sum[(-1)^k*n!/((n-k)*k!), {k, 0, n-1}]; Table[a[n], {n, 0, 21}] (* Jean-François Alcover, Aug 30 2011, after Michael 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

Extensions

Better description from Len Smiley

Additional comments from Michael Somos, Jun 21 2002

Status

approved