A000387 Rencontres numbers: number of permutations of [n] with exactly two fixed points.

0, 0, 1, 0, 6, 20, 135, 924, 7420, 66744, 667485, 7342280, 88107426, 1145396460, 16035550531, 240533257860, 3848532125880, 65425046139824, 1177650830516985, 22375365779822544, 447507315596451070, 9397653627525472260, 206748379805560389951

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy

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

Examples

			a(4)=6 because we have 1243, 1432, 1324, 4231, 3214, and 2134. - _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

• Chai Wah Wu, Table of n, a(n) for n = 0..200 (first 100 terms from T. D. Noe)
• Bashir Ali and A. Umar, Some combinatorial properties of the alternating group, Southeast Asian Bulletin Math. 32 (2008), 823-830.
• FindStat - Combinatorial Statistic Finder, The number of fixed points of a permutation
• G. Gordon and E. McMahon, Moving faces to other places: facet derangements, Amer. Math. Monthly, 117 (2010), 865-88.
• Piotr Miska, Arithmetic Properties of the Sequence of Derangements and its Generalizations, arXiv:1508.01987 [math.NT], 2015. (see Chapter 5 p. 44)
• J. M. Thomas, The number of even and odd absolute permutations of n letters, Bull. Amer. Math. Soc. 31 (1925), 303-304.
• M. Wohlgemuth, Derangements revisited
• Index entries for sequences related to permutations with fixed points

Crossrefs

Column k=2 of A008290.

Cf. A003221.

A diagonal of A008291.

Cf. A170942.

Programs

Maple

A000387:= n-> -add((n-1)!*add((-1)^k/(k-1)!, j=0..n-1), k=1..n-1)/2: seq(A000387(n), n=0..25); # Zerinvary Lajos, May 18 2007
A000387 := n -> (-1)^n*(hypergeom([-n,1],[],1)+n-1)/2:
seq(simplify(A000387(n)), n=0..22); # Peter Luschny, May 09 2017

Mathematica

Table[Subfactorial[n - 2]*Binomial[n, 2], {n, 0, 22}] (* Zerinvary Lajos, Jul 10 2009 *)

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

Python

A145221_list, m, x = [], 1, 0
for n in range(201):
    x, m = x*n + m*(n*(n-1)//2), -m
    A145221_list.append(x) # Chai Wah Wu, Sep 23 2014

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) = A000166(n) - A003221(n).

a(n) = A000166(n-2)*binomial(n, 2). - David Wasserman, Aug 13 2004

E.g.f.: z^2*exp(-z)/(2*(1-z)). - Emeric Deutsch, Jul 22 2009

a(n) ~ n!*exp(-1)/2. - Steven Finch, Mar 11 2022

a(n) = n*a(n-1) + (-1^n)*n*(n-1)/2, a(0) = 0. - Chai Wah Wu, Sep 23 2014

a(n) = A003221(n) + (-1)^n*(n-1) (see Miska). - Michel Marcus, Aug 11 2015

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

Extensions

Prepended a(0)=a(1)=0, Joerg Arndt, Apr 22 2016