cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-10 of 24 results. Next

A233440 Triangle read by rows: T(n, k) = n*binomial(n, k)*A000757(k), 0 <= k <= n.

Original entry on oeis.org

0, 1, 0, 2, 0, 0, 3, 0, 0, 3, 4, 0, 0, 16, 4, 5, 0, 0, 50, 25, 40, 6, 0, 0, 120, 90, 288, 216, 7, 0, 0, 245, 245, 1176, 1764, 1603, 8, 0, 0, 448, 560, 3584, 8064, 14656, 13000, 9, 0, 0, 756, 1134, 9072, 27216, 74196, 131625, 118872, 10, 0, 0, 1200, 2100, 20160, 75600, 274800, 731250, 1320800, 1202880
Offset: 0

Views

Author

Luis Manuel Rivera Martínez, Dec 09 2013

Keywords

Comments

For n >= 0, 0 <= k <= n, T(n, k) is the number of permutations of n symbols that k-commute with an n-cycle (we say that two permutations f and g k-commute if H(fg, gf) = k, where H(, ) denotes the Hamming distance between permutations).
Row sums give A000142.

Examples

			For n = 4 and k = 4, T(4, 4) = 4 because all the permutations of 4 symbols that 4-commute with permutation (1, 2, 3, 4) are (1, 3), (2, 4), (1, 2)(3, 4) and (1, 4)(2, 3).

Links

Crossrefs

Cf. A007318, A000757.

Programs

  • Mathematica
    T[n_, k_] := n Binomial[n, k] ((-1)^k+Sum[(-1)^j k!/(k-j)/j!, {j, 0, k-1}]);
Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Nov 03 2018 *)

Formula

T(n,k) = n*C(n,k)*A000757(k), 0 <= k <= n.
Bivariate e.g.f.: G(z, u) = z*exp(z*(1-u))*(u/(1-z*u)+(1-log(1-z*u))*(1-u)).
T(n, 0) = A001477(n), n>=0;
T(n, 1) = A000004(n), n>=1;
T(n, 2) = A000004(n), n>=2;
T(n, 3) = A004320(n-2), n>=3;
T(n, 4) = A027764(n-1), n>=4;
T(n, 5) = A027765(n-1)*A000757(5), n>=5;
T(n, 6) = A027766(n-1)*A000757(6), n>=6;
T(n, 7) = A027767(n-1)*A000757(7), n>=7;
T(n, 8) = A027768(n-1)*A000757(8), n>=8;
T(n, 9) = A027769(n-1)*A000757(9), n>=9;
T(n, 10) = A027770(n-1)*A000757(10), n>=10;
T(n, 11) = A027771(n-1)*A000757(11), n>=11;
T(n, 12) = A027772(n-1)*A000757(12), n>=12;
T(n, 13) = A027773(n-1)*A000757(13), n>=13;
T(n, 14) = A027774(n-1)*A000757(14), n>=14;
T(n, 15) = A027775(n-1)*A000757(15), n>=15;
T(n, 16) = A027776(n-1)*A000757(16), n>=16. - Luis Manuel Rivera Martínez, Feb 08 2014
T(n, 0)+T(n, 3) = n*A050407(n+1), for n>=0. - Luis Manuel Rivera Martínez, Mar 06 2014

A000142 Factorial numbers: n! = 1*2*3*4*...*n (order of symmetric group S_n, number of permutations of n letters).

Original entry on oeis.org

1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 87178291200, 1307674368000, 20922789888000, 355687428096000, 6402373705728000, 121645100408832000, 2432902008176640000, 51090942171709440000, 1124000727777607680000
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

The earliest publication that discusses this sequence appears to be the Sepher Yezirah [Book of Creation], circa AD 300. (See Knuth, also the Zeilberger link.) - N. J. A. Sloane, Apr 07 2014
For n >= 1, a(n) is the number of n X n (0,1) matrices with each row and column containing exactly one entry equal to 1.
This sequence is the BinomialMean transform of A000354. (See A075271 for definition.) - John W. Layman, Sep 12 2002 [This is easily verified from the Paul Barry formula for A000354, by interchanging summations and using the formula: Sum_k (-1)^k C(n-i, k) = KroneckerDelta(i,n). - David Callan, Aug 31 2003]
Number of distinct subsets of T(n-1) elements with 1 element A, 2 elements B, ..., n - 1 elements X (e.g., at n = 5, we consider the distinct subsets of ABBCCCDDDD and there are 5! = 120). - Jon Perry, Jun 12 2003
n! is the smallest number with that prime signature. E.g., 720 = 2^4 * 3^2 * 5. - Amarnath Murthy, Jul 01 2003
a(n) is the permanent of the n X n matrix M with M(i, j) = 1. - Philippe Deléham, Dec 15 2003
Given n objects of distinct sizes (e.g., areas, volumes) such that each object is sufficiently large to simultaneously contain all previous objects, then n! is the total number of essentially different arrangements using all n objects. Arbitrary levels of nesting of objects are permitted within arrangements. (This application of the sequence was inspired by considering leftover moving boxes.) If the restriction exists that each object is able or permitted to contain at most one smaller (but possibly nested) object at a time, the resulting sequence begins 1,2,5,15,52 (Bell Numbers?). Sets of nested wooden boxes or traditional nested Russian dolls come to mind here. - Rick L. Shepherd, Jan 14 2004
From Michael Somos, Mar 04 2004; edited by M. F. Hasler, Jan 02 2015: (Start)
Stirling transform of [2, 2, 6, 24, 120, ...] is A052856 = [2, 2, 4, 14, 76, ...].
Stirling transform of [1, 2, 6, 24, 120, ...] is A000670 = [1, 3, 13, 75, ...].
Stirling transform of [0, 2, 6, 24, 120, ...] is A052875 = [0, 2, 12, 74, ...].
Stirling transform of [1, 1, 2, 6, 24, 120, ...] is A000629 = [1, 2, 6, 26, ...].
Stirling transform of [0, 1, 2, 6, 24, 120, ...] is A002050 = [0, 1, 5, 25, 140, ...].
Stirling transform of (A165326*A089064)(1...) = [1, 0, 1, -1, 8, -26, 194, ...] is [1, 1, 2, 6, 24, 120, ...] (this sequence). (End)
First Eulerian transform of 1, 1, 1, 1, 1, 1... The first Eulerian transform transforms a sequence s to a sequence t by the formula t(n) = Sum_{k=0..n} e(n, k)s(k), where e(n, k) is a first-order Eulerian number [A008292]. - Ross La Haye, Feb 13 2005
Conjecturally, 1, 6, and 120 are the only numbers which are both triangular and factorial. - Christopher M. Tomaszewski (cmt1288(AT)comcast.net), Mar 30 2005
n! is the n-th finite difference of consecutive n-th powers. E.g., for n = 3, [0, 1, 8, 27, 64, ...] -> [1, 7, 19, 37, ...] -> [6, 12, 18, ...] -> [6, 6, ...]. - Bryan Jacobs (bryanjj(AT)gmail.com), Mar 31 2005
a(n+1) = (n+1)! = 1, 2, 6, ... has e.g.f. 1/(1-x)^2. - Paul Barry, Apr 22 2005
Write numbers 1 to n on a circle. Then a(n) = sum of the products of all n - 2 adjacent numbers. E.g., a(5) = 1*2*3 + 2*3*4 + 3*4*5 + 4*5*1 +5*1*2 = 120. - Amarnath Murthy, Jul 10 2005
The number of chains of maximal length in the power set of {1, 2, ..., n} ordered by the subset relation. - Rick L. Shepherd, Feb 05 2006
The number of circular permutations of n letters for n >= 0 is 1, 1, 1, 2, 6, 24, 120, 720, 5040, 40320, ... - Xavier Noria (fxn(AT)hashref.com), Jun 04 2006
a(n) is the number of deco polyominoes of height n (n >= 1; see definitions in the Barcucci et al. references). - Emeric Deutsch, Aug 07 2006
a(n) is the number of partition tableaux of size n. See Steingrimsson/Williams link for the definition. - David Callan, Oct 06 2006
Consider the n! permutations of the integer sequence [n] = 1, 2, ..., n. The i-th permutation consists of ncycle(i) permutation cycles. Then, if the Sum_{i=1..n!} 2^ncycle(i) runs from 1 to n!, we have Sum_{i=1..n!} 2^ncycle(i) = (n+1)!. E.g., for n = 3 we have ncycle(1) = 3, ncycle(2) = 2, ncycle(3) = 1, ncycle(4) = 2, ncycle(5) = 1, ncycle(6) = 2 and 2^3 + 2^2 + 2^1 + 2^2 + 2^1 + 2^2 = 8 + 4 + 2 + 4 + 2 + 4 = 24 = (n+1)!. - Thomas Wieder, Oct 11 2006
a(n) is the number of set partitions of {1, 2, ..., 2n - 1, 2n} into blocks of size 2 (perfect matchings) in which each block consists of one even and one odd integer. For example, a(3) = 6 counts 12-34-56, 12-36-45, 14-23-56, 14-25-36, 16-23-45, 16-25-34. - David Callan, Mar 30 2007
Consider the multiset M = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4, ...] = [1, 2, 2, ..., n x 'n'] and form the set U (where U is a set in the strict sense) of all subsets N (where N may be a multiset again) of M. Then the number of elements |U| of U is equal to (n+1)!. E.g. for M = [1, 2, 2] we get U = [[], [2], [2, 2], [1], [1, 2], [1, 2, 2]] and |U| = 3! = 6. This observation is a more formal version of the comment given already by Rick L. Shepherd, Jan 14 2004. - Thomas Wieder, Nov 27 2007
For n >= 1, a(n) = 1, 2, 6, 24, ... are the positions corresponding to the 1's in decimal expansion of Liouville's constant (A012245). - Paul Muljadi, Apr 15 2008
Triangle A144107 has n! for row sums (given n > 0) with right border n! and left border A003319, the INVERTi transform of (1, 2, 6, 24, ...). - Gary W. Adamson, Sep 11 2008
Equals INVERT transform of A052186 and row sums of triangle A144108. - Gary W. Adamson, Sep 11 2008
From Abdullahi Umar, Oct 12 2008: (Start)
a(n) is also the number of order-decreasing full transformations (of an n-chain).
a(n-1) is also the number of nilpotent order-decreasing full transformations (of an n-chain). (End)
n! is also the number of optimal broadcast schemes in the complete graph K_{n}, equivalent to the number of binomial trees embedded in K_{n} (see Calin D. Morosan, Information Processing Letters, 100 (2006), 188-193). - Calin D. Morosan (cd_moros(AT)alumni.concordia.ca), Nov 28 2008
Let S_{n} denote the n-star graph. The S_{n} structure consists of n S_{n-1} structures. This sequence gives the number of edges between the vertices of any two specified S_{n+1} structures in S_{n+2} (n >= 1). - K.V.Iyer, Mar 18 2009
Chromatic invariant of the sun graph S_{n-2}.
It appears that a(n+1) is the inverse binomial transform of A000255. - Timothy Hopper, Aug 20 2009
a(n) is also the determinant of a square matrix, An, whose coefficients are the reciprocals of beta function: a{i, j} = 1/beta(i, j), det(An) = n!. - Enrique Pérez Herrero, Sep 21 2009
The asymptotic expansions of the exponential integrals E(x, m = 1, n = 1) ~ exp(-x)/x*(1 - 1/x + 2/x^2 - 6/x^3 + 24/x^4 + ...) and E(x, m = 1, n = 2) ~ exp(-x)/x*(1 - 2/x + 6/x^2 - 24/x^3 + ...) lead to the factorial numbers. See A163931 and A130534 for more information. - Johannes W. Meijer, Oct 20 2009
Satisfies A(x)/A(x^2), A(x) = A173280. - Gary W. Adamson, Feb 14 2010
a(n) = G^n where G is the geometric mean of the first n positive integers. - Jaroslav Krizek, May 28 2010
Increasing colored 1-2 trees with choice of two colors for the rightmost branch of nonleaves. - Wenjin Woan, May 23 2011
Number of necklaces with n labeled beads of 1 color. - Robert G. Wilson v, Sep 22 2011
The sequence 1!, (2!)!, ((3!)!)!, (((4!)!)!)!, ..., ((...(n!)!)...)! (n times) grows too rapidly to have its own entry. See Hofstadter.
The e.g.f. of 1/a(n) = 1/n! is BesselI(0, 2*sqrt(x)). See Abramowitz-Stegun, p. 375, 9.3.10. - Wolfdieter Lang, Jan 09 2012
a(n) is the length of the n-th row which is the sum of n-th row in triangle A170942. - Reinhard Zumkeller, Mar 29 2012
Number of permutations of elements 1, 2, ..., n + 1 with a fixed element belonging to a cycle of length r does not depend on r and equals a(n). - Vladimir Shevelev, May 12 2012
a(n) is the number of fixed points in all permutations of 1, ..., n: in all n! permutations, 1 is first exactly (n-1)! times, 2 is second exactly (n-1)! times, etc., giving (n-1)!*n = n!. - Jon Perry, Dec 20 2012
For n >= 1, a(n-1) is the binomial transform of A000757. See Moreno-Rivera. - Luis Manuel Rivera Martínez, Dec 09 2013
Each term is divisible by its digital root (A010888). - Ivan N. Ianakiev, Apr 14 2014
For m >= 3, a(m-2) is the number hp(m) of acyclic Hamiltonian paths in a simple graph with m vertices, which is complete except for one missing edge. For m < 3, hp(m)=0. - Stanislav Sykora, Jun 17 2014
a(n) is the number of increasing forests with n nodes. - Brad R. Jones, Dec 01 2014
The factorial numbers can be calculated by means of the recurrence n! = (floor(n/2)!)^2 * sf(n) where sf(n) are the swinging factorials A056040. This leads to an efficient algorithm if sf(n) is computed via prime factorization. For an exposition of this algorithm see the link below. - Peter Luschny, Nov 05 2016
Treeshelves are ordered (plane) binary (0-1-2) increasing trees where the nodes of outdegree 1 come in 2 colors. There are n! treeshelves of size n, and classical Françon's bijection maps bijectively treeshelves into permutations. - Sergey Kirgizov, Dec 26 2016
Satisfies Benford's law [Diaconis, 1977; Berger-Hill, 2017] - N. J. A. Sloane, Feb 07 2017
a(n) = Sum((d_p)^2), where d_p is the number of standard tableaux in the Ferrers board of the integer partition p and summation is over all integer partitions p of n. Example: a(3) = 6. Indeed, the partitions of 3 are [3], [2,1], and [1,1,1], having 1, 2, and 1 standard tableaux, respectively; we have 1^2 + 2^2 + 1^2 = 6. - Emeric Deutsch, Aug 07 2017
a(n) is the n-th derivative of x^n. - Iain Fox, Nov 19 2017
a(n) is the number of maximum chains in the n-dimensional Boolean cube {0,1}^n in respect to the relation "precedes". It is defined as follows: for arbitrary vectors u, v of {0,1}^n, such that u = (u_1, u_2, ..., u_n) and v = (v_1, v_2, ..., v_n), "u precedes v" if u_i <= v_i, for i=1, 2, ..., n. - Valentin Bakoev, Nov 20 2017
a(n) is the number of shortest paths (for example, obtained by Breadth First Search) between the nodes (0,0,...,0) (i.e., the all-zeros vector) and (1,1,...,1) (i.e., the all-ones vector) in the graph H_n, corresponding to the n-dimensional Boolean cube {0,1}^n. The graph is defined as H_n = (V_n, E_n), where V_n is the set of all vectors of {0,1}^n, and E_n contains edges formed by each pair adjacent vectors. - Valentin Bakoev, Nov 20 2017
a(n) is also the determinant of the symmetric n X n matrix M defined by M(i,j) = sigma(gcd(i,j)) for 1 <= i,j <= n. - Bernard Schott, Dec 05 2018
a(n) is also the number of inversion sequences of length n. A length n inversion sequence e_1, e_2, ..., e_n is a sequence of n integers such that 0 <= e_i < i. - Juan S. Auli, Oct 14 2019
The term "factorial" ("factorielle" in French) was coined by the French mathematician Louis François Antoine Arbogast (1759-1803) in 1800. The notation "!" was first used by the French mathematician Christian Kramp (1760-1826) in 1808. - Amiram Eldar, Apr 16 2021
Also the number of signotopes of rank 2, i.e., mappings X:{{1..n} choose 2}->{+,-} such that for any three indices a < b < c, the sequence X(a,b), X(a,c), X(b,c) changes its sign at most once (see Felsner-Weil reference). - Manfred Scheucher, Feb 09 2022
a(n) is also the number of labeled commutative semisimple rings with n elements. As an example the only commutative semisimple rings with 4 elements are F_4 and F_2 X F_2. They both have exactly 2 automorphisms, hence a(4)=24/2+24/2=24. - Paul Laubie, Mar 05 2024
a(n) is the number of extremely unlucky Stirling permutations of order n+1; i.e., the number of Stirling permutations of order n+1 that have exactly one lucky car. - Bridget Tenner, Apr 09 2024

Examples

			There are 3! = 1*2*3 = 6 ways to arrange 3 letters {a, b, c}, namely abc, acb, bac, bca, cab, cba.
Let n = 2. Consider permutations of {1, 2, 3}. Fix element 3. There are a(2) = 2 permutations in each of the following cases: (a) 3 belongs to a cycle of length 1 (permutations (1, 2, 3) and (2, 1, 3)); (b) 3 belongs to a cycle of length 2 (permutations (3, 2, 1) and (1, 3, 2)); (c) 3 belongs to a cycle of length 3 (permutations (2, 3, 1) and (3, 1, 2)). - _Vladimir Shevelev_, May 13 2012
G.f. = 1 + x + 2*x^2 + 6*x^3 + 24*x^4 + 120*x^5 + 720*x^6 + 5040*x^7 + ...

References

  • M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 833.
  • A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 125; also p. 90, ex. 3.
  • Florian Cajori, A History of Mathematical Notations, Dover edition (2012), pars. 448-449.
  • John H. Conway and Richard K. Guy, The Book of Numbers, New York: Springer-Verlag, 1996. See pp. 64-66.
  • Jan Gullberg, Mathematics from the Birth of Numbers, W. W. Norton & Co., NY & London, 1997, §4.1 Symbols Galore, p. 106.
  • Douglas R. Hofstadter, Fluid concepts & creative analogies: computer models of the fundamental mechanisms of thought, Basic Books, 1995, pages 44-46.
  • A. N. Khovanskii. The Application of Continued Fractions and Their Generalizations to Problem in Approximation Theory. Groningen: Noordhoff, Netherlands, 1963. See p. 141 (10.19).
  • D. E. Knuth, The Art of Computer Programming, Vol. 3, Section 5.1.2, p. 23. [From N. J. A. Sloane, Apr 07 2014]
  • J.-M. De Koninck and A. Mercier, 1001 Problèmes en Théorie Classique des Nombres, Problème 693 pp. 90, 297, Ellipses Paris 2004.
  • A. P. Prudnikov, Yu. A. Brychkov, and O. I. Marichev, "Integrals and Series", Volume 1: "Elementary Functions", Chapter 4: "Finite Sums", New York, Gordon and Breach Science Publishers, 1986-1992.
  • R. W. Robinson, Counting arrangements of bishops, pp. 198-214 of Combinatorial Mathematics IV (Adelaide 1975), Lect. Notes Math., 560 (1976).
  • Sepher Yezirah [Book of Creation], circa AD 300. See verse 52.
  • 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).
  • Jerome Spanier and Keith B. Oldham, "Atlas of Functions", Hemisphere Publishing Corp., 1987, chapter 2, pages 19-24.
  • D. Stanton and D. White, Constructive Combinatorics, Springer, 1986; see p. 91.
  • Carlo Suares, Sepher Yetsira, Shambhala Publications, 1976. See verse 52.
  • David Wells, The Penguin Dictionary of Curious and Interesting Numbers, Penguin Books, 1987, pp. 102.

Links

Crossrefs

Cf. A000165, A001044, A001563, A003422, A009445, A010050, A012245, A033312, A034886, A038507, A047920, A048631.
Factorial base representation: A007623.
Cf. A003319, A052186, A144107, A144108. - Gary W. Adamson, Sep 11 2008
Complement of A063992. - Reinhard Zumkeller, Oct 11 2008
Cf. A053657, A163176. - Jonathan Sondow, Jul 26 2009
Cf. A173280. - Gary W. Adamson, Feb 14 2010
Boustrophedon transforms: A230960, A230961.
Cf. A233589.
Cf. A245334.
A row of the array in A249026.
Cf. A001013 (multiplicative closure).
For factorials with initial digit d (1 <= d <= 9) see A045509, A045510, A045511, A045516, A045517, A045518, A282021, A045519; A045520, A045521, A045522, A045523, A045524, A045525, A045526, A045527, A045528, A045529.
Cf. A000169, A075513, A152917, A258773.

Programs

  • Axiom
    [factorial(n) for n in 0..10]
  • GAP
    List([0..22],Factorial); # Muniru A Asiru, Dec 05 2018
  • Haskell
    a000142 :: (Enum a, Num a, Integral t) => t -> a
a000142 n = product [1 .. fromIntegral n]
a000142_list = 1 : zipWith (*) [1..] a000142_list
-- Reinhard Zumkeller, Mar 02 2014, Nov 02 2011, Apr 21 2011
  • Julia
    print([factorial(big(n)) for n in 0:28]) # Paul Muljadi, May 01 2024
  • Magma
    a:= func< n | Factorial(n) >; [ a(n) : n in [0..10]];
  • Maple
    A000142 := n -> n!; seq(n!,n=0..20);
spec := [ S, {S=Sequence(Z) }, labeled ]; seq(combstruct[count](spec,size=n), n=0..20);
# Maple program for computing cycle indices of symmetric groups
M:=6: f:=array(0..M): f[0]:=1: print(`n= `,0); print(f[0]); f[1]:=x[1]: print(`n= `, 1); print(f[1]); for n from 2 to M do f[n]:=expand((1/n)*add( x[l]*f[n-l],l=1..n)); print(`n= `, n); print(f[n]); od:
with(combstruct):ZL0:=[S,{S=Set(Cycle(Z,card>0))},labeled]: seq(count(ZL0,size=n),n=0..20); # Zerinvary Lajos, Sep 26 2007
  • Mathematica
    Table[Factorial[n], {n, 0, 20}] (* Stefan Steinerberger, Mar 30 2006 *)
FoldList[#1 #2 &, 1, Range@ 20] (* Robert G. Wilson v, May 07 2011 *)
Range[20]! (* Harvey P. Dale, Nov 19 2011 *)
RecurrenceTable[{a[n] == n*a[n - 1], a[0] == 1}, a, {n, 0, 22}] (* Ray Chandler, Jul 30 2015 *)
  • PARI
    a(n)=prod(i=1, n, i) \\ Felix Fröhlich, Aug 17 2014
  • PARI
    {a(n) = if(n<0, 0, n!)}; /* Michael Somos, Mar 04 2004 */
  • Python
    for i in range(1, 1000):
    y = i
    for j in range(1, i):
       y *= i - j
    print(y, "\n")
  • Python
    import math
for i in range(1, 1000):
    math.factorial(i)
    print("")
# Ruskin Harding, Feb 22 2013
  • Sage
    [factorial(n) for n in (1..22)] # Giuseppe Coppoletta, Dec 05 2014
  • Scala
    (1: BigInt).to(24: BigInt).scanLeft(1: BigInt)( * ) // Alonso del Arte, Mar 02 2019

Formula

Exp(x) = Sum_{m >= 0} x^m/m!. - Mohammad K. Azarian, Dec 28 2010
Sum_{i=0..n} (-1)^i * i^n * binomial(n, i) = (-1)^n * n!. - Yong Kong (ykong(AT)curagen.com), Dec 26 2000
Sum_{i=0..n} (-1)^i * (n-i)^n * binomial(n, i) = n!. - Peter C. Heinig (algorithms(AT)gmx.de), Apr 10 2007
The sequence trivially satisfies the recurrence a(n+1) = Sum_{k=0..n} binomial(n,k) * a(k)*a(n-k). - Robert FERREOL, Dec 05 2009
D-finite with recurrence: a(n) = n*a(n-1), n >= 1. n! ~ sqrt(2*Pi) * n^(n+1/2) / e^n (Stirling's approximation).
a(0) = 1, a(n) = subs(x = 1, (d^n/dx^n)(1/(2-x))), n = 1, 2, ... - Karol A. Penson, Nov 12 2001
E.g.f.: 1/(1-x). - Michael Somos, Mar 04 2004
a(n) = Sum_{k=0..n} (-1)^(n-k)*A000522(k)*binomial(n, k) = Sum_{k=0..n} (-1)^(n-k)*(x+k)^n*binomial(n, k). - Philippe Deléham, Jul 08 2004
Binomial transform of A000166. - Ross La Haye, Sep 21 2004
a(n) = Sum_{i=1..n} ((-1)^(i-1) * sum of 1..n taken n - i at a time) - e.g., 4! = (1*2*3 + 1*2*4 + 1*3*4 + 2*3*4) - (1*2 + 1*3 + 1*4 + 2*3 + 2*4 + 3*4) + (1 + 2 + 3 + 4) - 1 = (6 + 8 + 12 + 24) - (2 + 3 + 4 + 6 + 8 + 12) + 10 - 1 = 50 - 35 + 10 - 1 = 24. - Jon Perry, Nov 14 2005
a(n) = (n-1)*(a(n-1) + a(n-2)), n >= 2. - Matthew J. White, Feb 21 2006
1 / a(n) = determinant of matrix whose (i,j) entry is (i+j)!/(i!(j+1)!) for n > 0. This is a matrix with Catalan numbers on the diagonal. - Alexander Adamchuk, Jul 04 2006
Hankel transform of A074664. - Philippe Deléham, Jun 21 2007
For n >= 2, a(n-2) = (-1)^n*Sum_{j=0..n-1} (j+1)*Stirling1(n,j+1). - Milan Janjic, Dec 14 2008
From Paul Barry, Jan 15 2009: (Start)
G.f.: 1/(1-x-x^2/(1-3x-4x^2/(1-5x-9x^2/(1-7x-16x^2/(1-9x-25x^2... (continued fraction), hence Hankel transform is A055209.
G.f. of (n+1)! is 1/(1-2x-2x^2/(1-4x-6x^2/(1-6x-12x^2/(1-8x-20x^2... (continued fraction), hence Hankel transform is A059332. (End)
a(n) = Product_{p prime} p^(Sum_{k > 0} floor(n/p^k)) by Legendre's formula for the highest power of a prime dividing n!. - Jonathan Sondow, Jul 24 2009
a(n) = A053657(n)/A163176(n) for n > 0. - Jonathan Sondow, Jul 26 2009
It appears that a(n) = (1/0!) + (1/1!)*n + (3/2!)*n*(n-1) + (11/3!)*n*(n-1)*(n-2) + ... + (b(n)/n!)*n*(n-1)*...*2*1, where a(n) = (n+1)! and b(n) = A000255. - Timothy Hopper, Aug 12 2009
Sum_{n >= 0} 1/a(n) = e. - Jaume Oliver Lafont, Mar 03 2009
a(n) = a(n-1)^2/a(n-2) + a(n-1), n >= 2. - Jaume Oliver Lafont, Sep 21 2009
a(n) = Gamma(n+1). - Enrique Pérez Herrero, Sep 21 2009
a(n) = A173333(n,1). - Reinhard Zumkeller, Feb 19 2010
a(n) = A_{n}(1) where A_{n}(x) are the Eulerian polynomials. - Peter Luschny, Aug 03 2010
a(n) = n*(2*a(n-1) - (n-1)*a(n-2)), n > 1. - Gary Detlefs, Sep 16 2010
1/a(n) = -Sum_{k=1..n+1} (-2)^k*(n+k+2)*a(k)/(a(2*k+1)*a(n+1-k)). - Groux Roland, Dec 08 2010
From Vladimir Shevelev, Feb 21 2011: (Start)
a(n) = Product_{p prime, p <= n} p^(Sum_{i >= 1} floor(n/p^i)).
The infinitary analog of this formula is: a(n) = Product_{q terms of A050376 <= n} q^((n)_q), where (n)_q denotes the number of those numbers <= n for which q is an infinitary divisor (for the definition see comment in A037445). (End)
The terms are the denominators of the expansion of sinh(x) + cosh(x). - Arkadiusz Wesolowski, Feb 03 2012
G.f.: 1 / (1 - x / (1 - x / (1 - 2*x / (1 - 2*x / (1 - 3*x / (1 - 3*x / ... )))))). - Michael Somos, May 12 2012
G.f. 1 + x/(G(0)-x) where G(k) = 1 - (k+1)*x/(1 - x*(k+2)/G(k+1)); (continued fraction, 2-step). - Sergei N. Gladkovskii, Aug 14 2012
G.f.: W(1,1;-x)/(W(1,1;-x) - x*W(1,2;-x)), where W(a,b,x) = 1 - a*b*x/1! + a*(a+1)*b*(b+1)*x^2/2! - ... + a*(a+1)*...*(a+n-1)*b*(b+1)*...*(b+n-1)*x^n/n! + ...; see [A. N. Khovanskii, p. 141 (10.19)]. - Sergei N. Gladkovskii, Aug 15 2012
From Sergei N. Gladkovskii, Dec 26 2012: (Start)
G.f.: A(x) = 1 + x/(G(0) - x) where G(k) = 1 + (k+1)*x - x*(k+2)/G(k+1); (continued fraction).
Let B(x) be the g.f. for A051296, then A(x) = 2 - 1/B(x). (End)
G.f.: 1 + x*(G(0) - 1)/(x-1) where G(k) = 1 - (2*k+1)/(1-x/(x - 1/(1 - (2*k+2)/(1-x/(x - 1/G(k+1) ))))); (continued fraction). - Sergei N. Gladkovskii, Jan 15 2013
G.f.: 1 + x*(1 - G(0))/(sqrt(x)-x) where G(k) = 1 - (k+1)*sqrt(x)/(1-sqrt(x)/(sqrt(x)-1/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jan 25 2013
G.f.: 1 + x/G(0) where G(k) = 1 - x*(k+2)/( 1 - x*(k+1)/G(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Mar 23 2013
a(n) = det(S(i+1, j), 1 <= i, j <=n ), where S(n,k) are Stirling numbers of the second kind. - Mircea Merca, Apr 04 2013
G.f.: G(0)/2, where G(k) = 1 + 1/(1 - x*(k+1)/(x*(k+1) + 1/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 24 2013
G.f.: 2/G(0), where G(k) = 1 + 1/(1 - 1/(1 - 1/(2*x*(k+1)) + 1/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 29 2013
G.f.: G(0), where G(k) = 1 + x*(2*k+1)/(1 - x*(2*k+2)/(x*(2*k+2) + 1/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 07 2013
a(n) = P(n-1, floor(n/2)) * floor(n/2)! * (n - (n-2)*((n+1) mod 2)), where P(n, k) are the k-permutations of n objects, n > 0. - Wesley Ivan Hurt, Jun 07 2013
a(n) = a(n-2)*(n-1)^2 + a(n-1), n > 1. - Ivan N. Ianakiev, Jun 18 2013
a(n) = a(n-2)*(n^2-1) - a(n-1), n > 1. - Ivan N. Ianakiev, Jun 30 2013
G.f.: 1 + x/Q(0), m=+2, where Q(k) = 1 - 2*x*(2*k+1) - m*x^2*(k+1)*(2*k+1)/( 1 - 2*x*(2*k+2) - m*x^2*(k+1)*(2*k+3)/Q(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Sep 24 2013
a(n) = A245334(n,n). - Reinhard Zumkeller, Aug 31 2014
a(n) = Product_{i = 1..n} A014963^floor(n/i) = Product_{i = 1..n} A003418(floor(n/i)). - Matthew Vandermast, Dec 22 2014
a(n) = round(Sum_{k>=1} log(k)^n/k^2), for n>=1, which is related to the n-th derivative of the Riemann zeta function at x=2 as follows: round((-1)^n * zeta^(n)(2)). Also see A073002. - Richard R. Forberg, Dec 30 2014
a(n) ~ Sum_{j>=0} j^n/e^j, where e = A001113. When substituting a generic variable for "e" this infinite sum is related to Eulerian polynomials. See A008292. This approximation of n! is within 0.4% at n = 2. See A255169. Accuracy, as a percentage, improves rapidly for larger n. - Richard R. Forberg, Mar 07 2015
a(n) = Product_{k=1..n} (C(n+1, 2)-C(k, 2))/(2*k-1); see Masanori Ando link. - Michel Marcus, Apr 17 2015
Sum_{n>=0} a(n)/(a(n + 1)*a(n + 2)) = Sum_{n>=0} 1/((n + 2)*(n + 1)^2*a(n)) = 2 - exp(1) - gamma + Ei(1) = 0.5996203229953..., where gamma = A001620, Ei(1) = A091725. - Ilya Gutkovskiy, Nov 01 2016
a(2^n) = 2^(2^n - 1) * 1!! * 3!! * 7!! * ... * (2^n - 1)!!. For example, 16! = 2^15*(1*3)*(1*3*5*7)*(1*3*5*7*9*11*13*15) = 20922789888000. - Peter Bala, Nov 01 2016
a(n) = sum(prod(B)), where the sum is over all subsets B of {1,2,...,n-1} and where prod(B) denotes the product of all the elements of set B. If B is a singleton set with element b, then we define prod(B)=b, and, if B is the empty set, we define prod(B) to be 1. For example, a(4)=(1*2*3)+(1*2)+(1*3)+(2*3)+(1)+(2)+(3)+1=24. - Dennis P. Walsh, Oct 23 2017
Sum_{n >= 0} 1/(a(n)*(n+2)) = 1. - Multiplying the denominator by (n+2) in Jaume Oliver Lafont's entry above creates a telescoping sum. - Fred Daniel Kline, Nov 08 2020
O.g.f.: Sum_{k >= 0} k!*x^k = Sum_{k >= 0} (k+y)^k*x^k/(1 + (k+y)*x)^(k+1) for arbitrary y. - Peter Bala, Mar 21 2022
E.g.f.: 1/(1 + LambertW(-x*exp(-x))) = 1/(1-x), see A258773. -(1/x)*substitute(z = x*exp(-x), z*(d/dz)LambertW(-z)) = 1/(1 - x). See A075513. Proof: Use the compositional inverse (x*exp(-x))^[-1] = -LambertW(-z). See A000169 or A152917, and Richard P. Stanley: Enumerative Combinatorics, vol. 2, p. 37, eq. (5.52). - Wolfdieter Lang, Oct 17 2022
Sum_{k >= 1} 1/10^a(k) = A012245 (Liouville constant). - Bernard Schott, Dec 18 2022
From David Ulgenes, Sep 19 2023: (Start)
1/a(n) = (e/(2*Pi*n)*Integral_{x=-oo..oo} cos(x-n*arctan(x))/(1+x^2)^(n/2) dx). Proof: take the real component of Laplace's integral for 1/Gamma(x).
a(n) = Integral_{x=0..1} e^(-t)*LerchPhi(1/e, -n, t) dt. Proof: use the relationship Gamma(x+1) = Sum_{n >= 0} Integral_{t=n..n+1} e^(-t)t^x dt = Sum_{n >= 0} Integral_{t=0..1} e^(-(t+n))(t+n)^x dt and interchange the order of summation and integration.
Conjecture: a(n) = 1/(2*Pi)*Integral_{x=-oo..oo}(n+i*x+1)!/(i*x+1)-(n+i*x-1)!/(i*x-1)dx. (End)
a(n) = floor(b(n)^n / (floor(((2^b(n) + 1) / 2^n)^b(n)) mod 2^b(n))), where b(n) = (n + 1)^(n + 2) = A007778(n+1). Joint work with Mihai Prunescu. - Lorenzo Sauras Altuzarra, Oct 18 2023
a(n) = e^(Integral_{x=1..n+1} Psi(x) dx) where Psi(x) is the digamma function. - Andrea Pinos, Jan 10 2024
a(n) = Integral_{x=0..oo} e^(-x^(1/n)) dx, for n > 0. - Ridouane Oudra, Apr 20 2024
O.g.f.: N(x) = hypergeometric([1,1], [], x) = LaplaceTransform(x/(1-x))/x, satisfying x^2*N'(x) + (x-1)*N(x) + 1 = 0, with N(0) = 1. - Wolfdieter Lang, May 31 2025

A000166 Subfactorial or rencontres numbers, or derangements: number of permutations of n elements with no fixed points.

Original entry on oeis.org

1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, 176214841, 2290792932, 32071101049, 481066515734, 7697064251745, 130850092279664, 2355301661033953, 44750731559645106, 895014631192902121, 18795307255050944540, 413496759611120779881, 9510425471055777937262
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Euler (1809) 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) = n*a(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énien 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) is the 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
Convolution of sequence A135799 with the sequence generated by 1+x^2/(2*x+1). - Thomas Baruchel, Jan 08 2016
The number of interior lattice points of the subpolytope of the n-dimensional permutohedron whose vertices correspond to permutations avoiding 132 and 312. - Robert Davis, Oct 05 2016
Consider n circles of different radii, where each circle is either put inside some bigger circle or contains a smaller circle inside it (no common points are allowed). Then a(n) gives the number of such combinations. - Anton Zakharov, Oct 12 2016
If we partition the permutations of [n+1] in A000240 according to their starting digit, we will get (n+1) equinumerous classes each of size a(n), i.e., A000240(n+1) = (n+1)*a(n), hence a(n) is the size of each class of permutations of [n+1] in A000240. For example, for n = 4 we have 45 = 5*9. - Enrique Navarrete, Jan 10 2017
Call d_n1 the permutations of [n] that have the substring n1 but no substring in {12,23,...,(n-1)n}. If we partition them according to their starting digit, we will get (n-1) equinumerous classes each of size A000166(n-2) (the class starting with the digit 1 is empty since we must have the substring n1). Hence d_n1 = (n-1)*A000166(n-2) and A000166(n-2) is the size of each nonempty class in d_n1. For example, d_71 = 6*44 = 264, so there are 264 permutations in d_71 distributed in 6 nonempty classes of size A000166(5) = 44. (To get permutations in d_n1 recursively from more basic ones see the link "Forbidden Patterns" below.) - Enrique Navarrete, Jan 15 2017
Also the number of maximum matchings and minimum edge covers in the n-crown graph. - Eric W. Weisstein, Jun 14 and Dec 24 2017
The sequence a(n) taken modulo a positive integer k is periodic with exact period dividing k when k is even and dividing 2*k when k is odd. This follows from the congruence a(n+k) = (-1)^k*a(n) (mod k) for all n and k, which in turn is easily proved by induction making use of the recurrence a(n) = n*a(n-1) + (-1)^n. - Peter Bala, Nov 21 2017
a(n) is the number of distinct possible solutions for a directed, no self loop containing graph (not necessarily connected) that has n vertices, and each vertex has an in- and out-degree of exactly 1. - Patrik Holopainen, Sep 18 2018
a(n) is the dimension of the kernel of the random-to-top and random-to-random shuffling operators over a collection of n objects (in a vector space of size n!), as noticed by M. Wachs and V. Reiner. See the Reiner, Saliola and Welker reference below. - Nadia Lafreniere, Jul 18 2019
a(n) is the number of distinct permutations for a Secret Santa gift exchange with n participants. - Patrik Holopainen, Dec 30 2019
a(2*n+1) is even. More generally, a(m*n+1) is divisible by m*n, which follows from a(n+1) = n*(a(n) + a(n-1)) = n*A000255(n-1) for n >= 1. a(2*n) is odd; in fact, a(2*n) == 1 (mod 8). Other divisibility properties include a(6*n) == 1 (mod 24), a(9*n+4) == a(9*n+7) == 0 (mod 9), a(10*n) == 1 (mod 40), a(11*n+5) == 0 (mod 11) and a(13*n+8 ) == 0 (mod 13). - Peter Bala, Apr 05 2022
Conjecture: a(n) with n > 2 is a perfect power only for n = 4 with a(4) = 3^2. This has been verified for n <= 1000. - Zhi-Wei Sun, Jan 09 2025

Examples

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

References

  • U. Abel, Some new identities for derangement numbers, Fib. Q., 56:4 (2018), 313-318.
  • M. Bona, Combinatorics of Permutations, Chapman & Hall/CRC, Boca Raton, Florida, 2004.
  • Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 32.
  • 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.
  • L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 182.
  • Florence Nightingale David and D. E. Barton, Combinatorial Chance. Hafner, NY, 1962, p. 168.
  • Florence Nightingale David, Maurice George Kendall, and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 263, Table 7.5.1, row 1.
  • 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.
  • J. M. de Saint-Martin, "Le problème 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.
  • Leonhard 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.
  • 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).
  • Irving Kaplansky, John Riordan, The problème des ménages. Scripta Math. 12 (1946), 113-124. See Eq(1).
  • Arnold Kaufmann, "Introduction à la combinatorique en vue des applications." Dunod, Paris, 1968. See p. 92.
  • 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.
  • M. S. Petković, "Non-attacking rooks", Famous Puzzles of Great Mathematicians, pp. 265-268, Amer. Math. Soc.(AMS), 2009.
  • V. Reiner, F. Saliola, and V. Welker. Spectra of Symmetrized Shuffling Operators, Memoirs of the American Mathematical Society, vol. 228, Amer. Math. Soc., Providence, RI, 2014, pp. 1-121. See section VI.9.
  • J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 65.
  • 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).
  • David Wells, The Penguin Dictionary of Curious and Interesting Numbers. Penguin Books, NY, 1986, Revised edition 1987. See p. 122.
  • D. B. West, Combinatorial Mathematics, Cambridge, 2021, p. 82.
  • H. S. Wilf, Generatingfunctionology, Academic Press, NY, 1990, p. 147, Eq. 5.2.9 (q=1).

Links

Crossrefs

Cf. A000142, A002467, A003221, A000522, A000240, A000387, A000449, A000475, A129135, A092582, A000255, A002469, A159610, A068985, A068996, A047865, A038205, A008279, A281682.
For the probabilities a(n)/n!, see A053557/A053556 and A103816/A053556.
A diagonal of A008291 and A068106. Column A008290(n,0).
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).
Column k=0 of A086764 and of A334715. Column k=1 of A364068.
Row sums of A216963 and of A323671.

Programs

  • Haskell
    a000166 n = a000166_list !! n
a000166_list = 1 : 0 : zipWith (*) [1..]
                       (zipWith (+) a000166_list $ tail a000166_list)
-- Reinhard Zumkeller, Dec 09 2012
  • Magma
    I:=[0,1]; [1] cat [n le 2 select I[n] else (n-1)*(Self(n-1)+Self(n-2)): n in [1..30]]; // Vincenzo Librandi, Jan 07 2016
  • 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
seq(simplify(KummerU(-n, -n, -1)), n = 0..23); # Peter Luschny, May 10 2022
  • 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 *)
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_] := (-1)^n HypergeometricPFQ[{- n, 1}, {}, 1]; (* Michael Somos, Jun 01 2013 *)
a[n_] := n! SeriesCoefficient[Exp[-x] /(1 - x), {x, 0, n}]; (* Michael Somos, Jun 01 2013 *)
Table[Subfactorial[n], {n, 0, 21}] (* Jean-François Alcover, Jan 10 2014 *)
RecurrenceTable[{a[n] == n*a[n - 1] + (-1)^n, a[0] == 1}, a, {n, 0, 23}] (* Ray Chandler, Jul 30 2015 *)
Subfactorial[Range[0, 20]] (* Eric W. Weisstein, Dec 31 2017 *)
nxt[{n_,a_}]:={n+1,a(n+1)+(-1)^(n+1)}; NestList[nxt,{0,1},25][[All,2]] (* Harvey P. Dale, Jun 01 2019 *)
  • Maxima
    s[0]:1$
s[n]:=n*s[n-1]+(-1)^n$
makelist(s[n],n,0,12); /* Emanuele Munarini, Mar 01 2011 */
  • PARI
    {a(n) = if( n<1, 1, n * a(n-1) + (-1)^n)}; /* Michael Somos, Mar 24 2003 */
  • PARI
    {a(n) = 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
  • PARI
    apply( {A000166(n)=n!\/exp(n>0)}, [0..22]) \\ M. F. Hasler, Nov 09 2024
  • Python
    See Hobson link.
  • Python
    A000166_list, m, x = [], 1, 1
for n in range(10*2):
    x, m = x*n + m, -m
    A000166_list.append(x) # Chai Wah Wu, Nov 03 2014

Formula

(A000166 + A000522)/2 = A009179, (A000166 - A000522)/2 = A009628.
a(n) = A008290(n,0).
a(n) + A003048(n+1) = 2*n!. - 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) = round(n!/e) = floor(n!/e + 1/2) for n > 0.
a(n) = n!*Sum_{k=0..n} (-1)^k/k!.
D-finite with recurrence 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).
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
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..oo} (x-1)^n*exp(-x) dx. - Gerald McGarvey, Oct 14 2006
a(n) = Sum_{k=2,4,...} T(n,k), where T(n,k) = A092582(n,k) = k*n!/(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. (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_{p in Pano1(n)} M2(p), 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
Integral_{x=0..1} x^n*exp(x) = (-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
From Sergei N. Gladkovskii, Nov 25 2011, Jul 05 2012, Sep 23 2012, Oct 13 2012, Mar 09 2013, Mar 10 2013, Oct 18 2013: (Start)
Continued fractions:
In general, e.g.f. (1+a*x)/exp(b*x) = U(0) with U(k) = 1 + a*x/(1-b/(b-a*(k+1)/U(k+1))). For a=-1, b=-1: exp(-x)/(1-x) = 1/U(0).
E.g.f.: (1-x/(U(0)+x))/(1-x), where U(k) = k+1 - x + (k+1)*x/U(k+1).
E.g.f.: 1/Q(0) where Q(k) = 1 - x/(1 - 1/(1 - (k+1)/Q(k+1))).
G.f.: 1/U(0) where U(k) = 1 + x - x*(k+1)/(1 - x*(k+1)/U(k+1)).
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))).
G.f.: 1/Q(0) where Q(k) = 1 - 2*k*x - x^2*(k + 1)^2/Q(k+1).
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)). (End)
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
a(n) = Sum_{k = 0..n} (-1)^(n-k)*binomial(n,k)*(k + x)^k*(k + x + 1)^(n-k) = Sum_{k = 0..n} (-1)^(n-k)*binomial(n,k)*(k + x)^(n-k)*(k + x - 1)^k, for arbitrary x. - Peter Bala, Feb 19 2017
From Peter Luschny, Jun 20 2017: (Start)
a(n) = Sum_{j=0..n} Sum_{k=0..n} binomial(-j-1, -n-1)*abs(Stirling1(j, k)).
a(n) = Sum_{k=0..n} (-1)^(n-k)*Pochhammer(n-k+1, k) (cf. A008279). (End)
a(n) = n! - Sum_{j=0..n-1} binomial(n,j) * a(j). - Alois P. Heinz, Jan 23 2019
Sum_{n>=2} 1/a(n) = A281682. - Amiram Eldar, Nov 09 2020
a(n) = KummerU(-n, -n, -1). - Peter Luschny, May 10 2022
a(n) = (-1)^n*Sum_{k=0..n} Bell(k)*Stirling1(n+1, k+1). - Mélika Tebni, Jul 05 2022

Extensions

Minor edits by M. F. Hasler, Jan 16 2017

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

Original entry on oeis.org

1, 1, 3, 11, 53, 309, 2119, 16687, 148329, 1468457, 16019531, 190899411, 2467007773, 34361893981, 513137616783, 8178130767479, 138547156531409, 2486151753313617, 47106033220679059, 939765362752547227, 19690321886243846661, 432292066866171724421
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

a(n) counts permutations of [1,...,n+1] having no substring [k,k+1]. - Len Smiley, Oct 13 2001
Also, for n > 0, determinant of the tridiagonal n X n matrix M such that M(i,i)=i and for i=1..n-1, M(i,i+1)=-1, M(i+1,i)=i. - Mario Catalani (mario.catalani(AT)unito.it), Feb 04 2003
Also, for n > 0, maximal permanent of a nonsingular n X n (0,1)-matrix, which is achieved by the matrix with just n-1 0's, all on main diagonal. [For proof, see next entry.] - W. Edwin Clark, Oct 28 2003
Proof from Richard Brualdi and W. Edwin Clark, Nov 15 2003: Let n >= 4. Take an n X n (0,1)-matrix A which is nonsingular. It has t >= n-1, 0's, otherwise there will be two rows of all 1's. Let B be the matrix obtained from A by replacing t-(n-1) of A's 0's with 1's. Let D be the matrix with all 1's except for 0's in the first n-1 positions on the diagonal. This matrix is easily seen to be non-singular. Now we have per(A) < = per(B) < = per (D), where the first inequality follows since replacing 0's by 1's cannot decrease the permanent and the second from Corollary 4.4 in the Brualdi et al. reference, which shows that per(D) is the maximum permanent of ANY n X n matrix with n -1 0's. Corollary 4.4 requires n >= 4. a(n) for n < 4 can be computed directly.
With offset 1, permanent of (0,1)-matrix of size n X (n+d) with d=1 and n zeros not on a line. This is a special case of Theorem 2.3 of Seok-Zun Song et al., Extremes of permanents of (0,1)-matrices, pp. 201-202. - Jaap Spies, Dec 12 2003
Number of fixed-point-free permutations of n+2 that begin with a 2; e.g., for 1234, we have 2143, 2341, 2413, so a(2)=3. Also number of permutations of 2..n+2 that have no agreements with 1..n+1. E.g., for 123 against permutations of 234, we have 234, 342 and 432. Compare A047920. - Jon Perry, Jan 23 2004. [This can be proved by the standard argument establishing that d(n+2) = (n+1)(d(n+1)+d(n)) for derangements A000166 (n+1 choices of where 1 goes, then either 1 is in a transposition, or in a cycle of length at least 3, etc.). - D. G. Rogers, Aug 28 2006]
Stirling transform of A006252(n+1)=[1,1,2,4,14,38,...] is a(n)=[1,3,11,53,309,...]. - Michael Somos, Mar 04 2004
a(n+1) is the sequence of numerators of the self-convergents to 1/(e-2); see A096654. - Clark Kimberling, Jul 01 2004
Euler's interpretation was "fixedpoint-free permutations beginning with 2" and he listed the terms up to 148329 (although he was blind at the time). - Don Knuth, Jan 25 2007
Equals lim_{k->infinity} A153869^k. - Gary W. Adamson, Jan 03 2009
Hankel transform is A059332. - Paul Barry, Apr 22 2009
This sequence appears in the analysis of Euler's divergent series 1 - 1! + 2! - 3! + 4! ... by Lacroix, see Hardy. For information about this and related divergent series see A163940. - Johannes W. Meijer, Oct 16 2009
a(n), n >= 1, enumerates also the ways to distribute n beads, labeled differently from 1 to n, over a set of (unordered) necklaces, excluding necklaces with exactly one bead, and one open cord allowed to have any number of beads. Each beadless necklace as well as the beadless cord contributes a factor 1 in the counting, e.g., a(0):=1*1=1. There are k! possibilities for the cord with k>=0 beads, which means that the two ends of the cord should be considered as fixed, in short: a fixed cord. This produces for a(n) the exponential (aka binomial) convolution of the sequences {n!=A000142(n)} and the subfactorials {A000166(n)}.
See the formula below. Alternatively, the e.g.f. for this problem is seen to be (exp(-x)/(1-x))*(1/(1-x)), namely the product of the e.g.f.s for the subfactorials (from the unordered necklace problem, without necklaces with exactly one bead) and the factorials (from the fixed cord problem). Therefore the recurrence with inputs holds also. 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 02 2010
a(n) = (n-1)a(n-1) + (n-2)a(n-2) gives the same sequence offset by a 1. - Jon Perry, Sep 20 2012
Also, number of reduced 2 X (n+2) Latin rectangles. - A.H.M. Smeets, Nov 03 2013
Second column of Euler's difference table (second diagonal in example of A068106). - Enrique Navarrete, Dec 13 2016
If we partition the permutations of [n+2] in A000166 according to their starting digit, we will get (n+1) equinumerous classes each of size a(n) (the class starting with the digit 1 is empty since no derangement starts with 1). Hence, A000166(n+2)=(n+1)*a(n), so a(n) is the size of each nonempty class of permutations of [n+2] in A000166. For example, for n=3 we have 44=4*11 (see link). - Enrique Navarrete, Jan 11 2017
For n >= 1, the number of circular permutations (in cycle notation) on [n+2] that avoid substrings (j,j+2), 1 <= j <= n. For example, for n=2, the 3 circular permutations in S4 that avoid substrings {13,24} are (1234),(1423),(1432). Note that each of these circular permutations represent 4 permutations in one-line notation (see link 2017). - Enrique Navarrete, Feb 15 2017
The sequence a(n) taken modulo a positive integer k is periodic with exact period dividing k when k is even and dividing 2*k when k is odd. This follows from the congruence a(n+k) = (-1)^k*a(n) (mod k) holding for all n and k, which in turn is easily proved by induction making use of the given recurrences. - Peter Bala, Nov 21 2017
Number of permutations of [n] where the k-th fixed points are k-colored and all other points are unicolored. - Alois P. Heinz, Apr 28 2025

Examples

			a(3)=11: 1 3 2 4; 1 4 3 2; 2 1 4 3; 2 4 1 3; 3 2 1 4; 3 2 4 1; 4 1 3 2; 4 2 1 3; 4 3 2 1; 2 4 3 1; 3 1 4 2. The last two correspond to (n-1)*a(n-2) since they contain a [j,n+1,j+1].
Cord-necklaces problem. For n=4 one considers the following weak two part compositions of 4: (4,0), (2,2), (1,3), and (0,4), where (3,1) does not appear because there are no necklaces with 1 bead. These compositions contribute respectively 4!*1, (binomial(4,2)*2)*sf(2), (binomial(4,1)*1)*sf(3), and 1*sf(4) with the subfactorials sf(n):=A000166(n) (see the necklace comment there). This adds up as 24 + 6*2 + 4*2 + 9 = 53 = a(4). - _Wolfdieter Lang_, Jun 02 2010
G.f. = 1 + x + 3*x^2 + 11*x^3 + 53*x^4 + 309*x^5 + 2119*x^6 + 16687*x^7 + ...

References

  • Richard A. Brualdi and Herbert J. Ryser, Combinatorial Matrix Theory, Camb. Univ. Press, 1991, Section 7.2, p. 202.
  • Charalambos A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC, Boca Raton, Florida, 2002, p. 179, Table 5.4 and p. 177 (5.1).
  • CRC Handbook of Combinatorial Designs, 1996, p. 104.
  • F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, pp. 263-264. See Table 7.5.1, row 0; also Table 7.6.1, row 0.
  • John Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 188.
  • 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).
  • N. Ya. Vilenkin, Combinatorics, pp. 54 - 56, Academic Press, 1971. Caravan in the Desert, E_n = a(n-1), n >= 1.

Links

Crossrefs

Row sums of triangle in A046740. A diagonal of triangle in A068106.
Cf. A000153, A000166, A000261, A001909, A001910, A055790.
Cf. A090010, A090012, A090013, A090014, A090015, A090016.
A052655 gives occurrence count for non-singular (0, 1)-matrices with maximal permanent, A089475 number of different values of permanent, A089480 occurrence counts for permanents all non-singular (0, 1)-matrices, A087982, A087983.
A diagonal in triangle A010027.
Cf. A153869, A159610, A002469.
a(n) = A086764(n+1,1).

Programs

  • Haskell
    a000255 n = a000255_list !! n
a000255_list = 1 : 1 : zipWith (+) zs (tail zs) where
   zs = zipWith (*) [1..] a000255_list
-- Reinhard Zumkeller, Dec 05 2011
  • Magma
    I:=[1, 3]; [1] cat  [n le 2 select I[n] else n*Self(n-1)+(n-1)*Self(n-2): n in [1..30]]; // Vincenzo Librandi, Aug 09 2018
  • Maple
    a := n -> hypergeom([2,-n], [], 1)*(-1)^n:
seq(simplify(a(n)), n=0..19); # Peter Luschny, Sep 20 2014
seq(simplify(KummerU(-n, -n-1, -1)), n=0..21); # Peter Luschny, May 10 2022
  • Mathematica
    c = CoefficientList[Series[Exp[ -z]/(1 - z)^2, {z, 0, 30}], z]; For[n = 0, n < 31, n++; Print[c[[n]]*(n - 1)! ]]
Table[Subfactorial[n] + Subfactorial[n + 1], {n, 0, 20}] (* Zerinvary Lajos, Jul 09 2009 *)
RecurrenceTable[{a[n]==n a[n-1]+(n-1)a[n-2],a[0]==1,a[1]==1},a[n], {n,20}] (* Harvey P. Dale, May 10 2011 *)
a[ n_] := If[ n < 0, 0, Round[ n! (n + 2) / E]] (* Michael Somos, Jun 01 2013 *)
a[ n_] := If[ n < 0, 0, n! SeriesCoefficient[ Exp[ -x] / (1 - x)^2, {x, 0, n}]] (* Michael Somos, Jun 01 2013 *)
a[ n_] := If[ n < 0, 0, (-1)^n HypergeometricPFQ[ {- n, 2}, {}, 1]] (* Michael Somos, Jun 01 2013 *)
sa[k_Integer]/;k>=2 := SparseArray[{{i_, i_} -> i, Band[{2, 1}] -> -1, {i_, j_} /; (i == j - 1) :> i}, {k, k}]; {1, 1}~Join~Array[Det[sa[#]] &, 20, 2] (* Shenghui Yang, Oct 15 2024 *)
  • PARI
    {a(n) = if( n<0, 0, contfracpnqn( matrix( 2, n, i, j, j - (i==1)))[1, 1])};
  • PARI
    {a(n) = if( n<0, 0, n! * polcoeff( exp( -x + x * O(x^n)) / (1 - x)^2, n))};
  • Sage
    from sage.combinat.sloane_functions import ExtremesOfPermanentsSequence2
e = ExtremesOfPermanentsSequence2()
it = e.gen(1,1,1)
[next(it) for i in range(20)]
# Zerinvary Lajos, May 15 2009

Formula

E.g.f.: exp(-x)/(1-x)^2.
a(n) = Sum_{k=0..n} (-1)^k * (n-k+1) * n!/k!. - Len Smiley
Inverse binomial transform of (n+1)!. - Robert A. Stump (bee_ess107(AT)yahoo.com), Dec 09 2001
a(n-2) = !n/(n - 1) where !n is the subfactorial of n, A000166(n). - Lekraj Beedassy, Jun 18 2002
a(n) = floor((1/e)*n!*(n+2)+1/2). - Benoit Cloitre, Jan 15 2004
Apparently lim_{n->infinity} log(n) - log(a(n))/n = 1. - Gerald McGarvey, Jun 12 2004
a(n) = (n*(n+2)*a(n-1) + (-1)^n)/(n+1) for n >= 1, a(0)=1. See the Charalambides reference.
a(n) = GAMMA(n+3,-1)*exp(-1)/(n+1) (incomplete Gamma function). - Mark van Hoeij, Nov 11 2009
a(n) = A000166(n) + A000166(n+1).
A002469(n) = (n-2)*a(n-1) + A000166(n). - Gary W. Adamson, Apr 17 2009
If we take b(n) = (-1)^(n+1)*a(n) for n > 0, then for n > 1 the arithmetic mean of the first n terms is -b(n-1). - Franklin T. Adams-Watters, May 20 2010
a(n) = hypergeometric([2,-n],[],1)*(-1)^n = KummerU(2,3+n,-1)*(-1)^n. See the Abramowitz-Stegun handbook (for the reference see e.g. A103921) p. 504, 13.1.10, and for the recurrence p. 507, 13.4.16. - Wolfdieter Lang, May 20 2010
a(n) = n!*(1 + Sum_{k=0..n-2} sf(n-k)/(n-k)!) with the subfactorials sf(n):= A000166(n) (this follows from the exponential convolution). - Wolfdieter Lang, Jun 02 2010
a(n) = 1/(n+1)*floor(((n+1)!+1)/e). - Gary Detlefs, Jul 11 2010
a(n) = (Subfactorial(n+2))/(n+1). - Alexander R. Povolotsky, Jan 26 2011
G.f.: 1/(1-x-2x^2/(1-3x-6x^2/(1-5x-12x^2/(1-7x-20x^2/(1-.../(1-(2n+1)x-(n+1)(n+2)x^2/(1-... (continued fraction). - Paul Barry, Apr 11 2011
G.f.: hypergeom([1,2],[],x/(x+1))/(x+1). - Mark van Hoeij, Nov 07 2011
From Sergei N. Gladkovskii, Sep 24 2012 - Feb 05 2014: (Start)
Continued fractions:
E.g.f. 1/E(0) where E(k) = 1 - 2*x/(1 + x/(2 - x - 2/(1 + x*(k+1)/E(k+1)))).
G.f.: S(x)/x - 1/x = Q(0)/x - 1/x where S(x) = Sum_{k>=0} k!*(x/(1+x))^k, Q(k) = 1 + (2*k + 1)*x/(1 + x - 2*x*(1+x)*(k+1)/(2*x*(k+1) + (1+x)/Q(k+1))).
G.f.: 1/Q(0) where Q(k) = 1 + x - x*(k+2)/(1 - x*(k+1)/Q(k+1)).
G.f.: 1/x/Q(0) where Q(k) = 1/x - (2*k+1) - (k+2)*(k+1)/Q(k+1).
G.f.: (1+x)/(x*Q(0)) - 1/x where Q(k) = 1 - 2*k*x - x^2*(k + 1)^2/Q(k+1).
G.f.: 2/x/G(0) - 1/x where G(k) = 1 + 1/(1 - x*(2*k+2)/(x*(2*k+1) - 1 + x*(2*k+2)/ G(k+1))).
G.f.: ((Sum_{k>=0} k!*(x/(1+x))^k) - 1)/x = Q(0)/(2*x) - 1/x where Q(k) = 1 + 1/(1 - x*(k+1)/(x*(k+1) + (1+x)/Q(k+1))).
G.f.: W(0) where W(k) = 1 - x*(k+1)/(x*(k+1) - 1/(1 - x*(k+2)/(x*(k+1) - 1/W(k+1)))).
G.f.: G(0)/(1-x) where G(k) = 1 - x^2*(k+1)*(k+2)/(x^2*(k+1)*(k+2) - (1-x*(1+2*k))*(1-x*(3+2*k))/G(k+1)). (End)
From Peter Bala, Sep 20 2013: (Start)
The sequence b(n) := n!*(n + 2) satisfies the defining recurrence for a(n) but with the starting values b(0) = 2 and b(1) = 3. This leads to the finite continued fraction expansion a(n) = n!*(n+2)*( 1/(2 + 1/(1 + 1/(2 + 2/(3 + ... + (n-1)/n)))) ), valid for n >= 2.
Also a(n) = n!*(n+2)*( Sum_{k = 0..n} (-1)^k/(k+2)! ). Letting n -> infinity gives the infinite continued fraction expansion 1/e = 1/(2 + 1/(1 + 1/(2 + 2/(3 + ... + (n-1)/(n + ...)))) ) due to Euler. (End)
0 = a(n)*(+a(n+1) + 2*a(n+2) - a(n+3)) + a(n+1)*(+2*a(n+2) - a(n+3)) + a(n+2)*(+a(n+2)) if n >= 0. - Michael Somos, May 06 2014
a(n-3) = (n-2)*A000757(n-2) + (2*n-5)*A000757(n-3) + (n-3)*A000757(n-4), n >= 3. - Luis Manuel Rivera Martínez, Mar 14 2015
a(n) = A000240(n) + A000240(n+1), n >= 1. Let D(n) = A000240(n) be the permutations of [n] having no substring in {12,23,...,(n-1)n,n1}. Let d(n) = a(n-1) be the permutations of [n] having no substring in {12,23,...,(n-1)n}. Let d_n1 = A000240(n-1) be the permutations of [n] that have the substring n1 but no substring in {12,23,...,(n-1)n}. Then the link "Forbidden Patterns" shows the bijection d_n1 ~ D(n-1) and since dn = d_n1 U D(n), we get dn = D(n-1) U D(n). Taking cardinalities we get the result for n-1, i.e., a(n-1) = A000240(n-1) + A000240(n). For example, for n=4 in this last equation, we get a(4) = 11 = 3+8. - Enrique Navarrete, Jan 16 2017
a(n) = (n+1)!*hypergeom([-n], [-n-1], -1). - Peter Luschny, Nov 02 2018
Sum_{n>=0} (-1)^n*n!/(a(n)*a(n+1)) = e - 2 (Herzig, 1998). - Amiram Eldar, Mar 07 2022
a(n) = KummerU(-n, -n - 1, -1). - Peter Luschny, May 10 2022

A002741 Logarithmic numbers: expansion of the e.g.f. -log(1-x) * e^(-x).

Original entry on oeis.org

0, 1, -1, 2, 0, 9, 35, 230, 1624, 13209, 120287, 1214674, 13469896, 162744945, 2128047987, 29943053062, 451123462672, 7245940789073, 123604151490591, 2231697509543362, 42519034050101744, 852495597142800377, 17942811657908144163, 395553947953212635718, 9114871523102565301544, 219135339782236105192745
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Examples

			a(3) = 2 = 2! - 3*1! + 3*0! - 0. a(4) = 0 = 3! - 4*2! + 6*1! - 4*0! + 0. - _Michael Somos_, Mar 28 2011

References

  • J. M. Gandhi, On logarithmic numbers, Math. Student, 31 (1963), 73-83.
  • 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).

Links

Crossrefs

Cf. A000142, A000166, A000757.

Programs

  • Maple
    a := n -> (-1)^(n-1)*n*hypergeom([1,1,1-n], [2], 1):
seq(simplify(a(n)), n = 0..25); # Peter Luschny, May 09 2017
  • Mathematica
    a[n_] := Sum[(-1)^k*n!/((n-k)*k!), {k, 0, n-1}]; Table[a[n], {n, 0, 19}](* Jean-François Alcover, Nov 21 2011 *)
With[{nn=30},CoefficientList[Series[-Log[1-x] E^-x,{x,0,nn}],x] Range[0,nn]!] (* Harvey P. Dale, Nov 28 2022 *)
  • PARI
    {a(n) = if( n<0, 0, sum( k=0, n-1, (-1)^k * binomial(n, k) * (n - k - 1)!))} /* Michael Somos, Jun 21 2002 */

Formula

From Michael Somos, Jun 21 2002: (Start)
E.g.f.: -log(1-x) / e^x.
a(n) = (n-2) * a(n-1) + (n-1) * a(n-2) - (-1)^n, n > 0.
A000757(n) = (-1)^n + a(n). (End)
a(n) = n-th forward difference of [0, 1, 1, 2, 6, 24, ...] (factorials A000142 with 0 prepended). - Michael Somos, Mar 28 2011
a(n) ~ exp(-1)*(n-1)!. - Vaclav Kotesovec, Mar 10 2014
From Vladimir Reshetnikov, Oct 29 2015: (Start)
Recurrence: a(0) = 0, a(1) = 1, a(2) = -1, a(n) = (n-3)*a(n-1) + 2*(n-2)*a(n-2) + (n-2)*a(n-3).
a(n) + a(n+1) = A000166(n). (End)
a(n) = (-1)^(n-1)*n*hypergeom([1,1,1-n], [2], 1). - Peter Luschny, May 09 2017

Extensions

More terms from Jeffrey Shallit
More terms from Joerg Arndt, Sep 02 2013

A134832 Triangle of succession numbers for circular permutations.

Original entry on oeis.org

1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 4, 0, 0, 1, 8, 5, 10, 0, 0, 1, 36, 48, 15, 20, 0, 0, 1, 229, 252, 168, 35, 35, 0, 0, 1, 1625, 1832, 1008, 448, 70, 56, 0, 0, 1, 13208, 14625, 8244, 3024, 1008, 126, 84, 0, 0, 1, 120288, 132080, 73125, 27480, 7560, 2016, 210, 120, 0, 0, 1
Offset: 0

Views

Author

Wolfdieter Lang, Jan 21 2008

Keywords

Comments

Imagine seating n people numbered 1,2,...n around a circular table. There are only n!/n=(n-1)! inequivalent permutations due to the action of the cyclic group Z_n. a(n,k) enumerates such circular permutations which have precisely k successor pairs (i,i+1). Due to cyclicity (n,1) is also counted as successor pair. See the Charalambides reference.
This is an example of a Sheffer triangle of the Appell type denoted by (((1-log(1-x))/e^x,x). This explains the e.g.f. for column no. k given below. For Sheffer a- and z-sequences see the W. Lang link under A006232.

Examples

			Triangle begins:
  [1];
  [0,1];
  [0,0,1];
  [1,0,0,1];
  [1,4,0,0,1];
  ...
Recurrence: 15=a(6,2) = (6/2)*a(5,1)=3*5 (from Sheffer a-sequence).
Recurrence: 36=a(6,0)=6*(0+0+(1/3)*10+0+0+(8/3)*1) =6*6 (from Sheffer z-sequence).

References

  • Ch. A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC, Boca Raton, Florida, 2002, p. 183, eq. (5.15).

Links

Crossrefs

Cf. A000142 (row sums are factorials), A134833 (alternating row sums).

Programs

  • Mathematica
    A000757[n_] := (-1)^n + Sum[(-1)^k*n!/((n-k)*k!), {k, 0, n-1}]; a[n_, n_] = 1; a[n_, 0] := A000757[n]; a[n_, k_] := a[n, k] = n/k*a[n-1, k-1]; Table[a[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Oct 02 2013 *)

Formula

a(n,k) = binomial(n,k)*a(n-k,0), k>=1 with a(n-k,0):=A000757(n), n>=0.
E.g.f. column k: ((1-log(1-x))/e^x)*(x^k)/k!, k>=0 (from the Sheffer property).
Recurrence a(n,k) = (n/k)*a(n-1,k-1), n >= k >= 1, (from the Sheffer a-sequences [1,0,0,...] due to the Appell type).
Recurrence a(n,0) = n*sum(z(j)*a(n-1,j),j=0..n-1), n>=1; a(0,0):=1, with the Sheffer z-sequence z(j):= A135808(j).

A135799 Second column (k=1) of triangle A134832 (circular succession numbers).

Original entry on oeis.org

1, 0, 0, 4, 5, 48, 252, 1832, 14625, 132080, 1323168, 14576076, 175108661, 2278429216, 31920719820, 479088848976, 7669098865441, 130426934203296, 2348478878321248, 44633950190867220, 892899715052136645
Offset: 0

Views

Author

Wolfdieter Lang, Jan 21 2008, Feb 22 2008

Keywords

Comments

a(n) enumerates circular permutations of {1,2,...,n+1} with exactly one successor pair (i,i+1). Due to cyclicity also (n+1,1) is a successor pair.
The o.g.f. of this sequence seems to be the product of the o.g.f. for A000166 (derangements) by the fraction (1+2*x)/(1+x)^2 = 1 - x^2+ 2*x^3 - 3*x^4 + ... = 1 + sum( (-1)^i i x^(i+1), i=0..infinity) - Thomas Baruchel, Jan 08 2016
This correspond to the following transform: a(n) = b(n) - sum((-1)^(n + i) (n - i - 1)*b(i), (i=0..n-2)) - Olivier Gérard, Mar 05 2016

Examples

			a(3)=4 because the 4!/4 = 6 circular permutations of n=4 elements (1,2,3,4), (1,4, 3,2), (1,3,4,2),(1,2,4,3), (1,4,2,3) and (1,3,2,4) have 4,0,1,1, 1 and 1 successor pair(s), respectively.

References

  • Ch. A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC, Boca Raton, Florida, 2002, p. 183, eq. (5.15), for k=1.

Links

Crossrefs

Cf. A000757 (k=0 column), A134515 (k=2 column).

Programs

  • Mathematica
    f[n_] := (-1)^n + Sum[(-1)^k*n!/((n - k)*k!), {k, 0, n - 1}]; a[n_, n_] = 1; a[n_, 0] := f[n]; a[n_, k_] := a[n, k] = n/k*a[n - 1, k - 1]; Table[a[n, 1], {n, 21}] (* Michael De Vlieger, Jan 09 2016, after Jean-François Alcover at A134832 *)

Formula

a(n) = (n+1)*A000757(n), n>=0.
E.g.f.: (d/dx) x*(1-log(1-x))/e^x.
O.g.f.: see comment section.

A135802 Fifth column (k=4) of triangle A134832 (circular succession numbers).

Original entry on oeis.org

1, 0, 0, 35, 70, 1008, 7560, 75570, 804375, 9443720, 120408288, 1658028645, 24515212540, 387332966720, 6511826843280, 116059273664436, 2185693176650685, 43366955622595920, 904164368153680480
Offset: 0

Views

Author

Wolfdieter Lang, Jan 21 2008, Feb 22 2008

Keywords

Comments

a(n) enumerates circular permutations of {1,2,...,n+4} with exactly four successor pairs (i,i+1). Due to cyclicity also (n+4,1) is a successor pair.

Examples

			a(0)=1 because the 4!/4 = 6 circular permutations of n=4 elements (1,2,3,4), (1,4,3,2), (1,3,4,2),(1,2,4,3), (1,4,2,3) and (1,3,2,4) have 4,0,1,1,1 and 1 successor pair, respectively. Hence (1,2,3,4) is the only circular permutation with 4 successors.

References

  • Ch. A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC, Boca Raton, Florida, 2002, p. 183, eq. (5.15), for k=4.

Links

Crossrefs

Cf. A135801 (column k=3), A135803 (column k=5).

Programs

  • Mathematica
    f[n_] := (-1)^n + Sum[(-1)^k*n!/((n - k)*k!), {k, 0, n - 1}]; a[n_, n_] = 1; a[n_, 0] := f[n]; a[n_, k_] := a[n, k] = n/k*a[n - 1, k - 1]; Table[a[n, 4], {n, 4, 25}] (* G. C. Greubel, Nov 10 2016 *)

Formula

a(n) = binomial(n+4,4)*A000757(n), n>=0.
E.g.f.: (d^4/dx^4) (x^4/4!)*(1-log(1-x))/e^x.

A135803 Sixth column (k=5) of triangle A134832 (circular succession numbers).

Original entry on oeis.org

1, 0, 0, 56, 126, 2016, 16632, 181368, 2091375, 26442416, 361224864, 5305691664, 83351722636, 1394398680192, 24744942004464, 464237094657744, 9179911341932877, 190814604739422048, 4159156093506930208
Offset: 0

Views

Author

Wolfdieter Lang, Jan 21 2008

Keywords

Comments

a(n) enumerates circular permutations of {1,2,...,n+5} with exactly five successor pairs (i,i+1). Due to cyclicity also (n+5,1) is a successor pair.

Examples

			a(0)=1 because from the 5!/5 = 24 circular permutations of n=5 elements only one, namely (1,2,3,4,5), has five successors.

References

  • Ch. A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC, Boca Raton, Florida, 2002, p. 183, eq. (5.15), for k=5.

Links

Crossrefs

Cf. A135802 (column k=4), A135804 (column k=6).

Programs

  • Mathematica
    f[n_] := (-1)^n + Sum[(-1)^k*n!/((n - k)*k!), {k, 0, n - 1}]; a[n_, n_] = 1; a[n_, 0] := f[n]; a[n_, k_] := a[n, k] = n/k*a[n - 1, k - 1]; Table[a[n, 5], {n, 5, 25}] (* G. C. Greubel, Nov 10 2016 *)

Formula

a(n) = binomial(n+5,5)*A000757(n), n>=0.
E.g.f.: (d^5/dx^5) (x^5/5!)*(1-log(1-x))/e^x.

A135804 Seventh column (k=6) of triangle A134832 (circular succession numbers).

Original entry on oeis.org

1, 0, 0, 84, 210, 3696, 33264, 392964, 4879875, 66106040, 963266304, 15032793048, 250055167908, 4415595820608, 82483140014880, 1624829831302104, 33659674920420549, 731455984834451184, 16636624374027720832
Offset: 0

Views

Author

Wolfdieter Lang, Jan 21 2008

Keywords

Comments

a(n) enumerates circular permutations of {1,2,...,n+6} with exactly six successor pairs (i,i+1). Due to cyclicity also (n+6,1) is a successor pair.

Examples

			a(0)=1 because from the 6!/6 = 120 circular permutations of n=6 elements only one, namely (1,2,3,4,5,6), has six successors.

References

  • Ch. A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC, Boca Raton, Florida, 2002, p. 183, eq. (5.15), for k=6.

Links

Crossrefs

Cf. A135803 (column k=5), A135805 (column k=7).

Programs

  • Mathematica
    f[n_] := (-1)^n + Sum[(-1)^k*n!/((n - k)*k!), {k, 0, n - 1}]; a[n_, n_] = 1; a[n_, 0] := f[n]; a[n_, k_] := a[n, k] = n/k*a[n - 1, k - 1]; Table[a[n, 6], {n, 6, 25}] (* G. C. Greubel, Nov 10 2016 *)

Formula

a(n) = binomial(n+6,6)*A000757(n), n>=0.
E.g.f.: (d^6/dx^6) (x^6/6!)*(1-log(1-x))/e^x.
Showing 1-10 of 24 results. Next

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

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