login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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, p. 182 and p. 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.

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

a(n) = (-1)^n + sum((-1)^k*binomial(n, k)*(n-k-1)!, k=0..n-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)). - Michael Somos, Jun 21 2002

a(n) = (n-2) * a(n-1) + (n-1) * a(n-2) - (-1)^n, if 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).

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 17 22:48 EDT 2018. Contains 316297 sequences. (Running on oeis4.)