|
|
A000387
|
|
Rencontres numbers: number of permutations of [n] with exactly two fixed points.
(Formerly M4138 N1716)
|
|
25
|
|
|
0, 0, 1, 0, 6, 20, 135, 924, 7420, 66744, 667485, 7342280, 88107426, 1145396460, 16035550531, 240533257860, 3848532125880, 65425046139824, 1177650830516985, 22375365779822544, 447507315596451070, 9397653627525472260, 206748379805560389951
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,5
|
|
COMMENTS
|
Also: odd permutations of length n with no fixed points. - Martin Wohlgemuth (mail(AT)matroid.com), May 31 2003
Also number of cycles of length 2 in all derangements of [n]. Example: a(4)=6 because in the derangements of [4], namely (1432), (1342), (13)(24), (1423), (12)(34), (1243), (1234), (1324), and (14)(23), we have altogether 6 cycles of length 2. - Emeric Deutsch, Mar 31 2009
|
|
REFERENCES
|
A. Kaufmann, Introduction à la combinatorique en vue des applications, Dunod, Paris, 1968 (see p. 92).
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 65.
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).
|
|
LINKS
|
|
|
FORMULA
|
a(n) = Sum_{j=2..n-2} (-1)^j*n!/(2!*j!) = A008290(n,2).
a(n) = (n!/2) * Sum_{i=0..n-2} ((-1)^i)/i!.
a(n) = n*a(n-1) + (-1^n)*n*(n-1)/2, a(0) = 0. - Chai Wah Wu, Sep 23 2014
O.g.f.: (1/2)*Sum_{k>=2} k!*x^k/(1 + x)^(k+1). - Ilya Gutkovskiy, Apr 13 2017
D-finite with recurrence +(-n+2)*a(n) +n*(n-3)*a(n-1) +n*(n-1)*a(n-2)=0. - R. J. Mathar, Jul 06 2023
|
|
EXAMPLE
|
a(4)=6 because we have 1243, 1432, 1324, 4231, 3214, and 2134. - Emeric Deutsch, Mar 31 2009
|
|
MAPLE
|
A000387 := n -> (-1)^n*(hypergeom([-n, 1], [], 1)+n-1)/2:
|
|
MATHEMATICA
|
Table[Subfactorial[n - 2]*Binomial[n, 2], {n, 0, 22}] (* Zerinvary Lajos, Jul 10 2009 *)
|
|
PROG
|
(Python)
for n in range(201):
x, m = x*n + m*(n*(n-1)//2), -m
(PARI) my(x='x+O('x^33)); concat([0, 0], Vec( serlaplace(exp(-x)/(1-x)*(x^2/2!)) ) ) \\ Joerg Arndt, Feb 19 2014
(PARI) a(n) = ( n!*sum(r=2, n, (-1)^r/r!) - (-1)^(n-1)*(n-1))/2; \\ Michel Marcus, Apr 22 2016
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|