A000240 Rencontres numbers: number of permutations of [n] with exactly one fixed point.

1, 0, 3, 8, 45, 264, 1855, 14832, 133497, 1334960, 14684571, 176214840, 2290792933, 32071101048, 481066515735, 7697064251744, 130850092279665, 2355301661033952, 44750731559645107, 895014631192902120, 18795307255050944541, 413496759611120779880

Offset: 1

Author

N. J. A. Sloane, Simon Plouffe

Keywords

• nonn
• easy
• nice

Comments

a(n) is also the number of permutations of [n] having no circular succession. A circular succession in a permutation p of [n] is either a pair p(i), p(i+1), where p(i+1)=p(i)+1 or the pair p(n), p(1) if p(1)=p(n)+1. a(4)=8 because we have 1324, 1432, 4132, 2143, 2413, 3214, 3241, and 4321. - Emeric Deutsch, Sep 06 2010

a(n) is also the number of permutations of [n] having no substring in {12, 23, ..., (n-1)n, n1}. For example, a(4) = 8 since we have 1324, 1432, 4213, 2143, 2431, 3214, 3142, 4321 (different from permutations having no circular succession). - Enrique Navarrete, Oct 07 2016

a(n-1) is also the number of permutations of [n] that allow the substring n1 in the set of permutations of [n] having no substring in {12, 23, ..., (n-1)n}. For example, for n=5 the 8 permutations in S5 having no substring in {12,23,34,45} that allow the substring 51 are {51324,51432,25143,24351,35142,32514,42513,43251} (see link). - Enrique Navarrete, Jan 11 2017

From Enrique Navarrete, Mar 25 2017: (Start)

Let D(n,k) be the set of permutations on [n] that for fixed k, 0 < k < n, avoid substrings j(j+k) for 1 <= j <= n - k, and avoid substrings j(j+k) (mod n) for n-k < j <= n. Then the number of permutations in D(n,k) with k relative prime to n, n>=2, is given by a(n). For example, the forbidden substrings in D(4,3) are {14;21,32,43} (the forbidden substrings (mod 4) are written after the semicolon and lie below the diagonal in the chessboard below):

1 2 3 4

1 |||_|x|

2 |x|||_|

3 ||x||_|

4 |||x|_|

_

Then since 4 and 3 are relatively prime, a(4)=8, and the permutations in D(4,3) are 1234, 1342, 2341, 2413, 3124, 3412, 4123, 4231.

For another example, the forbidden substrings in D(8,5) are {16,27,38;41, 52,63,74,85} and the number of permutations in D(8,5) is a(8)=14832 (see the "K-Shift Forbidden Substrings" link).

(End)

Examples

			a(3) = 3 because the permutations of {1,2,3} with exactly one fixed point are the transpositions (1 2), (1 3) and (2 3).
a(4) = 8 because for each element x of {1,2,3,4} there are exactly two permutations which leave only x invariant, namely the two circular permutations of the three remaining numbers, one being the inverse (and the square) of the other. - _M. F. Hasler_, Jan 16 2017
		

References

• Kaufmann, Arnold. "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).
• N. Ya. Vilenkin, Combinatorics, p. 56, eq.(13), F_n = a(n). Academic Press, 1971.

Links

• T. D. Noe, Table of n, a(n) for n=1..100
• Bhadrachalam Chitturi and Krishnaveni K S, Adjacencies in Permutations, arXiv preprint arXiv:1601.04469 [cs.DM], 2016.
• S. K. Das and N. Deo, Rencontres graphs: a family of bipartite graphs, Fib. Quart., Vol. 25, No. 3, August 1987, 250-262.
• FindStat - Combinatorial Statistic Finder, The number of fixed points of a permutation
• I. Kaplansky, Symbolic solution of certain problems in permutations, Bull. Amer. Math. Soc., 50 (1944), 906-914.
• Enrique Navarrete, Forbidden Patterns and the Alternating Derangement Sequence, arXiv:1610.01987 [math.CO], 2016.
• Enrique Navarrete, Generalized K-Shift Forbidden Substrings in Permutations, arXiv:1610.06217 [math.CO], 2016.
• S. M. Tanny, Permutations and successions, J. Combinatorial Theory, Series A, 21 (1976), 196-202.
• Index entries for sequences related to permutations with fixed points

Crossrefs

Cf. A008290, A000166, A000387, A000449, A000475, A129135, etc.

A diagonal of A008291.

Cf. A180188, A170942.

Programs

Maple

G(x):=exp(-x)/(1-x)*x: f[0]:=G(x): for n from 1 to 26 do f[n]:=diff(f[n-1],x) od: x:=0: seq(f[n],n=1..22);# Zerinvary Lajos, Apr 03 2009
A000240 := proc(n)
        n!*add((-1)^k/k!,k=0..n-1) ;
end proc: # R. J. Mathar, Jul 09 2012
a := n -> (-1)^(n-1)*n*hypergeom([1,1-n], [], 1):
seq(simplify(a(n)), n=1..22); # Peter Luschny, May 09 2017

Mathematica

Table[Subfactorial[n]-(-1)^n, {n, 1, 25}] (* Zerinvary Lajos, Jul 10 2009, updated for offset 1 by Jean-François Alcover, Jan 10 2014 *)
Table[n!*Sum[(-1)^k/k!,{k,0,n-1}],{n,1,25}] (* Vaclav Kotesovec, Sep 26 2012 *)
Table[n!*SeriesCoefficient[x*E^(-x)/(1-x),{x,0,n}],{n,1,25}] (* Vaclav Kotesovec, Sep 26 2012 *)
Rest[With[{nn=30},CoefficientList[Series[x Exp[-x]/(1-x),{x,0,nn}],x] Range[0,nn]!]] (* Harvey P. Dale, May 29 2025 *)

PARI

x='x+O('x^66); Vec( serlaplace(x*exp(-x)/(1-x)) ) \\ Joerg Arndt, Feb 19 2014

PARI

a(n,p=vector(n,i,i),s=x->!x)=sum(k=1,n!,#select(s,numtoperm(n,k)-p)==1) \\ For illustrative purpose. #select(...) is almost twice as fast as {p=numtoperm(n,k);sum(i=1,n,p[i]==i)}. - M. F. Hasler, Jan 16 2017

Python

a = 0
for i in range(1, 51):
    a = (a - (-1)**i)*i
    print(a, end=',') # Alex Ratushnyak, Apr 20 2012

Formula

E.g.f.: x*exp(-x)/(1-x). [Corrected by Vaclav Kotesovec, Sep 26 2012]

a(n) = Sum_{k=0..n-1} (-1)^k*n!/k!.

a(n) = A180188(n,0). - Emeric Deutsch, Sep 06 2010

E.g.f.: x*A(x) where A(x) is the e.g.f. for A000166. - Geoffrey Critzer, Jan 14 2012

a(n) = n*a(n-1) - (-1)^n*n = A000166(n) - (-1)^n = n*A000166(n-1) = A000387(n+1)*2/(n+1) = A000449(n+2)*6/((n+1)*(n+2)).

a(n) = n*floor(((n-1)!+1)/e), n > 1. - Gary Detlefs, Jul 13 2010

Limit_{n->infinity} n!/a(n) = e = 2.71828...

a(n) = (n-1)*(a(n-1)+a(n-2)) + (-1)^(n-1), n>=2. - Enrique Navarrete, Oct 07 2016

O.g.f.: Sum_{k>=1} k!*x^k/(1 + x)^(k+1). - Ilya Gutkovskiy, Apr 13 2017

a(n) = (-1)^(n-1)*n*hypergeom([1,1-n], [], 1). - Peter Luschny, May 09 2017