Search: id:A000166 Results 1-1 of 1 results found. %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, Table of n, a(n) for n = 0..200 %H A000166 Joerg Arndt, Fxtbook %H A000166 D. Barsky, Analyse p-adique et suites classiques de nombres, Sem. Loth. Comb. B05b (1981) 1-21. %H A000166 P. Cvitanovic, Group theory for Feynman diagrams in non-Abelian gauge theories, Phys. Rev. D14 (1976), 1536-1553. %H A000166 J. D\'esarm\'enien, Une autre interpretation des nombres de derangements, Sem. Loth. Comb. B08b (1982) 11-16. %H A000166 R. M. Dickau, Derangements %H A000166 H. Fripertinger, The Rencontre Numbers %H A000166 Mehdi Hassani, Derangements and Applications , Journal of Integer Sequences, Vol. 6 (2003), #03.1.2 %H A000166 M. Hassani, Counting and computing by e %H A000166 Nick Hobson, Python program %H A000166 INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 21 %H A000166 A. R. Kr\"auter, \"Uber die Permanente gewisser zirkul\"arer Matrizen... %H A000166 A. F. Labossiere, Sobalian Coefficients. %H A000166 A. F. Labossiere, Miscellaneous. %H A000166 J. W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5. %H A000166 P. Peart and W.-J. Woan, Generating Functions via Hankel and Stieltjes Matrices, J. Integer Seqs., Vol. 3 (2000), #00.2.1. %H A000166 Alexsandar Petojevic, The Function vM_m(s; a; z) and Some Well-Known Sequences, Journal of Integer Sequences, Vol. 5 (2002), Article 02.1.7 %H A000166 E. Sandifer, How Euler Did It, Derangements %H A000166 Xinyu Sun, New Lower Bound On The Number of Ternary Square-Free Words, J. Integer Seqs., Vol. 6, 2003. %H A000166 G. Villemin's Almanach of Numbers, Sous-factorielle %H A000166 Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics. %H A000166 Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics. %H A000166 Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics. %H A000166 Eric Weisstein's World of Mathematics, Exponential Distribution %H A000166 H. S. Wilf, Generatingfunctionology, 2nd edn., Academic Press, NY, 1994, p. 176, Eq. 5.2.9 (q=1). %H A000166 Wikipedia, Derangement %H A000166 Wikipedia, Subfactorial %H A000166 Wikipedia, Rencontres numbers %H A000166 Index entries for "core" sequences %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=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). Search completed in 0.004 seconds