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

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

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

Examples

			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 + ...
		

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 and 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]

Crossrefs

Cf. A000142, A000166, A002741.

Programs

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 *)

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 */

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

Extensions

Better description from Len Smiley

Additional comments from Michael Somos, Jun 21 2002