|
%I M2763 N1111 #131 Aug 18 2023 11:26:20
%S 1,0,3,8,45,264,1855,14832,133497,1334960,14684571,176214840,
%T 2290792933,32071101048,481066515735,7697064251744,130850092279665,
%U 2355301661033952,44750731559645107,895014631192902120,18795307255050944541,413496759611120779880
%N Rencontres numbers: number of permutations of [n] with exactly one fixed point.
%C 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
%C 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
%C 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
%C From _Enrique Navarrete_, Mar 25 2017: (Start)
%C 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):
%C 1 2 3 4
%C 1 |_|_|_|x|
%C 2 |x|_|_|_|
%C 3 |_|x|_|_|
%C 4 |_|_|x|_|
%C _
%C 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.
%C 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).
%C (End)
%D Kaufmann, Arnold. "Introduction à la combinatorique en vue des applications." Dunod, Paris, 1968. See p. 92.
%D J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 65.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D N. Ya. Vilenkin, Combinatorics, p. 56, eq.(13), F_n = a(n). Academic Press, 1971.
%H T. D. Noe, <a href="/A000240/b000240.txt">Table of n, a(n) for n=1..100</a>
%H Bhadrachalam Chitturi and Krishnaveni K S, <a href="https://arxiv.org/abs/1601.04469">Adjacencies in Permutations</a>, arXiv preprint arXiv:1601.04469 [cs.DM], 2016.
%H S. K. Das and N. Deo, <a href="http://www.fq.math.ca/Scanned/25-3/das.pdf">Rencontres graphs: a family of bipartite graphs</a>, Fib. Quart., Vol. 25, No. 3, August 1987, 250-262.
%H FindStat - Combinatorial Statistic Finder, <a href="http://www.findstat.org/St000022">The number of fixed points of a permutation</a>
%H I. Kaplansky, <a href="http://dx.doi.org/10.1090/S0002-9904-1944-08261-X">Symbolic solution of certain problems in permutations</a>, Bull. Amer. Math. Soc., 50 (1944), 906-914.
%H Enrique Navarrete, <a href="https://arxiv.org/abs/1610.01987">Forbidden Patterns and the Alternating Derangement Sequence</a>, arXiv:1610.01987 [math.CO], 2016.
%H Enrique Navarrete, <a href="http://arxiv.org/abs/1610.06217">Generalized K-Shift Forbidden Substrings in Permutations</a>, arXiv:1610.06217 [math.CO], 2016.
%H S. M. Tanny, <a href="http://dx.doi.org/10.1016/0097-3165(76)90063-7">Permutations and successions</a>, J. Combinatorial Theory, Series A, 21 (1976), 196-202.
%H <a href="/index/Per#IntegerPermutationCatAuto">Index entries for sequences related to permutations with fixed points</a>
%F E.g.f.: x*exp(-x)/(1-x). [Corrected by _Vaclav Kotesovec_, Sep 26 2012]
%F a(n) = Sum_{k=0..n-1} (-1)^k*n!/k!.
%F a(n) = A180188(n,0). - _Emeric Deutsch_, Sep 06 2010
%F E.g.f.: x*A(x) where A(x) is the e.g.f. for A000166. - _Geoffrey Critzer_, Jan 14 2012
%F 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)).
%F a(n) = n*floor(((n-1)!+1)/e), n > 1. - _Gary Detlefs_, Jul 13 2010
%F Limit_{n->infinity} n!/a(n) = e = 2.71828...
%F a(n) = (n-1)*(a(n-1)+a(n-2)) + (-1)^(n-1), n>=2. - _Enrique Navarrete_, Oct 07 2016
%F O.g.f.: Sum_{k>=1} k!*x^k/(1 + x)^(k+1). - _Ilya Gutkovskiy_, Apr 13 2017
%F a(n) = (-1)^(n-1)*n*hypergeom([1,1-n], [], 1). - _Peter Luschny_, May 09 2017
%e 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).
%e 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
%p 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
%p A000240 := proc(n)
%p n!*add((-1)^k/k!,k=0..n-1) ;
%p end proc: # _R. J. Mathar_, Jul 09 2012
%p a := n -> (-1)^(n-1)*n*hypergeom([1,1-n], [], 1):
%p seq(simplify(a(n)), n=1..22); # _Peter Luschny_, May 09 2017
%t 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 *)
%t Table[n!*Sum[(-1)^k/k!,{k,0,n-1}],{n,1,25}] (* _Vaclav Kotesovec_, Sep 26 2012 *)
%t Table[n!*SeriesCoefficient[x*E^(-x)/(1-x),{x,0,n}],{n,1,25}] (* _Vaclav Kotesovec_, Sep 26 2012 *)
%o (Python)
%o a = 0
%o for i in range(1, 51):
%o a = (a - (-1)**i)*i
%o print(a, end=',') # _Alex Ratushnyak_, Apr 20 2012
%o (PARI) x='x+O('x^66); Vec( serlaplace(x*exp(-x)/(1-x)) ) \\ _Joerg Arndt_, Feb 19 2014
%o (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
%Y Cf. A008290, A000166, A000387, A000449, A000475, A129135, etc.
%Y A diagonal of A008291.
%Y Cf. A180188, A170942.
%K nonn,easy,nice
%O 1,3
%A _N. J. A. Sloane_, _Simon Plouffe_
|
