%I M4521 N1915 #74 Aug 30 2023 07:28:18

%S 1,0,0,1,1,8,36,229,1625,13208,120288,1214673,13469897,162744944,

%T 2128047988,29943053061,451123462673,7245940789072,123604151490592,

%U 2231697509543361,42519034050101745,852495597142800376

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

%D Ch. A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC, Boca Raton, Florida, 2002, pp. 182, 183, Table 5.6.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D R. P. Stanley, Space Programs Summary. Jet Propulsion Laboratory, California Institute of Technology, Pasadena, California, Vol. 37-40-4 (1966), pp. 208-214.

%D R. P. Stanley, Enumerative Combinatorics I, Chap. 2, Exercise 8, p. 88.

%D N. Ya. Vilenkin, Combinatorics, pp. 56-57, Q_n = a(n), n >= 3. Academic Press, 1971. On the Merry Go-Round.

%H Vincenzo Librandi, <a href="/A000757/b000757.txt">Table of n, a(n) for n = 0..200</a>

%H Roland Bacher, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i3p7">Counting Packings of Generic Subsets in Finite Groups</a>, Electr. J. Combinatorics, 19 (2012), #P7. - _N. J. A. Sloane_, Feb 06 2013

%H Bhadrachalam Chitturi and Krishnaveni K S, <a href="https://arxiv.org/abs/1601.04469">Adjacencies in Permutations</a>, arXiv preprint arXiv:1601.04469 [cs.DM], 2016.

%H S. M. Jacob, <a href="http://dx.doi.org/10.1112/plms/s2-31.1.329">The enumeration of the Latin rectangle of depth three...</a>, Proc. London Math. Soc., 31 (1928), 329-336.

%H R. Moreno, L. M. Rivera, <a href="http://arxiv.org/abs/1306.5708">Blocks in Cycles and k-commuting Permutations</a>, arXiv preprint arXiv:1306.5708 [math.CO], 2013.

%H Luis Manuel Rivera, <a href="http://arxiv.org/abs/1406.3081">Integer sequences and k-commuting permutations</a>, arXiv preprint arXiv:1406.3081 [math.CO], 2014.

%H R. P. Stanley, <a href="/A000757/a000757.pdf">Permutations with no runs of length 2</a>, Space Programs Summary. Jet Propulsion Laboratory, California Institute of Technology, Pasadena, California, Vol. 37-40-4 (1966), pp. 208-214. [Annotated scanned copy]

%F From _Michael Somos_, Jun 21 2002: (Start)

%F a(n) = (-1)^n + Sum_{k=0..n-1} (-1)^k*binomial(n, k)*(n-k-1)!;

%F e.g.f.: (1 - log(1 - x)) / e^x;

%F a(n) = (n-3) * a(n-1) + (n-2) * (2*a(n-2) + a(n-3)).

%F a(n) = (n-2) * a(n-1) + (n-1) * a(n-2) - (-1)^n, if n > 0.

%F a(n) = (-1)^n + A002741(n). (End)

%F a(n) = n-th forward difference of [1, 1, 1, 2, 6, 24, ...] (factorials A000142 with 1 prepended). - _Michael Somos_, Mar 28 2011

%F a(n) = Sum_{j=3..n} (-1)^(n-j)*D(j-1), n >= 3, with the derangements numbers (subfactorials) D(n) = A000166(n).

%F a(n) + a(n+1) = A000166(n). - _Aaron Meyerowitz_, Feb 08 2014

%F 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

%e 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

%e 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

%e G.f. = 1 + x^3 + x^4 + 8*x^5 + 36*x^6 + 229*x^7 + 1625*x^8 + 13208*x^9 + ...

%t 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_ *)

%o (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 */

%Y Cf. A000142, A002741.

%K nonn,easy,nice

%O 0,6

%A _N. J. A. Sloane_

%E Better description from _Len Smiley_

%E Additional comments from _Michael Somos_, Jun 21 2002