%I A000166 M1937 N0766
%S A000166 1,0,1,2,9,44,265,1854,14833,133496,1334961,14684570,176214841,
%T A000166 2290792932,32071101049,481066515734,7697064251745,130850092279664,
%U A000166 2355301661033953,44750731559645106,895014631192902121,18795307255050944540
%N A000166 Subfactorial or rencontres numbers, or derangements: number of permutations
of n elements with no fixed points.
%C A000166 Euler not only gives the first ten or so terms of the sequence, he also
proves both recurrences a(n)=(n-1)(a(n-1)+a(n-2)) and a(n)=na(n-1)+(-1)^n.
%C A000166 a(n) is the permanent of the matrix with 0 on the diagonal and 1 elsewhere.
- Yuval Dekel, Nov 01 2003
%C A000166 a(n) is the number of desarrangements of length n. A desarrangement of
length n is a permutation p of {1,2,...,n} for which the smallest
of all the ascents of p (taken to be n if there are no ascents) is
even. Example: a(3)=2 because we have 213 and 312 (smallest ascents
at i=2). See the J. D\'esarm\'enien link and the Bona reference (p.
118). - Emeric Deutsch (deutsch(AT)duke.poly.edu), Dec 28 2007
%C A000166 a(n) is the number of deco polyominoes of height n and having in the
last column an even number of cells. A deco polyomino is a directed
column-convex polyomino in which the height, measured along the diagonal,
is attained only in the last column. - Emeric Deutsch (deutsch(AT)duke.poly.edu),
Dec 28 2007
%C A000166 Attributed to Nicholas Bernoulli in connection with a probability problem
that he presented. See Problem #15, p. 494, in "History of Mathematics"
by David M. Burton, 6th edition. - Mohammad K. Azarian (azarian(AT)evansville.edu),
Feb 25 2008
%C A000166 a(n) is the number of permutations p of {1,2,...,n} with p(1)!=1 and
having no right-to-left minima in consecutive positions. Example
a(3)=2 because we have 231 and 321. - Emeric Deutsch (deutsch(AT)duke.poly.edu),
Mar 12 2008
%C A000166 a(n) is the number of permutations p of {1,2,...,n} with p(n)!=n and
having no left to right maxima in consecutive positions. Example
a(3)=2 because we have 312 and 321. - Emeric Deutsch (deutsch(AT)duke.poly.edu),
Mar 12 2008
%C A000166 Number of wedged (n-1)-spheres in the homotopy type of the Boolean complex
of the complete graph K_n. - Bridget Eileen Tenner (bridget(AT)math.depaul.edu),
Jun 04 2008
%C A000166 The only prime number in the sequence is 2. [From Howard Berman (howard_berman(AT)hotmail.com),
Nov 08 2008]
%C A000166 Contribution from Emeric Deutsch (deutsch(AT)duke.poly.edu), Apr 02 2009:
(Start)
%C A000166 a(n) is the number of permutations of {1,2,...,n} having exactly one
small ascent. A small ascent in a permutation (p_1,p_2,...,p_n) is
a position i such that p_{i+1} - p_i =1. (Example: a(3)=2 because
we have 312 and 231 (see the Charalambides reference, pp. 176-180).
%C A000166 a(n) is the number of permutations of {1,2,...,n} having exactly one
small descent. A small descent in a permutation (p_1,p_2,...,p_n)
is a position i such that p_i - p_{i+1} =1. (Example: a(3)=2 because
we have 132 and 213. (End)
%C A000166 For n>2, a(n) + a(n-1) = A000255(n-1); where A000255 = (1, 1, 3, 11,
53,...) [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Apr 16 2009]
%C A000166 Contribution from Gary W. Adamson (qntmpkt(AT)yahoo.com), Apr 17 2009:
(Start)
%C A000166 Connection to A002469 (game of mousetrap with n cards): A002469(n) =
%C A000166 (n-2)*A000255(n-1) + A000166(n). (Cf. triangle A159610). (End)
%C A000166 Contribution from Emeric Deutsch (deutsch(AT)duke.poly.edu), Jul 18 2009:
(Start)
%C A000166 a(n) is the sum of the values of the largest fixed points of all non-derangements
of length n-1. Example: a(4)=9 because the non-derangements of length
3 are 123, 132, 213, and 321, having largest fixed points 3, 1, 3,
and 2, respectively.
%C A000166 a(n) is the number of non-derangements of length n+1 for which the difference
between the largest and smallest fixed point is 2. Example: a(3)=2
because we have 1'43'2 and 32'14'; a(4)=9 because we have 1'23'54,
1'43'52, 1'53'24, 52'34'1, 52'14'3, 32'54'1, 213'45', 243'15', and
413'25' (the extreme fixed points are marked).
%C A000166 (End)
%D A000166 E. Barcucci, A. del Lungo and R. Pinzani, "Deco" polyominoes, permutations
and random generation, Theoretical Computer Science, 159, 1996, 29-42.
%D A000166 M. Bona, Combinatorics of Permutations, Chapman & Hall/CRC, Boca Raton,
Florida, 2004.
%D A000166 R. A. Brualdi and H. J. Ryser: Combinatorial Matrix Theory, 1992, Section
7.2, p. 202.
%D A000166 Ch. A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC,
Boca Raton, Florida, 2002. [From Emeric Deutsch (deutsch(AT)duke.poly.edu),
Apr 02 2009]
%D A000166 L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 182.
%D A000166 P. Cvitanovic, Group theory for Feynman diagrams in non-Abelian gauge
theories, Phys. Rev. D 14 (1976), 1536-1553.
%D A000166 S. K. Das and N. Deo, Rencontres graphs: a family of bipartite graphs,
Fib. Quart., Vol. 25, No. 3, August 1987, 250-262.
%D A000166 F. N. David and D. E. Barton, Combinatorial Chance. Hafner, NY, 1962,
p. 168.
%D A000166 E. Deutsch and S. Elizalde, The largest and the smallest fixed points
of permutations, arXiv:0904.2792v1, 2009. [From Emeric Deutsch (deutsch(AT)duke.poly.edu),
Jul 18 2009]
%D A000166 H. Doerrie, 100 Great Problems of Elementary Mathematics, Dover, NY,
1965, p. 19.
%D A000166 L. Euler, Solution quaestionis curiosae ex doctrina combinationum, M\'emoires
Acad\'emie sciences St. P\'etersburg 3 (1809/1810), 57-64; also E738
in his Collected Works, series I, volume 7, pages 435-440.
%D A000166 Fulman and Guralnick, "Derangements in simple and primitive groups",
http://front.math.ucdavis.edu/math.GR/0208022.
%D A000166 J. M. Gandhi, On logarithmic numbers, Math. Student, 31 (1963), 73-83.
%D A000166 A. Hald, A History of Probability and Statistics and Their Applications
Before 1750, Wiley, NY, 1990 (Chapter 19).
%D A000166 Florian Kerschbaum and Orestis Terzidis, Filtering for Private Collaborative
Benchmarking, in Emerging Trends in Information and Communication
Security, Lecture Notes in Computer Science, Volume 3995/2006,
%D A000166 E. Lozansky and C. Rousseau, Winning Solutions, Springer, 1996; see p.
152.
%D A000166 P. A. MacMahon, Combinatory Analysis, 2 vols., Chelsea, NY, 1960, see
p. 102.
%D A000166 P. R. de Montmort, On the Game of Thirteen (1713), reprinted in Annotated
Readings in the History of Statistics, ed. H. A. David and A. W.
F. Edwards, Springer-Verlag, 2001, pp. 25-29.
%D A000166 R. Ondrejka, The first 100 exact subfactorials, Math. Comp., 21 (1967),
502.
%D A000166 K. Ragnarsson and B. E. Tenner, Homotopy type of the Boolean complex
of a Coxeter system
%D A000166 J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p.
65.
%D A000166 M. Rumney and E. J. F. Primrose, A sequence connected with the subfactorial
sequence, Note 3207, Math. Gaz. 52 (1968), 381-382.
%D A000166 H. J. Ryser, Combinatorial Mathematics. Mathematical Association of America,
Carus Mathematical Monograph 14, 1963, p. 23.
%D A000166 J. M. de Saint-Martin, "Le probleme des rencontres" in Quadrature, No.
61, pp. 14-19, 2006, EDP-Sciences Les Ulis(France).
%D A000166 T. Simpson, Permutations with unique fixed and reflected points. Ars
Combin. 39 (1995), 97-108.
%D A000166 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973
(includes this sequence).
%D A000166 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences,
Academic Press, 1995 (includes this sequence).
%D A000166 Michael Z. Spivey and Laura L. Steil, The k-Binomial Transforms and the
Hankel Transform, Journal of Integer Sequences, Vol. 9 (2006), Article
06.1.1.
%D A000166 H. S. Wilf, Generatingfunctionology, Academic Press, NY, 1990, p. 147,
Eq. 5.2.9 (q=1).
%D A000166 E. M. Wright, Arithmetical properties of Euler's rencontre number, J.
London Math. Soc., (2) (1971/1972), 437-442.
%H A000166 T. D. Noe, <a href="b000166.txt">Table of n, a(n) for n = 0..200</a>
%H A000166 Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Fxtbook</a>
%H A000166 D. Barsky, <a href="http://www.mat.univie.ac.at/~slc/opapers/s05barsky.html">
Analyse p-adique et suites classiques de nombres</a>, Sem. Loth.
Comb. B05b (1981) 1-21.
%H A000166 P. Cvitanovic, <a href="http://www.nbi.dk/~predrag/papers/PRD14-76.pdf">
Group theory for Feynman diagrams in non-Abelian gauge theories</
a>, Phys. Rev. D14 (1976), 1536-1553.
%H A000166 J. D\'esarm\'enien, <a href="http://www.mat.univie.ac.at/~slc/opapers/
s08desar.html">Une autre interpretation des nombres de derangements</
a>, Sem. Loth. Comb. B08b (1982) 11-16.
%H A000166 R. M. Dickau, <a href="http://mathforum.org/advanced/robertd/derangements.html">
Derangements</a>
%H A000166 H. Fripertinger, <a href="http://www-ang.kfunigraz.ac.at/~fripert/fga/
k1rencontre.html">The Rencontre Numbers</a>
%H A000166 Mehdi Hassani, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL6/
Hassani/hassani5.html">Derangements and Applications </a>, Journal
of Integer Sequences, Vol. 6 (2003), #03.1.2
%H A000166 M. Hassani, <a href="http://arXiv.org/abs/math.CO/0606613">Counting and
computing by e</a>
%H A000166 Nick Hobson, <a href="a000166.py.txt">Python program</a>
%H A000166 INRIA Algorithms Project, <a href="http://algo.inria.fr/bin/encyclopedia?Search=ECSnb&argsearch=21">
Encyclopedia of Combinatorial Structures 21</a>
%H A000166 A. R. Kr\"auter, <a href="http://www.mat.univie.ac.at/~slc/opapers/s11kraeu.html">
\"Uber die Permanente gewisser zirkul\"arer Matrizen...</a>
%H A000166 A. F. Labossiere, <a href="http://members.lycos.co.uk/sobalian/index.html">
Sobalian Coefficients</a>.
%H A000166 A. F. Labossiere, <a href="http://members.lycos.co.uk/stereotomography/
index.html">Miscellaneous</a>.
%H A000166 J. W. Layman, <a href="http://www.cs.uwaterloo.ca/journals/JIS/index.html">
The Hankel Transform and Some of its Properties</a>, J. Integer Sequences,
4 (2001), #01.1.5.
%H A000166 P. Peart and W.-J. Woan, <a href="http://www.cs.uwaterloo.ca/journals/
JIS/index.html">Generating Functions via Hankel and Stieltjes Matrices</
a>, J. Integer Seqs., Vol. 3 (2000), #00.2.1.
%H A000166 Alexsandar Petojevic, <a href="http://www.cs.uwaterloo.ca/journals/JIS/
index.html">The Function vM_m(s; a; z) and Some Well-Known Sequences</
a>, Journal of Integer Sequences, Vol. 5 (2002), Article 02.1.7
%H A000166 E. Sandifer, How Euler Did It, <a href="http://www.maa.org/editorial/
euler/How%20Euler%20Did%20It%2011%20Derangements.pdf">Derangements</
a>
%H A000166 Xinyu Sun, <a href="http://www.cs.uwaterloo.ca/journals/JIS/index.html">
New Lower Bound On The Number of Ternary Square-Free Words</a>, J.
Integer Seqs., Vol. 6, 2003.
%H A000166 G. Villemin's Almanach of Numbers, <a href="http://membres.lycos.fr/villemingerard/
Compter/Factsous.htm">Sous-factorielle</a>
%H A000166 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
Derangement.html">Link to a section of The World of Mathematics.</
a>
%H A000166 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
RooksProblem.html">Link to a section of The World of Mathematics.</
a>
%H A000166 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
Subfactorial.html">Link to a section of The World of Mathematics.</
a>
%H A000166 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
ExponentialDistribution.html">Exponential Distribution</a>
%H A000166 H. S. Wilf, <a href="http://www.math.upenn.edu/~wilf/DownldGF.html">Generatingfunctionology</
a>, 2nd edn., Academic Press, NY, 1994, p. 176, Eq. 5.2.9 (q=1).
%H A000166 Wikipedia, <a href="http://en.wikipedia.org/wiki/Derangement">Derangement</
a>
%H A000166 Wikipedia, <a href="http://en.wikipedia.org/wiki/Subfactorial">Subfactorial</
a>
%H A000166 Wikipedia, <a href="http://en.wikipedia.org/wiki/Rencontres_numbers">
Rencontres numbers</a>
%H A000166 <a href="Sindx_Cor.html#core">Index entries for "core" sequences</a>
%F A000166 (this_sequence + A000522)/2 = A009179, (this_sequence - A000522)/2 =
A009628.
%F A000166 The termwise sum of this sequence and A003048 gives the factorial numbers
- D. G. Rogers, Aug 26 2006
%F A000166 a(n)=[(n!+1)/e] for n>0, a(n)=[n!/e+1/n] for n>1 and a(n)=[(e+1/e).n!
]-[e.n! ] for n>1; where [x] denotes the floor of x. - Mehdi Hassani
(mmhassany(AT)srttu(DOT)com), Aug 20 2006
%F A000166 a(0) = 1, a(n) = [ n!/e + 1/2 ] for n > 0.
%F A000166 a(n) = n!*Sum((-1)^k/k!, k=0..n).
%F A000166 a(n) = (n-1)*(a(n-1)+a(n-2)), n>0.
%F A000166 a(n) = n*a(n-1)+(-1)^n.
%F A000166 E.g.f.: e^(-x)/(1-x).
%F A000166 O.g.f. for number of permutations with exactly k fixed points is (1/k!)*Sum_{i>
=k} i!*x^i/(1+x)^(i+1). - Vladeta Jovovic (vladeta(AT)eunet.rs),
Aug 12 2002
%F A000166 E.g.f. for number of permutations with exactly k fixed points is x^k/
(k!*exp(x)*(1-x)). - Vladeta Jovovic (vladeta(AT)eunet.rs), Aug 25
2002
%F A000166 a(n)=sum{k=0..n, binomial(n, k)(-1)^(n-k)k!}=sum{k=0..n, (-1)^(n-k)*n!/
(n-k)!} - Paul Barry (pbarry(AT)wit.ie), Aug 26 2004
%F A000166 The e.g.f. y(x) satisfies y' = xy/(1-x).
%F A000166 Inverse binomial transform of A000142. - Ross La Haye (rlahaye(AT)new.rr.com),
Sep 21 2004
%F A000166 Subf(n) = n^(n-1) - { 2*C(n-2, 0) +2*C(n-2, 1) +C(n-2, 2) }*n^(n-2) +
{ 4*C(n-3, 0) +11*C(n-3, 1) +16*C(n-3, 2) +11*C(n-3, 3) +3*C(n-3,
4) }*n^(n-3) - { 10*C(n-4, 0) +55*C(n-4, 1) +147*C(n-4, 2) +215*C(n-4,
3) +179*C(n-4, 4) +80*C(n-4, 5) +15*C(n-4, 6) }*n^(n-4) + ..... .
- Andre F. Labossiere (boronali(AT)laposte.net), Dec 06 2004
%F A000166 In Maple notation, representation as n-th moment of a positive function
on [ -1, infinity] : a(n)= int( x^n*exp(-x-1), x=-1..infinity ),
n=0, 1... . a(n) is the Hamburger moment of the function exp(-1-x)*Heaviside(x+1)
. From Karol A. Penson - penson(AT)lptl.jussieu.fr, Jan 21 2005
%F A000166 a(n) = A001120(n) - n! . - Philippe DELEHAM (kolotoko(AT)wanadoo.fr),
Sep 04 2005
%F A000166 a(n) = Integral_{x=0..infinity} (x-1)^n*exp(-x) dx - Gerald McGarvey
(gerald.mcgarvey(AT)comcast.net), Oct 14 2006
%F A000166 a(n)=Sum(T(n,k),k=2,4,...), where T(n,k)=A092582(n,k)=kn!/(k+1)! for
1<=k<n and T(n,n)=1. - Emeric Deutsch (deutsch(AT)duke.poly.edu),
Feb 23 2008
%F A000166 a(n) = n!/e + (-1)^n*(1/(n+2 - 1/(n+3 - 2/(n+4 - 3/(n+5 - ...))))). Asymptotic
result (Ramanujan): (-1)^n*(a(n) - n!/e) ~ 1/n - 2/n^2 + 5/n^3 -
15/n^4 + ..., where the sequence [1,2,5,15,...] is the sequence of
Bell numbers A000110. - Peter Bala (pbala(AT)toucansurf.com), Jul
14 2008
%F A000166 G.f.: 2*exp(-x)/(1-x), seq(f[n]/2 . [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com),
Apr 03 2009]
%F A000166 Contribution from William Vaughn (wvaughn(AT)cvs.rochester.edu), Apr
13 2009: (Start)
%F A000166 a(n) = Integral_{p=0..1} (log(1/(1-p)) - 1)^n dp
%F A000166 Proof: Using the substitutions 1=log(e) and y = e(1-p) the
%F A000166 above integral can be converted to:
%F A000166 ((-1)^n/e) Integral_{y=0..e} (log(y))^n dy.
%F A000166 From CRC Integral tables we find the antiderivative of
%F A000166 (log(y))^n is (-1)^n n! Sum_{k=0..n} (-1)^k y(log(y))^k / k!.
%F A000166 Using the fact that e(log(e))^r = e for any r>=0 and
%F A000166 0(log(0))^r = 0 for any r>=0 the Integral becomes
%F A000166 n! Sum_{k=0..n} (-1)^k / k!, which is line 9 of the "formula" section.
%F A000166 Q.E.D. (End)
%F A000166 a(n) = exp(-1)*GAMMA(n+1,-1) (incomplete Gamma function) [From Mark van
Hoeij (hoeij(AT)math.fsu.edu), Nov 11 2009]
%e A000166 a(2)=1, a(3)=2 and a(4)=9 since the possibilities are {BA}, {BCA, CAB}
and {BADC, BCDA, BDAC, CADB, CDAB, CDBA, DABC, DCAB, DCBA} - Henry
Bottomley (se16(AT)btinternet.com), Jan 17 2001
%e A000166 The Boolean complex of the complete graph K_4 is homotopy equivalent
to the wedge of 9 3-spheres.
%p A000166 A000166 := proc(n) option remember; if n<=1 then 1-n else (n-1)*(A000166(n-1)+A000166(n-2));
fi; end;
%p A000166 a:=n->n!*sum((-1)^k/k!, k=0..n): seq(a(n), n=0..21);#, - Zerinvary Lajos
(zerinvarylajos(AT)yahoo.com), May 17 2007
%p A000166 ZL1:=[S,{S=Set(Cycle(Z,card>1))},labeled]: seq(count(ZL1,size=n),n=0..21);
- Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Sep 26 2007
%p A000166 with (combstruct):a:=proc(m) [ZL,{ZL=Set(Cycle(Z,card>=m))},labeled];
end: A000166:=a(2):seq(count(A000166,size=n),n=0..21); - Zerinvary
Lajos (zerinvarylajos(AT)yahoo.com), Oct 02 2007
%p A000166 Z := (x, m)->m!^2*sum(x^j/((m-j)!^2), j=0..m): R := (x, n, m)->Z(x, m)^n:
f := (t, n, m)->sum(coeff(R(x, n, m), x, j)*(t-1)^j*(n*m-j)!, j=0..n*m):
seq(f(0, n, 1), n=0..21); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com),
Jan 22 2008
%p A000166 a:=proc(n) if `mod`(n,2)=1 then sum(2*k*factorial(n)/factorial(2*k+1),
k=1.. floor((1/2)*n)) else 1+sum(2*k*factorial(n)/factorial(2*k+1),
k=1..floor((1/2)*n)-1) end if end proc: seq(a(n),n=0..20); - Emeric
Deutsch (deutsch(AT)duke.poly.edu), Feb 23 2008
%p A000166 restart: G(x):=2*exp(-x)/(1-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]/2,n=0..21);# [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com),
Apr 03 2009]
%t A000166 a[0] = 1; a[n_] := n*a[n - 1] + (-1)^n; a /@ Range[0, 21] (* Robert G.
Wilson v *)
%t A000166 a[0] = 1; a[1] = 0; a[n_] := Round[n!/E] /; n >= 1 (Michael Taktikos
(michael.taktikos(AT)hanse.net), May 26 2006. This is very fast.)
%o A000166 (PARI) a(n)=if(n<1,n==0,n*a(n-1)+(-1)^n)
%o A000166 (PARI) a(n)=if(n<0,0,n!*polcoeff(exp(-x+x*O(x^n))/(1-x),n))
%o A000166 (Python) See Hobson link.
%Y A000166 Cf. A000142, A002467, A008290, A003221, A000522, A000240, A000387, A000449,
A000475.
%Y A000166 For the probabilities a(n)/n!, see A053557/A053556 and A103816/A053556.
%Y A000166 See also A068985, A068996, A047865, A038205, A000255.
%Y A000166 A diagonal of A008291 and A068106. A column of A008290.
%Y A000166 A001120 has a similar recurrence.
%Y A000166 For other derangement numbers see also A053871, A033030, A088991, A088992.
%Y A000166 Pairwise sums of A002741 and A000757. Differences of A001277.
%Y A000166 Cf. A101560, A101559, A000110, A101033, A101032, A000204, A100492, A099731,
A000045, A094216, A094638, A000108.
%Y A000166 A diagonal in triangle A010027.
%Y A000166 a(n)/n! = A053557/A053556 = (N(n, n) of A103361)/(D(n, n) of A103360)
%Y A000166 Cf. A092582.
%Y A000166 Cf. A000255, A002469, A159610. [From Gary W. Adamson (qntmpkt(AT)yahoo.com),
Apr 16 2009]
%Y A000166 Sequence in context: A047119 A052881 A020071 this_sequence A093464 A073478
A088369
%Y A000166 Adjacent sequences: A000163 A000164 A000165 this_sequence A000167 A000168
A000169
%K A000166 core,nonn,easy,nice,new
%O A000166 0,4
%A A000166 N. J. A. Sloane (njas(AT)research.att.com).
|
