The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A000240 Rencontres numbers: number of permutations of [n] with exactly one fixed point. (Formerly M2763 N1111) 37
 1, 0, 3, 8, 45, 264, 1855, 14832, 133497, 1334960, 14684571, 176214840, 2290792933, 32071101048, 481066515735, 7697064251744, 130850092279665, 2355301661033952, 44750731559645107, 895014631192902120, 18795307255050944541, 413496759611120779880 (list; graph; refs; listen; history; text; internal format)
 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). 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. 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 lim_{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: A074435 A039647 A071533 * A182390 A132103 A334316 Adjacent sequences:  A000237 A000238 A000239 * A000241 A000242 A000243 KEYWORD nonn,easy,nice AUTHOR STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified January 17 06:24 EST 2021. Contains 340214 sequences. (Running on oeis4.)