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 74 results. Next

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

A000312 a(n) = n^n; number of labeled mappings from n points to themselves (endofunctions).

Original entry on oeis.org

1, 1, 4, 27, 256, 3125, 46656, 823543, 16777216, 387420489, 10000000000, 285311670611, 8916100448256, 302875106592253, 11112006825558016, 437893890380859375, 18446744073709551616, 827240261886336764177, 39346408075296537575424, 1978419655660313589123979
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Also number of labeled pointed rooted trees (or vertebrates) on n nodes.
For n >= 1 a(n) is also the number of n X n (0,1) matrices in which each row contains exactly one entry equal to 1. - Avi Peretz (njk(AT)netvision.net.il), Apr 21 2001
Also the number of labeled rooted trees on (n+1) nodes such that the root is lower than its children. Also the number of alternating labeled rooted ordered trees on (n+1) nodes such that the root is lower than its children. - Cedric Chauve (chauve(AT)lacim.uqam.ca), Mar 27 2002
With p(n) = the number of integer partitions of n, p(i) = the number of parts of the i-th partition of n, d(i) = the number of different parts of the i-th partition of n, p(j, i) = the j-th part of the i-th partition of n, m(i, j) = multiplicity of the j-th part of the i-th partition of n, one has: a(n) = Sum_{i=1..p(n)} (n!/(Product_{j=1..p(i)} p(i, j)!)) * ((n!/(n - p(i)))!/(Product_{j=1..d(i)} m(i, j)!)). - Thomas Wieder, May 18 2005
All rational solutions to the equation x^y = y^x, with x < y, are given by x = A000169(n+1)/A000312(n), y = A000312(n+1)/A007778(n), where n = 1, 2, 3, ... . - Nick Hobson, Nov 30 2006
a(n) is the total number of leaves in all (n+1)^(n-1) trees on {0,1,2,...,n} rooted at 0. For example, with edges directed away from the root, the trees on {0,1,2} are {0->1,0->2},{0->1->2},{0->2->1} and contain a total of a(2)=4 leaves. - David Callan, Feb 01 2007
Limit_{n->infinity} A000169(n+1)/a(n) = exp(1). Convergence is slow, e.g., it takes n > 74 to get one decimal place correct and n > 163 to get two of them. - Alonso del Arte, Jun 20 2011
Also smallest k such that binomial(k, n) is divisible by n^(n-1), n > 0. - Michel Lagneau, Jul 29 2013
For n >= 2 a(n) is represented in base n as "one followed by n zeros". - R. J. Cano, Aug 22 2014
Number of length-n words over the alphabet of n letters. - Joerg Arndt, May 15 2015
Number of prime parking functions of length n+1. - Rui Duarte, Jul 27 2015
The probability density functions p(x, m=q, n=q, mu=1) = A000312(q)*E(x, q, q) and p(x, m=q, n=1, mu=q) = (A000312(q)/A000142(q-1))*x^(q-1)*E(x, q, 1), with q >= 1, lead to this sequence, see A163931, A274181 and A008276. - Johannes W. Meijer, Jun 17 2016
Satisfies Benford's law [Miller, 2015]. - N. J. A. Sloane, Feb 12 2017
A signed version of this sequence apart from the first term (1, -4, -27, 256, 3125, -46656, ...), has the following property: for every prime p == 1 (mod 2n), (-1)^(n(n-1)/2)*n^n = A057077(n)*a(n) is always a 2n-th power residue modulo p. - Jianing Song, Sep 05 2018
From Juhani Heino, May 07 2019: (Start)
n^n is both Sum_{i=0..n} binomial(n,i)*(n-1)^(n-i)
and Sum_{i=0..n} binomial(n,i)*(n-1)^(n-i)*i.
The former is the familiar binomial distribution of a throw of n n-sided dice, according to how many times a required side appears, 0 to n. The latter is the same but each term is multiplied by its amount. This means that if the bank pays the player 1 token for each die that has the chosen side, it is always a fair game if the player pays 1 token to enter - neither bank nor player wins on average.
Examples:
2-sided dice (2 coins): 4 = 1 + 2 + 1 = 1*0 + 2*1 + 1*2 (0 omitted from now on);
3-sided dice (3 long triangular prisms): 27 = 8 + 12 + 6 + 1 = 12*1 + 6*2 + 1*3;
4-sided dice (4 long square prisms or 4 tetrahedrons): 256 = 81 + 108 + 54 + 12 + 1 = 108*1 + 54*2 + 12*3 + 1*4;
5-sided dice (5 long pentagonal prisms): 3125 = 1024 + 1280 + 640 + 160 + 20 + 1 = 1280*1 + 640*2 + 160*3 + 20*4 + 1*5;
6-sided dice (6 cubes): 46656 = 15625 + 18750 + 9375 + 2500 + 375 + 30 + 1 = 18750*1 + 9375*2 + 2500*3 + 375*4 + 30*5 + 1*6.
(End)
For each n >= 1 there is a graph on a(n) vertices whose largest independent set has size n and whose independent set sequence is constant (specifically, for each k=1,2,...,n, the graph has n^n independent sets of size k). There is no graph of smaller order with this property (Ball et al. 2019). - David Galvin, Jun 13 2019
For n >= 2 and 1 <= k <= n, a(n)*(n + 1)/4 + a(n)*(k - 1)*(n + 1 - k)/2*n is equal to the sum over all words w = w(1)...w(n) of length n over the alphabet {1, 2, ..., n} of the following quantity: Sum_{i=1..w(k)} w(i). Inspired by Problem 12432 in the AMM (see links). - Sela Fried, Dec 10 2023
Also, dimension of the unique cohomology group of the smallest interval containing the poset of partitions decorated by Perm, i.e. the poset of pointed partitions. - Bérénice Delcroix-Oger, Jun 25 2025

Examples

			G.f. = 1 + x + 4*x^2 + 27*x^3 + 256*x^4 + 3125*x^5 + 46656*x^6 + 823543*x^7 + ...

References

  • F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, pp. 62, 63, 87.
  • L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 173, #39.
  • 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, Eq. (4.2.2.37)
  • 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. A000107, A000169, A000272, A001372, A007778, A007830, A008785-A008791, A019538, A048993, A008279, A085741, A062206, A212333.
First column of triangle A055858. Row sums of A066324.
Cf. A001923 (partial sums), A002109 (partial products), A007781 (first differences), A066588 (sum of digits).
Cf. A056665, A081721, A130293, A168658, A275549-A275558 (various classes of endofunctions).
Cf. A174824, A204688.
Cf. A055137, A083648.

Programs

  • Haskell
    a000312 n = n ^ n
a000312_list = zipWith (^) [0..] [0..]  -- Reinhard Zumkeller, Jul 07 2012
  • Maple
    A000312 := n->n^n: seq(A000312(n), n=0..17);
  • Mathematica
    Array[ #^# &, 16] (* Vladimir Joseph Stephan Orlovsky, May 01 2008 *)
Table[Sum[StirlingS2[n, i] i! Binomial[n, i], {i, 0, n}], {n, 0, 20}] (* Geoffrey Critzer, Mar 17 2009 *)
a[ n_] := If[ n < 1, Boole[n == 0], n^n]; (* Michael Somos, May 24 2014 *)
a[ n_] := If[ n < 0, 0, n! SeriesCoefficient[ 1 / (1 + LambertW[-x]), {x, 0, n}]]; (* Michael Somos, May 24 2014 *)
a[ n_] := If[n < 0, 0, n! SeriesCoefficient[ Nest[ 1 / (1 - x / (1 - Integrate[#, x])) &, 1 + O[x], n], {x, 0, n}]]; (* Michael Somos, May 24 2014 *)
a[ n_] := If[ n < 0, 0, With[{m = n + 1}, m! SeriesCoefficient[ InverseSeries[ Series[ (x - 1) Log[1 - x], {x, 0, m}]], m]]]; (* Michael Somos, May 24 2014 *)
  • Maxima
    A000312[n]:=if n=0 then 1 else n^n$
makelist(A000312[n],n,0,30); /* Martin Ettl, Oct 29 2012 */
  • PARI
    {a(n) = n^n};
  • PARI
    is(n)=my(b,k=ispower(n,,&b));if(k,for(e=1,valuation(k,b), if(k/b^e == e, return(1)))); n==1 \\ Charles R Greathouse IV, Jan 14 2013
  • PARI
    {a(n) = my(A = 1 + O(x)); if( n<0, 0, for(k=1, n, A = 1 / (1 - x / (1 - intformal( A)))); n! * polcoeff( A, n))}; /* Michael Somos, May 24 2014 */
  • Python
    def A000312(n): return n**n # Chai Wah Wu, Nov 07 2022

Formula

a(n-1) = -Sum_{i=1..n} (-1)^i*i*n^(n-1-i)*binomial(n, i). - Yong Kong (ykong(AT)curagen.com), Dec 28 2000
E.g.f.: 1/(1 + W(-x)), W(x) = principal branch of Lambert's function.
a(n) = Sum_{k>=0} binomial(n, k)*Stirling2(n, k)*k! = Sum_{k>=0} A008279(n,k)*A048993(n,k) = Sum_{k>=0} A019538(n,k)*A007318(n,k). - Philippe Deléham, Dec 14 2003
E.g.f.: 1/(1 - T), where T = T(x) is Euler's tree function (see A000169).
a(n) = A000169(n+1)*A128433(n+1,1)/A128434(n+1,1). - Reinhard Zumkeller, Mar 03 2007
Comment on power series with denominators a(n): Let f(x) = 1 + Sum_{n>=1} x^n/n^n. Then as x -> infinity, f(x) ~ exp(x/e)*sqrt(2*Pi*x/e). - Philippe Flajolet, Sep 11 2008
E.g.f.: 1 - exp(W(-x)) with an offset of 1 where W(x) = principal branch of Lambert's function. - Vladimir Kruchinin, Sep 15 2010
a(n) = (n-1)*a(n-1) + Sum_{i=1..n} binomial(n, i)*a(i-1)*a(n-i). - Vladimir Shevelev, Sep 30 2010
With an offset of 1, the e.g.f. is the compositional inverse ((x - 1)*log(1 - x))^(-1) = x + x^2/2! + 4*x^3/3! + 27*x^4/4! + .... - Peter Bala, Dec 09 2011
a(n) = denominator((1 + 1/n)^n) for n > 0. - Jean-François Alcover, Jan 14 2013
a(n) = A089072(n,n) for n > 0. - Reinhard Zumkeller, Mar 18 2013
a(n) = (n-1)^(n-1)*(2*n) + Sum_{i=1..n-2} binomial(n, i)*(i^i*(n-i-1)^(n-i-1)), n > 1, a(0) = 1, a(1) = 1. - Vladimir Kruchinin, Nov 28 2014
log(a(n)) = lim_{k->infinity} k*(n^(1+1/k) - n). - Richard R. Forberg, Feb 04 2015
From Ilya Gutkovskiy, Jun 18 2016: (Start)
Sum_{n>=1} 1/a(n) = 1.291285997... = A073009.
Sum_{n>=1} 1/a(n)^2 = 1.063887103... = A086648.
Sum_{n>=1} n!/a(n) = 1.879853862... = A094082. (End)
A000169(n+1)/a(n) -> e, as n -> oo. - Daniel Suteu, Jul 23 2016
a(n) = n!*Product_{k=1..n} binomial(n, k)/Product_{k=1..n-1} binomial(n-1, k) = n!*A001142(n)/A001142(n-1). - Tony Foster III, Sep 05 2018
a(n-1) = abs(p_n(2-n)), for n > 2, the single local extremum of the n-th row polynomial of A055137 with Bagula's sign convention. - Tom Copeland, Nov 15 2019
Sum_{n>=1} (-1)^(n+1)/a(n) = A083648. - Amiram Eldar, Jun 25 2021
Limit_{n->oo} (a(n+1)/a(n) - a(n)/a(n-1)) = e (see Brothers/Knox link). - Harlan J. Brothers, Oct 24 2021
Conjecture: a(n) = Sum_{i=0..n} A048994(n, i) * A048993(n+i, n) for n >= 0; proved by Mike Earnest, see link at A354797. - Werner Schulte, Jun 19 2022

A001710 Order of alternating group A_n, or number of even permutations of n letters.

Original entry on oeis.org

1, 1, 1, 3, 12, 60, 360, 2520, 20160, 181440, 1814400, 19958400, 239500800, 3113510400, 43589145600, 653837184000, 10461394944000, 177843714048000, 3201186852864000, 60822550204416000, 1216451004088320000, 25545471085854720000, 562000363888803840000
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

For n >= 3, a(n-1) is also the number of ways that a 3-cycle in the symmetric group S_n can be written as a product of 2 long cycles (of length n). - Ahmed Fares (ahmedfares(AT)my-deja.com), Aug 14 2001
a(n) is the number of Hamiltonian circuit masks for an n X n adjacency matrix of an undirected graph. - Chad Brewbaker, Jan 31 2003
a(n-1) is the number of necklaces one can make with n distinct beads: n! bead permutations, divide by two to represent flipping the necklace over, divide by n to represent rotating the necklace. Related to Stirling numbers of the first kind, Stirling cycles. - Chad Brewbaker, Jan 31 2003
Number of increasing runs in all permutations of [n-1] (n>=2). Example: a(4)=12 because we have 12 increasing runs in all the permutations of [3] (shown in parentheses): (123), (13)(2), (3)(12), (2)(13), (23)(1), (3)(2)(1). - Emeric Deutsch, Aug 28 2004
Minimum permanent over all n X n (0,1)-matrices with exactly n/2 zeros. - Simone Severini, Oct 15 2004
The number of permutations of 1..n that have 2 following 1 for n >= 1 is 0, 1, 3, 12, 60, 360, 2520, 20160, ... . - Jon Perry, Sep 20 2008
Starting (1, 3, 12, 60, ...) = binomial transform of A000153: (1, 2, 7, 32, 181, ...). - Gary W. Adamson, Dec 25 2008
First column of A092582. - Mats Granvik, Feb 08 2009
The asymptotic expansion of the higher order exponential integral E(x,m=1,n=3) ~ exp(-x)/x*(1 - 3/x + 12/x^2 - 60/x^3 + 360/x^4 - 2520/x^5 + 20160/x^6 - 81440/x^7 + ...) leads to the sequence given above. See A163931 and A130534 for more information. - Johannes W. Meijer, Oct 20 2009
For n>1: a(n) = A173333(n,2). - Reinhard Zumkeller, Feb 19 2010
Starting (1, 3, 12, 60, ...) = eigensequence of triangle A002260, (a triangle with k terms of (1,2,3,...) in each row given k=1,2,3,...). Example: a(6) = 360, generated from (1, 2, 3, 4, 5) dot (1, 1, 3, 12, 60) = (1 + 2 + 9 + 48 + 300). - Gary W. Adamson, Aug 02 2010
For n>=2: a(n) is the number of connected 2-regular labeled graphs on (n+1) nodes (Cf. A001205). - Geoffrey Critzer, Feb 16 2011.
The Fi1 and Fi2 triangle sums of A094638 are given by the terms of this sequence (n>=1). For the definition of these triangle sums see A180662. - Johannes W. Meijer, Apr 20 2011
Also [1, 1] together with the row sums of triangle A162608. - Omar E. Pol, Mar 09 2012
a(n-1) is, for n>=2, also the number of necklaces with n beads (only C_n symmetry, no turnover) with n-1 distinct colors and signature c[.]^2 c[.]^(n-2). This means that two beads have the same color, and for n=2 the second factor is omitted. Say, cyclic(c[1]c[1]c[2]c[3]..c[n-1]), in short 1123...(n-1), taken cyclically. E.g., n=2: 11, n=3: 112, n=4: 1123, 1132, 1213, n=5: 11234, 11243, 11324, 11342, 11423, 11432, 12134, 12143, 13124, 13142, 14123, 14132. See the next-to-last entry in line n>=2 of the representative necklace partition array A212359. - Wolfdieter Lang, Jun 26 2012
For m >= 3, a(m-1) is the number of distinct Hamiltonian circuits in a complete simple graph with m vertices. See also A001286. - Stanislav Sykora, May 10 2014
In factorial base (A007623) these numbers have a simple pattern: 1, 1, 1, 11, 200, 2200, 30000, 330000, 4000000, 44000000, 500000000, 5500000000, 60000000000, 660000000000, 7000000000000, 77000000000000, 800000000000000, 8800000000000000, 90000000000000000, 990000000000000000, etc. See also the formula based on this observation, given below. - Antti Karttunen, Dec 19 2015
Also (by definition) the independence number of the n-transposition graph. - Eric W. Weisstein, May 21 2017
Number of permutations of n letters containing an even number of even cycles. - Michael Somos, Jul 11 2018
Equivalent to Brewbaker's and Sykora's comments, a(n - 1) is the number of undirected cycles covering n labeled vertices, hence the logarithmic transform of A002135. - Gus Wiseman, Oct 20 2018
For n >= 2 and a set of n distinct leaf labels, a(n) is the number of binary, rooted, leaf-labeled tree topologies that have a caterpillar shape (column k=1 of A306364). - Noah A Rosenberg, Feb 11 2019
Also the clique covering number of the n-Bruhat graph. - Eric W. Weisstein, Apr 19 2019
a(n) is the number of lattices of the form [s,w] in the weak order on S_n, for a fixed simple reflection s. - Bridget Tenner, Jan 16 2020
For n > 3, a(n) = p_1^e_1*...*p_m^e_m, where p_1 = 2 and e_m = 1. There exists p_1^x where x <= e_1 such that p_1^x*p_m^e_m is a primitive Zumkeller number (A180332) and p_1^e_1*p_m^e_m is a Zumkeller number (A083207). Therefore, for n > 3, a(n) = p_1^e_1*p_m^e_m*r, where r is relatively prime to p_1*p_m, is also a Zumkeller number. - Ivan N. Ianakiev, Mar 11 2020
For n>1, a(n) is the number of permutations of [n] that have 1 and 2 as cycle-mates, that is, 1 and 2 are contained in the same cycle of a cyclic representation of permutations of [n]. For example, a(4) counts the 12 permutations with 1 and 2 as cycle-mates, namely, (1 2 3 4), (1 2 4 3), (1 3 2 4), (1 3 4 2), (1 4 2 3), (1 4 3 2), (1 2 3) (4), (1 3 2) (4), (1 2 4 )(3), (1 4 2)(3), (1 2)(3 4), and (1 2)(3)(4). Since a(n+2)=row sums of A162608, our result readily follows. - Dennis P. Walsh, May 28 2020

Examples

			G.f. = 1 + x + x^2 + 3*x^3 + 12*x^4 + 60*x^5 + 360*x^6 + 2520*x^7 + ...

References

  • J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, pp. 87-8, 20. (a), c_n^e(t=1).
  • 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, A000153, A000255, A001147, A001286, A001720, A002135, A002260, A007623, A007717, A049444, A049459, A093468, A094587, A094638, A138533, A153880, A173333, A213936, A215771, A319225, A319226, A320655.
a(n+1)= A046089(n, 1), n >= 1 (first column of triangle), A161739 (q(n) sequence).
Bisections are A002674 and A085990 (essentially).
Row 3 of A265609 (essentially).
Row sums of A307429.

Programs

  • Magma
    [1] cat [Order(AlternatingGroup(n)): n in [1..20]]; // Arkadiusz Wesolowski, May 17 2014
  • Maple
    seq(mul(k, k=3..n), n=0..20); # Zerinvary Lajos, Sep 14 2007
  • Mathematica
    a[n_]:= If[n > 2, n!/2, 1]; Array[a, 21, 0]
a[n_]:= If[n<3, 1, n*a[n-1]]; Array[a, 21, 0]; (* Robert G. Wilson v, Apr 16 2011 *)
a[ n_]:= If[n<0, 0, n! SeriesCoefficient[(2-x^2)/(2-2x), {x, 0, n}]]; (* Michael Somos, May 22 2014 *)
a[ n_]:= If[n<0, 0, n! SeriesCoefficient[1 +Sinh[-Log[1-x]], {x, 0, n}]]; (* Michael Somos, May 22 2014 *)
Numerator[Range[0, 20]!/2] (* Eric W. Weisstein, May 21 2017 *)
Table[GroupOrder[AlternatingGroup[n]], {n, 0, 20}] (* Eric W. Weisstein, May 21 2017 *)
  • PARI
    {a(n) = if( n<2, n>=0, n!/2)};
  • PARI
    a(n)=polcoeff(1+x*sum(m=0,n,m^m*x^m/(1+m*x+x*O(x^n))^m),n) \\ Paul D. Hanna
  • PARI
    A001710=n->n!\2+(n<2) \\ M. F. Hasler, Dec 01 2013
  • Python
    from math import factorial
def A001710(n): return factorial(n)>>1 if n > 1 else 1 # Chai Wah Wu, Feb 14 2023
  • SageMath
    def A001710(n): return (factorial(n) +int(n<2))//2
[A001710(n) for n in range(31)] # G. C. Greubel, Sep 28 2024
  • Scheme
    ;; Using memoization-macro definec for which an implementation can be found in http://oeis.org/wiki/Memoization
(definec (A001710 n) (cond ((<= n 2) 1) (else (* n (A001710 (- n 1))))))
;; Antti Karttunen, Dec 19 2015

Formula

a(n) = numerator(n!/2) and A141044(n) = denominator(n!/2).
D-finite with recurrence: a(0) = a(1) = a(2) = 1; a(n) = n*a(n-1) for n>2. - Chad Brewbaker, Jan 31 2003 [Corrected by N. J. A. Sloane, Jul 25 2008]
a(0) = 0, a(1) = 1; a(n) = Sum_{k=1..n-1} k*a(k). - Amarnath Murthy, Oct 29 2002
Stirling transform of a(n+1) = [1, 3, 12, 160, ...] is A083410(n) = [1, 4, 22, 154, ...]. - Michael Somos, Mar 04 2004
First Eulerian transform of A000027. See A000142 for definition of FET. - Ross La Haye, Feb 14 2005
From Paul Barry, Apr 18 2005: (Start)
a(n) = 0^n + Sum_{k=0..n} (-1)^(n-k-1)*T(n-1, k)*cos(Pi*(n-k-1)/2)^2.
T(n,k) = abs(A008276(n, k)). (End)
E.g.f.: (2 - x^2)/(2 - 2*x).
E.g.f. of a(n+2), n>=0, is 1/(1-x)^3.
E.g.f.: 1 + sinh(log(1/(1-x))). - Geoffrey Critzer, Dec 12 2010
a(n+1) = (-1)^n * A136656(n,1), n>=1.
a(n) = n!/2 for n>=2 (proof from the e.g.f). - Wolfdieter Lang, Apr 30 2010
a(n) = (n-2)! * t(n-1), n>1, where t(n) is the n-th triangular number (A000217). - Gary Detlefs, May 21 2010
a(n) = ( A000254(n) - 2* A001711(n-3) )/3, n>2. - Gary Detlefs, May 24 2010
O.g.f.: 1 + x*Sum_{n>=0} n^n*x^n/(1 + n*x)^n. - Paul D. Hanna, Sep 13 2011
a(n) = if n < 2 then 1, otherwise Pochhammer(n,n)/binomial(2*n,n). - Peter Luschny, Nov 07 2011
a(n) = Sum_{k=0..floor(n/2)} s(n,n-2*k) where s(n,k) are Stirling number of the first kind, A048994. - Mircea Merca, Apr 07 2012
a(n-1), n>=3, is M_1([2,1^(n-2)])/n = (n-1)!/2, with the M_1 multinomial numbers for the given n-1 part partition of n. See the second to last entry in line n>=3 of A036038, and the above necklace comment by W. Lang. - Wolfdieter Lang, Jun 26 2012
G.f.: A(x) = 1 + x + x^2/(G(0)-2*x) where G(k) = 1 - (k+1)*x/(1 - x*(k+3)/G(k+1)); (continued fraction). - Sergei N. Gladkovskii, Dec 26 2012.
G.f.: 1 + x + (Q(0)-1)*x^2/(2*(sqrt(x)+x)), where Q(k) = 1 + (k+2)*sqrt(x)/(1 - sqrt(x)/(sqrt(x) + 1/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 15 2013
G.f.: 1 + x + (x*Q(x)-x^2)/(2*(sqrt(x)+x)), where Q(x) = Sum_{n>=0} (n+1)!*x^n*sqrt(x)*(sqrt(x) + x*(n+2)). - Sergei N. Gladkovskii, May 15 2013
G.f.: 1 + x/2 + (Q(0)-1)*x/(2*(sqrt(x)+x)), where Q(k) = 1 + (k+1)*sqrt(x)/(1 - sqrt(x)/(sqrt(x) + 1/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 15 2013
G.f.: 1 + x + x^2*G(0)/2, where G(k) = 1 + 1/(1 - x/(x + 1/(k+3)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 01 2013
G.f.: 1+x + x^2*W(0), where W(k) = 1 - x*(k+3)/( x*(k+3) - 1/(1 - x*(k+1)/( x*(k+1) - 1/W(k+1) ))); (continued fraction). - Sergei N. Gladkovskii, Aug 26 2013
From Antti Karttunen, Dec 19 2015: (Start)
a(0)=a(1)=1; after which, for even n: a(n) = (n/2) * (n-1)!, and for odd n: a(n) = (n-1)/2 * ((n-1)! + (n-2)!). [The formula was empirically found after viewing these numbers in factorial base, A007623, and is easily proved by considering formulas from Lang (Apr 30 2010) and Detlefs (May 21 2010) shown above.]
For n >= 1, a(2*n+1) = a(2*n) + A153880(a(2*n)). [Follows from above.] (End)
Inverse Stirling transform of a(n) is (-1)^(n-1)*A009566(n). - Anton Zakharov, Aug 07 2016
a(n) ~ sqrt(Pi/2)*n^(n+1/2)/exp(n). - Ilya Gutkovskiy, Aug 07 2016
a(n) = A006595(n-1)*n/A000124(n) for n>=2. - Anton Zakharov, Aug 23 2016
a(n) = A001563(n-1) - A001286(n-1) for n>=2. - Anton Zakharov, Sep 23 2016
From Peter Bala, May 24 2017: (Start)
The o.g.f. A(x) satisfies the Riccati equation x^2*A'(x) + (x - 1)*A(x) + 1 - x^2 = 0.
G.f.: A(x) = 1 + x + x^2/(1 - 3*x/(1 - x/(1 - 4*x/(1 - 2*x/(1 - 5*x/(1 - 3*x/(1 - ... - (n + 2)*x/(1 - n*x/(1 - ... ))))))))) (apply Stokes, 1982).
A(x) = 1 + x + x^2/(1 - 2*x - x/(1 - 3*x/(1 - 2*x/(1 - 4*x/(1 - 3*x/(1 - 5*x/(1 - ... - n*x/(1 - (n+2)*x/(1 - ... ))))))))). (End)
H(x) = (1 - (1 + x)^(-2)) / 2 = x - 3*x^2/2! + 12*x^3/3! - ..., an e.g.f. for the signed sequence here (n!/2!), ignoring the first two terms, is the compositional inverse of G(x) = (1 - 2*x)^(-1/2) - 1 = x + 3*x^2/2! + 15*x^3/3! + ..., an e.g.f. for A001147. Cf. A094638. H(x) is the e.g.f. for the sequence (-1)^m * m!/2 for m = 2,3,4,... . Cf. A001715 for n!/3! and A001720 for n!/4!. Cf. columns of A094587, A173333, and A213936 and rows of A138533. - Tom Copeland, Dec 27 2019
From Amiram Eldar, Jan 08 2023: (Start)
Sum_{n>=0} 1/a(n) = 2*(e-1).
Sum_{n>=0} (-1)^n/a(n) = 2/e. (End)

Extensions

More terms from Larry Reeves (larryr(AT)acm.org), Aug 20 2001
Further terms from Simone Severini, Oct 15 2004

A000254 Unsigned Stirling numbers of first kind, s(n+1,2): a(n+1) = (n+1)*a(n) + n!.

Original entry on oeis.org

0, 1, 3, 11, 50, 274, 1764, 13068, 109584, 1026576, 10628640, 120543840, 1486442880, 19802759040, 283465647360, 4339163001600, 70734282393600, 1223405590579200, 22376988058521600, 431565146817638400, 8752948036761600000, 186244810780170240000
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Number of permutations of n+1 elements with exactly two cycles.
Number of cycles in all permutations of [n]. Example: a(3) = 11 because the permutations (1)(2)(3), (1)(23), (12)(3), (13)(2), (132), (123) have 11 cycles altogether. - Emeric Deutsch, Aug 12 2004
Row sums of A094310: In the symmetric group S_n, each permutation factors into k independent cycles; a(n) = sum k over S_n. - Harley Flanders (harley(AT)umich.edu), Jun 28 2004
The sum of the top levels of the last column over all deco polyominoes of height n. A deco polyomino is a directed column-convex polyomino in which the height, measured along the diagonal, is attained only in the last column. Example: a(2)=3 because the deco polyominoes of height 2 are the vertical and horizontal dominoes, the levels of their last columns being 2 and 1, respectively. - Emeric Deutsch, Aug 12 2006
a(n) is divisible by n for all composite n >= 6. a(2*n) is divisible by 2*n + 1. - Leroy Quet, May 20 2007
For n >= 2 the determinant of the n-1 X n-1 matrix M(i,j) = i + 2 for i = j and 1 otherwise (i,j = 1..n-1). E.g., for n = 3 the determinant of [(3, 1), (1, 4)]. See 53rd Putnam Examination, 1992, Problem B5. - Franz Vrabec, Jan 13 2008, Mar 26 2008
The numerator of the fraction when we sum (without simplification) the terms in the harmonic sequence. (1 + 1/2 = 2/2 + 1/2 = 3/2; 3/2 + 1/3 = 9/6 + 2/6 = 11/6; 11/6 + 1/4 = 44/24 + 6/24 = 50/24;...). The denominator of this fraction is n!*A000142. - Eric Desbiaux, Jan 07 2009
The asymptotic expansion of the higher order exponential integral E(x,m=2,n=1) ~ exp(-x)/x^2*(1 - 3/x + 11/x^2 - 50/x^3 + 274/x^4 - 1764/x^5 + 13068/x^6 - ...) leads to the sequence given above. See A163931 and A028421 for more information. - Johannes W. Meijer, Oct 20 2009
a(n) is the number of permutations of [n+1] containing exactly 2 cycles. Example: a(2) = 3 because the permutations (1)(23), (12)(3), (13)(2) are the only permutations of [3] with exactly 2 cycles. - Tom Woodward (twoodward(AT)macalester.edu), Nov 12 2009
It appears that, with the exception of n= 4, a(n) mod n = 0 if n is composite and = n-1 if n is prime. - Gary Detlefs, Sep 11 2010
a(n) is a multiple of A025527(n). - Charles R Greathouse IV, Oct 16 2012
Numerator of harmonic number H(n) = Sum_{i=1..n} 1/i when not reduced. See A001008 (Wolstenholme numbers) for the reduced numerators. - Rahul Jha, Feb 18 2015
The Stirling transform of this sequence is A222058(n) (Harmonic-geometric numbers). - Anton Zakharov, Aug 07 2016
a(n) is the (n-1)-st elementary symmetric function of the first n numbers. - Anton Zakharov, Nov 02 2016
The n-th iterated integral of log(x) is x^n * (n! * log(x) - a(n))/(n!)^2 + a polynomial of degree n-1 with arbitrary coefficients. This can be proven using the recurrence relation a(n) = (n-1)! + n*a(n-1). - Mohsen Maesumi, Oct 31 2018
Primes p such that p^3 | a(p-1) are the Wolstenholme primes A088164. - Amiram Eldar and Thomas Ordowski, Aug 08 2019
Total number of left-to-right maxima (or minima) in all permutations of [n]. a(3) = 11 = 3+2+2+2+1+1: (1)(2)(3), (1)(3)2, (2)1(3), (2)(3)1, (3)12, (3)21. - Alois P. Heinz, Aug 01 2020

Examples

			(1-x)^-1 * (-log(1-x)) = x + 3/2*x^2 + 11/6*x^3 + 25/12*x^4 + ...
G.f. = x + x^2 + 5*x^3 + 14*x^4 + 94*x^5 + 444*x^6 + 3828*x^7 + 25584*x^8 + ...

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, identities 186-190.
  • N. Bleistein and R. A. Handelsman, Asymptotic Expansions of Integrals, Dover Publications, 1986, see page 2. MR0863284 (89d:41049)
  • L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 217.
  • F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 226.
  • Shanzhen Gao, Permutations with Restricted Structure (in preparation).
  • K. Javorszky, Natural Orders: De Ordinibus Naturalibus, 2016, ISBN 978-3-99057-139-2.
  • 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. A000399, A000454, A000482, A001233, A001234, A243569, A243570.
Cf. A000774, A004041, A024167, A046674, A049034, A008275.
Cf. A021009, A081358, A092691, A094587, A151881, A121633.
With signs: A081048.
Column 1 in triangle A008969.
Row sums of A136662.

Programs

  • Magma
    a:=[]; for n in [1..22] do a:=a cat [Abs(StirlingFirst(n,2))]; end for; a; // Marius A. Burtea, Jan 01 2020
  • Maple
    A000254 := proc(n) option remember; if n<=1 then n else n*A000254(n-1)+(n-1)!; fi; end: seq(A000254(n),n=0..21);
a := n -> add(n!/k, k=1..n): seq(a(n), n=0..21); # Zerinvary Lajos, Jan 22 2008
  • Mathematica
    Table[ (PolyGamma[ m ]+EulerGamma) (m-1)!, {m, 1, 24} ] (* Wouter Meeussen *)
Table[ n!*HarmonicNumber[n], {n, 0, 19}] (* Robert G. Wilson v, May 21 2005 *)
Table[Sum[1/i,{i,1,n}]/Product[1/i,{i,1,n}],{n,1,30}] (* Alexander Adamchuk, Jul 11 2006 *)
Abs[StirlingS1[Range[20],2]] (* Harvey P. Dale, Aug 16 2011 *)
Table[Gamma'[n + 1] /. EulerGamma -> 0, {n, 0, 30}] (* Li Han, Feb 14 2024*)
  • Maxima
    a(n):=(-1)^(n+1)/2*(n+1)*sum(k*bern(k-1)*stirling1(n,k),k,1,n); /* Vladimir Kruchinin, Nov 20 2016 */
  • MuPAD
    A000254 := proc(n) begin n*A000254(n-1)+fact(n-1) end_proc: A000254(1) := 1:
  • PARI
    {a(n) = if( n<0, 0, (n+1)! / 2 * sum( k=1, n, 1 / k / (n+1-k)))} /* Michael Somos, Feb 05 2004 */
  • Sage
    [stirling_number1(i, 2) for i in range(1, 22)]  # Zerinvary Lajos, Jun 27 2008

Formula

Let P(n,X) = (X+1)*(X+2)*(X+3)*...*(X+n); then a(n) is the coefficient of X; or a(n) = P'(n,0). - Benoit Cloitre, May 09 2002
Sum_{k > 0} a(k) * x^k/ k!^2 = exp(x) *(Sum_{k>0} (-1)^(k+1) * x^k / (k * k!)). - Michael Somos, Mar 24 2004; corrected by Warren D. Smith, Feb 12 2006
a(n) is the coefficient of x^(n+2) in (-log(1-x))^2, multiplied by (n+2)!/2.
a(n) = n! * Sum_{i=1..n} 1/i = n! * H(n), where H(n) = A001008(n)/A002805(n) is the n-th harmonic number.
a(n) ~ 2^(1/2)*Pi^(1/2)*log(n)*n^(1/2)*e^-n*n^n. - Joe Keane (jgk(AT)jgk.org), Jun 06 2002
E.g.f.: log(1 - x) / (x-1). (= (log(1 - x))^2 / 2 if offset 1). - Michael Somos, Feb 05 2004
D-finite with recurrence: a(n) = a(n-1) * (2*n - 1) - a(n-2) * (n - 1)^2, if n > 1. - Michael Somos, Mar 24 2004
a(n) = A081358(n)+A092691(n). - Emeric Deutsch, Aug 12 2004
a(n) = n!*Sum_{k=1..n} (-1)^(k+1)*binomial(n, k)/k. - Vladeta Jovovic, Jan 29 2005
p^2 divides a(p-1) for prime p > 3. a(n) = (Sum_{i=1..n} 1/i) / Product_{i=1..n} 1/i. - Alexander Adamchuk, Jul 11 2006
a(n) = 3* A001710(n) + 2* A001711(n-3) for n > 2; e.g., 11 = 3*3 + 2*1, 50 = 3*12 + 2*7, 274 = 3*60 + 2*47, ... - Gary Detlefs, May 24 2010
a(n) = A138772(n+1) - A159324(n). - Gary Detlefs, Jul 05 2010
a(n) = A121633(n) + A002672(n). - Gary Detlefs, Jul 18 2010
a(n+1) = Sum_{i=1..floor((n-1)/2)} n!/((n-i)*i) + Sum_{i=ceiling(n/2)..floor(n/2)} n!/(2*(n-i)*i). - Shanzhen Gao, Sep 14 2010
From Gary Detlefs, Sep 11 2010: (Start)
a(n) = (a(n-1)*(n^2 - 2*n + 1) + (n + 1)!)/(n - 1) for n > 2.
It appears that, with the exception of n = 2, (a(n+1)^2 - a(n)^2) mod n^2 = 0 if n is composite and 4*n if n is prime.
It appears that, with the exception of n = 2, (a(n+1)^3 - a(n)^2) mod n = 0 if n is composite and n - 2 if n is prime.
It appears that, with the exception of n = 2, (a(n)^2 + a(n+1)^2) mod n = 0 if n is composite and = 2 if n is prime. (End)
a(n) = Integral_{x=0..oo} (x^n - n!)*log(x)*exp(-x) dx. - Groux Roland, Mar 28 2011
a(n) = 3*n!/2 + 2*(n-2)!*Sum_{k=0..n-3} binomial(k+2,2)/(n-2-k) for n >= 2. - Gary Detlefs, Sep 02 2011
a(n)/(n-1)! = ml(n) = n*ml(n-1)/(n-1) + 1 for n > 1, where ml(n) is the average number of random draws from an n-set with replacement until the total set has been observed. G.f. of ml: x*(1 - log(1 - x))/(1 - x)^2. - Paul Weisenhorn, Nov 18 2011
a(n) = det(|S(i+2, j+1)|, 1 <= i,j <= n-2), where S(n,k) are Stirling numbers of the second kind. - Mircea Merca, Apr 06 2013
E.g.f.: x/(1 - x)*E(0)/2, where E(k) = 2 + E(k+1)*x*(k + 1)/(k + 2). - Sergei N. Gladkovskii, Jun 01 2013 [Edited by Michael Somos, Nov 28 2013]
0 = a(n) * (a(n+4) - 6*a(n+3) + 7*a(n+2) - a(n+1)) - a(n+1) * (4*a(n+3) - 6*a(n+2) + a(n+1)) + 3*a(n+2)^2 unless n=0. - Michael Somos, Nov 28 2013
For a simple way to calculate the sequence, multiply n! by the integral from 0 to 1 of (1 - x^n)/(1 - x) dx. - Rahul Jha, Feb 18 2015
From Ilya Gutkovskiy, Aug 07 2016: (Start)
Inverse binomial transform of A073596.
a(n) ~ sqrt(2*Pi*n) * n^n * (log(n) + gamma)/exp(n), where gamma is the Euler-Mascheroni constant A001620. (End)
a(n) = ((-1)^(n+1)/2*(n+1))*Sum_{k=1..n} k*Bernoulli(k-1)*Stirling1(n,k). - Vladimir Kruchinin, Nov 20 2016
a(n) = (n)! * (digamma(n+1) + gamma), where gamma is the Euler-Mascheroni constant A001620. - Pedro Caceres, Mar 10 2018
From Andy Nicol, Oct 21 2021: (Start)
Gamma'(x) = a(x-1) - (x-1)!*gamma, where Gamma'(x) is the derivative of the gamma function at positive integers and gamma is the Euler-Mascheroni constant. E.g.:
Gamma'(1) = -gamma, Gamma'(2) = 1-gamma, Gamma'(3) = 3-2*gamma,
Gamma'(22) = 186244810780170240000 - 51090942171709440000*gamma. (End)
From Peter Bala, Feb 03 2022: (Start)
The following are all conjectural:
E.g.f.: for nonzero m, (1/m)*Sum_{n >= 1} (-1)^(n+1)*(1/n)*binomial(m*n,n)* x^n/(1 - x)^(m*n+1) = x + 3*x^2/2! + 11*x^3/3! + 50*x^4/4! + ....
For nonzero m, a(n) = (1/m)*n!*Sum_{k = 1..n} (-1)^(k+1)*(1/k)*binomial(m*k,k)* binomial(n+(m-1)*k,n-k).
a(n)^2 = (1/2)*n!^2*Sum_{k = 1..n} (-1)^(k+1)*(1/k^2)*binomial(n,k)* binomial(n+k,k). (End)
From Mélika Tebni, Jun 20 2022: (Start)
a(n) = -Sum_{k=0..n} k!*A021009(n, k+1).
a(n) = Sum_{k=0..n} k!*A094587(n, k+1). (End)
a(n) = n! * 1/(1 - 1^2/(3 - 2^2/(5 - 3^2/(7 - ... - (n - 1)^2/((2*n - 1)))))). - Peter Bala, Mar 16 2024

A001563 a(n) = n*n! = (n+1)! - n!.

Original entry on oeis.org

0, 1, 4, 18, 96, 600, 4320, 35280, 322560, 3265920, 36288000, 439084800, 5748019200, 80951270400, 1220496076800, 19615115520000, 334764638208000, 6046686277632000, 115242726703104000, 2311256907767808000, 48658040163532800000, 1072909785605898240000
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

A similar sequence, with the initial 0 replaced by 1, namely A094258, is defined by the recurrence a(2) = 1, a(n) = a(n-1)*(n-1)^2/(n-2). - Andrey Ryshevich (ryshevich(AT)notes.idlab.net), May 21 2002
Denominators in power series expansion of E_1(x) + gamma + log(x), x > 0. - Michael Somos, Dec 11 2002
If all the permutations of any length k are arranged in lexicographic order, the n-th term in this sequence (n <= k) gives the index of the permutation that rotates the last n elements one position to the right. E.g., there are 24 permutations of 4 items. In lexicographic order they are (0,1,2,3), (0,1,3,2), (0,2,1,3), ... (3,2,0,1), (3,2,1,0). Permutation 0 is (0,1,2,3), which rotates the last 1 element, i.e., it makes no change. Permutation 1 is (0,1,3,2), which rotates the last 2 elements. Permutation 4 is (0,3,1,2), which rotates the last 3 elements. Permutation 18 is (3,0,1,2), which rotates the last 4 elements. The same numbers work for permutations of any length. - Henry H. Rich (glasss(AT)bellsouth.net), Sep 27 2003
Stirling transform of a(n+1)=[4,18,96,600,...] is A083140(n+1)=[4,22,154,...]. - Michael Somos, Mar 04 2004
From Michael Somos, Apr 27 2012: (Start)
Stirling transform of a(n)=[1,4,18,96,...] is A069321(n)=[1,5,31,233,...].
Partial sums of a(n)=[0,1,4,18,...] is A033312(n+1)=[0,1,5,23,...].
Binomial transform of A000166(n+1)=[0,1,2,9,...] is a(n)=[0,1,4,18,...].
Binomial transform of A000255(n+1)=[1,3,11,53,...] is a(n+1)=[1,4,18,96,...].
Binomial transform of a(n)=[0,1,4,18,...] is A093964(n)=[0,1,6,33,...].
Partial sums of A001564(n)=[1,3,4,14,...] is a(n+1)=[1,4,18,96,...].
(End)
Number of small descents in all permutations of [n+1]. A small descent in a permutation (x_1,x_2,...,x_n) is a position i such that x_i - x_(i+1) =1. Example: a(2)=4 because there are 4 small descents in the permutations 123, 13\2, 2\13, 231, 312, 3\2\1 of {1,2,3} (shown by \). a(n)=Sum_{k=0..n-1}k*A123513(n,k). - Emeric Deutsch, Oct 02 2006
Equivalently, in the notation of David, Kendall and Barton, p. 263, this is the total number of consecutive ascending pairs in all permutations on n+1 letters (cf. A010027). - N. J. A. Sloane, Apr 12 2014
a(n-1) is the number of permutations of n in which n is not fixed; equivalently, the number of permutations of the positive integers in which n is the largest element that is not fixed. - Franklin T. Adams-Watters, Nov 29 2006
Number of factors in a determinant when writing down all multiplication permutations. - Mats Granvik, Sep 12 2008
a(n) is also the sum of the positions of the left-to-right maxima in all permutations of [n]. Example: a(3)=18 because the positions of the left-to-right maxima in the permutations 123,132,213,231,312 and 321 of [3] are 123, 12, 13, 12, 1 and 1, respectively and 1+2+3+1+2+1+3+1+2+1+1=18. - Emeric Deutsch, Sep 21 2008
Equals eigensequence of triangle A002024 ("n appears n times"). - Gary W. Adamson, Dec 29 2008
Preface the series with another 1: (1, 1, 4, 18, ...); then the next term = dot product of the latter with "n occurs n times". Example: 96 = (1, 1, 4, 8) dot (4, 4, 4, 4) = (4 + 4 + 16 + 72). - Gary W. Adamson, Apr 17 2009
Row lengths of the triangle in A030298. - Reinhard Zumkeller, Mar 29 2012
a(n) is also the number of minimum (n-)distinguishing labelings of the star graph S_{n+1} on n+1 nodes. - Eric W. Weisstein, Oct 14 2014
When the numbers denote finite permutations (as row numbers of A055089) these are the circular shifts to the right, i.e., a(n) is the permutation with the cycle notation (0 1 ... n-1 n). Compare array A051683 for circular shifts to the right in a broader sense. Compare sequence A007489 for circular shifts to the left. - Tilman Piesk, Apr 29 2017
a(n-1) is the number of permutations on n elements with no cycles of length n. - Dennis P. Walsh, Oct 02 2017
The number of pandigital numbers in base n+1, such that each digit appears exactly once. For example, there are a(9) = 9*9! = 3265920 pandigital numbers in base 10 (A050278). - Amiram Eldar, Apr 13 2020

Examples

			E_1(x) + gamma + log(x) = x/1 - x^2/4 + x^3/18 - x^4/96 + ..., x > 0. - _Michael Somos_, Dec 11 2002
G.f. = x + 4*x^2 + 18*x^3 + 96*x^4 + 600*x^5 + 4320*x^6 + 35280*x^7 + 322560*x^8 + ...

References

  • A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 218.
  • J. M. Borwein and P. B. Borwein, Pi and the AGM, Wiley, 1987, p. 336.
  • F. N. David, M. G. Kendall, and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 263.
  • 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 37, equation 37:6:1 at page 354.

Links

Crossrefs

Cf. A000142, A002024, A047920, A047922, A053495, A055089, A123513, A143946, A229837, A239069.
Cf. A163931 (E(x,m,n)), A002775 (n^2*n!), A091363 (n^3*n!), A091364 (n^4*n!).
Cf. sequences with formula (n + k)*n! listed in A282466.
Row sums of A185105, A322383, A322384, A094485.

Programs

  • GAP
    List([0..20], n-> n*Factorial(n) ); # G. C. Greubel, Dec 30 2019
  • Haskell
    a001563 n = a001563_list !! n
a001563_list = zipWith (-) (tail a000142_list) a000142_list
-- Reinhard Zumkeller, Aug 05 2013
  • Magma
    [Factorial(n+1)-Factorial(n): n in [0..20]]; // Vincenzo Librandi, Aug 08 2014
  • Maple
    A001563 := n->n*n!;
  • Mathematica
    Table[n!n,{n,0,25}] (* Harvey P. Dale, Oct 03 2011 *)
  • PARI
    {a(n) = if( n<0, 0, n * n!)} /* Michael Somos, Dec 11 2002 */
  • Sage
    [n*factorial(n) for n in (0..20)] # G. C. Greubel, Dec 30 2019

Formula

From Michael Somos, Dec 11 2002: (Start)
E.g.f.: x / (1 - x)^2.
a(n) = -A021009(n, 1), n >= 0. (End)
The coefficient of y^(n-1) in expansion of (y+n!)^n, n >= 1, gives the sequence 1, 4, 18, 96, 600, 4320, 35280, ... - Artur Jasinski, Oct 22 2007
Integral representation as n-th moment of a function on a positive half-axis: a(n) = Integral_{x=0..oo} x^n*(x*(x-1)*exp(-x)) dx, for n>=0. This representation may not be unique. - Karol A. Penson, Sep 27 2001
a(0)=0, a(n) = n*a(n-1) + n!. - Benoit Cloitre, Feb 16 2003
a(0) = 0, a(n) = (n - 1) * (1 + Sum_{i=1..n-1} a(i)) for i > 0. - Gerald McGarvey, Jun 11 2004
Arises in the denominators of the following identities: Sum_{n>=1} 1/(n*(n+1)*(n+2)) = 1/4, Sum_{n>=1} 1/(n*(n+1)*(n+2)*(n+3)) = 1/18, Sum_{n>=1} 1/(n*(n+1)*(n+2)*(n+3)*(n+4)) = 1/96, etc. The general expression is Sum_{n>=k} 1/C(n, k) = k/(k-1). - Dick Boland, Jun 06 2005 [And the general expression implies that Sum_{n>=1} 1/(n*(n+1)*...*(n+k-1)) = (Sum_{n>=k} 1/C(n, k))/k! = 1/((k-1)*(k-1)!) = 1/a(k-1), k >= 2. - Jianing Song, May 07 2023]
a(n) = Sum_{m=2..n+1} |Stirling1(n+1, m)|, n >= 1 and a(0):=0, where Stirling1(n, m) = A048994(n, m), n >= m = 0.
a(n) = 1/(Sum_{k>=0} k!/(n+k+1)!), n > 0. - Vladeta Jovovic, Sep 13 2006
a(n) = Sum_{k=1..n(n+1)/2} k*A143946(n,k). - Emeric Deutsch, Sep 21 2008
The reciprocals of a(n) are the lead coefficients in the factored form of the polynomials obtained by summing the binomial coefficients with a fixed lower term up to n as the upper term, divided by the term index, for n >= 1: Sum_{k = i..n} C(k, i)/k = (1/a(n))*n*(n-1)*..*(n-i+1). The first few such polynomials are Sum_{k = 1..n} C(k, 1)/k = (1/1)*n, Sum_{k = 2..n} C(k, 2)/k = (1/4)*n*(n-1), Sum_{k = 3..n} C(k, 3)/k = (1/18)*n*(n-1)*(n-2), Sum_{k = 4..n} C(k, 4)/k = (1/96)*n*(n-1)*(n-2)*(n-3), etc. - Peter Breznay (breznayp(AT)uwgb.edu), Sep 28 2008
If we define f(n,i,x) = Sum_{k=i..n} Sum_{j=i..k} binomial(k,j)*Stirling1(n,k)* Stirling2(j,i)*x^(k-j) then a(n) = (-1)^(n-1)*f(n,1,-2), (n >= 1). - Milan Janjic, Mar 01 2009
Sum_{n>=1} (-1)^(n+1)/a(n) = 0.796599599... [Jolley eq. 289]
G.f.: 2*x*Q(0), where Q(k) = 1 - 1/(k+2 - x*(k+2)^2*(k+3)/(x*(k+2)*(k+3)-1/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, Apr 19 2013
G.f.: W(0)*(1-sqrt(x)) - 1, where W(k) = 1 + sqrt(x)/( 1 - sqrt(x)*(k+2)/(sqrt(x)*(k+2) + 1/W(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Aug 18 2013
G.f.: T(0)/x - 1/x, where T(k) = 1 - x^2*(k+1)^2/( x^2*(k+1)^2 - (1-x-2*x*k)*(1-3*x-2*x*k)/T(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Oct 17 2013
G.f.: Q(0)*(1-x)/x - 1/x, where Q(k) = 1 - x*(k+1)/( x*(k+1) - 1/(1 - x*(k+1)/( x*(k+1) - 1/Q(k+1) ))); (continued fraction). - Sergei N. Gladkovskii, Oct 22 2013
D-finite with recurrence: a(n) +(-n-2)*a(n-1) +(n-1)*a(n-2)=0. - R. J. Mathar, Jan 14 2020
a(n) = (-1)^(n+1)*(n+1)*Sum_{k=1..n} A094485(n,k)*Bernoulli(k). The inverse of the Worpitzky representation of the Bernoulli numbers. - Peter Luschny, May 28 2020
From Amiram Eldar, Aug 04 2020: (Start)
Sum_{n>=1} 1/a(n) = Ei(1) - gamma = A229837.
Sum_{n>=1} (-1)^(n+1)/a(n) = gamma - Ei(-1) = A239069. (End)
a(n) = Gamma(n)*A000290(n) for n > 0. - Jacob Szlachetka, Jan 01 2022

A008279 Triangle T(n,k) = n!/(n-k)! (0 <= k <= n) read by rows, giving number of permutations of n things k at a time.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 1, 3, 6, 6, 1, 4, 12, 24, 24, 1, 5, 20, 60, 120, 120, 1, 6, 30, 120, 360, 720, 720, 1, 7, 42, 210, 840, 2520, 5040, 5040, 1, 8, 56, 336, 1680, 6720, 20160, 40320, 40320, 1, 9, 72, 504, 3024, 15120, 60480, 181440, 362880, 362880
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Also called permutation coefficients.
Also falling factorials triangle A068424 with column a(n,0)=1 and row a(0,1)=1 otherwise a(0,k)=0, added. - Wolfdieter Lang, Nov 07 2003
The higher-order exponential integrals E(x,m,n) are defined in A163931; for information about the asymptotic expansion of E(x,m=1,n) see A130534. The asymptotic expansions for n = 1, 2, 3, 4, ..., lead to the right hand columns of the triangle given above. - Johannes W. Meijer, Oct 16 2009
The number of injective functions from a set of size k to a set of size n. - Dennis P. Walsh, Feb 10 2011
The number of functions f from {1,2,...,k} to {1,2,...,n} that satisfy f(x) >= x for all x in {1,2,...,k}. - Dennis P. Walsh, Apr 20 2011
T(n,k) = A181511(n,k) for k=1..n-1. - Reinhard Zumkeller, Nov 18 2012
The e.g.f.s enumerating the faces of the permutohedra / permutahedra, Perm(s,t;x) = [e^(sx)-1]/[s-t(e^(sx)-1)], (cf. A090582 and A019538) and the stellahedra / stellohedra, St(s,t;x) = [s e^((s+t)x)]/[s-t(e^(sx)-1)], (cf. A248727) given in Toric Topology satisfy exp[u*d/dt] St(s,t;x) = St(s,u+t;x) = [e^(ux)/(1-u*Perm(s,t;x))]*St(s,t;x), where e^(ux)/(1-uy) is a bivariate e.g.f. for the row polynomials of this entry and A094587. Equivalently, d/dt St = (x+Perm)*St and d/dt Perm = Perm^2, or d/dt log(St) = x + Perm and d/dt log(Perm) = Perm. - Tom Copeland, Nov 14 2016
T(n, k)/n! are the coefficients of the n-th exponential Taylor polynomial, or truncated exponentials, which was proved to be irreducible by Schur. See Coleman link. - Michel Marcus, Feb 24 2020
Given a generic choice of k+2 residues, T(n, k) is the number of meromorphic differentials on the Riemann sphere having a zero of order n and these prescribed residues at its k+2 poles. - Quentin Gendron, Jan 16 2025

Examples

			Triangle begins:
  1;
  1,  1;
  1,  2,  2;
  1,  3,  6,   6;
  1,  4, 12,  24,   24;
  1,  5, 20,  60,  120,   120;
  1,  6, 30, 120,  360,   720,    720;
  1,  7, 42, 210,  840,  2520,   5040,   5040;
  1,  8, 56, 336, 1680,  6720,  20160,  40320,   40320;
  1,  9, 72, 504, 3024, 15120,  60480, 181440,  362880,  362880;
  1, 10, 90, 720, 5040, 30240, 151200, 604800, 1814400, 3628800, 3628800;
  ...
For example, T(4,2)=12 since there are 12 injective functions f:{1,2}->{1,2,3,4}. There are 4 choices for f(1) and then, since f is injective, 3 remaining choices for f(2), giving us 12 ways to construct an injective function. - _Dennis P. Walsh_, Feb 10 2011
For example, T(5,3)=60 since there are 60 functions f:{1,2,3}->{1,2,3,4,5} with f(x) >= x. There are 5 choices for f(1), 4 choices for f(2), and 3 choices for f(3), giving us 60 ways to construct such a function. - _Dennis P. Walsh_, Apr 30 2011

References

  • CRC Standard Mathematical Tables and Formulae, 30th ed., 1996, p. 176; 31st ed., p. 215, Section 3.3.11.1.
  • Maple V Reference Manual, p. 490, numbperm(n,k).

Links

Crossrefs

Row sums give A000522.
Cf. A001497, A001498, A136572.
T(n,0)=A000012, T(n,1)=A000027, T(n+1,2)=A002378, T(n,3)=A007531, T(n,4)=A052762, and T(n,n)=A000142.
Cf. A019538, A090582, A094587, A248727.

Programs

  • Haskell
    a008279 n k = a008279_tabl !! n !! k
a008279_row n = a008279_tabl !! n
a008279_tabl = iterate f [1] where
   f xs = zipWith (+) ([0] ++ zipWith (*) xs [1..]) (xs ++ [0])
-- Reinhard Zumkeller, Dec 15 2013, Nov 18 2012
  • Magma
    /* As triangle */ [[Factorial(n)/Factorial(n-k): k in [0..n]]: n in [0.. 15]]; // Vincenzo Librandi, Oct 11 2015
  • Maple
    with(combstruct): for n from 0 to 10 do seq(count(Permutation(n),size=m), m = 0 .. n) od; # Zerinvary Lajos, Dec 16 2007
seq(seq(n!/(n-k)!,k=0..n),n=0..10); # Dennis P. Walsh, Apr 20 2011
seq(print(seq(pochhammer(n-k+1,k),k=0..n)),n=0..6); # Peter Luschny, Mar 26 2015
  • Mathematica
    Table[CoefficientList[Series[(1 + x)^m, {x, 0, 20}], x]* Table[n!, {n, 0, m}], {m, 0, 10}] // Grid (* Geoffrey Critzer, Mar 16 2010 *)
Table[ Pochhammer[n - k + 1, k], {n, 0, 9}, {k, 0, n}] // Flatten (* or *)
Table[ FactorialPower[n, k], {n, 0, 9}, {k, 0, n}] // Flatten  (* Jean-François Alcover, Jul 18 2013, updated Jan 28 2016 *)
  • PARI
    {T(n, k) = if( k<0 || k>n, 0, n!/(n-k)!)}; /* Michael Somos, Nov 14 2002 */
  • PARI
    {T(n, k) = my(A, p); if( k<0 || k>n, 0, if( n==0, 1, A = matrix(n, n, i, j, x + (i==j)); polcoeff( sum(i=1, n!, if( p = numtoperm(n, i), prod(j=1, n, A[j, p[j]]))), k)))}; /* Michael Somos, Mar 05 2004 */
  • Python
    from math import factorial, isqrt, comb
def A008279(n): return factorial(a:=(m:=isqrt(k:=n+1<<1))-(k<=m*(m+1)))//factorial(a-n+comb(a+1,2)) # Chai Wah Wu, Nov 13 2024
  • Sage
    for n in range(8): [falling_factorial(n,k) for k in (0..n)] # Peter Luschny, Mar 26 2015

Formula

E.g.f.: Sum T(n,k) x^n/n! y^k = exp(x)/(1-x*y). - Vladeta Jovovic, Aug 19 2002
Equals A007318 * A136572. - Gary W. Adamson, Jan 07 2008
T(n, k) = n*T(n-1, k-1) = k*T(n-1, k-1)+T(n-1, k) = n*T(n-1, k)/(n-k) = (n-k+1)*T(n, k-1). - Henry Bottomley, Mar 29 2001
T(n, k) = n!/(n-k)! if n >= k >= 0, otherwise 0.
G.f. for k-th column k!*x^k/(1-x)^(k+1), k >= 0.
E.g.f. for n-th row (1+x)^n, n >= 0.
Sum T(n, k)x^k = permanent of n X n matrix a_ij = (x+1 if i=j, x otherwise). - Michael Somos, Mar 05 2004
Ramanujan psi_1(k, x) polynomials evaluated at n+1. - Ralf Stephan, Apr 16 2004
E.g.f.: Sum T(n,k) x^n/n! y^k/k! = e^{x+xy}. - Franklin T. Adams-Watters, Feb 07 2006
The triangle is the binomial transform of an infinite matrix with (1, 1, 2, 6, 24, ...) in the main diagonal and the rest zeros. - Gary W. Adamson, Nov 20 2006
G.f.: 1/(1-x-xy/(1-xy/(1-x-2xy/(1-2xy/(1-x-3xy/(1-3xy/(1-x-4xy/(1-4xy/(1-... (continued fraction). - Paul Barry, Feb 11 2009
T(n,k) = Sum_{j=0..k} binomial(k,j)*T(x,j)*T(y,k-j) for x+y = n. - Dennis P. Walsh, Feb 10 2011
From Dennis P. Walsh, Apr 20 2011: (Start)
E.g.f (with k fixed): x^k*exp(x).
G.f. (with k fixed): k!*x^k/(1-x)^(k+1). (End)
For n >= 2 and m >= 2, Sum_{k=0..m-2} S2(n, k+2)*T(m-2, k) = Sum_{p=0..n-2} m^p. S2(n,k) are the Stirling numbers of the second kind A008277. - Tony Foster III, Jul 23 2019

A130534 Triangle T(n,k), 0 <= k <= n, read by rows, giving coefficients of the polynomial (x+1)(x+2)...(x+n), expanded in increasing powers of x. T(n,k) is also the unsigned Stirling number |s(n+1, k+1)|, denoting the number of permutations on n+1 elements that contain exactly k+1 cycles.

Original entry on oeis.org

1, 1, 1, 2, 3, 1, 6, 11, 6, 1, 24, 50, 35, 10, 1, 120, 274, 225, 85, 15, 1, 720, 1764, 1624, 735, 175, 21, 1, 5040, 13068, 13132, 6769, 1960, 322, 28, 1, 40320, 109584, 118124, 67284, 22449, 4536, 546, 36, 1, 362880, 1026576, 1172700, 723680, 269325, 63273, 9450, 870, 45, 1
Offset: 0

Views

Author

Philippe Deléham, Aug 09 2007

Keywords

Comments

This triangle is an unsigned version of the triangle of Stirling numbers of the first kind, A008275, which is the main entry for these numbers. - N. J. A. Sloane, Jan 25 2011
Or, triangle T(n,k), 0 <= k <= n, read by rows given by [1,1,2,2,3,3,4,4,5,5,6,6,...] DELTA [1,0,1,0,1,0,1,0,1,0,1,0,...] where DELTA is the operator defined in A084938.
Reversal of A094638.
Equals A132393*A007318, as infinite lower triangular matrices. - Philippe Deléham, Nov 13 2007
From Johannes W. Meijer, Oct 07 2009: (Start)
The higher order exponential integrals E(x,m,n) are defined in A163931. The asymptotic expansion of the exponential integrals E(x,m=1,n) ~ (exp(-x)/x)*(1 - n/x + n*(n+1)/x^2 - n*(n+1)*(n+2)/x^3 + ...), see Abramowitz and Stegun. This formula follows from the general formula for the asymptotic expansion, see A163932. We rewrite E(x,m=1,n) ~ (exp(-x)/x)*(1 - n/x + (n^2+n)/x^2 - (2*n+3*n^2+n^3)/x^3 + (6*n+11*n^2+6*n^3+n^4)/x^3 - ...) and observe that the T(n,m) are the polynomials coefficients in the denominators. Looking at the a(n,m) formula of A028421, A163932 and A163934, and shifting the offset given above to 1, we can write T(n-1,m-1) = a(n,m) = (-1)^(n+m)*Stirling1(n,m), see the Maple program.
The asymptotic expansion leads for values of n from one to eleven to known sequences, see the cross-references. With these sequences one can form the triangles A008279 (right-hand columns) and A094587 (left-hand columns).
See A163936 for information about the o.g.f.s. of the right-hand columns of this triangle.
(End)
The number of elements greater than i to the left of i in a permutation gives the i-th element of the inversion vector. (Skiena-Pemmaraju 2003, p. 69.) T(n,k) is the number of n-permutations that have exactly k 0's in their inversion vector. See evidence in Mathematica code below. - Geoffrey Critzer, May 07 2010
T(n,k) counts the rooted trees with k+1 trunks in forests of "naturally grown" rooted trees with n+2 nodes. This corresponds to sums of coefficients of iterated derivatives representing vectors, Lie derivatives, or infinitesimal generators for flow fields and formal group laws. Cf. links in A139605. - Tom Copeland, Mar 23 2014
A refinement is A036039. - Tom Copeland, Mar 30 2014
From Tom Copeland, Apr 05 2014: (Start)
With initial n=1 and row polynomials of T as p(n,x)=x(x+1)...(x+n-1), the powers of x correspond to the number of trunks of the rooted trees of the "naturally-grown" forest referred to above. With each trunk allowed m colors, p(n,m) gives the number of such non-plane colored trees for the forest with each tree having n+1 vertices.
p(2,m) = m + m^2 = A002378(m) = 2*A000217(m) = 2*(first subdiag of |A238363|).
p(3,m) = 2m + 3m^2 + m^3 = A007531(m+2) = 3*A007290(m+2) = 3*(second subdiag A238363).
p(4,m) = 6m + 11m^2 + 6m^3 + m^4 = A052762(m+3) = 4*A033487(m) = 4*(third subdiag).
From the Joni et al. link, p(n,m) also represents the disposition of n distinguishable flags on m distinguishable flagpoles.
The chromatic polynomial for the complete graph K_n is the falling factorial, which encodes the colorings of the n vertices of K_n and gives a shifted version of p(n,m).
E.g.f. for the row polynomials: (1-y)^(-x).
(End)
A relation to derivatives of the determinant |V(n)| of the n X n Vandermonde matrix V(n) in the indeterminates c(1) thru c(n):
|V(n)| = Product_{1<=jTom Copeland, Apr 10 2014
From Peter Bala, Jul 21 2014: (Start)
Let M denote the lower unit triangular array A094587 and for k = 0,1,2,... define M(k) to be the lower unit triangular block array
/I_k 0\
\ 0 M/
having the k X k identity matrix I_k as the upper left block; in particular, M(0) = M. Then the present triangle equals the infinite matrix product M(0)*M(1)*M(2)*... (which is clearly well defined). See the Example section. (End)
For the relation of this rising factorial to the moments of Viennot's Laguerre stories, see the Hetyei link, p. 4. - Tom Copeland, Oct 01 2015
Can also be seen as the Bell transform of n! without column 0 (and shifted enumeration). For the definition of the Bell transform see A264428. - Peter Luschny, Jan 27 2016

Examples

			Triangle  T(n,k) begins:
n\k         0        1        2       3       4      5      6     7    8  9 10
n=0:        1
n=1:        1        1
n=2:        2        3        1
n=3:        6       11        6       1
n=4:       24       50       35      10       1
n=5:      120      274      225      85      15      1
n=6:      720     1764     1624     735     175     21      1
n=7:     5040    13068    13132    6769    1960    322     28     1
n=8:    40320   109584   118124   67284   22449   4536    546    36    1
n=9:   362880  1026576  1172700  723680  269325  63273   9450   870   45  1
n=10: 3628800 10628640 12753576 8409500 3416930 902055 157773 18150 1320 55  1
[Reformatted and extended by _Wolfdieter Lang_, Feb 05 2013]
T(3,2) = 6 because there are 6 permutations of {1,2,3,4} that have exactly 2 0's in their inversion vector: {1, 2, 4, 3}, {1, 3, 2, 4}, {1, 3, 4, 2}, {2, 1, 3, 4},{2, 3, 1, 4}, {2, 3, 4, 1}. The respective inversion vectors are {0, 0, 1}, {0, 1, 0}, {0, 2, 0}, {1, 0, 0}, {2, 0, 0}, {3, 0, 0}. - _Geoffrey Critzer_, May 07 2010
T(3,1)=11 since there are exactly 11 permutations of {1,2,3,4} with exactly 2 cycles, namely, (1)(234), (1)(243), (2)(134), (2)(143), (3)(124), (3)(142), (4)(123), (4)(143), (12)(34), (13)(24), and (14)(23). - _Dennis P. Walsh_, Jan 25 2011
From _Peter Bala_, Jul 21 2014: (Start)
With the arrays M(k) as defined in the Comments section, the infinite product M(0*)M(1)*M(2)*... begins
  / 1          \/1        \/1        \      / 1           \
  | 1  1       ||0 1      ||0 1      |      | 1  1        |
  | 2  2  1    ||0 1 1    ||0 0 1    |... = | 2  3  1     |
  | 6  6  3 1  ||0 2 2 1  ||0 0 1 1  |      | 6 11  6  1  |
  |24 24 12 4 1||0 6 6 3 1||0 0 2 2 1|      |24 50 35 10 1|
  |...         ||...      ||...      |      |...          |
(End)

References

  • John H. Conway and Richard K. Guy, The Book of Numbers, New York: Springer-Verlag, 1996. See pp. 93-94.
  • Sriram Pemmaraju and Steven Skiena, Computational Discrete Mathematics, Cambridge University Press, 2003, pp. 69-71. [Geoffrey Critzer, May 07 2010]

Links

Crossrefs

See A008275, which is the main entry for these numbers; A094638 (reversed rows).
Diagonals: A000012 A000217 A000914 A001303 A000915 A053567 A112002 A191685. Columns A000142 A000254 A000399 A000454 A000482 A001233 A001234.
From Johannes W. Meijer, Oct 07 2009: (Start)
Row sums equal A000142.
The asymptotic expansions lead to A000142 (n=1), A000142(n=2; minus a(0)), A001710 (n=3), A001715 (n=4), A001720 (n=5), A001725 (n=6), A001730 (n=7), A049388 (n=8), A049389 (n=9), A049398 (n=10), A051431 (n=11), A008279 and A094587.
Cf. A163931 (E(x,m,n)), A028421 (m=2), A163932 (m=3), A163934 (m=4), A163936.
(End)
Cf. A136662.

Programs

  • Haskell
    a130534 n k = a130534_tabl !! n !! k
a130534_row n = a130534_tabl !! n
a130534_tabl = map (map abs) a008275_tabl
-- Reinhard Zumkeller, Mar 18 2013
  • Maple
    with(combinat): A130534 := proc(n,m): (-1)^(n+m)*stirling1(n+1,m+1) end proc: seq(seq(A130534(n,m), m=0..n), n=0..10); # Johannes W. Meijer, Oct 07 2009, revised Sep 11 2012
# The function BellMatrix is defined in A264428.
# Adds (1,0,0,0, ..) as column 0 (and shifts the enumeration).
BellMatrix(n -> n!, 9); # Peter Luschny, Jan 27 2016
  • Mathematica
    Table[Table[ Length[Select[Map[ToInversionVector, Permutations[m]], Count[ #, 0] == n &]], {n, 0, m - 1}], {m, 0, 8}] // Grid (* Geoffrey Critzer, May 07 2010 *)
rows = 10;
t = Range[0, rows]!;
T[n_, k_] := BellY[n, k, t];
Table[T[n, k], {n, 1, rows}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jun 22 2018, after Peter Luschny *)

Formula

T(0,0) = 1, T(n,k) = 0 if k > n or if n < 0, T(n,k) = T(n-1,k-1) + n*T(n-1,k). T(n,0) = n! = A000142(n). T(2*n,n) = A129505(n+1). Sum_{k=0..n} T(n,k) = (n+1)! = A000142(n+1). Sum_{k=0..n} T(n,k)^2 = A047796(n+1). T(n,k) = |Stirling1(n+1,k+1)|, see A008275. (x+1)(x+2)...(x+n) = Sum_{k=0..n} T(n,k)*x^k. [Corrected by Arie Bos, Jul 11 2008]
Sum_{k=0..n} T(n,k)*x^k = A000007(n), A000142(n), A000142(n+1), A001710(n+2), A001715(n+3), A001720(n+4), A001725(n+5), A001730(n+6), A049388(n), A049389(n), A049398(n), A051431(n) for x = -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, respectively. - Philippe Deléham, Nov 13 2007
For k=1..n, let A={a_1,a_2,...,a_k} denote a size-k subset of {1,2,...,n}. Then T(n,n-k) = Sum(Product_{i=1..k} a_i) where the sum is over all subsets A. For example, T(4,1)=50 since 1*2*3 + 1*2*4 + 1*3*4 + 2*3*4 = 50. - Dennis P. Walsh, Jan 25 2011
The preceding formula means T(n,k) = sigma_{n-k}(1,2,3,..,n) with the (n-k)-th elementary symmetric function sigma with the indeterminates chosen as 1,2,...,n. See the Oct 24 2011 comment in A094638 with sigma called there a. - Wolfdieter Lang, Feb 06 2013
From Gary W. Adamson, Jul 08 2011: (Start)
n-th row of the triangle = top row of M^n, where M is the production matrix:
1, 1;
1, 2, 1;
1, 3, 3, 1;
1, 4, 6, 4, 1;
... (End)
Exponential Riordan array [1/(1 - x), log(1/(1 - x))]. Recurrence: T(n+1,k+1) = Sum_{i=0..n-k} (n + 1)!/(n + 1 - i)!*T(n-i,k). - Peter Bala, Jul 21 2014

A001715 a(n) = n!/6.

Original entry on oeis.org

1, 4, 20, 120, 840, 6720, 60480, 604800, 6652800, 79833600, 1037836800, 14529715200, 217945728000, 3487131648000, 59281238016000, 1067062284288000, 20274183401472000, 405483668029440000, 8515157028618240000, 187333454629601280000, 4308669456480829440000
Offset: 3

Views

Author

N. J. A. Sloane

Keywords

Comments

The numbers (4, 20, 120, 840, 6720, ...) arise from the divisor values in the general formula a(n) = n*(n+1)*(n+2)*(n+3)* ... *(n+k)*(n*(n+k) + (k-1)*k/6)/((k+3)!/6) (which covers the following sequences: A000578, A000537, A024166, A101094, A101097, A101102). - Alexander R. Povolotsky, May 17 2008
a(n) is also the number of decreasing 3-cycles in the decomposition of permutations as product of disjoint cycles, a(3)=1, a(4)=4, a(5)=20. - Wenjin Woan, Dec 21 2008
Equals eigensequence of triangle A130128 reflected. - Gary W. Adamson, Dec 23 2008
a(n) is the number of n-permutations having 1, 2, and 3 in three distinct cycles. - Geoffrey Critzer, Apr 26 2009
From Johannes W. Meijer, Oct 20 2009: (Start)
The asymptotic expansion of the higher order exponential integral E(x,m=1,n=4) ~ exp(-x)/x*(1 - 4/x + 20/x^2 - 120/x^3 + 840/x^4 - 6720/x^5 + 60480/x^6 - 604800/x^7 + ...) leads to the sequence given above. See A163931 and A130534 for more information.
(End)

References

  • 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. A049352, A049458, A049460.
Cf. A034472, A130128.
Cf. A245334, A000142, A111530.
Cf. A001710, A001720, A007759, A094638.
Cf. A094587, A138533, A173333, A213936.

Programs

Formula

a(n) = A049352(n-2, 1) (first column of triangle).
E.g.f. if offset 0: 1/(1-x)^4.
a(n) = A173333(n,3). - Reinhard Zumkeller, Feb 19 2010
G.f.: G(0)/2, where G(k) = 1 + 1/(1 - x/(x + 1/(k+4)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 01 2013
G.f.: W(0), where W(k) = 1 - x*(k+4)/( x*(k+4) - 1/(1 - x*(k+1)/( x*(k+1) - 1/W(k+1) ))); (continued fraction). - Sergei N. Gladkovskii, Aug 26 2013
a(n) = A245334(n,n-3) / 4. - Reinhard Zumkeller, Aug 31 2014
From Peter Bala, May 22 2017: (Start)
The o.g.f. A(x) satisfies the Riccati equation x^2*A'(x) + (4*x - 1)*A(x) + 1 = 0.
G.f. as an S-fraction: A(x) = 1/(1 - 4*x/(1 - x/(1 - 5*x/(1 - 2*x/(1 - 6*x/(1 - 3*x/(1 - ... - (n + 3)*x/(1 - n*x/(1 - ... ))))))))) (apply Stokes, 1982).
A(x) = 1/(1 - 3*x - x/(1 - 4*x/(1 - 2*x/(1 - 5*x/(1 - 3*x/(1 - 6*x/(1 - ... - n*x/(1 - (n+3)*x/(1 - ... ))))))))). (End)
H(x) = (1 - (1 + x)^(-3)) / 3 = x - 4 x^2/2! + 20 x^3/3! - ... is an e.g.f. of the signed sequence (n!/4!), which is the compositional inverse of G(x) = (1 - 3*x)^(-1/3) - 1, an e.g.f. for A007559. Cf. A094638, A001710 (for n!/2!), and A001720 (for n!/4!). Cf. columns of A094587, A173333, and A213936 and rows of A138533.- Tom Copeland, Dec 27 2019
E.g.f.: x^3 / (3! * (1 - x)). - Ilya Gutkovskiy, Jul 09 2021
From Amiram Eldar, Jan 15 2023: (Start)
Sum_{n>=3} 1/a(n) = 6*e - 15.
Sum_{n>=3} (-1)^(n+1)/a(n) = 3 - 6/e. (End)

Extensions

More terms from Harvey P. Dale, Aug 12 2012

A094587 Triangle of permutation coefficients arranged with 1's on the diagonal. Also, triangle of permutations on n letters with exactly k+1 cycles and with the first k+1 letters in separate cycles.

Original entry on oeis.org

1, 1, 1, 2, 2, 1, 6, 6, 3, 1, 24, 24, 12, 4, 1, 120, 120, 60, 20, 5, 1, 720, 720, 360, 120, 30, 6, 1, 5040, 5040, 2520, 840, 210, 42, 7, 1, 40320, 40320, 20160, 6720, 1680, 336, 56, 8, 1, 362880, 362880, 181440, 60480, 15120, 3024, 504, 72, 9, 1, 3628800, 3628800
Offset: 0

Views

Author

Paul Barry, May 13 2004

Keywords

Comments

Also, table of Pochhammer sequences read by antidiagonals (see Rudolph-Lilith, 2015). - N. J. A. Sloane, Mar 31 2016
Reverse of A008279. Row sums are A000522. Diagonal sums are A003470. Rows of inverse matrix begin {1}, {-1,1}, {0,-2,1}, {0,0,-3,1}, {0,0,0,-4,1} ... The signed lower triangular matrix (-1)^(n+k)n!/k! has as row sums the signed rencontres numbers Sum_{k=0..n} (-1)^(n+k)n!/k!. (See A000166). It has matrix inverse 1 1,1 0,2,1 0,0,3,1 0,0,0,4,1,...
Exponential Riordan array [1/(1-x),x]; column k has e.g.f. x^k/(1-x). - Paul Barry, Mar 27 2007
From Tom Copeland, Nov 01 2007: (Start)
T is the umbral extension of n!*Lag[n,(.)!*Lag[.,x,-1],0] = (1-D)^(-1) x^n = (-1)^n * n! * Lag(n,x,-1-n) = Sum_{j=0..n} binomial(n,j) * j! * x^(n-j) = Sum_{j=0..n} (n!/j!) x^j. The inverse operator is A132013 with generalizations discussed in A132014.
b = T*a can be characterized several ways in terms of a(n) and b(n) or their o.g.f.'s A(x) and B(x).
1) b(n) = n! Lag[n,(.)!*Lag[.,a(.),-1],0], umbrally,
2) b(n) = (-1)^n n! Lag(n,a(.),-1-n)
3) b(n) = Sum_{j=0..n} (n!/j!) a(j)
4) B(x) = (1-xDx)^(-1) A(x), formally
5) B(x) = Sum_{j=0,1,...} (xDx)^j A(x)
6) B(x) = Sum_{j=0,1,...} x^j * D^j * x^j A(x)
7) B(x) = Sum_{j=0,1,...} j! * x^j * L(j,-:xD:,0) A(x) where Lag(n,x,m) are the Laguerre polynomials of order m, D the derivative w.r.t. x and (:xD:)^j = x^j * D^j. Truncating the operator series at the j = n term gives an o.g.f. for b(0) through b(n).
c = (0!,1!,2!,3!,4!,...) is the sequence associated to T under the list partition transform and the associated operations described in A133314 so T(n,k) = binomial(n,k)*c(n-k). The reciprocal sequence is d = (1,-1,0,0,0,...). (End)
From Peter Bala, Jul 10 2008: (Start)
This array is the particular case P(1,1) of the generalized Pascal triangle P(a,b), a lower unit triangular matrix, shown below:
n\k|0.....................1...............2.......3......4
----------------------------------------------------------
0..|1.....................................................
1..|a....................1................................
2..|a(a+b)...............2a..............1................
3..|a(a+b)(a+2b).........3a(a+b).........3a........1......
4..|a(a+b)(a+2b)(a+3b)...4a(a+b)(a+2b)...6a(a+b)...4a....1
...
The entries A(n,k) of this array satisfy the recursion A(n,k) = (a+b*(n-k-1))*A(n-1,k) + A(n-1,k-1), which reduces to the Pascal formula when a = 1, b = 0.
Various cases are recorded in the database, including: P(1,0) = Pascal's triangle A007318, P(2,0) = A038207, P(3,0) = A027465, P(2,1) = A132159, P(1,3) = A136215 and P(2,3) = A136216.
When b <> 0 the array P(a,b) has e.g.f. exp(x*y)/(1-b*y)^(a/b) = 1 + (a+x)*y + (a*(a+b)+2a*x+x^2)*y^2/2! + (a*(a+b)*(a+2b) + 3a*(a+b)*x + 3a*x^2+x^3)*y^3/3! + ...; the array P(a,0) has e.g.f. exp((x+a)*y).
We have the matrix identities P(a,b)*P(a',b) = P(a+a',b); P(a,b)^-1 = P(-a,b).
An analog of the binomial expansion for the row entries of P(a,b) has been proved by [Echi]. Introduce a (generally noncommutative and nonassociative) product ** on the ring of polynomials in two variables by defining F(x,y)**G(x,y) = F(x,y)G(x,y) + by^2*d/dy(G(x,y)).
Define the iterated product F^(n)(x,y) of a polynomial F(x,y) by setting F^(1) = F(x,y) and F^(n)(x,y) = F(x,y)**F^(n-1)(x,y) for n >= 2. Then (x+a*y)^(n) = x^n + C(n,1)*a*x^(n-1)*y + C(n,2)*a*(a+b)*x^(n-2)*y^2 + ... + C(n,n)*a*(a+b)*(a+2b)*...*(a+(n-1)b)*y^n. (End)
(n+1) * n-th row = reversal of triangle A068424: (1; 2,2; 6,6,3; ...) - Gary W. Adamson, May 03 2009
Let G(m, k, p) = (-p)^k*Product_{j=0..k-1}(j - m - 1/p) and T(n,k,p) = G(n-1,n-k,p) then T(n, k, 1) is this sequence, T(n, k, 2) = A112292(n, k) and T(n, k, 3) = A136214. - Peter Luschny, Jun 01 2009, revised Jun 18 2019
The higher order exponential integrals E(x,m,n) are defined in A163931. For a discussion of the asymptotic expansions of the E(x,m=1,n) ~ (exp(-x)/x)*(1 - n/x + (n^2+n)/x^2 - (2*n+3*n^2+n^3)/x^3 + (6*n+11*n^2+6*n^3+n^4)/x^3 - ...) see A130534. The asymptotic expansion of E(x,m=1,n) leads for n >= 1 to the left hand columns of the triangle given above. Triangle A165674 is generated by the asymptotic expansions of E(x,m=2,n). - Johannes W. Meijer, Oct 07 2009
T(n,k) = n!/k! = number of permutations of [n+1] with exactly k+1 cycles and with elements 1,2,...,k+1 in separate cycles. See link and example below. - Dennis P. Walsh, Jan 24 2011
T(n,k) is the number of n permutations that leave some size k subset of {1,2,...,n} fixed. Sum_{k=0..n}(-1)^k*T(n,k) = A000166(n) (the derangements). - Geoffrey Critzer, Dec 11 2011
T(n,k) = A162995(n-1,k-1), 2 <= k <= n; T(n,k) = A173333(n,k), 1 <= k <= n. - Reinhard Zumkeller, Jul 05 2012
The row polynomials form an Appell sequence. The matrix is a special case of a group of general matrices sketched in A132382. - Tom Copeland, Dec 03 2013
For interpretations in terms of colored necklaces, see A213936 and A173333. - Tom Copeland, Aug 18 2016
See A008279 for a relation of this entry to the e.g.f.s enumerating the faces of permutahedra and stellahedra. - Tom Copeland, Nov 14 2016
Also, T(n,k) is the number of ways to arrange n-k nonattacking rooks on the n X (n-k) chessboard. - Andrey Zabolotskiy, Dec 16 2016
The infinitesimal generator of this triangle is the generalized exponential Riordan array [-log(1-x), x] and equals the unsigned version of A238363. - Peter Bala, Feb 13 2017
Formulas for exponential and power series infinitesimal generators for this triangle T are given in Copeland's 2012 and 2014 formulas as T = unsigned exp[(I-A238385)] = 1/(I - A132440), where I is the identity matrix. - Tom Copeland, Jul 03 2017
If A(0) = 1/(1-x), and A(n) = d/dx(A(n-1)), then A(n) = n!/(1-x)^(n+1) = Sum_{k>=0} (n+k)!/k!*x^k = Sum_{k>=0} T(n+k, k)*x^k. - Michael Somos, Sep 19 2021

Examples

			Rows begin {1}, {1,1}, {2,2,1}, {6,6,3,1}, ...
For n=3 and k=1, T(3,1)=6 since there are exactly 6 permutations of {1,2,3,4} with exactly 2 cycles and with 1 and 2 in separate cycles. The permutations are (1)(2 3 4), (1)(2 4 3), (1 3)(2 4), (1 4)(2 3), (1 3 4)(2), and (1 4 3)(2). - _Dennis P. Walsh_, Jan 24 2011
Triangle begins:
     1,
     1,    1,
     2,    2,    1,
     6,    6,    3,    1,
    24,   24,   12,    4,    1,
   120,  120,   60,   20,    5,    1,
   720,  720,  360,  120,   30,    6,    1,
  5040, 5040, 2520,  840,  210,   42,    7,    1
The production matrix is:
      1,     1,
      1,     1,     1,
      2,     2,     1,    1,
      6,     6,     3,    1,    1,
     24,    24,    12,    4,    1,   1,
    120,   120,    60,   20,    5,   1,   1,
    720,   720,   360,  120,   30,   6,   1,   1,
   5040,  5040,  2520,  840,  210,  42,   7,   1,   1,
  40320, 40320, 20160, 6720, 1680, 336,  56,   8,   1,   1
which is the exponential Riordan array A094587, or [1/(1-x),x], with an extra superdiagonal of 1's.
Inverse begins:
   1,
  -1,  1,
   0, -2,  1,
   0,  0, -3,  1,
   0,  0,  0, -4,  1,
   0,  0,  0,  0, -5,  1,
   0,  0,  0,  0,  0, -6,  1,
   0,  0,  0,  0,  0,  0, -7,  1

Links

Crossrefs

Cf. A000166 (alt. row sums), A000522 (row sums).
Cf. A068424, A036039, A173333, A213936, A263916.
Cf. A000670, A008279, A021009, A048994, A132013, A132014, A132159, A132440, A133314, A218234, A235706, A238385.

Programs

  • Haskell
    a094587 n k = a094587_tabl !! n !! k
a094587_row n = a094587_tabl !! n
a094587_tabl = map fst $ iterate f ([1], 1)
   where f (row, i) = (map (* i) row ++ [1], i + 1)
-- Reinhard Zumkeller, Jul 04 2012
  • Maple
    T := proc(n, m): n!/m! end: seq(seq(T(n, m), m=0..n), n=0..9);  # Johannes W. Meijer, Oct 07 2009, revised Nov 25 2012
# Alternative: Note that if you leave out 'abs' you get A021009.
T := proc(n, k) option remember; if n = 0 and k = 0 then 1 elif k < 0 or k > n then 0 else abs((n + k)*T(n-1, k) - T(n-1, k-1)) fi end: #  Peter Luschny, Dec 30 2021
  • Mathematica
    Flatten[Table[Table[n!/k!, {k,0,n}], {n,0,10}]] (* Geoffrey Critzer, Dec 11 2011 *)
  • Sage
    def A094587_row(n): return (factorial(n)*exp(x).taylor(x,0,n)).list()
for n in (0..7): print(A094587_row(n)) # Peter Luschny, Sep 28 2017

Formula

T(n, k) = n!/k! if n >= k >= 0, otherwise 0.
T(n, k) = Sum_{i=k..n} |S1(n+1, i+1)*S2(i, k)| * (-1)^i, with S1, S2 the Stirling numbers.
T(n,k) = (n-k)*T(n-1,k) + T(n-1,k-1). E.g.f.: exp(x*y)/(1-y) = 1 + (1+x)*y + (2+2*x+x^2)*y^2/2! + (6+6*x+3*x^2+x^3)*y^3/3!+ ... . - Peter Bala, Jul 10 2008
A094587 = 1 / ((-1)*A129184 * A127648 + I), I = Identity matrix. - Gary W. Adamson, May 03 2009
From Johannes W. Meijer, Oct 07 2009: (Start)
The o.g.f. of right hand column k is Gf(z;k) = (k-1)!/(1-z)^k, k => 1.
The recurrence relations of the right hand columns lead to Pascal's triangle A007318. (End)
Let f(x) = (1/x)*exp(-x). The n-th row polynomial is R(n,x) = (-x)^n/f(x)*(d/dx)^n(f(x)), and satisfies the recurrence equation R(n+1,x) = (x+n+1)*R(n,x)-x*R'(n,x). Cf. A132159. - Peter Bala, Oct 28 2011
A padded shifted version of this lower triangular matrix with zeros in the first column and row except for a one in the diagonal position is given by integral(t=0 to t=infinity) exp[-t(I-P)] = 1/(I-P) = I + P^2 + P^3 + ... where P is the infinitesimal generator matrix A218234 and I the identity matrix. The non-padded version is given by P replaced by A132440. - Tom Copeland, Oct 25 2012
From Peter Bala, Aug 28 2013: (Start)
The row polynomials R(n,x) form a Sheffer sequence of polynomials with associated delta operator equal to d/dx. Thus d/dx(R(n,x)) = n*R(n-1,x). The Sheffer identity is R(n,x + y) = Sum_{k=0..n} binomial(n,k)*y^(n-k)*R(k,x).
Let P(n,x) = Product_{k=0..n-1} (x + k) denote the rising factorial polynomial sequence with the convention that P(0,x) = 1. Then this is triangle of connection constants when expressing the basis polynomials P(n,x + 1) in terms of the basis P(n,x). For example, row 3 is (6, 6, 3, 1) so P(3,x + 1) = (x + 1)*(x + 2)*(x + 3) = 6 + 6*x + 3*x*(x + 1) + x*(x + 1)*(x + 2). (End)
From Tom Copeland, Apr 21 & 26, and Aug 13 2014: (Start)
T-I = M = -A021009*A132440*A021009 with e.g.f. y*exp(x*y)/(1-y). Cf. A132440. Dividing the n-th row of M by n generates the (n-1)th row of T.
T = 1/(I - A132440) = {2*I - exp[(A238385-I)]}^(-1) = unsigned exp[(I-A238385)] = exp[A000670(.)*(A238385-I)] = , umbrally, where I = identity matrix.
The e.g.f. is exp(x*y)/(1-y), so the row polynomials form an Appell sequence with lowering operator d/dx and raising operator x + 1/(1-D).
With L(n,m,x)= Laguerre polynomials of order m, the row polynomials are (-1)^n*n!*L(n,-1-n,x) = (-1)^n*(-1!/(-1-n)!)*K(-n,-1-n+1,x) = n!* K(-n,-n,x) where K is Kummer's confluent hypergeometric function (as a limit of n+s as s tends to zero).
Operationally, (-1)^n*n!*L(n,-1-n,-:xD:) = (-1)^n*x^(n+1)*:Dx:^n*x^(-1-n) = (-1)^n*x*:xD:^n*x^(-1) = (-1)^n*n!*binomial(xD-1,n) = n!*K(-n,-n,-:xD:) where :AB:^n = A^n*B^n for any two operators. Cf. A235706 and A132159.
The n-th row of signed M has the coefficients of d[(-:xD:)^n]/d(:Dx:)= f[d/d(-:xD:)](-:xD:)^n with f(y)=y/(y-1), :Dx:^n= n!L(n,0,-:xD:), and (-:xD:)^n = n!L(n,0,:Dx:). M has the coefficients of [D/(1-D)]x^n. (End)
From Tom Copeland, Nov 18 2015: (Start)
Coefficients of the row polynomials of the e.g.f. Sum_{n>=0} P_n(b1,b2,..,bn;t) x^n/n! = e^(P.(..;t) x) = e^(xt) / (1-b.x) = (1 + b1 x + b2 x^2 + b3 x^3 + ...) e^(xt) = 1 + (b1 + t) x + (2 b2 + 2 b1 t + t^2) x^2/2! + (6 b3 + 6 b2 t + 3 b1 t^2 + t^3) x^3/3! + ... , with lowering operator L = d/dt, i.e., L P_n(..;t) = n * P_(n-1)(..;t), and raising operator R = t + d[log(1 + b1 D + b2 D^2 + ...)]/dD = t - Sum_{n>=1} F(n,b1,..,bn) D^(n-1), i.e., R P_n(..,;t) = P_(n+1)(..;t), where D = d/dt and F(n,b1,..,bn) are the Faber polynomials of A263916.
Also P_n(b1,..,bn;t) = CIP_n(t-F(1,b1),-F(2,b1,b2),..,-F(n,b1,..,bn)), the cycle index polynomials A036039.
(End)
The raising operator R = x + 1/(1-D) = x + 1 + D + D^2 + ... in matrix form acting on an o.g.f. (formal power series) is the transpose of the production matrix M below. The linear term x is the diagonal of ones after transposition. The other transposed diagonals come from D^m x^n = n! / (n-m)! x^(n-m). Then P(n,x) = (1,x,x^2,..) M^n (1,0,0,..)^T is a matrix representation of R P(n-1,x) = P(n,x). - Tom Copeland, Aug 17 2016
The row polynomials have e.g.f. e^(xt)/(1-t) = exp(t*q.(x)), umbrally. With p_n(x) the row polynomials of A132013, q_n(x) = v_n(p.(u.(x))), umbrally, where u_n(x) = (-1)^n v_n(-x) = (-1)^n Lah_n(x), the Lah polynomials with e.g.f. exp[x*t/(t-1)]. This has the matrix form [T] = [q] = [v]*[p]*[u]. Conversely, p_n(x) = u_n (q.(v.(x))). - Tom Copeland, Nov 10 2016
From the Appell sequence formalism, 1/(1-b.D) t^n = P_n(b1,b2,..,bn;t), the generalized row polynomials noted in the Nov 18 2015 formulas, consistent with the 2007 comments. - Tom Copeland, Nov 22 2016
From Peter Bala, Feb 18 2017: (Start)
G.f.: Sum_{n >= 1} (n*x)^(n-1)/(1 + (n - t)*x)^n = 1 + (1 + t)*x + (2 + 2*t + t^2)*x^2 + ....
n-th row polynomial R(n,t) = Sum_{k = 0..n} (-1)^(n-k)*binomial(n,k)*(x + k)^k*(x + k - t)^(n-k) = Sum_{k = 0..n} (-1)^(n-k)*binomial(n,k)*(x + k)^(n-k)*(x + k + t)^k, for arbitrary x. The particular case of the latter sum when x = 0 and t = 1 is identity 10.35 in Gould, Vol.4. (End)
Rodrigues-type formula for the row polynomials: R(n, x) = -exp(x)*Int(exp(-x)* x^n, x), for n >= 0. Recurrence: R(n, x) = x^n + n*R(n-1, x), for n >= 1, and R(0, x) = 1. d/dx(R(n, x)) = R(n, x) - x^n, for n >= 0 (compare with the formula from Peter Bala, Aug 28 2013). - Wolfdieter Lang, Dec 23 2019
T(n, k) = Sum_{i=0..n-k} A048994(n-k, i) * n^i for 0 <= k <= n. - Werner Schulte, Jul 26 2022

Extensions

Edited by Johannes W. Meijer, Oct 07 2009
New description from Dennis P. Walsh, Jan 24 2011

A001705 Generalized Stirling numbers: a(n) = n! * Sum_{k=0..n-1} (k+1)/(n-k).

Original entry on oeis.org

0, 1, 5, 26, 154, 1044, 8028, 69264, 663696, 6999840, 80627040, 1007441280, 13575738240, 196287356160, 3031488633600, 49811492505600, 867718162483200, 15974614352793600, 309920046408806400, 6320046028584960000, 135153868608460800000, 3024476051557847040000
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

a(n) is also the sum of the positions of the right-to-left minima in all permutations of [n]. Example: a(3)=26 because the positions of the right-to-left minima in the permutations 123,132,213,231,312 and 321 are 123, 13, 23, 3, 23 and 3, respectively and 1 + 2 + 3 + 1 + 3 + 2 + 3 + 3 + 2 + 3 + 3 = 26. - Emeric Deutsch, Sep 22 2008
The asymptotic expansion of the higher order exponential integral E(x,m=2,n=2) ~ exp(-x)/x^2*(1 - 5/x + 26/x^2 - 154/x^3 + 1044/x^4 - 8028/x^5 + 69264/x^6 - ...) leads to the sequence given above. See A163931 and A028421 for more information. - Johannes W. Meijer, Oct 20 2009
a(n) is the total number of cycles (excluding fixed points) in all permutations of [n+1]. - Olivier Gérard, Oct 23 2012; Dec 31 2012
A length n sequence is formed by randomly selecting (one-by-one) n real numbers in (0,1). a(n)/(n+1)! is the expected value of the sum of the new maximums in such a sequence. For example for n=3: If we select (in this order): 0.591996, 0.646474, 0.163659 we would add 0.591996 + 0.646474 which would be a bit above the average of a(3)/4! = 26/24. - Geoffrey Critzer, Oct 17 2013

Examples

			(1-x)^-2 * (-log(1-x)) = x + 5/2*x^2 + 13/3*x^3 + 77/12*x^4 + ...
Examples: a(6) = 6!*(1/6 + 2/5 + 3/4 + 4/3 + 5/2 + 6/1) = 8028; a(20) = 20!*(1/20 + 2/19 + 3/18 + 4/17 + 5/16 + ... + 16/5 + 17/4 + 18/3 + 19/2 + 20/1) = 135153868608460800000. - _Alexander Adamchuk_, Oct 09 2004
From _Olivier Gérard_, Dec 31 2012: (Start)
The cycle decomposition of all permutations of 4 elements gives the following list: {{{1},{2},{3},{4}}, {{1},{2},{3,4}}, {{1},{2,3},{4}}, {{1},{2,4,3}}, {{1},{2,3,4}}, {{1},{2,4},{3}}, {{1,2},{3},{4}}, {{1,2},{3,4}}, {{1,3,2},{4}},{{1,4,3,2}}, {{1,3,4,2}}, {{1,4,2},{3}}, {{1,2,3},{4}}, {{1,2,4,3}},{{1,3},{2},{4}}, {{1,4,3},{2}}, {{1,3},{2,4}}, {{1,4,2,3}}, {{1,2,3,4}}, {{1,2,4},{3}}, {{1,3,4},{2}}, {{1,4},{2},{3}}, {{1,3,2,4}}, {{1,4},{2,3}}}.
Deleting the fixed points gives the following 26 items: {{3,4}, {2,3}, {2,4,3}, {2,3,4}, {2,4}, {1,2}, {1,2}, {3,4}, {1,3,2}, {1,4,3,2}, {1,3,4,2}, {1,4,2}, {1,2,3}, {1,2,4,3}, {1,3}, {1,4,3}, {1,3}, {2,4}, {1,4,2,3}, {1,2,3,4}, {1,2,4}, {1,3,4}, {1,4}, {1,3,2,4}, {1,4}, {2,3}}. (End)

References

  • 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. A000254 (total number of cycles in permutations, including fixed points).
Cf. A002104 (number of different cycles in permutations, without fixed points).
Cf. A006231 (number of different cycles in permutations, including fixed points).
Cf. A001008, A002805, A006675, A066667, A132159, A143947.
Related to n!*the k-th successive summation of the harmonic numbers:
(k=0) A000254, (k=1) A001705, (k=2) A001711, (k=3) A001716,
(k=4) A001721, (k=5) A051524, (k=6) A051545, (k=7) A051560,
(k=8) A051562, (k=9) A051564.

Programs

  • Maple
    a := n-> add((n+1)!/k, k=2..n+1): seq(a(n), n=0..21); # Zerinvary Lajos, Jan 22 2008; edited Johannes W. Meijer, Nov 28 2012
a := n -> ((n+1)!*(h(n+1)-1)): h := n-> harmonic(n): seq(a(n), n=0..21); # Gary Detlefs, Dec 18 2009; corrected by Johannes W. Meijer, Nov 28 2012
  • Mathematica
    Table[n!*Sum[Sum[1/k,{k,1,m}], {m,1,n}], {n,0,20}] (* Alexander Adamchuk, Apr 14 2006 *)
a[n_] := (n + 1)! (EulerGamma - 1 + PolyGamma[n + 2]);
Table[a[n], {n, 0, 21}] (* Peter Luschny, Feb 19 2022 *)
  • Maxima
    a(n):=n!*sum(((-1)^(k+1)*binomial(n+1,k+1))/k,k,1,n); /* Vladimir Kruchinin, Oct 10 2016 */
  • PARI
    for(n=0,25, print1(n!*sum(k=0,n-1,(k+1)/(n-k)), ", ")) \\ G. C. Greubel, Jan 20 2017
  • Python
    from math import factorial
def A001705(n):
    f = factorial(n)
    return sum(f*(k+1)//(n-k) for k in range(n)) # Chai Wah Wu, Jun 23 2022

Formula

Partial sum of first n harmonic numbers multiplied by n!.
a(n) = n!*Sum_{m=1..n} Sum_{k=1..m} 1/k = n!*Sum_{m=1..n} H(m), where H(m) = Sum_{k=1..m} 1/k = A001008(m)/A002805(m) is m-th Harmonic number.
E.g.f.: - log (1 - x) / (1 - x)^2.
a(n) = (n+1)! * H(n) - n*n!, H(n) = Sum_{k=1..n} (1/k).
a(n) = A112486(n, 1).
a(n) = a(n-1)*(n+1) + n! = A000254(n+1) - A000142(n+1) = A067176(n+1, 1). - Henry Bottomley, Jan 09 2002
a(n) = Sum_{k=0..n-1} ((-1)^(n-1+k) * (k+1) * 2^k * Stirling1(n, k+1)). - Borislav Crstici (bcrstici(AT)etv.utt.ro), Jan 26 2004
With alternating signs: Ramanujan polynomials psi_2(n, x) evaluated at 0. - Ralf Stephan, Apr 16 2004
a(n) = Sum_{k=1..n} (k*StirlingCycle(n+1,k+1)). - David Callan, Sep 25 2006
a(n) = Sum_{k=n..n*(n+1)/2} k*A143947(n,k). - Emeric Deutsch, Sep 22 2008
For n >= 1, a(n) = Sum_{j=0..n-1} ((-1)^(n-j-1) * 2^j * (j+1) * Stirling1(n,j+1)). - Milan Janjic, Dec 14 2008
a(n) = (2*n+1)*a(n-1) - n^2*a(n-2). - Gary Detlefs, Nov 27 2009
a(n) = (n+1)!*(H(n+1) - 1) where H(n) is the n-th harmonic number. - Gary Detlefs, Dec 18 2009
a(n) = n!*Sum_{k=1..n} (-1)^(k+1)*binomial(n+1,k+1)/k. - Vladimir Kruchinin, Oct 10 2016
a(n) = (n+1)!*Sum_{k = 1..n} (-1)^(k+1)*binomial(n+1,k+1)*k/(k+1). - Peter Bala, Feb 15 2022
a(n) = Gamma(n + 2) * (Digamma(n + 2) + EulerGamma - 1). - Peter Luschny, Feb 19 2022
From Mélika Tebni, Jun 22 2022: (Start)
a(n) = -Sum_{k=0..n} k!*A066667(n, k+1).
a(n) = Sum_{k=0..n} k!*A132159(n, k+1). (End)
a(n) = n*(n + 1)!*hypergeom([1, 1, 1 - n], [2, 3], 1)/2. - Peter Luschny, Jun 22 2022

Extensions

More terms from Sascha Kurz, Mar 22 2002
Showing 1-10 of 74 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.