A000240 Rencontres numbers: number of permutations of [n] with exactly one fixed point. (Formerly M2763 N1111)

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

Offset

1,3

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)

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

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

Example

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

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 *)

Prog

(Python)
a = 0
for i in range(1, 51):
    a = (a - (-1)**i)*i
    print(a, end=', ') # Alex Ratushnyak, Apr 20 2012
(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

Crossrefs

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

A diagonal of A008291.

Cf. A180188, A170942.

Sequence in context: A039647 A071533 A361716 * A182390 A132103 A334316

Adjacent sequences: A000237 A000238 A000239 * A000241 A000242 A000243

Keyword

nonn,easy,nice

Author

N. J. A. Sloane, Simon Plouffe

Status

approved