|
| |
|
|
A000240
|
|
Rencontres numbers: number of permutations of [n] with exactly one fixed point.
(Formerly M2763 N1111)
|
|
30
|
|
|
|
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
|
|
|
REFERENCES
|
Kaufmann, Arnold. "Introduction a 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
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.
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((-1)^k*n!/k!, k=0..n-1).
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...
|
|
|
EXAMPLE
|
a(3) = 3 because the permutations of (1,2,3) with one fixed point are (1,2), (1,3), (2,3).
|
|
|
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
|
|
|
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
|
|
|
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
|
| |
|
|
