|
| |
|
|
A000240
|
|
Rencontres numbers: number of permutations of [n] with exactly one fixed point.
(Formerly M2763 N1111)
|
|
34
|
|
|
|
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, # 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 A180508
Adjacent sequences: A000237 A000238 A000239 * A000241 A000242 A000243
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
|
AUTHOR
|
N. J. A. Sloane, Simon Plouffe
|
|
|
STATUS
|
approved
|
| |
|
|
