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
KEYWORD
nonn,easy,nice
AUTHOR
EXTENSIONS
Better description from Len Smiley
Additional comments from Michael Somos, Jun 21 2002
STATUS
approved