login
This site is supported by donations to The OEIS Foundation.

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000166 Subfactorial or rencontres numbers, or derangements: number of permutations of n elements with no fixed points.
(Formerly M1937 N0766)
296
1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, 176214841, 2290792932, 32071101049, 481066515734, 7697064251745, 130850092279664, 2355301661033953, 44750731559645106, 895014631192902121, 18795307255050944540 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

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.

a(n) is the permanent of the matrix with 0 on the diagonal and 1 elsewhere. - Yuval Dekel, Nov 01 2003

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ésarméenien link and the Bona reference (p. 118). - Emeric Deutsch, Dec 28 2007

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

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

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

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

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

The only prime number in the sequence is 2. - Howard Berman (howard_berman(AT)hotmail.com), Nov 08 2008

From Emeric Deutsch, Apr 02 2009: (Start)

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.) [See also David, Kendall and Barton, p. 263. - N. J. A. Sloane, Apr 11 2014]

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)

For n>2, a(n) + a(n-1) = A000255(n-1); where A000255 = (1, 1, 3, 11, 53,...). - Gary W. Adamson, Apr 16 2009

Connection to A002469 (game of mousetrap with n cards): A002469(n) = (n-2)*A000255(n-1) + A000166(n). (Cf. triangle A159610). - Gary W. Adamson, Apr 17 2009

From Emeric Deutsch, Jul 18 2009: (Start)

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.

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).

(End)

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 (Feb 27 2010). - Wolfdieter Lang, Jun 01 2010

From Emeric Deutsch, Sep 06 2010: (Start)

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.

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.

(End)

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

a(n) = number of zeros in n-th row of the triangle in A170942, n > 0. - Reinhard Zumkeller, Mar 29 2012

a(n) is the maximal number of totally mixed Nash equilibria in games of n players, each with 2 pure options. - Raimundas Vidunas, Jan 22 2014

REFERENCES

Roland Bacher, Counting Packings of Generic Subsets in Finite Groups, Electr. J. Combinatorics, 19 (2012), #P7.

B. Balof, H. Jenne, Tilings, Continued Fractions, Derangements, Scramblings, and e, - Journal of Integer Sequences, 17 (2014), #14.2.7.

E. Barcucci, A. del Lungo and R. Pinzani, "Deco" polyominoes, permutations and random generation, Theoretical Computer Science, 159, 1996, 29-42.

M. Bona, Combinatorics of Permutations, Chapman & Hall/CRC, Boca Raton, Florida, 2004.

R. A. Brualdi and H. J. Ryser: Combinatorial Matrix Theory, 1992, Section 7.2, p. 202.

Ch. A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC, Boca Raton, Florida, 2002. - From Emeric Deutsch, Apr 02 2009

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 182.

P. Cvitanovic, Group theory for Feynman diagrams in non-Abelian gauge theories, Phys. Rev. D 14 (1976), 1536-1553.

S. K. Das and N. Deo, Rencontres graphs: a family of bipartite graphs, Fib. Quart., Vol. 25, No. 3, August 1987, 250-262.

F. N. David and D. E. Barton, Combinatorial Chance. Hafner, NY, 1962, p. 168.

F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 263, Table 7.5.1, row 1.

J. M. de Saint-Martin, "Le probleme des rencontres" in Quadrature, No. 61, pp. 14-19, 2006, EDP-Sciences Les Ulis (France).

H. Doerrie, 100 Great Problems of Elementary Mathematics, Dover, NY, 1965, p. 19.

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

L. Euler, Solution quaestionis curiosae ex doctrina combinationum, Mémoires Académie sciences St. Pétersburg 3 (1809/1810), 57-64; also E738 in his Collected Works, series I, volume 7, pages 435-440.

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.

J. M. Gandhi, On logarithmic numbers, Math. Student, 31 (1963), 73-83.

G. Gordon and E. McMahon, Moving faces to other places: facet derangements, Amer. Math. Monthly, 117 (2010), 865-88.

A. Hald, A History of Probability and Statistics and Their Applications Before 1750, Wiley, NY, 1990 (Chapter 19).

E. Irurozki, B. Calvo, J. A. Lozano, Sampling and learning the Mallows and Weighted Mallows models under the Hamming distance, 2014; https://addi.ehu.es/bitstream/10810/11240/1/tr14-3.pdf

M. Janjic, Determinants and Recurrence Sequences, Journal of Integer Sequences, 2012, Article 12.3.5. - From N. J. A. Sloane, Sep 16 2012

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,

E. Lozansky and C. Rousseau, Winning Solutions, Springer, 1996; see p. 152.

P. A. MacMahon, Combinatory Analysis, 2 vols., Chelsea, NY, 1960, see p. 102.

R.D. McKelvey and A. McLennan, The maximal number of regular totally mixed Nash equilibria, J. Economic Theory, 72 (1997) 411-425.

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.

R. Ondrejka, The first 100 exact subfactorials, Math. Comp., 21 (1967), 502.

K. Ragnarsson and B. E. Tenner, Homotopy type of the Boolean complex of a Coxeter system, Adv. Math. 222 (2009), 409-430.

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 65.

M. Rumney and E. J. F. Primrose, A sequence connected with the subfactorial sequence, Note 3207, Math. Gaz. 52 (1968), 381-382.

H. J. Ryser, Combinatorial Mathematics. Mathematical Association of America, Carus Mathematical Monograph 14, 1963, p. 23.

T. Simpson, Permutations with unique fixed and reflected points. Ars Combin. 39 (1995), 97-108.

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).

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.

H. S. Wilf, Generatingfunctionology, Academic Press, NY, 1990, p. 147, Eq. 5.2.9 (q=1).

E. M. Wright, Arithmetical properties of Euler's rencontre number, J. London Math. Soc., (2) (1971/1972), 437-442.

LINKS

T. D. Noe, Table of n, a(n) for n = 0..200

Joerg Arndt, Generating Random Permutations, PhD thesis, Australian National University, Camberra, Australia, (2010).

Joerg Arndt, Fxtbook, p. 280

D. Barsky, Analyse p-adique et suites classiques de nombres, Sem. Loth. Comb. B05b (1981) 1-21.

H. Bergeron, E. M. F. Curado, J. P. Gazeau and L. M. C. S. Rodrigues, A note about combinatorial sequences and Incomplete Gamma function, arXiv preprint arXiv: 1309.6910, 2013

P. Cvitanovic, Group theory for Feynman diagrams in non-Abelian gauge theories, Phys. Rev. D14 (1976), 1536-1553.

J. Désarménien, Une autre interpretation des nombres de derangements, Sem. Loth. Comb. B08b (1982) 11-16.

E. Deutsch and S. Elizalde, The largest and the smallest fixed points of permutations, arXiv:0904.2792v1, 2009.

R. M. Dickau, Derangements

J. East, R. D. Gray, Idempotent generators in finite partition monoids and related semigroups, arXiv preprint arXiv:1404.2359, 2014

FindStat - Combinatorial Statistic Finder, The number of fixed points of a permutation

H. Fripertinger, The Rencontre Numbers

Fulman and Guralnick, Derangements in simple and primitive groups, arXiv:math.GR/0208022.

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

Mehdi Hassani, Derangements and Applications , Journal of Integer Sequences, Vol. 6 (2003), #03.1.2

M. Hassani, Counting and computing by e

Nick Hobson, Python program

Q.-H. Hou, Z.-W. Sun and H.-M. Wen, On monotonicity of some combinatorial sequences, arXiv:1208.3903.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 21

A. R. Kräuter, Über die Permanente gewisser zirkulärer Matrizen...

J. W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5.

Romeo Mestrovic, Variations of Kurepa's left factorial hypothesis, arXiv preprint arXiv:1312.7037, 2013

P. Peart and W.-J. Woan, Generating Functions via Hankel and Stieltjes Matrices, J. Integer Seqs., Vol. 3 (2000), #00.2.1.

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

Plouffe, Simon, Exact formulas for integer sequences

E. Sandifer, How Euler Did It, Derangements

M. Shattuck, Combinatorial proofs of some Bell number formulas, arXiv preprint arXiv:1401.6588, 2014

Xinyu Sun, New Lower Bound On The Number of Ternary Square-Free Words, J. Integer Seqs., Vol. 6, 2003.

L. Takacs, The Problem of Coincidences, Archive for History of Exact Sciences, Volume 21, No. 3, Sept. 1980. pp 229-244, paragraph 3.

R. Vidunas, MacMahon's master theorem and totally mixed Nash equilibria, arXiv:1401.5400 [math.CO], see (7).

G. Villemin's Almanach of Numbers, Sous-factorielle

Yi Wang and Bao-Xuan Zhu, Proofs of some conjectures on monotonicity of number-theoretic and combinatorial sequences, arXiv preprint arXiv:1303.5595, 2013

Eric Weisstein's World of Mathematics, Derangement

Eric Weisstein's World of Mathematics, Rooks Problem

Eric Weisstein's World of Mathematics, Subfactorial

Eric Weisstein's World of Mathematics, Exponential Distribution

Wikipedia, Derangement

Wikipedia, Rencontres numbers

H. S. Wilf, Generatingfunctionology, 2nd edn., Academic Press, NY, 1994, p. 176, Eq. 5.2.9 (q=1).

D. Zeilberger, Automatic Enumeration of Generalized Menage Numbers, arXiv preprint arXiv:1401.1089, 2014

Index entries for "core" sequences

FORMULA

(this_sequence + A000522)/2 = A009179, (this_sequence - A000522)/2 = A009628.

The termwise sum of this sequence and A003048 gives the factorial numbers. - D. G. Rogers, Aug 26 2006

a(n) = {(n-1)!)/exp(1)}, n > 1, where {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]

a(0) = 1, a(n) = floor( n!/e + 1/2) for n > 0.

a(n) = n!*Sum((-1)^k/k!, k=0..n).

a(n) = (n-1)*(a(n-1)+a(n-2)), n>0.

a(n) = n*a(n-1)+(-1)^n.

E.g.f.: exp(-x)/(1-x).

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

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

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

The e.g.f. y(x) satisfies y' = x*y/(1-x).

Inverse binomial transform of A000142. - Ross La Haye, Sep 21 2004

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) + ... . - André F. Labossière, Dec 06 2004

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). - Karol A. Penson, Jan 21 2005

a(n) = A001120(n) - n!. - Philippe Deléham, Sep 04 2005

a(n) = Integral_{x=0..infinity} (x-1)^n*exp(-x) dx. - Gerald McGarvey, Oct 14 2006

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

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

From William Vaughn (wvaughn(AT)cvs.rochester.edu), Apr 13 2009: (Start)

a(n) = Integral_{p=0..1} (log(1/(1-p)) - 1)^n dp.

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.

From CRC Integral tables we find the antiderivative of

(log(y))^n is (-1)^n n! Sum_{k=0..n} (-1)^k y(log(y))^k / k!.

Using the fact that e(log(e))^r = e for any r>=0 and

0(log(0))^r = 0 for any r>=0 the Integral becomes

n! Sum_{k=0..n} (-1)^k / k!, which is line 9 of the "formula" section.

Q.E.D. (End)

a(n) = exp(-1)*GAMMA(n+1,-1) (incomplete Gamma function). - Mark van Hoeij, Nov 11 2009

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). - Paul Barry, Nov 27 2009

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. - Wolfdieter Lang, Jun 01 2010

a(n) = row sum of A008306(n), n>1. - Gary Detlefs, Jul 14 2010

a(n)= ((-1)^n)*(n-1)*hypergeom([ -n+2, 2], [], 1), n>=1; 1 for n=0. - Wolfdieter Lang, Aug 16 2010

a(n)= (-1)^n * hypergeom([ -n, 1], [], 1), n>=1; 1 for n=0. From the binomial convolution due to the e.g.f. - Wolfdieter Lang, Aug 26 2010

int(x^n*exp(x),x=0..1)=(-1)^n*(a(n)*e-n!).

O.g.f.: Sum_{n>=0} n^n*x^n/(1 + (n+1)*x)^(n+1). - Paul D. Hanna, Oct 06 2011

Abs((a(n)+a(n-1))*e-(A000142(n)+A000142(n-1)) < 2/n. - Seiichi Kirikami, Oct 17 2011

G.f.: hypergeom([1,1],[],x/(x+1))/(x+1). - Mark van Hoeij, Nov 07 2011

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

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

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

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

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

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

G.f.: T(0), where T(k) = 1 - x^2*(k+1)^2/( x^2*(k+1)^2 - (1-2*x*k)*(1-2*x-2*x*k)/T(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Oct 18 2013

0 = a(n) * (a(n+1) + a(n+2) - a(n+3)) + a(n+1) * (a(n+1) + 2*a(n+2) - a(n+3)) + a(n+2) * (a(n+2)) if n>=0. - Michael Somos, Jan 25 2014

EXAMPLE

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

The Boolean complex of the complete graph K_4 is homotopy equivalent to the wedge of 9 3-spheres.

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. - Wolfdieter Lang, Jun 01 2010

G.f. = 1 + x^2 + 9*x^3 + 44*x^4 + 265*x^5 + 1854*x^6 + 14833*x^7 + 133496*x^8 + ...

MAPLE

A000166 := proc(n) option remember; if n<=1 then 1-n else (n-1)*(procname(n-1)+procname(n-2)); fi; end;

a:=n->n!*sum((-1)^k/k!, k=0..n): seq(a(n), n=0..21); # Zerinvary Lajos, May 17 2007

ZL1:=[S, {S=Set(Cycle(Z, card>1))}, labeled]: seq(count(ZL1, size=n), n=0..21); # Zerinvary Lajos, Sep 26 2007

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, Oct 02 2007

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, Jan 22 2008

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

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); # Zerinvary Lajos, Apr 03 2009

MATHEMATICA

a[0] = 1; a[n_] := n*a[n - 1] + (-1)^n; a /@ Range[0, 21] (* Robert G. Wilson v *)

a[0] = 1; a[1] = 0; a[n_] := Round[n!/E] /; n >= 1 (* Michael Taktikos, May 26 2006. This is very fast. *)

Range[0, 20]! CoefficientList[ Series[ Exp[ -x]/(1 - x), {x, 0, 20}], x]

dr[{n_, a1_, a2_}]:={n+1, a2, n(a1+a2)}; Transpose[NestList[dr, {0, 0, 1}, 30]][[3]] (* Harvey P. Dale, Feb 23 2013 *)

a[ n_] := If[ n < 1, Boole[n == 0], Round[ n! / E]] (* Michael Somos, Jun 01 2013 *)

a[ n_] := If[ n < 0, 0, (-1)^n HypergeometricPFQ[ {- n, 1}, {}, 1]] (* Michael Somos, Jun 01 2013 *)

a[ n_] := If[ n < 0, 0, n! SeriesCoefficient[ Exp[ -x] /(1 - x), {x, 0, n}]] (* Michael Somos, Jun 01 2013 *)

LinearRecurrence[{#1, #1}, {1, 0}, 22] (* Robert G. Wilson v, Jun 15 2013 *)

Table[Subfactorial[n], {n, 0, 21}] (* Jean-François Alcover, Jan 10 2014 *)

PROG

(PARI) {a(n) = if( n<1, n==0, n * a(n-1) + (-1)^n)} /* Michael Somos, Mar 24 2003 */

(PARI) {a(n) = if( n<0, 0, n! * polcoeff( exp(-x + x * O(x^n)) / (1 - x), n))} /* Michael Somos, Mar 24 2003 */

(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 */

(PARI) A000166=n->n!*sum(k=0, n, (-1)^k/k!)  \\ M. F. Hasler, Jan 26 2012

(PARI) a(n)=if(n, round(n!/exp(1)), 1) \\ Charles R Greathouse IV, Jun 17 2012

(Python) See Hobson link.

(Maxima)

s[0]:1$s

s[n]:=n*s[n-1]+(-1)^n$

makelist(s[n], n, 0, 12);  (* Emanuele Munarini, Mar 01 2011 *)

(Haskell)

a000166 n = a000166_list !! n

a000166_list = 1 : 0 : zipWith (*) [1..]

                       (zipWith (+) a000166_list $ tail a000166_list)

-- Reinhard Zumkeller, Dec 09 2012

CROSSREFS

Cf. A000142, A002467, A008290, A003221, A000522, A000240, A000387, A000449, A000475, A129135, A092582, A000255, A002469, A159610, A068985, A068996, A047865, A038205, A000255.

For the probabilities a(n)/n!, see A053557/A053556 and A103816/A053556.

A diagonal of A008291 and A068106. A column of A008290.

A001120 has a similar recurrence.

For other derangement numbers see also A053871, A033030, A088991, A088992.

Pairwise sums of A002741 and A000757. Differences of A001277.

Cf. A101560, A101559, A000110, A101033, A101032, A000204, A100492, A099731, A000045, A094216, A094638, A000108.

A diagonal in triangles A008305 and A010027.

a(n)/n! = A053557/A053556 = (N(n, n) of A103361)/(D(n, n) of A103360)

a(n) = A086764(n,0).

Sequence in context: A047119 A052881 A020071 * A182386 A093464 A196301

Adjacent sequences:  A000163 A000164 A000165 * A000167 A000168 A000169

KEYWORD

core,nonn,easy,nice,changed

AUTHOR

N. J. A. Sloane

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified August 21 15:23 EDT 2014. Contains 245856 sequences.