0,4

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\'esarm\'enien link and the Bona reference (p. 118). - Emeric Deutsch (deutsch(AT)duke.poly.edu), 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 (deutsch(AT)duke.poly.edu), 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 (azarian(AT)evansville.edu), 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 (deutsch(AT)duke.poly.edu), 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 (deutsch(AT)duke.poly.edu), Mar 12 2008

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

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.

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

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.

Fulman and Guralnick, "Derangements in simple and primitive groups", http://front.math.ucdavis.edu/math.GR/0208022.

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

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

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.

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.

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.

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

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

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.

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.

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

Joerg Arndt, Fxtbook

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

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

J. D\'esarm\'enien, Une autre interpretation des nombres de derangements, Sem. Loth. Comb. B08b (1982) 11-16.

R. M. Dickau, Derangements

H. Fripertinger, The Rencontre Numbers

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

Nick Hobson, Python program

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 21

A. R. Kr\"auter, \"Uber die Permanente gewisser zirkul\"arer Matrizen...

A. F. Labossiere, Sobalian Coefficients.

A. F. Labossiere, Miscellaneous.

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

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

E. Sandifer, How Euler Did It, Derangements

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

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

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

Eric Weisstein's World of Mathematics, Exponential Distribution

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

Wikipedia, Derangement

Wikipedia, Subfactorial

Wikipedia, Rencontres numbers

Index entries for "core" sequences

M. Hassani, Counting and computing by e

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

a(0) = 1, a(n) = [ 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.: e^(-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 (vladeta(AT)Eunet.yu), 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 (vladeta(AT)Eunet.yu), 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 (pbarry(AT)wit.ie), Aug 26 2004

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

Inverse binomial transform of A000142. - Ross La Haye (rlahaye(AT)new.rr.com), 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) + ..... . - Andre F. Labossiere (boronali(AT)laposte.net), 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) . From Karol A. Penson - penson(AT)lptl.jussieu.fr, Jan 21 2005

a(n) = A001120(n) - n! . - Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Sep 04 2005

a(n) = Integral_{x=0..infinity} (x-1)^n*exp(-x) dx - Gerald McGarvey (gerald.mcgarvey(AT)comcast.net), 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 (deutsch(AT)duke.poly.edu), Feb 23 2008

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

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

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

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

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

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

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

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 (michael.taktikos(AT)hanse.net), May 26 2006. This is very fast.)

(PARI) a(n)=if(n<1, n==0, n*a(n-1)+(-1)^n)

(PARI) a(n)=if(n<0, 0, n!*polcoeff(exp(-x+x*O(x^n))/(1-x), n))

(Python) See Hobson link.

Cf. A000142, A002467, A008290, A003221, A000522, A000240, A000387, A000449, A000475.

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

See also A068985, A068996, A047865, A038205, A000255.

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 triangle A010027.

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

Cf. A092582.

Adjacent sequences: A000163 A000164 A000165 this_sequence A000167 A000168 A000169

Sequence in context: A047119 A052881 A020071 this_sequence A093464 A073478 A088369

core,nonn,easy,nice

njas