|
%I M1937 N0766
%S 1,0,1,2,9,44,265,1854,14833,133496,1334961,14684570,176214841,
%T 2290792932,32071101049,481066515734,7697064251745,130850092279664,
%U 2355301661033953,44750731559645106,895014631192902121,18795307255050944540
%N Subfactorial or rencontres numbers, or derangements: number of permutations of n elements with no fixed points.
%C 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 a(n) is the permanent of the matrix with 0 on the diagonal and 1 elsewhere. - Yuval Dekel, Nov 01 2003
%C 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_, Dec 28 2007
%C 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_, Dec 28 2007
%C 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_, Feb 25 2008
%C 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_, Mar 12 2008
%C 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_, Mar 12 2008
%C Number of wedged (n-1)-spheres in the homotopy type of the Boolean complex of the complete graph K_n. - _Bridget Tenner_, Jun 04 2008
%C The only prime number in the sequence is 2. [From Howard Berman (howard_berman(AT)hotmail.com), Nov 08 2008]
%C Contribution from _Emeric Deutsch_, Apr 02 2009: (Start)
%C 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 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 For n>2, a(n) + a(n-1) = A000255(n-1); where A000255 = (1, 1, 3, 11, 53,...) [From _Gary W. Adamson_, Apr 16 2009]
%C Connection to A002469 (game of mousetrap with n cards): A002469(n) = (n-2)*A000255(n-1) + A000166(n). (Cf. triangle A159610). [From _Gary W. Adamson_, Apr 17 2009]
%C Contribution from _Emeric Deutsch_, Jul 18 2009: (Start)
%C 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 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 (End)
%C a(n), n>=1, is also the number of unordered necklaces with n beads, labeled differently from 1 to n, where each necklace has >=2 beads. This produces the M2 multinomial formula involving partitions without part 1 given below. Because M2(p) counts the permutations with cycle structure given by partition p, this formula gives the number of permutations without fixed points (no 1-cycles), i.e., the derangements, hence the subfactorials with their recurrence relation and inputs. Each necklace with no beads is assumed to contribute a factor 1 in the counting, hence a(0)=1. This comment derives from a family of recurrences found by Malin Sjodahl for a combinatorial problem for certain quark and gluon diagrams ( Febr 27 2010). [From _Wolfdieter Lang_, Jun 01 2010]
%C Contribution from _Emeric Deutsch_, Sep 06 2010: (Start)
%C a(n) is the number of permutations of {1,2,...,n, n+1} starting with 1 and having no successions. A succession 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 1324 and 1432.
%C a(n) is the number of permutations of {1,2,...,n} that do not start with 1 and have no successions. A succession 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 213 and 321.
%C (End)
%C Increasing colored 1-2 trees with choice of two colors for the rightmost branch of nonleave except on the leftmost path, there is no vertex of outdegree one on the leftmost path. [Wenjin Woan, May 23, 2011]
%C a(n) = number of zeros in n-th row of the triangle in A170942, n > 0. [_Reinhard Zumkeller_, Mar 29 2012]
%D Roland Bacher, Counting Packings of Generic Subsets in Finite Groups, Electr. J. Combinatorics, 19 (2012), #P7. - From _N. J. A. Sloane_, Feb 06 2013
%D E. Barcucci, A. del Lungo and R. Pinzani, "Deco" polyominoes, permutations and random generation, Theoretical Computer Science, 159, 1996, 29-42.
%D M. Bona, Combinatorics of Permutations, Chapman & Hall/CRC, Boca Raton, Florida, 2004.
%D R. A. Brualdi and H. J. Ryser: Combinatorial Matrix Theory, 1992, Section 7.2, p. 202.
%D Ch. A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC, Boca Raton, Florida, 2002. [From _Emeric Deutsch_, Apr 02 2009]
%D L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 182.
%D P. Cvitanovic, Group theory for Feynman diagrams in non-Abelian gauge theories, Phys. Rev. D 14 (1976), 1536-1553.
%D S. K. Das and N. Deo, Rencontres graphs: a family of bipartite graphs, Fib. Quart., Vol. 25, No. 3, August 1987, 250-262.
%D F. N. David and D. E. Barton, Combinatorial Chance. Hafner, NY, 1962, p. 168.
%D E. Deutsch and S. Elizalde, The largest and the smallest fixed points of permutations, arXiv:0904.2792v1, 2009. [From _Emeric Deutsch_, Jul 18 2009]
%D H. Doerrie, 100 Great Problems of Elementary Mathematics, Dover, NY, 1965, p. 19.
%D Doslic, Tomislav and Veljan, Darko. Logarithmic behavior of some combinatorial sequences. Discrete Math. 308 (2008), no. 11, 2182--2212. MR2404544 (2009j:05019) - From _N. J. A. Sloane_, May 01 2012
%D 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 Philip Feinsilver and John McSorley, Zeons, Permanents, the Johnson Scheme, and Generalized Derangements, International Journal of Combinatorics, Volume 2011, Article ID 539030, 29 pages; doi:10.1155/2011/539030.
%D Fulman and Guralnick, "Derangements in simple and primitive groups", http://front.math.ucdavis.edu/math.GR/0208022.
%D J. M. Gandhi, On logarithmic numbers, Math. Student, 31 (1963), 73-83.
%D O. Gonzalez, C. Beltran and I. Santamaria, On the Number of Interference Alignment Solutions for the K-User MIMO Channel with Constant Coefficients, arXiv preprint arXiv:1301.6196, 2013. - From _N. J. A. Sloane_, Feb 19 2013
%D G. Gordon and E. McMahon, Moving faces to other places: facet derangements, Amer. Math. Monthly, 117 (2010), 865-88.
%D A. Hald, A History of Probability and Statistics and Their Applications Before 1750, Wiley, NY, 1990 (Chapter 19).
%D M. Janjic, Determinants and Recurrence Sequences, Journal of Integer Sequences, 2012, Article 12.3.5. - From _N. J. A. Sloane_, Sep 16 2012
%D 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 E. Lozansky and C. Rousseau, Winning Solutions, Springer, 1996; see p. 152.
%D P. A. MacMahon, Combinatory Analysis, 2 vols., Chelsea, NY, 1960, see p. 102.
%D 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 R. Ondrejka, The first 100 exact subfactorials, Math. Comp., 21 (1967), 502.
%D K. Ragnarsson and B. E. Tenner, Homotopy type of the Boolean complex of a Coxeter system, Adv. Math. 222 (2009), 409-430.
%D J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 65.
%D M. Rumney and E. J. F. Primrose, A sequence connected with the subfactorial sequence, Note 3207, Math. Gaz. 52 (1968), 381-382.
%D H. J. Ryser, Combinatorial Mathematics. Mathematical Association of America, Carus Mathematical Monograph 14, 1963, p. 23.
%D J. M. de Saint-Martin, "Le probleme des rencontres" in Quadrature, No. 61, pp. 14-19, 2006, EDP-Sciences Les Ulis(France).
%D T. Simpson, Permutations with unique fixed and reflected points. Ars Combin. 39 (1995), 97-108.
%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 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 H. S. Wilf, Generatingfunctionology, Academic Press, NY, 1990, p. 147, Eq. 5.2.9 (q=1).
%D E. M. Wright, Arithmetical properties of Euler's rencontre number, J. London Math. Soc., (2) (1971/1972), 437-442.
%H T. D. Noe, <a href="/A000166/b000166.txt">Table of n, a(n) for n = 0..200</a>
%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Fxtbook</a>, p.280
%H 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 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 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 R. M. Dickau, <a href="http://mathforum.org/advanced/robertd/derangements.html">Derangements</a>
%H H. Fripertinger, <a href="http://www-ang.kfunigraz.ac.at/~fripert/fga/k1rencontre.html">The Rencontre Numbers</a>
%H 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 M. Hassani, <a href="http://arXiv.org/abs/math.CO/0606613">Counting and computing by e</a>
%H Nick Hobson, <a href="/A000166/a000166.py.txt">Python program</a>
%H INRIA Algorithms Project, <a href="http://algo.inria.fr/ecs/ecs?searchType=1&service=Search&searchTerms=21">Encyclopedia of Combinatorial Structures 21</a>
%H 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 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 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 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 Plouffe, Simon, <a href="http://www.plouffe.fr/simon/exact.htm">Exact formulas for integer sequences</a>
%H E. Sandifer, How Euler Did It, <a href="http://www.maa.org/editorial/euler/How%20Euler%20Did%20It%2011%20Derangements.pdf">Derangements</a>
%H 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 L. Takacs, <a href="http://www.springerlink.com/content/0003-9519/21/3/">The Problem of Coincidences</a>, Archive for History of Exact Sciences, Volume 21, No. 3, Sept. 1980. pp 229-244, paragraph 3.
%H G. Villemin's Almanach of Numbers, <a href="http://villemin.gerard.free.fr/Wwwgvmm/Compter/Factsous.htm">Sous-factorielle</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Derangement.html">Derangement</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/RooksProblem.html">Rooks Problem</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Subfactorial.html">Subfactorial</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ExponentialDistribution.html">Exponential Distribution</a>
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Derangement">Derangement</a>
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Rencontres_numbers">Rencontres numbers</a>
%H 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 <a href="/index/Cor#core">Index entries for "core" sequences</a>
%F (this_sequence + A000522)/2 = A009179, (this_sequence - A000522)/2 = A009628.
%F The termwise sum of this sequence and A003048 gives the factorial numbers - D. G. Rogers, Aug 26 2006
%F a(n) = {(n-1)!)/exp(1)}, n > 1, and {x} is the nearest integer function. Simon Plouffe, March 1993 [This uses offset 1, see below for the version with offset 0. _Charles R Greathouse IV_, Jan 25 2012]
%F a(0) = 1, a(n) = floor( n!/e + 1/2) for n > 0.
%F a(n) = n!*Sum((-1)^k/k!, k=0..n).
%F a(n) = (n-1)*(a(n-1)+a(n-2)), n>0.
%F a(n) = n*a(n-1)+(-1)^n.
%F E.g.f.: exp(-x)/(1-x).
%F 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_, Aug 12 2002
%F E.g.f. for number of permutations with exactly k fixed points is x^k/(k!*exp(x)*(1-x)). - _Vladeta Jovovic_, Aug 25 2002
%F 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_, Aug 26 2004
%F The e.g.f. y(x) satisfies y' = x*y/(1-x).
%F Inverse binomial transform of A000142. - Ross La Haye (rlahaye(AT)new.rr.com), Sep 21 2004
%F 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 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_, Jan 21 2005
%F a(n) = A001120(n) - n! . - _Philippe DELEHAM_, Sep 04 2005
%F a(n) = Integral_{x=0..infinity} (x-1)^n*exp(-x) dx - _Gerald McGarvey_, Oct 14 2006
%F 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_, Feb 23 2008
%F 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_, Jul 14 2008
%F Contribution from William Vaughn (wvaughn(AT)cvs.rochester.edu), Apr 13 2009: (Start)
%F a(n) = Integral_{p=0..1} (log(1/(1-p)) - 1)^n dp
%F Proof: Using the substitutions 1=log(e) and y = e(1-p) the above integral can be converted to: ((-1)^n/e) Integral_{y=0..e} (log(y))^n dy.
%F From CRC Integral tables we find the antiderivative of
%F (log(y))^n is (-1)^n n! Sum_{k=0..n} (-1)^k y(log(y))^k / k!.
%F Using the fact that e(log(e))^r = e for any r>=0 and
%F 0(log(0))^r = 0 for any r>=0 the Integral becomes
%F n! Sum_{k=0..n} (-1)^k / k!, which is line 9 of the "formula" section.
%F Q.E.D. (End)
%F a(n) = exp(-1)*GAMMA(n+1,-1) (incomplete Gamma function) [From _Mark van Hoeij_, Nov 11 2009]
%F G.f.: 1/(1-x^2/(1-2x-4x^2/(1-4x-9x^2/(1-6x-16x^2/(1-8x-25x^2/(1-... (continued fraction). [From _Paul Barry_, Nov 27 2009]
%F a(n) = sum(M2(p), p from Pano1(n)), n>=1, with Pano1(n) the set of partitions without part 1, and the multinomial M2 numbers. See the characteristic array for partitions without part 1 given by A145573 in Abramowitz-Stegun (A-S) order, with A002865(n) the total number of such partitions. The M2 numbers are given for each partition in A-St order by the array A036039. [From _Wolfdieter Lang_, Jun 01 2010]
%F a(n) = row sum of A008306(n), n>1 [From _Gary Detlefs_, Jul 14 2010]
%F a(n)= ((-1)^n)*(n-1)*hypergeom([ -n+2, 2], [], 1), n>=1; 1 for n=0. [From _Wolfdieter Lang_, Aug 16 2010]
%F a(n)= hypergeom([ -n, 1], [], 1), n>=1; 1 for n=0. From the binomial convolution due to the e.g.f. [From _Wolfdieter Lang_, Aug 26 2010]
%F int(x^n*exp(x),x=0..1)=(-1)^n*(a(n)*e-n!)
%F O.g.f.: Sum_{n>=0} n^n*x^n/(1 + (n+1)*x)^(n+1). [_Paul D. Hanna_, Oct 06 2011]
%F Abs((a(n)+a(n-1))*e-(A000142(n)+A000142(n-1)) < 2/n. - Seiichi Kirikami, Oct 17 2011
%F G.f.: hypergeom([1,1],[],x/(x+1))/(x+1) - Mark van Hoeij, Nov 07 2011
%F In general, E.g.f.: (1+a*x)/exp(b*x) =U(0); U(k)= 1+a*x/(1-b/(b-a*(k+1)/U(k+1))); for E.g.f.: exp(-x)/(1-x)=1/U(0), a=-1,b=-1; (continued fraction). - _Sergei N. Gladkovskii_, Nov 25 2011
%F E.g.f.: (1-x/(U(0)+x))/(1-x), where U(k)= k+1 - x + (k+1)*x/U(k+1); (continued fraction, Euler's 1st kind, 1-step ). - _Sergei N. Gladkovskii_, Jul 05 2012
%F E.g.f.: 1/Q(0) where Q(k) = 1 - x/(1 - 1/(1 - (k+1)/Q(k+1))); (continued fraction, 3-step). - _Sergei N. Gladkovskii_, Sep 23 2012
%F G.f.: 1/U(0) where U(k)= 1 + x - x*(k+1)/(1 - x*(k+1)/U(k+1)); (continued fraction, 2-step). - _Sergei N. Gladkovskii_, Oct 13 2012
%F G.f.: Q(0)/(1+x) where Q(k) =1 + (2*k + 1)*x/( (1+x) - 2*x*(1+x)*(k+1)/(2*x*(k+1) + (1+x)/Q(k+1) )); (continued fraction). - _Sergei N. Gladkovskii_, Mar 09 2013
%F G.f.: 1/Q(0) where Q(k) = 1 - 2*k*x - x^2*(k + 1)^2/Q(k+1); (continued fraction). - _Sergei N. Gladkovskii_, Mar 10 2013
%e 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_, Jan 17 2001
%e The Boolean complex of the complete graph K_4 is homotopy equivalent to the wedge of 9 3-spheres.
%e Necklace problem for n=6: partitions without part 1 and M2 numbers for n=6: there are A002865(6)=4 such partitions, namely (6), (2,4), (3^2) and (2^3) in A-St order with the M2 numbers 5!, 90, 40 and 15, respectively, adding up to 265=a(6). This corresponds to 1 necklace with 6 beads, two necklaces with 2 and 4 beads respectively, two necklaces with 3 beads each and three necklaces with 2 beads each. [From _Wolfdieter Lang_, Jun 01 2010]
%p A000166 := proc(n) option remember; if n<=1 then 1-n else (n-1)*(procname(n-1)+procname(n-2)); fi; end;
%p 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 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 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 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 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_, Feb 23 2008
%p 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 a[0] = 1; a[n_] := n*a[n - 1] + (-1)^n; a /@ Range[0, 21] (* _Robert G. Wilson v_ *)
%t a[0] = 1; a[1] = 0; a[n_] := Round[n!/E] /; n >= 1 (* _Michael Taktikos_, May 26 2006. This is very fast. *)
%t Range[0, 20]! CoefficientList[ Series[ Exp[ -x]/(1 - x), {x, 0, 20}], x]
%t dr[{n_,a1_,a2_}]:={n+1,a2,n(a1+a2)}; Transpose[NestList[dr,{0,0,1},30]][[3]] (* _Harvey P. Dale_, Feb 23 2013 *)
%o (PARI) a(n)=if(n<1,n==0,n*a(n-1)+(-1)^n)
%o (PARI) a(n)=if(n<0,0,n!*polcoeff(exp(-x+x*O(x^n))/(1-x),n))
%o (PARI) {a(n)=polcoeff(sum(m=0,n,m^m*x^m/(1+(m+1)*x+x*O(x^n))^(m+1)),n)} /* _Paul D. Hanna_ */
%o (PARI) A000166=n->n!*sum(k=0,n,(-1)^k/k!) \\ _M. F. Hasler_, Jan 26 2012
%o (PARI) a(n)=if(n,round(n!/exp(1)),1) \\ _Charles R Greathouse IV_, Jun 17 2012
%o (Python) See Hobson link.
%o (Maxima)
%o s[0]:1$s
%o s[n]:=n*s[n-1]+(-1)^n$
%o makelist(s[n],n,0,12); [_Emanuele Munarini_, Mar 01 2011].
%o (Haskell)
%o a000166 n = a000166_list !! n
%o a000166_list = 1 : 0 : zipWith (*) [1..]
%o (zipWith (+) a000166_list $ tail a000166_list)
%o -- _Reinhard Zumkeller_, Dec 09 2012
%Y Cf. A000142, A002467, A008290, A003221, A000522, A000240, A000387, A000449, A000475, A092582, A000255, A002469, A159610, A068985, A068996, A047865, A038205, A000255.
%Y For the probabilities a(n)/n!, see A053557/A053556 and A103816/A053556.
%Y A diagonal of A008291 and A068106. A column of A008290.
%Y A001120 has a similar recurrence.
%Y For other derangement numbers see also A053871, A033030, A088991, A088992.
%Y Pairwise sums of A002741 and A000757. Differences of A001277.
%Y Cf. A101560, A101559, A000110, A101033, A101032, A000204, A100492, A099731, A000045, A094216, A094638, A000108.
%Y A diagonal in triangles A008305 and A010027.
%Y a(n)/n! = A053557/A053556 = (N(n, n) of A103361)/(D(n, n) of A103360)
%Y a(n) = A086764(n,0).
%K core,nonn,easy,nice,changed
%O 0,4
%A _N. J. A. Sloane_.
|
