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

A000110 Bell or exponential numbers: number of ways to partition a set of n labeled elements.

Original entry on oeis.org

1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, 190899322, 1382958545, 10480142147, 82864869804, 682076806159, 5832742205057, 51724158235372, 474869816156751, 4506715738447323, 44152005855084346, 445958869294805289, 4638590332229999353, 49631246523618756274
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

The leading diagonal of its difference table is the sequence shifted, see Bernstein and Sloane (1995). - N. J. A. Sloane, Jul 04 2015
Also the number of equivalence relations that can be defined on a set of n elements. - Federico Arboleda (federico.arboleda(AT)gmail.com), Mar 09 2005
a(n) = number of nonisomorphic colorings of a map consisting of a row of n+1 adjacent regions. Adjacent regions cannot have the same color. - David W. Wilson, Feb 22 2005
If an integer is squarefree and has n distinct prime factors then a(n) is the number of ways of writing it as a product of its divisors. - Amarnath Murthy, Apr 23 2001
Consider rooted trees of height at most 2. Letting each tree 'grow' into the next generation of n means we produce a new tree for every node which is either the root or at height 1, which gives the Bell numbers. - Jon Perry, Jul 23 2003
Begin with [1,1] and follow the rule that [1,k] -> [1,k+1] and [1,k] k times, e.g., [1,3] is transformed to [1,4], [1,3], [1,3], [1,3]. Then a(n) is the sum of all components: [1,1] = 2; [1,2], [1,1] = 5; [1,3], [1,2], [1,2], [1,2], [1,1] = 15; etc. - Jon Perry, Mar 05 2004
Number of distinct rhyme schemes for a poem of n lines: a rhyme scheme is a string of letters (e.g., 'abba') such that the leftmost letter is always 'a' and no letter may be greater than one more than the greatest letter to its left. Thus 'aac' is not valid since 'c' is more than one greater than 'a'. For example, a(3)=5 because there are 5 rhyme schemes: aaa, aab, aba, abb, abc; also see example by Neven Juric. - Bill Blewett, Mar 23 2004
In other words, number of length-n restricted growth strings (RGS) [s(0),s(1),...,s(n-1)] where s(0)=0 and s(k) <= 1 + max(prefix) for k >= 1, see example (cf. A080337 and A189845). - Joerg Arndt, Apr 30 2011
Number of partitions of {1, ..., n+1} into subsets of nonconsecutive integers, including the partition 1|2|...|n+1. E.g., a(3)=5: there are 5 partitions of {1,2,3,4} into subsets of nonconsecutive integers, namely, 13|24, 13|2|4, 14|2|3, 1|24|3, 1|2|3|4. - Augustine O. Munagi, Mar 20 2005
Triangle (addition) scheme to produce terms, derived from the recurrence, from Oscar Arevalo (loarevalo(AT)sbcglobal.net), May 11 2005:
1
1 2
2 3 5
5 7 10 15
15 20 27 37 52
... [This is Aitken's array A011971]
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)!)) * (1/(Product_{j=1..d(i)} m(i,j)!)). - Thomas Wieder, May 18 2005
a(n+1) is the number of binary relations on an n-element set that are both symmetric and transitive. - Justin Witt (justinmwitt(AT)gmail.com), Jul 12 2005
If the rule from Jon Perry, Mar 05 2004, is used, then a(n-1) = [number of components used to form a(n)] / 2. - Daniel Kuan (dkcm(AT)yahoo.com), Feb 19 2006
a(n) is the number of functions f from {1,...,n} to {1,...,n,n+1} that satisfy the following two conditions for all x in the domain: (1) f(x) > x; (2) f(x)=n+1 or f(f(x))=n+1. E.g., a(3)=5 because there are exactly five functions that satisfy the two conditions: f1={(1,4),(2,4),(3,4)}, f2={(1,4),(2,3),(3,4)}, f3={(1,3),(2,4),(3,4)}, f4={(1,2),(2,4),(3,4)} and f5={(1,3),(2,3),(3,4)}. - Dennis P. Walsh, Feb 20 2006
Number of asynchronic siteswap patterns of length n which have no zero-throws (i.e., contain no 0's) and whose number of orbits (in the sense given by Allen Knutson) is equal to the number of balls. E.g., for n=4, the condition is satisfied by the following 15 siteswaps: 4444, 4413, 4242, 4134, 4112, 3441, 2424, 1344, 2411, 1313, 1241, 2222, 3131, 1124, 1111. Also number of ways to choose n permutations from identity and cyclic permutations (1 2), (1 2 3), ..., (1 2 3 ... n) so that their composition is identity. For n=3 we get the following five: id o id o id, id o (1 2) o (1 2), (1 2) o id o (1 2), (1 2) o (1 2) o id, (1 2 3) o (1 2 3) o (1 2 3). (To see the bijection, look at Ehrenborg and Readdy paper.) - Antti Karttunen, May 01 2006
a(n) is the number of permutations on [n] in which a 3-2-1 (scattered) pattern occurs only as part of a 3-2-4-1 pattern. Example: a(3) = 5 counts all permutations on [3] except 321. See "Eigensequence for Composition" reference a(n) = number of permutation tableaux of size n (A000142) whose first row contains no 0's. Example: a(3)=5 counts {{}, {}, {}}, {{1}, {}}, {{1}, {0}}, {{1}, {1}}, {{1, 1}}. - David Callan, Oct 07 2006
From Gottfried Helms, Mar 30 2007: (Start)
This sequence is also the first column in the matrix-exponential of the (lower triangular) Pascal-matrix, scaled by exp(-1): PE = exp(P) / exp(1) =
1
1 1
2 2 1
5 6 3 1
15 20 12 4 1
52 75 50 20 5 1
203 312 225 100 30 6 1
877 1421 1092 525 175 42 7 1
First 4 columns are A000110, A033306, A105479, A105480. The general case is mentioned in the two latter entries. PE is also the Hadamard-product Toeplitz(A000110) (X) P:
1
1 1
2 1 1
5 2 1 1
15 5 2 1 1 (X) P
52 15 5 2 1 1
203 52 15 5 2 1 1
877 203 52 15 5 2 1 1
(End)
The terms can also be computed with finite steps and precise integer arithmetic. Instead of exp(P)/exp(1) one can compute A = exp(P - I) where I is the identity-matrix of appropriate dimension since (P-I) is nilpotent to the order of its dimension. Then a(n)=A[n,1] where n is the row-index starting at 1. - Gottfried Helms, Apr 10 2007
When n is prime, a(n) == 2 (mod n), but the converse is not always true. Define a Bell pseudoprime to be a composite number n such that a(n) == 2 (mod n). W. F. Lunnon recently found the Bell pseudoprimes 21361 = 41*521 and C46 = 3*23*16218646893090134590535390526854205539989357 and conjectured that Bell pseudoprimes are extremely scarce. So the second Bell pseudoprime is unlikely to be known with certainty in the near future. I confirmed that 21361 is the first. - David W. Wilson, Aug 04 2007 and Sep 24 2007
This sequence and A000587 form a reciprocal pair under the list partition transform described in A133314. - Tom Copeland, Oct 21 2007
Starting (1, 2, 5, 15, 52, ...), equals row sums and right border of triangle A136789. Also row sums of triangle A136790. - Gary W. Adamson, Jan 21 2008
This is the exponential transform of A000012. - Thomas Wieder, Sep 09 2008
From Abdullahi Umar, Oct 12 2008: (Start)
a(n) is also the number of idempotent order-decreasing full transformations (of an n-chain).
a(n) is also the number of nilpotent partial one-one order-decreasing transformations (of an n-chain).
a(n+1) is also the number of partial one-one order-decreasing transformations (of an n-chain). (End)
From Peter Bala, Oct 19 2008: (Start)
Bell(n) is the number of n-pattern sequences [Cooper & Kennedy]. An n-pattern sequence is a sequence of integers (a_1,...,a_n) such that a_i = i or a_i = a_j for some j < i. For example, Bell(3) = 5 since the 3-pattern sequences are (1,1,1), (1,1,3), (1,2,1), (1,2,2) and (1,2,3).
Bell(n) is the number of sequences of positive integers (N_1,...,N_n) of length n such that N_1 = 1 and N_(i+1) <= 1 + max{j = 1..i} N_j for i >= 1 (see the comment by B. Blewett above). It is interesting to note that if we strengthen the latter condition to N_(i+1) <= 1 + N_i we get the Catalan numbers A000108 instead of the Bell numbers.
(End)
Equals the eigensequence of Pascal's triangle, A007318; and starting with offset 1, = row sums of triangles A074664 and A152431. - Gary W. Adamson, Dec 04 2008
The entries f(i, j) in the exponential of the infinite lower-triangular matrix of binomial coefficients b(i, j) are f(i, j) = b(i, j) e a(i - j). - David Pasino, Dec 04 2008
Equals lim_{k->oo} A071919^k. - Gary W. Adamson, Jan 02 2009
Equals A154107 convolved with A014182, where A014182 = expansion of exp(1-x-exp(-x)), the eigensequence of A007318^(-1). Starting with offset 1 = A154108 convolved with (1,2,3,...) = row sums of triangle A154109. - Gary W. Adamson, Jan 04 2009
Repeated iterates of (binomial transform of [1,0,0,0,...]) will converge upon (1, 2, 5, 15, 52, ...) when each result is prefaced with a "1"; such that the final result is the fixed limit: (binomial transform of [1,1,2,5,15,...]) = (1,2,5,15,52,...). - Gary W. Adamson, Jan 14 2009
From Karol A. Penson, May 03 2009: (Start)
Relation between the Bell numbers B(n) and the n-th derivative of 1/Gamma(1+x) evaluated at x=1:
a) produce a number of such derivatives through seq(subs(x=1, simplify((d^n/dx^n)GAMMA(1+x)^(-1))), n=1..5);
b) leave them expressed in terms of digamma (Psi(k)) and polygamma (Psi(k,n)) functions and unevaluated;
Examples of such expressions, for n=1..5, are:
n=1: -Psi(1),
n=2: -(-Psi(1)^2 + Psi(1,1)),
n=3: -Psi(1)^3 + 3*Psi(1)*Psi(1,1) - Psi(2,1),
n=4: -(-Psi(1)^4 + 6*Psi(1)^2*Psi(1,1) - 3*Psi(1,1)^2 - 4*Psi(1)*Psi(2,1) + Psi(3, 1)),
n=5: -Psi(1)^5 + 10*Psi(1)^3*Psi(1,1) - 15*Psi(1)*Psi(1,1)^2 - 10*Psi(1)^2*Psi(2,1) + 10*Psi(1,1)*Psi(2,1) + 5*Psi(1)*Psi(3,1) - Psi(4,1);
c) for a given n, read off the sum of absolute values of coefficients of every term involving digamma or polygamma functions.
This sum is equal to B(n). Examples: B(1)=1, B(2)=1+1=2, B(3)=1+3+1=5, B(4)=1+6+3+4+1=15, B(5)=1+10+15+10+10+5+1=52;
d) Observe that this decomposition of the Bell number B(n) apparently does not involve the Stirling numbers of the second kind explicitly.
(End)
The numbers given above by Penson lead to the multinomial coefficients A036040. - Johannes W. Meijer, Aug 14 2009
Column 1 of A162663. - Franklin T. Adams-Watters, Jul 09 2009
Asymptotic expansions (0!+1!+2!+...+(n-1)!)/(n-1)! = a(0) + a(1)/n + a(2)/n^2 + ... and (0!+1!+2!+...+n!)/n! = 1 + a(0)/n + a(1)/n^2 + a(2)/n^3 + .... - Michael Somos, Jun 28 2009
Starting with offset 1 = row sums of triangle A165194. - Gary W. Adamson, Sep 06 2009
a(n+1) = A165196(2^n); where A165196 begins: (1, 2, 4, 5, 7, 12, 14, 15, ...). such that A165196(2^3) = 15 = A000110(4). - Gary W. Adamson, Sep 06 2009
The divergent series g(x=1,m) = 1^m*1! - 2^m*2! + 3^m*3! - 4^m*4! + ..., m >= -1, which for m=-1 dates back to Euler, is related to the Bell numbers. We discovered that g(x=1,m) = (-1)^m * (A040027(m) - A000110(m+1) * A073003). We observe that A073003 is Gompertz's constant and that A040027 was published by Gould, see for more information A163940. - Johannes W. Meijer, Oct 16 2009
a(n) = E(X^n), i.e., the n-th moment about the origin of a random variable X that has a Poisson distribution with (rate) parameter, lambda = 1. - Geoffrey Critzer, Nov 30 2009
Let A000110 = S(x), then S(x) = A(x)/A(x^2) when A(x) = A173110; or (1, 1, 2, 5, 15, 52, ...) = (1, 1, 3, 6, 20, 60, ...) / (1, 0, 1, 0, 3, 0, 6, 0, 20, ...). - Gary W. Adamson, Feb 09 2010
The Bell numbers serve as the upper limit for the number of distinct homomorphic images from any given finite universal algebra. Every algebra homomorphism is determined by its kernel, which must be a congruence relation. As the number of possible congruence relations with respect to a finite universal algebra must be a subset of its possible equivalence classes (given by the Bell numbers), it follows naturally. - Max Sills, Jun 01 2010
For a proof of the o.g.f. given in the R. Stephan comment see, e.g., the W. Lang link under A071919. - Wolfdieter Lang, Jun 23 2010
Let B(x) = (1 + x + 2x^2 + 5x^3 + ...). Then B(x) is satisfied by A(x)/A(x^2) where A(x) = polcoeff A173110: (1 + x + 3x^2 + 6x^3 + 20x^4 + 60x^5 + ...) = B(x) * B(x^2) * B(x^4) * B(x^8) * .... - Gary W. Adamson, Jul 08 2010
Consider a set of A000217(n) balls of n colors in which, for each integer k = 1 to n, exactly one color appears in the set a total of k times. (Each ball has exactly one color and is indistinguishable from other balls of the same color.) a(n+1) equals the number of ways to choose 0 or more balls of each color without choosing any two colors the same positive number of times. (See related comments for A000108, A008277, A016098.) - Matthew Vandermast, Nov 22 2010
A binary counter with faulty bits starts at value 0 and attempts to increment by 1 at each step. Each bit that should toggle may or may not do so. a(n) is the number of ways that the counter can have the value 0 after n steps. E.g., for n=3, the 5 trajectories are 0,0,0,0; 0,1,0,0; 0,1,1,0; 0,0,1,0; 0,1,3,0. - David Scambler, Jan 24 2011
No Bell number is divisible by 8, and no Bell number is congruent to 6 modulo 8; see Theorem 6.4 and Table 1.7 in Lunnon, Pleasants and Stephens. - Jon Perry, Feb 07 2011, clarified by Eric Rowland, Mar 26 2014
a(n+1) is the number of (symmetric) positive semidefinite n X n 0-1 matrices. These correspond to equivalence relations on {1,...,n+1}, where matrix element M[i,j] = 1 if and only if i and j are equivalent to each other but not to n+1. - Robert Israel, Mar 16 2011
a(n) is the number of monotonic-labeled forests on n vertices with rooted trees of height less than 2. We note that a labeled rooted tree is monotonic-labeled if the label of any parent vertex is greater than the label of any offspring vertex. See link "Counting forests with Stirling and Bell numbers". - Dennis P. Walsh, Nov 11 2011
a(n) = D^n(exp(x)) evaluated at x = 0, where D is the operator (1+x)*d/dx. Cf. A000772 and A094198. - Peter Bala, Nov 25 2011
B(n) counts the length n+1 rhyme schemes without repetitions. E.g., for n=2 there are 5 rhyme schemes of length 3 (aaa, aab, aba, abb, abc), and the 2 without repetitions are aba, abc. This is basically O. Munagi's result that the Bell numbers count partitions into subsets of nonconsecutive integers (see comment above dated Mar 20 2005). - Eric Bach, Jan 13 2012
Right and left borders and row sums of A212431 = A000110 or a shifted variant. - Gary W. Adamson, Jun 21 2012
Number of maps f: [n] -> [n] where f(x) <= x and f(f(x)) = f(x) (projections). - Joerg Arndt, Jan 04 2013
Permutations of [n] avoiding any given one of the 8 dashed patterns in the equivalence classes (i) 1-23, 3-21, 12-3, 32-1, and (ii) 1-32, 3-12, 21-3, 23-1. (See Claesson 2001 reference.) - David Callan, Oct 03 2013
Conjecture: No a(n) has the form x^m with m > 1 and x > 1. - Zhi-Wei Sun, Dec 02 2013
Sum_{n>=0} a(n)/n! = e^(e-1) = 5.57494152476..., see A234473. - Richard R. Forberg, Dec 26 2013 (This is the e.g.f. for x=1. - Wolfdieter Lang, Feb 02 2015)
Sum_{j=0..n} binomial(n,j)*a(j) = (1/e)*Sum_{k>=0} (k+1)^n/k! = (1/e) Sum_{k=1..oo} k^(n+1)/k! = a(n+1), n >= 0, using the Dobinski formula. See the comment by Gary W. Adamson, Dec 04 2008 on the Pascal eigensequence. - Wolfdieter Lang, Feb 02 2015
In fact it is not really an eigensequence of the Pascal matrix; rather the Pascal matrix acts on the sequence as a shift. It is an eigensequence (the unique eigensequence with eigenvalue 1) of the matrix derived from the Pascal matrix by adding at the top the row [1, 0, 0, 0 ...]. The binomial sum formula may be derived from the definition in terms of partitions: label any element X of a set S of N elements, and let X(k) be the number of subsets of S containing X with k elements. Since each subset has a unique coset, the number of partitions p(N) of S is given by p(N) = Sum_{k=1..N} (X(k) p(N-k)); trivially X(k) = N-1 choose k-1. - Mason Bogue, Mar 20 2015
a(n) is the number of ways to nest n matryoshkas (Russian nesting dolls): we may identify {1, 2, ..., n} with dolls of ascending sizes and the sets of a set partition with stacks of dolls. - Carlo Sanna, Oct 17 2015
Number of permutations of [n] where the initial elements of consecutive runs of increasing elements are in decreasing order. a(4) = 15: `1234, `2`134, `23`14, `234`1, `24`13, `3`124, `3`2`14, `3`24`1, `34`12, `34`2`1, `4`123, `4`2`13, `4`23`1, `4`3`12, `4`3`2`1. - Alois P. Heinz, Apr 27 2016
Taking with alternating signs, the Bell numbers are the coefficients in the asymptotic expansion (Ramanujan): (-1)^n*(A000166(n) - n!/exp(1)) ~ 1/n - 2/n^2 + 5/n^3 - 15/n^4 + 52/n^5 - 203/n^6 + O(1/n^7). - Vladimir Reshetnikov, Nov 10 2016
Number of treeshelves avoiding pattern T231. See A278677 for definitions and examples. - Sergey Kirgizov, Dec 24 2016
Presumably this satisfies Benford's law, although the results in Hürlimann (2009) do not make this clear. - N. J. A. Sloane, Feb 09 2017
a(n) = Sum(# of standard immaculate tableaux of shape m, m is a composition of n), where this sum is over all integer compositions m of n > 0. This formula is easily seen to hold by identifying standard immaculate tableaux of size n with set partitions of { 1, 2, ..., n }. For example, if we sum over integer compositions of 4 lexicographically, we see that 1+1+2+1+3+3+3+1 = 15 = A000110(4). - John M. Campbell, Jul 17 2017
a(n) is also the number of independent vertex sets (and vertex covers) in the (n-1)-triangular honeycomb bishop graph. - Eric W. Weisstein, Aug 10 2017
Even-numbered entries represent the numbers of configurations of identity and non-identity for alleles of a gene in n diploid individuals with distinguishable maternal and paternal alleles. - Noah A Rosenberg, Jan 28 2019
Number of partial equivalence relations (PERs) on a set with n elements (offset=1), i.e., number of symmetric, transitive (not necessarily reflexive) relations. The idea is to add a dummy element D to the set, and then take equivalence relations on the result; anything equivalent to D is then removed for the partial equivalence relation. - David Spivak, Feb 06 2019
Number of words of length n+1 with no repeated letters, when letters are unlabeled. - Thomas Anton, Mar 14 2019
Named by Becker and Riordan (1948) after the Scottish-American mathematician and writer Eric Temple Bell (1883 - 1960). - Amiram Eldar, Dec 04 2020
Also the number of partitions of {1,2,...,n+1} with at most one n+1 singleton. E.g., a(3)=5: {13|24, 12|34, 123|4, 14|23, 1234}. - Yuchun Ji, Dec 21 2020
a(n) is the number of sigma algebras on the set of n elements. Note that each sigma algebra is generated by a partition of the set. For example, the sigma algebra generated by the partition {{1}, {2}, {3,4}} is {{}, {1}, {2}, {1,2}, {3,4}, {1,3,4}, {2,3,4}, {1,2,3,4}}. - Jianing Song, Apr 01 2021
a(n) is the number of P_3-free graphs on n labeled nodes. - M. Eren Kesim, Jun 04 2021
a(n) is the number of functions X:([n] choose 2) -> {+,-} such that for any ordered 3-tuple abc we have X(ab)X(ac)X(bc) not in {+-+,++-,-++}. - Robert Lauff, Dec 09 2022
From Manfred Boergens, Mar 11 2025: (Start)
The partitions in the definition can be described as disjoint covers of the set. "Covers" in general give rise to the following amendments:
For disjoint covers which may include one empty set see A186021.
For arbitrary (including non-disjoint) covers see A003465.
For arbitrary (including non-disjoint) covers which may include one empty set see A000371. (End)

Examples

			G.f. = 1 + x + 2*x^2 + 5*x^3 + 15*x^4 + 52*x^5 + 203*x^6 + 877*x^7 + 4140*x^8 + ...
From Neven Juric, Oct 19 2009: (Start)
The a(4)=15 rhyme schemes for n=4 are
  aaaa, aaab, aaba, aabb, aabc, abaa, abab, abac, abba, abbb, abbc, abca, abcb, abcc, abcd
The a(5)=52 rhyme schemes for n=5 are
  aaaaa, aaaab, aaaba, aaabb, aaabc, aabaa, aabab, aabac, aabba, aabbb, aabbc, aabca, aabcb, aabcc, aabcd, abaaa, abaab, abaac, ababa, ababb, ababc, abaca, abacb, abacc, abacd, abbaa, abbab, abbac, abbba, abbbb, abbbc, abbca, abbcb, abbcc, abbcd, abcaa, abcab, abcac, abcad, abcba, abcbb, abcbc, abcbd, abcca, abccb, abccc, abccd, abcda, abcdb, abcdc, abcdd, abcde
(End)
From _Joerg Arndt_, Apr 30 2011: (Start)
Restricted growth strings (RGS):
For n=0 there is one empty string;
for n=1 there is one string [0];
for n=2 there are 2 strings [00], [01];
for n=3 there are a(3)=5 strings [000], [001], [010], [011], and [012];
for n=4 there are a(4)=15 strings
1: [0000], 2: [0001], 3: [0010], 4: [0011], 5: [0012], 6: [0100], 7: [0101], 8: [0102], 9: [0110], 10: [0111], 11: [0112], 12: [0120], 13: [0121], 14: [0122], 15: [0123].
These are one-to-one with the rhyme schemes (identify a=0, b=1, c=2, etc.).
(End)
Consider the set S = {1, 2, 3, 4}. The a(4) = 1 + 3 + 6 + 4 + 1 = 15 partitions are: P1 = {{1}, {2}, {3}, {4}}; P21 .. P23 = {{a,4}, S\{a,4}} with a = 1, 2, 3; P24 .. P29 = {{a}, {b}, S\{a,b}} with 1 <= a < b <= 4;  P31 .. P34 = {S\{a}, {a}} with a = 1 .. 4; P4 = {S}. See the Bottomley link for a graphical illustration. - _M. F. Hasler_, Oct 26 2017

References

  • Stefano Aguzzoli, Brunella Gerla and Corrado Manara, Poset Representation for Goedel and Nilpotent Minimum Logics, in Symbolic and Quantitative Approaches to Reasoning with Uncertainty, Lecture Notes in Computer Science, Volume 3571/2005, Springer-Verlag. [Added by N. J. A. Sloane, Jul 08 2009]
  • S. Ainley, Problem 19, QARCH, No. IV, Nov 03, 1980.
  • J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 205.
  • W. Asakly, A. Blecher, C. Brennan, A. Knopfmacher, T. Mansour, S. Wagner, Set partition asymptotics and a conjecture of Gould and Quaintance, Journal of Mathematical Analysis and Applications, Volume 416, Issue 2, Aug 15 2014, Pages 672-682.
  • J. Balogh, B. Bollobas and D. Weinreich, A jump to the Bell numbers for hereditary graph properties, J. Combin. Theory Ser. B 95 (2005), no. 1, 29-48.
  • R. E. Beard, On the coefficients in the expansion of exp(exp(t)) and exp(-exp(t)), J. Institute Actuaries, 76 (1951), 152-163.
  • H. W. Becker, Abstracts of two papers related to Bell numbers, Bull. Amer. Math. Soc., 52 (1946), p. 415.
  • E. T. Bell, The iterated exponential numbers, Ann. Math., 39 (1938), 539-557.
  • C. M. Bender, D. C. Brody and B. K. Meister, Quantum Field Theory of Partitions, J. Math. Phys., 40,7 (1999), 3239-45.
  • E. A. Bender and J. R. Goldman, Enumerative uses of generating functions, Indiana Univ. Math. J., 20 (1971), 753-765.
  • G. Birkhoff, Lattice Theory, Amer. Math. Soc., Revised Ed., 1961, p. 108, Ex. 1.
  • M. T. L. Bizley, On the coefficients in the expansion of exp(lambda exp(t)), J. Inst. Actuaries, 77 (1952), p. 122.
  • J. M. Borwein, D. H. Bailey and R. Girgensohn, Experimentation in Mathematics, A K Peters, Ltd., Natick, MA, 2004. x+357 pp. See p. 41.
  • Carlier, Jacques; and Lucet, Corinne; A decomposition algorithm for network reliability evaluation. In First International Colloquium on Graphs and Optimization (GOI), 1992 (Grimentz). Discrete Appl. Math. 65 (1996), 141-156.
  • Anders Claesson, Generalized Pattern Avoidance, European Journal of Combinatorics, 22 (2001) 961-971.
  • L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 210.
  • John H. Conway and Richard K. Guy, The Book of Numbers, New York: Springer-Verlag, 1996. See pp. 92-93.
  • John H. Conway et al., The Symmetries of Things, Peters, 2008, p. 207.
  • Colin Defant, Highly sorted permutations and Bell numbers, ECA 1:1 (2021) Article S2R6.
  • De Angelis, Valerio, and Dominic Marcello. "Wilf's Conjecture." The American Mathematical Monthly 123.6 (2016): 557-573.
  • N. G. de Bruijn, Asymptotic Methods in Analysis, Dover, 1981, Sections 3.3. Case b and 6.1-6.3.
  • J.-M. De Koninck, Ces nombres qui nous fascinent, Entry 52, p. 19, Ellipses, Paris 2008.
  • G. Dobinski, Summierung der Reihe Sum(n^m/n!) für m = 1, 2, 3, 4, 5, ..., Grunert Archiv (Arch. f. Math. und Physik), 61 (1877) 333-336.
  • L. F. Epstein, A function related to the series for exp(exp(z)), J. Math. and Phys., 18 (1939), 153-173.
  • G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255.
  • Steven R. Finch, Mathematical Constants, Encyclopedia of Mathematics and its Applications, vol. 94, Cambridge University Press, 2003, Section 5.8, p. 321.
  • Flajolet, Philippe and Schott, Rene, Nonoverlapping partitions, continued fractions, Bessel functions and a divergent series, European J. Combin. 11 (1990), no. 5, 421-432.
  • Martin Gardner, Fractal Music, Hypercards and More (Freeman, 1992), Chapter 2.
  • H. W. Gould, Research bibliography of two special number sequences, Mathematica Monongaliae, Vol. 12, 1971.
  • R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, 2nd ed., p. 493.
  • Silvia Heubach and Toufik Mansour, Combinatorics of Compositions and Words, CRC Press, 2010.
  • M. Kauers and P. Paule, The Concrete Tetrahedron, Springer 2011, p. 26.
  • D. E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, Section 7.2.1.5 (p. 418).
  • Christian Kramp, Der polynomische Lehrsatz (Leipzig: 1796), 113.
  • Lehmer, D. H. Some recursive sequences. Proceedings of the Manitoba Conference on Numerical Mathematics (Univ. Manitoba, Winnipeg, Man., 1971), pp. 15--30. Dept. Comput. Sci., Univ. Manitoba, Winnipeg, Man., 1971. MR0335426 (49 #208)
  • J. Levine and R. E. Dalton, Minimum periods, modulo p, of first-order Bell exponential integers, Math. Comp., 16 (1962), 416-423.
  • Levinson, H.; Silverman, R. Topologies on finite sets. II. Proceedings of the Tenth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1979), pp. 699--712, Congress. Numer., XXIII-XXIV, Utilitas Math., Winnipeg, Man., 1979. MR0561090 (81c:54006)
  • S. Linusson, The number of M-sequences and f-vectors, Combinatorica, 19 (1999), 255-266.
  • L. Lovasz, Combinatorial Problems and Exercises, North-Holland, 1993, pp. 14-15.
  • M. Meier, On the number of partitions of a given set, Amer. Math. Monthly, 114 (2007), p. 450.
  • Merris, Russell, and Stephen Pierce. "The Bell numbers and r-fold transitivity." Journal of Combinatorial Theory, Series A 12.1 (1972): 155-157.
  • Moser, Leo, and Max Wyman. An asymptotic formula for the Bell numbers. Trans. Royal Soc. Canada, 49 (1955), 49-53.
  • A. Murthy, Generalization of partition function, introducing Smarandache factor partition, Smarandache Notions Journal, Vol. 11, No. 1-2-3, Spring 2000.
  • Amarnath Murthy and Charles Ashbacher, Generalized Partitions and Some New Ideas on Number Theory and Smarandache Sequences, Hexis, Phoenix; USA 2005. See Section 1.4,1.8.
  • P. Peart, Hankel determinants via Stieltjes matrices. Proceedings of the Thirty-first Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 2000). Congr. Numer. 144 (2000), 153-159.
  • A. M. Robert, A Course in p-adic Analysis, Springer-Verlag, 2000; p. 212.
  • G.-C. Rota, Finite Operator Calculus.
  • Frank Ruskey, Jennifer Woodcock and Yuji Yamauchi, Counting and computing the Rand and block distances of pairs of set partitions, Journal of Discrete Algorithms, Volume 16, October 2012, Pages 236-248.
  • 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).
  • R. P. Stanley, Enumerative Combinatorics, Cambridge; see Section 1.4 and Example 5.2.4.
  • Abdullahi Umar, On the semigroups of order-decreasing finite full transformations, Proc. Roy. Soc. Edinburgh 120A (1992), 129-142.
  • Abdullahi Umar, On the semigroups of partial one-to-one order-decreasing finite transformations, Proc. Roy. Soc. Edinburgh 123A (1993), 355-363.

Links

Crossrefs

Equals row sums of triangle A008277 (Stirling subset numbers).
Partial sums give A005001. a(n) = A123158(n, 0).
See A061462 for powers of 2 dividing a(n).
Rightmost diagonal of triangle A121207. A144293 gives largest prime factor.
Cf. A000045, A000108, A000166, A000204, A000255, A000311, A000296, A003422, A024716, A029761, A049020, A058692, A060719, A084423, A087650, A094262, A103293, A165194, A165196, A173110, A227840, A182386.
Equals row sums of triangle A152432.
Row sums, right and left borders of A212431.
A diagonal of A011971. - N. J. A. Sloane, Jul 31 2012
Diagonal of A102661. - Manfred Boergens, Mar 11 2025
Cf. A054767 (period of this sequence mod n).
Row sums are A048993. - Wolfdieter Lang, Oct 16 2014
Sequences in the Erné (1974) paper: A000110, A000798, A001035, A001927, A001929, A006056, A006057, A006058, A006059.
Bell polynomials B(n,x): A001861 (x=2), A027710 (x=3), A078944 (x=4), A144180 (x=5), A144223 (x=6), A144263 (x=7), A221159 (x=8).
Cf. A243991 (sum of reciprocals), A085686 (inv. Euler Transf.).
Cf. A000371, A003465, A186021.

Programs

  • Haskell
    type N = Integer
n_partitioned_k :: N -> N -> N
1 `n_partitioned_k` 1 = 1
1 `n_partitioned_k` _ = 0
n `n_partitioned_k` k = k * (pred n `n_partitioned_k` k) + (pred n `n_partitioned_k` pred k)
n_partitioned :: N -> N
n_partitioned 0 = 1
n_partitioned n = sum $ map (\k -> n `n_partitioned_k` k) $ [1 .. n]
-- Felix Denis, Oct 16 2012
  • Haskell
    a000110 = sum . a048993_row -- Reinhard Zumkeller, Jun 30 2013
  • Julia
    function a(n)
    t = [zeros(BigInt, n+1) for _ in 1:n+1]
    t[1][1] = 1
    for i in 2:n+1
        t[i][1] = t[i-1][i-1]
        for j in 2:i
            t[i][j] = t[i-1][j-1] + t[i][j-1]
        end
    end
    return [t[i][1] for i in 1:n+1]
end
print(a(28)) # Paul Muljadi, May 07 2024
  • Magma
    [Bell(n): n in [0..40]]; // Vincenzo Librandi, Feb 07 2011
  • Maple
    A000110 := proc(n) option remember; if n <= 1 then 1 else add( binomial(n-1,i)*A000110(n-1-i),i=0..n-1); fi; end: # version 1
A := series(exp(exp(x)-1),x,60): A000110 := n->n!*coeff(A,x,n): # version 2
A000110:= n-> add(Stirling2(n, k), k=0..n): seq(A000110(n), n=0..22); # version 3, from Zerinvary Lajos, Jun 28 2007
A000110 := n -> combinat[bell](n): # version 4, from Peter Luschny, Mar 30 2011
spec:= [S, {S=Set(U, card >= 1), U=Set(Z, card >= 1)}, labeled]: G:={P=Set(Set(Atom, card>0))}: combstruct[gfsolve](G, unlabeled, x): seq(combstruct[count]([P, G, labeled], size=i), i=0..22);  # version 5, Zerinvary Lajos, Dec 16 2007
BellList := proc(m) local A, P, n; A := [1, 1]; P := [1]; for n from 1 to m - 2 do
P := ListTools:-PartialSums([A[-1], op(P)]); A := [op(A), P[-1]] od; A end: BellList(29); # Peter Luschny, Mar 24 2022
  • Mathematica
    f[n_] := Sum[ StirlingS2[n, k], {k, 0, n}]; Table[ f[n], {n, 0, 40}] (* Robert G. Wilson v *)
Table[BellB[n], {n, 0, 40}] (* Harvey P. Dale, Mar 01 2011 *)
B[0] = 1; B[n_] := 1/E Sum[k^(n - 1)/(k-1)!, {k, 1, Infinity}] (* Dimitri Papadopoulos, Mar 10 2015, edited by M. F. Hasler, Nov 30 2018 *)
BellB[Range[0,40]] (* Eric W. Weisstein, Aug 10 2017 *)
b[1] = 1; k = 1; Flatten[{1, Table[Do[j = k; k += b[m]; b[m] = j;, {m, 1, n-1}]; b[n] = k, {n, 1, 40}]}] (* Vaclav Kotesovec, Sep 07 2019 *)
Table[j! Coefficient[Series[Exp[Exp[x] - 1], {x, 0, 20}], x, j], {j, 0, 20}] (* Nikolaos Pantelidis, Feb 01 2023 *)
Table[(D[Exp[Exp[x]], {x, n}] /. x -> 0)/E, {n, 0, 20}] (* Joan Ludevid, Nov 05 2024 *)
  • Maxima
    makelist(belln(n),n,0,40); /* Emanuele Munarini, Jul 04 2011 */
  • PARI
    {a(n) = my(m); if( n<0, 0, m = contfracpnqn( matrix(2, n\2, i, k, if( i==1, -k*x^2, 1 - (k+1)*x))); polcoeff(1 / (1 - x + m[2,1] / m[1,1]) + x * O(x^n), n))}; /* Michael Somos */
  • PARI
    {a(n) = polcoeff( sum( k=0, n, prod( i=1, k, x / (1 - i*x)), x^n * O(x)), n)}; /* Michael Somos, Aug 22 2004 */
  • PARI
    a(n)=round(exp(-1)*suminf(k=0,1.0*k^n/k!)) \\ Gottfried Helms, Mar 30 2007 - WARNING! For illustration only: Gives silently a wrong result for n = 42 and an error for n > 42, with standard precision of 38 digits. - M. F. Hasler, Nov 30 2018
  • PARI
    {a(n) = if( n<0, 0, n! * polcoeff( exp( exp( x + x * O(x^n)) - 1), n))}; /* Michael Somos, Jun 28 2009 */
  • PARI
    Vec(serlaplace(exp(exp('x+O('x^66))-1))) \\ Joerg Arndt, May 26 2012
  • PARI
    A000110(n)=sum(k=0,n,stirling(n,k,2)) \\ M. F. Hasler, Nov 30 2018
  • Perl
    use bignum;sub a{my($n)=@;my@t=map{[(0)x($n+1)]}0..$n;$t[0][0]=1;for my$i(1..$n){$t[$i][0]=$t[$i-1][$i-1];for my$j(1..$i){$t[$i][$j]=$t[$i-1][$j-1]+$t[$i][$j-1]}}return map{$t[$][0]}0..$n-1}print join(", ",a(28)),"\n" # Paul Muljadi, May 08 2024
  • Python
    # The objective of this implementation is efficiency.
# m -> [a(0), a(1), ..., a(m)] for m > 0.
def A000110_list(m):
    A = [0 for i in range(m)]
    A[0] = 1
    R = [1, 1]
    for n in range(1, m):
        A[n] = A[0]
        for k in range(n, 0, -1):
            A[k-1] += A[k]
        R.append(A[0])
    return R
A000110_list(40) # Peter Luschny, Jan 18 2011
  • Python
    # requires python 3.2 or higher. Otherwise use def'n of accumulate in python docs.
from itertools import accumulate
A000110, blist, b = [1,1], [1], 1
for _ in range(20):
    blist = list(accumulate([b]+blist))
    b = blist[-1]
    A000110.append(b) # Chai Wah Wu, Sep 02 2014, updated Chai Wah Wu, Sep 19 2014
  • Python
    from sympy import bell
print([bell(n) for n in range(27)]) # Michael S. Branicky, Dec 15 2021
  • Python
    from functools import cache
@cache
def a(n, k=0): return int(n < 1) or k*a(n-1, k) + a(n-1, k+1)
print([a(n) for n in range(27)])  # Peter Luschny, Jun 14 2022
  • Sage
    from sage.combinat.expnums import expnums2; expnums2(30, 1) # Zerinvary Lajos, Jun 26 2008
  • Sage
    [bell_number(n) for n in (0..40)] # G. C. Greubel, Jun 13 2019

Formula

E.g.f.: exp(exp(x) - 1).
Recurrence: a(n+1) = Sum_{k=0..n} a(k)*binomial(n, k).
a(n) = Sum_{k=0..n} Stirling2(n, k).
a(n) = Sum_{j=0..n-1} (1/(n-1)!)*A000166(j)*binomial(n-1, j)*(n-j)^(n-1). - André F. Labossière, Dec 01 2004
G.f.: (Sum_{k>=0} 1/((1-k*x)*k!))/exp(1) = hypergeom([-1/x], [(x-1)/x], 1)/exp(1) = ((1-2*x)+LaguerreL(1/x, (x-1)/x, 1)+x*LaguerreL(1/x, (2*x-1)/x, 1))*Pi/(x^2*sin(Pi*(2*x-1)/x)), where LaguerreL(mu, nu, z) = (gamma(mu+nu+1)/(gamma(mu+1)*gamma(nu+1)))* hypergeom([-mu], [nu+1], z) is the Laguerre function, the analytic extension of the Laguerre polynomials, for mu not equal to a nonnegative integer. This generating function has an infinite number of poles accumulating in the neighborhood of x=0. - Karol A. Penson, Mar 25 2002
a(n) = exp(-1)*Sum_{k >= 0} k^n/k! [Dobinski]. - Benoit Cloitre, May 19 2002
a(n) is asymptotic to n!*(2 Pi r^2 exp(r))^(-1/2) exp(exp(r)-1) / r^n, where r is the positive root of r exp(r) = n. See, e.g., the Odlyzko reference.
a(n) is asymptotic to b^n*exp(b-n-1/2)*sqrt(b/(b+n)) where b satisfies b*log(b) = n - 1/2 (see Graham, Knuth and Patashnik, Concrete Mathematics, 2nd ed., p. 493). - Benoit Cloitre, Oct 23 2002, corrected by Vaclav Kotesovec, Jan 06 2013
Lovasz (Combinatorial Problems and Exercises, North-Holland, 1993, Section 1.14, Problem 9) gives another asymptotic formula, quoted by Mezo and Baricz. - N. J. A. Sloane, Mar 26 2015
G.f.: Sum_{k>=0} x^k/(Product_{j=1..k} (1-j*x)) (see Klazar for a proof). - Ralf Stephan, Apr 18 2004
a(n+1) = exp(-1)*Sum_{k>=0} (k+1)^(n)/k!. - Gerald McGarvey, Jun 03 2004
For n>0, a(n) = Aitken(n-1, n-1) [i.e., a(n-1, n-1) of Aitken's array (A011971)]. - Gerald McGarvey, Jun 26 2004
a(n) = Sum_{k=1..n} (1/k!)*(Sum_{i=1..k} (-1)^(k-i)*binomial(k, i)*i^n + 0^n). - Paul Barry, Apr 18 2005
a(n) = A032347(n) + A040027(n+1). - Jon Perry, Apr 26 2005
a(n) = (2*n!/(Pi*e))*Im( Integral_{x=0..Pi} e^(e^(e^(ix))) sin(nx) dx ) where Im denotes imaginary part [Cesaro]. - David Callan, Sep 03 2005
O.g.f.: 1/(1-x-x^2/(1-2*x-2*x^2/(1-3*x-3*x^2/(.../(1-n*x-n*x^2/(...)))))) (continued fraction due to Ph. Flajolet). - Paul D. Hanna, Jan 17 2006
From Karol A. Penson, Jan 14 2007: (Start)
Representation of Bell numbers B(n), n=1,2,..., as special values of hypergeometric function of type (n-1)F(n-1), in Maple notation: B(n)=exp(-1)*hypergeom([2,2,...,2],[1,1,...,1],1), n=1,2,..., i.e., having n-1 parameters all equal to 2 in the numerator, having n-1 parameters all equal to 1 in the denominator and the value of the argument equal to 1.
Examples:
B(1)=exp(-1)*hypergeom([],[],1)=1
B(2)=exp(-1)*hypergeom([2],[1],1)=2
B(3)=exp(-1)*hypergeom([2,2],[1,1],1)=5
B(4)=exp(-1)*hypergeom([2,2,2],[1,1,1],1)=15
B(5)=exp(-1)*hypergeom([2,2,2,2],[1,1,1,1],1)=52
(Warning: this formula is correct but its application by a computer may not yield exact results, especially with a large number of parameters.)
(End)
a(n+1) = 1 + Sum_{k=0..n-1} Sum_{i=0..k} binomial(k,i)*(2^(k-i))*a(i). - Yalcin Aktar, Feb 27 2007
a(n) = [1,0,0,...,0] T^(n-1) [1,1,1,...,1]', where T is the n X n matrix with main diagonal {1,2,3,...,n}, 1's on the diagonal immediately above and 0's elsewhere. [Meier]
a(n) = ((2*n!)/(Pi * e)) * ImaginaryPart(Integral[from 0 to Pi](e^e^e^(i*theta))*sin(n*theta) dtheta). - Jonathan Vos Post, Aug 27 2007
From Tom Copeland, Oct 10 2007: (Start)
a(n) = T(n,1) = Sum_{j=0..n} S2(n,j) = Sum_{j=0..n} E(n,j) * Lag(n,-1,j-n) = Sum_{j=0..n} [ E(n,j)/n! ] * [ n!*Lag(n,-1, j-n) ] where T(n,x) are the Bell / Touchard / exponential polynomials; S2(n,j), the Stirling numbers of the second kind; E(n,j), the Eulerian numbers; and Lag(n,x,m), the associated Laguerre polynomials of order m. Note that E(n,j)/n! = E(n,j) / (Sum_{k=0..n} E(n,k)).
The Eulerian numbers count the permutation ascents and the expression [n!*Lag(n,-1, j-n)] is A086885 with a simple combinatorial interpretation in terms of seating arrangements, giving a combinatorial interpretation to n!*a(n) = Sum_{j=0..n} E(n,j) * [n!*Lag(n,-1, j-n)].
(End)
Define f_1(x), f_2(x), ... such that f_1(x)=e^x and for n=2,3,... f_{n+1}(x) = (d/dx)(x*f_n(x)). Then for Bell numbers B_n we have B_n=1/e*f_n(1). - Milan Janjic, May 30 2008
a(n) = (n-1)! Sum_{k=1..n} a(n-k)/((n-k)! (k-1)!) where a(0)=1. - Thomas Wieder, Sep 09 2008
a(n+k) = Sum_{m=0..n} Stirling2(n,m) Sum_{r=0..k} binomial(k,r) m^r a(k-r). - David Pasino (davepasino(AT)yahoo.com), Jan 25 2009. (Umbrally, this may be written as a(n+k) = Sum_{m=0..n} Stirling2(n,m) (a+m)^k. - N. J. A. Sloane, Feb 07 2009)
Sum_{k=1..n-1} a(n)*binomial(n,k) = Sum_{j=1..n}(j+1)*Stirling2(n,j+1). - [Zhao] - R. J. Mathar, Jun 24 2024
From Thomas Wieder, Feb 25 2009: (Start)
a(n) = Sum_{k_1=0..n+1} Sum_{k_2=0..n}...Sum_{k_i=0..n-i}...Sum_{k_n=0..1}
delta(k_1,k_2,...,k_i,...,k_n)
where delta(k_1,k_2,...,k_i,...,k_n) = 0 if any k_i > k_(i+1) and k_(i+1) <> 0
and delta(k_1,k_2,...,k_i,...,k_n) = 1 otherwise.
(End)
Let A be the upper Hessenberg matrix of order n defined by: A[i,i-1]=-1, A[i,j]:=binomial(j-1,i-1), (i<=j), and A[i,j]=0 otherwise. Then, for n>=1, a(n)=det(A). - Milan Janjic, Jul 08 2010
G.f. satisfies A(x) = (x/(1-x))*A(x/(1-x)) + 1. - Vladimir Kruchinin, Nov 28 2011
G.f.: 1 / (1 - x / (1 - 1*x / (1 - x / (1 - 2*x / (1 - x / (1 - 3*x / ... )))))). - Michael Somos, May 12 2012
a(n+1) = Sum_{m=0..n} Stirling2(n, m)*(m+1), n >= 0. Compare with the third formula for a(n) above. Here Stirling2 = A048993. - Wolfdieter Lang, Feb 03 2015
G.f.: (-1)^(1/x)*((-1/x)!/e + (!(-1-1/x))/x) where z! and !z are factorial and subfactorial generalized to complex arguments. - Vladimir Reshetnikov, Apr 24 2013
The following formulas were proposed during the period Dec 2011 - Oct 2013 by Sergei N. Gladkovskii: (Start)
E.g.f.: exp(exp(x)-1) = 1 + x/(G(0)-x); G(k) = (k+1)*Bell(k) + x*Bell(k+1) - x*(k+1)*Bell(k)*Bell(k+2)/G(k+1) (continued fraction).
G.f.: W(x) = (1-1/(G(0)+1))/exp(1); G(k) = x*k^2 + (3*x-1)*k - 2 + x - (k+1)*(x*k+x-1)^2/G(k+1); (continued fraction Euler's kind, 1-step).
G.f.: W(x) = (1 + G(0)/(x^2-3*x+2))/exp(1); G(k) = 1 - (x*k+x-1)/( ((k+1)!) - (((k+1)!)^2)*(1-x-k*x+(k+1)!)/( ((k+1)!)*(1-x-k*x+(k+1)!) - (x*k+2*x-1)*(1-2*x-k*x+(k+2)!)/G(k+1))); (continued fraction).
G.f.: A(x) = 1/(1 - x/(1-x/(1 + x/G(0)))); G(k) = x - 1 + x*k + x*(x-1+x*k)/G(k+1); (continued fraction, 1-step).
G.f.: -1/U(0) where U(k) = x*k - 1 + x - x^2*(k+1)/U(k+1); (continued fraction, 1-step).
G.f.: 1 + x/U(0) where U(k) = 1 - x*(k+2) - x^2*(k+1)/U(k+1); (continued fraction, 1-step).
G.f.: 1 + 1/(U(0) - x) where U(k) = 1 + x - x*(k+1)/(1 - x/U(k+1)); (continued fraction, 2-step).
G.f.: 1 + x/(U(0)-x) where U(k) = 1 - x*(k+1)/(1 - x/U(k+1)); (continued fraction, 2-step).
G.f.: 1/G(0) where G(k) = 1 - x/(1 - x*(2*k+1)/(1 - x/(1 - x*(2*k+2)/G(k+1) ))); (continued fraction).
G.f.: G(0)/(1+x) where G(k) = 1 - 2*x*(k+1)/((2*k+1)*(2*x*k-1) - x*(2*k+1)*(2*k+3)*(2*x*k-1)/(x*(2*k+3) - 2*(k+1)*(2*x*k+x-1)/G(k+1) )); (continued fraction).
G.f.: -(1+2*x) * Sum_{k >= 0} x^(2*k)*(4*x*k^2-2*k-2*x-1) / ((2*k+1) * (2*x*k-1)) * A(k) / B(k) where A(k) = Product_{p=0..k} (2*p+1), B(k) = Product_{p=0..k} (2*p-1) * (2*x*p-x-1) * (2*x*p-2*x-1).
G.f.: (G(0) - 1)/(x-1) where G(k) = 1 - 1/(1-k*x)/(1-x/(x-1/G(k+1) )); (continued fraction).
G.f.: 1 + x*(S-1) where S = Sum_{k>=0} ( 1 + (1-x)/(1-x-x*k) )*(x/(1-x))^k/Product_{i=0..k-1} (1-x-x*i)/(1-x).
G.f.: (G(0) - 2)/(2*x-1) where G(k) = 2 - 1/(1-k*x)/(1-x/(x-1/G(k+1) )); (continued fraction).
G.f.: -G(0) where G(k) = 1 - (x*k - 2)/(x*k - 1 - x*(x*k - 1)/(x + (x*k - 2)/G(k+1) )); (continued fraction).
G.f.: G(0) where G(k) = 2 - (2*x*k - 1)/(x*k - 1 - x*(x*k - 1)/(x + (2*x*k - 1)/G(k+1) )); (continued fraction).
G.f.: (G(0) - 1)/(1+x) where G(k) = 1 + 1/(1-k*x)/(1-x/(x+1/G(k+1) )); (continued fraction).
G.f.: 1/(x*(1-x)*G(0)) - 1/x where G(k) = 1 - x/(x - 1/(1 + 1/(x*k-1)/G(k+1) )); (continued fraction).
G.f.: 1 + x/( Q(0) - x ) where Q(k) = 1 + x/( x*k - 1 )/Q(k+1); (continued fraction).
G.f.: 1+x/Q(0), where Q(k) = 1 - x - x/(1 - x*(k+1)/Q(k+1)); (continued fraction).
G.f.: 1/(1-x*Q(0)), where Q(k) = 1 + x/(1 - x + x*(k+1)/(x - 1/Q(k+1))); (continued fraction).
G.f.: Q(0)/(1-x), where Q(k) = 1 - x^2*(k+1)/( x^2*(k+1) - (1-x*(k+1))*(1-x*(k+2))/Q(k+1) ); (continued fraction).
(End)
a(n) ~ exp(exp(W(n))-n-1)*n^n/W(n)^(n+1/2), where W(x) is the Lambert W-function. - Vladimir Reshetnikov, Nov 01 2015
a(n) ~ n^n * exp(n/W(n)-1-n) / (sqrt(1+W(n)) * W(n)^n). - Vaclav Kotesovec, Nov 13 2015
From Natalia L. Skirrow, Apr 13 2025: (Start)
By taking logarithmic derivatives of the equivalent to Kotesovec's asymptotic for Bell polynomials at x=1, we obtain properties of the nth row of A008277 as a statistical distribution (where W=W(n),X=W(n)+1)
a(n+1)/a(n) ~ n/W + W/(2*(W+1)^2) is 1 more than the expectation.
(2*a(n+1)+a(n+2))/a(n) - (a(n+1)/a(n))^2 - a(n+2)/a(n+1) ~ n/(W*X)+1/(2*X^2)-3/(2*X^3)+1/X^4 is 1 more than the variance.
(This is a complete asymptotic characterisation, since they converge to normal distributions; see Harper, 1967)
(End)
a(n) are the coefficients in the asymptotic expansion of -exp(-1)*(-1)^x*x*Gamma(-x,0,-1), where Gamma(a,z0,z1) is the generalized incomplete Gamma function. - Vladimir Reshetnikov, Nov 12 2015
a(n) = 1 + floor(exp(-1) * Sum_{k=1..2*n} k^n/k!). - Vladimir Reshetnikov, Nov 13 2015
a(p^m) == m+1 (mod p) when p is prime and m >= 1 (see Lemma 3.1 in the Hurst/Schultz reference). - Seiichi Manyama, Jun 01 2016
a(n) = Sum_{k=0..n} hypergeom([1, -k], [], 1)*Stirling2(n+1, k+1) = Sum_{k=0..n} A182386(k)*Stirling2(n+1, k+1). - Mélika Tebni, Jul 02 2022
For n >= 1, a(n) = Sum_{i=0..n-1} a(i)*A074664(n-i). - Davide Rotondo, Apr 21 2024
a(n) is the n-th derivative of e^e^x divided by e at point x=0. - Joan Ludevid, Nov 05 2024

Extensions

Edited by M. F. Hasler, Nov 30 2018

A008277 Triangle of Stirling numbers of the second kind, S2(n,k), n >= 1, 1 <= k <= n.

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 7, 6, 1, 1, 15, 25, 10, 1, 1, 31, 90, 65, 15, 1, 1, 63, 301, 350, 140, 21, 1, 1, 127, 966, 1701, 1050, 266, 28, 1, 1, 255, 3025, 7770, 6951, 2646, 462, 36, 1, 1, 511, 9330, 34105, 42525, 22827, 5880, 750, 45, 1, 1, 1023, 28501, 145750, 246730, 179487, 63987, 11880, 1155, 55, 1
Offset: 1

Views

Author

N. J. A. Sloane

Keywords

Comments

Also known as Stirling set numbers and written {n, k}.
S2(n,k) counts partitions of an n-set into k nonempty subsets.
From Manfred Boergens, Apr 07 2025: (Start)
With regard to the preceding comment:
For disjoint collections of subsets see A256894.
For arbitrary collections of subsets see A163353.
For arbitrary collections of nonempty subsets see A055154. (End)
Triangle S2(n,k), 1 <= k <= n, read by rows, given by [0, 1, 0, 2, 0, 3, 0, 4, 0, 5, 0, 6, ...] DELTA [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, ...] where DELTA is Deléham's operator defined in A084938.
Number of partitions of {1, ..., n+1} into k+1 nonempty subsets of nonconsecutive integers, including the partition 1|2|...|n+1 if n=k. E.g., S2(3,2)=3 since the number of partitions of {1,2,3,4} into three subsets of nonconsecutive integers is 3, i.e., 13|2|4, 14|2|3, 1|24|3. - Augustine O. Munagi, Mar 20 2005
Draw n cards (with replacement) from a deck of k cards. Let prob(n,k) be the probability that each card was drawn at least once. Then prob(n,k) = S2(n,k)*k!/k^n (see A090582). - Rainer Rosenthal, Oct 22 2005
Define f_1(x), f_2(x), ..., such that f_1(x)=e^x and for n = 2, 3, ..., f_{n+1}(x) = (d/dx)(x*f_n(x)). Then f_n(x) = e^x*Sum_{k=1..n} S2(n,k)*x^(k-1). - Milan Janjic, May 30 2008
From Peter Bala, Oct 03 2008: (Start)
For tables of restricted Stirling numbers of the second kind see A143494 - A143496.
S2(n,k) gives the number of 'patterns' of words of length n using k distinct symbols - see [Cooper & Kennedy] for an exact definition of the term 'pattern'. As an example, the words AADCBB and XXEGTT, both of length 6, have the same pattern of letters. The five patterns of words of length 3 are AAA, AAB, ABA, BAA and ABC giving row 3 of this table as (1,3,1).
Equivalently, S2(n,k) gives the number of sequences of positive integers (N_1,...,N_n) of length n, with k distinct entries, such that N_1 = 1 and N_(i+1) <= 1 + max{j = 1..i} N_j for i >= 1 (restricted growth functions). For example, Stirling(4,2) = 7 since the sequences of length 4 having 2 distinct entries that satisfy the conditions are (1,1,1,2), (1,1,2,1), (1,2,1,1), (1,1,2,2), (1,2,2,2), (1,2,2,1) and (1,2,1,2).
(End)
Number of combinations of subsets in the plane. - Mats Granvik, Jan 13 2009
S2(n+1,k+1) is the number of size k collections of pairwise disjoint, nonempty subsets of [n]. For example: S2(4,3)=6 because there are six such collections of subsets of [3] that have cardinality two: {(1)(23)},{(12)(3)}, {(13)(2)}, {(1)(2)}, {(1)(3)}, {(2)(3)}. - Geoffrey Critzer, Apr 06 2009
Consider a set of A000217(n) balls of n colors in which, for each integer k = 1 to n, exactly one color appears in the set a total of k times. (Each ball has exactly one color and is indistinguishable from other balls of the same color.) a(n+1, k+1) equals the number of ways to choose 0 or more balls of each color in such a way that exactly (n-k) colors are chosen at least once, and no two colors are chosen the same positive number of times. - Matthew Vandermast, Nov 22 2010
S2(n,k) is the number of monotonic-labeled forests on n vertices with exactly k rooted trees, each of height one or less. See link "Counting forests with Stirling and Bell numbers" below. - Dennis P. Walsh, Nov 16 2011
If D is the operator d/dx, and E the operator xd/dx, Stirling numbers are given by: E^n = Sum_{k=1..n} S2(n,k) * x^k*D^k. - Hyunwoo Jang, Dec 13 2011
The Stirling polynomials of the second kind (a.k.a. the Bell / Touchard polynomials) are the umbral compositional inverses of the falling factorials (a.k.a. the Pochhammer symbol or Stirling polynomials of the first kind), i.e., binomial(Bell(.,x),n) = x^n/n! (cf. Copeland's 2007 formulas), implying binomial(xD,n) = binomial(Bell(.,:xD:),n) = :xD:^n/n! where D = d/dx and :xD:^n = x^n*D^n. - Tom Copeland, Apr 17 2014
S2(n,k) is the number of ways to nest n matryoshkas (Russian nesting dolls) so that exactly k matryoshkas are not contained in any other matryoshka. - Carlo Sanna, Oct 17 2015
The row polynomials R(n, x) = Sum_{k=1..n} S2(n, k)*x^k appear in the numerator of the e.g.f. of n-th powers, E(n, x) = Sum_{m>=0} m^n*x^m/m!, as E(n, x) = exp(x)*x*R(n, x), for n >= 1. - Wolfdieter Lang, Apr 02 2017
With offsets 0 for n and k this is the Sheffer product matrix A007318*A048993 denoted by (exp(t), (exp(t) - 1)) with e.g.f. exp(t)*exp(x*(exp(t) - 1)). - Wolfdieter Lang, Jun 20 2017
Number of words on k+1 unlabeled letters of length n+1 with no repeated letters. - Thomas Anton, Mar 14 2019
Also coefficients of moments of Poisson distribution about the origin expressed as polynomials in lambda. [Haight] (see also A331155). - N. J. A. Sloane, Jan 14 2020
k!*S2(n,k) is the number of surjections from an n-element set to a k-element set. - Jianing Song, Jun 01 2022

Examples

			The triangle S2(n, k) begins:
\ k    1       2       3        4         5         6         7         8        9
n \   10      11      12       13        14        15       ...
----------------------------------------------------------------------------------
1  |   1
2  |   1       1
3  |   1       3       1
4  |   1       7       6        1
5  |   1      15      25       10         1
6  |   1      31      90       65        15         1
7  |   1      63     301      350       140        21         1
8  |   1     127     966     1701      1050       266        28         1
9  |   1     255    3025     7770      6951      2646       462        36        1
10 |   1     511    9330    34105     42525     22827      5880       750       45
       1
11 |   1    1023   28501   145750    246730    179487     63987     11880     1155
      55       1
12 |   1    2047   86526   611501   1379400   1323652    627396    159027    22275
    1705      66       1
13 |   1    4095  261625  2532530   7508501   9321312   5715424   1899612   359502
   39325    2431      78        1
14 |   1    8191  788970 10391745  40075035  63436373  49329280  20912320  5135130
  752752   66066    3367       91         1
15 |   1   16383 2375101 42355950 210766920 420693273 408741333 216627840 67128490
12662650 1479478  106470     4550       105         1
...
----------------------------------------------------------------------------------
x^4 = 1 x_(1) + 7 x_(2) + 6 x_(3) + 1 x_(4), where x_(k) = P(x,k) = k!*C(x,k). - _Daniel Forgues_, Jan 16 2016

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. 835.
  • A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, p. 103ff.
  • B. A. Bondarenko, Generalized Pascal Triangles and Pyramids (in Russian), FAN, Tashkent, 1990, ISBN 5-648-00738-8.
  • G. Boole, Finite Differences, 5th ed. New York, NY: Chelsea, 1970.
  • C. A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC, 2002, Theorem 8.11, pp. 298-299.
  • L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 310.
  • J. H. Conway and R. K. Guy, The Book of Numbers, Springer, p. 92.
  • F. N. David, M. G. Kendall, and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 223.
  • S.N. Elaydi, An Introduction to Difference Equations, 3rd ed. Springer, 2005.
  • H. H. Goldstine, A History of Numerical Analysis, Springer-Verlag, 1977; Section 2.7.
  • R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 244.
  • Frank Avery Haight, Handbook of the Poisson distribution, John Wiley, 1967. See pages 6,7.
  • A. D. Korshunov, Asymptotic behavior of Stirling numbers of the second kind. (Russian) Metody Diskret. Analiz. No. 39 (1983), 24-41.
  • E. Kuz'min and A. I. Shirshov: On the number e, pp. 111-119, eq.(6), in: Kvant Selecta: Algebra and Analysis, I, ed. S. Tabachnikov, Am.Math.Soc., 1999, p. 116, eq. (11).
  • J. Riordan, An Introduction to Combinatorial Analysis, p. 48.
  • J. Stirling, The Differential Method, London, 1749; see p. 7.

Links

Crossrefs

Cf. A008275 (Stirling numbers of first kind), A048993 (another version of this triangle).
Cf. A000217, A001296, A001297, A001298, A007318, A028246, A039810-A039813, A048994, A087107-A087111, A087127, A094262, A127701.
See also A331155.
Cf. A038207, A086885, A132440, A138378, A173018, A238385.
Cf. A055154, A163353, A256894.
Cf. A000110 (row sums), A102661 (partial row sums).

Programs

  • Haskell
    a008277 n k = a008277_tabl !! (n-1) !! (k-1)
a008277_row n = a008277_tabl !! (n-1)
a008277_tabl = map tail $ a048993_tabl  -- Reinhard Zumkeller, Mar 26 2012
  • J
    n ((] (1 % !)) * +/@((^~ * (] (1 ^ |.)) * (! {:)@]) i.@>:)) k NB. _Stephen Makdisi, Apr 06 2016
  • Magma
    [[StirlingSecond(n,k): k in [1..n]]: n in [1..12]]; // G. C. Greubel, May 22 2019
  • Maple
    seq(seq(combinat[stirling2](n, k), k=1..n), n=1..10); # Zerinvary Lajos, Jun 02 2007
stirling_2 := (n,k) -> (1/k!) * add((-1)^(k-i)*binomial(k,i)*i^n, i=0..k);
  • Mathematica
    Table[StirlingS2[n, k], {n, 11}, {k, n}] // Flatten (* Robert G. Wilson v, May 23 2006 *)
BellMatrix[f_, len_] := With[{t = Array[f, len, 0]}, Table[BellY[n, k, t], {n, 0, len - 1}, {k, 0, len - 1}]];
rows = 12;
B = BellMatrix[1&, rows];
Table[B[[n, k]], {n, 2, rows}, {k, 2, n}] // Flatten (* Jean-François Alcover, Jun 28 2018, after Peter Luschny *)
a[n_, n_] := 1; a[n_, 1] := 1;
a[n_, k_] := a[n, k] = a[n-1, k-1] + k a[n-1, k]; Flatten@
Table[a[n, k], {n, 1, 11}, {k, 1, n}] (* Oliver Seipel, Jun 12 2024 *)
With[{m = 11},
 Flatten@MapIndexed[Take[#, #2[[1]]] &,
   Transpose@
    Table[Range[1, m]! Coefficient[(E^x-1)^k/k! + O[x]^(m+1), x,
Range[1, m]], {k, 1, m}]]] (* Oliver Seipel, Jun 12 2024 *)
  • Maxima
    create_list(stirling2(n+1,k+1),n,0,30,k,0,n); /* Emanuele Munarini, Jun 01 2012 */
  • PARI
    for(n=1,22,for(k=1,n,print1(stirling(n,k,2),", "));print()); \\ Joerg Arndt, Apr 21 2013
  • PARI
    Stirling2(n,k)=sum(i=0,k,(-1)^i*binomial(k,i)*i^n)*(-1)^k/k!  \\ M. F. Hasler, Mar 06 2012
  • Sage
    stirling_number2 # Danny Rorabaugh, Oct 11 2015

Formula

S2(n, k) = k*S2(n-1, k) + S2(n-1, k-1), n > 1. S2(1, k) = 0, k > 1. S2(1, 1) = 1.
E.g.f.: A(x, y) = e^(y*e^x-y). E.g.f. for m-th column: (e^x-1)^m/m!.
S2(n, k) = (1/k!) * Sum_{i=0..k} (-1)^(k-i)*binomial(k, i)*i^n.
Row sums: Bell number A000110(n) = Sum_{k=1..n} S2(n, k), n>0.
S(n, k) = Sum (i_1*i_2*...*i_(n-k)) summed over all (n-k)-combinations {i_1, i_2, ..., i_k} with repetitions of the numbers {1, 2, ..., k}. Also S(n, k) = Sum (1^(r_1)*2^(r_2)*...* k^(r_k)) summed over integers r_j >= 0, for j=1..k, with Sum{j=1..k} r_j = n-k. [Charalambides]. - Wolfdieter Lang, Aug 15 2019.
A019538(n, k) = k! * S2(n, k).
A028248(n, k) = (k-1)! * S2(n, k).
For asymptotics see Hsu (1948), among other sources.
Sum_{n>=0} S2(n, k)*x^n = x^k/((1-x)(1-2x)(1-3x)...(1-kx)).
Let P(n) = the number of integer partitions of n (A000041), p(i) = the number of parts of the i-th partition of n, d(i) = the number of distinct 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, and Sum_{i=1..P(n), p(i)=m} = sum running from i=1 to i=P(n) but taking only partitions with p(i)=m parts into account. Then S2(n, m) = Sum_{i=1..P(n), p(i)=m} n!/(Product_{j=1..p(i)} p(i, j)!) * 1/(Product_{j=1..d(i)} m(i, j)!). For example, S2(6, 3) = 90 because n=6 has the following partitions with m=3 parts: (114), (123), (222). Their complexions are: (114): 6!/(1!*1!*4!) * 1/(2!*1!) = 15, (123): 6!/(1!*2!*3!) * 1/(1!*1!*1!) = 60, (222): 6!/(2!*2!*2!) * 1/(3!) = 15. The sum of the complexions is 15+60+15 = 90 = S2(6, 3). - Thomas Wieder, Jun 02 2005
Sum_{k=1..n} k*S2(n,k) = B(n+1)-B(n), where B(q) are the Bell numbers (A000110). - Emeric Deutsch, Nov 01 2006
Recurrence: S2(n+1,k) = Sum_{i=0..n} binomial(n,i)*S2(i,k-1). With the starting conditions S2(n,k) = 1 for n = 0 or k = 1 and S2(n,k) = 0 for k = 0 we have the closely related recurrence S2(n,k) = Sum_{i=k..n} binomial(n-1,i-1)*S2(i-1,k-1). - Thomas Wieder, Jan 27 2007
Representation of Stirling numbers of the second kind S2(n,k), n=1,2,..., k=1,2,...,n, as special values of hypergeometric function of type (n)F(n-1): S2(n,k)= (-1)^(k-1)*hypergeom([ -k+1,2,2,...,2],[1,1,...,1],1)/(k-1)!, i.e., having n parameters in the numerator: one equal to -k+1 and n-1 parameters all equal to 2; and having n-1 parameters in the denominator all equal to 1 and the value of the argument equal to 1. Example: S2(6,k)= seq(evalf((-1)^(k-1)*hypergeom([ -k+1,2,2,2,2,2],[1,1,1,1,1],1)/(k-1)!),k=1..6)=1,31,90,65,15,1. - Karol A. Penson, Mar 28 2007
From Tom Copeland, Oct 10 2007: (Start)
Bell_n(x) = Sum_{j=0..n} S2(n,j) * x^j = Sum_{j=0..n} E(n,j) * Lag(n,-x, j-n) = Sum_{j=0..n} (E(n,j)/n!) * (n!*Lag(n,-x, j-n)) = Sum_{j=0..n} E(n,j) * binomial(Bell.(x)+j, n) umbrally where Bell_n(x) are the Bell / Touchard / exponential polynomials; S2(n,j), the Stirling numbers of the second kind; E(n,j), the Eulerian numbers; and Lag(n,x,m), the associated Laguerre polynomials of order m.
For x = 0, the equation gives Sum_{j=0..n} E(n,j) * binomial(j,n) = 1 for n=0 and 0 for all other n. By substituting the umbral compositional inverse of the Bell polynomials, the lower factorial n!*binomial(y,n), for x in the equation, the Worpitzky identity is obtained; y^n = Sum_{j=0..n} E(n,j) * binomial(y+j,n).
Note that E(n,j)/n! = E(n,j)/(Sum_{k=0..n}E(n,k)). Also (n!*Lag(n, -1, j-n)) is A086885 with a simple combinatorial interpretation in terms of seating arrangements, giving a combinatorial interpretation to the equation for x=1; n!*Bell_n(1) = n!*Sum_{j=0..n} S2(n,j) = Sum_{j=0..n} E(n,j) * (n!*Lag(n, -1, j-n)).
(Appended Sep 16 2020) For connections to the Bernoulli numbers, extensions, proofs, and a clear presentation of the number arrays involved in the identities above, see my post Reciprocity and Umbral Witchcraft. (End)
n-th row = leftmost column of nonzero terms of A127701^(n-1). Also, (n+1)-th row of the triangle = A127701 * n-th row; deleting the zeros. Example: A127701 * [1, 3, 1, 0, 0, 0, ...] = [1, 7, 6, 1, 0, 0, 0, ...]. - Gary W. Adamson, Nov 21 2007
The row polynomials are given by D^n(e^(x*t)) evaluated at x = 0, where D is the operator (1+x)*d/dx. Cf. A147315 and A094198. See also A185422. - Peter Bala, Nov 25 2011
Let f(x) = e^(e^x). Then for n >= 1, 1/f(x)*(d/dx)^n(f(x)) = 1/f(x)*(d/dx)^(n-1)(e^x*f(x)) = Sum_{k=1..n} S2(n,k)*e^(k*x). Similar formulas hold for A039755, A105794, A111577, A143494 and A154537. - Peter Bala, Mar 01 2012
S2(n,k) = A048993(n,k), 1 <= k <= n. - Reinhard Zumkeller, Mar 26 2012
O.g.f. for the n-th diagonal is D^n(x), where D is the operator x/(1-x)*d/dx. - Peter Bala, Jul 02 2012
n*i!*S2(n-1,i) = Sum_{j=(i+1)..n} (-1)^(j-i+1)*j!/(j-i)*S2(n,j). - Leonid Bedratyuk, Aug 19 2012
G.f.: (1/Q(0)-1)/(x*y), where Q(k) = 1 - (y+k)*x - (k+1)*y*x^2/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Nov 09 2013
From Tom Copeland, Apr 17 2014: (Start)
Multiply each n-th diagonal of the Pascal lower triangular matrix by x^n and designate the result as A007318(x) = P(x).
With Bell(n,x)=B(n,x) defined above, D = d/dx, and :xD:^n = x^n*D^n, a Dobinski formula gives umbrally f(y)^B(.,x) = e^(-x)*e^(f(y)*x). Then f(y)^B(.,:xD:)g(x) = [f(y)^(xD)]g(x) = e^[-(1-f(y)):xD:]g(x) = g[f(y)x].
In particular, for f(y) = (1+y),
A) (1+y)^B(.,x) = e^(-x)*e^((1+y)*x) = e^(x*y) = e^[log(1+y)B(.,x)],
B) (I+dP)^B(.,x) = e^(x*dP) = P(x) = e^[x*(e^M-I)]= e^[M*B(.,x)] with dP = A132440, M = A238385-I = log(I+dP), and I = identity matrix, and
C) (1+dP)^(xD) = e^(dP:xD:) = P(:xD:) = e^[(e^M-I):xD:] = e^[M*xD] with action e^(dP:xD:)g(x) = g[(I+dP)*x].
D) P(x)^m = P(m*x), which implies (Sum_{k=1..m} a_k)^j = B(j,m*x) where the sum is umbrally evaluated only after exponentiation with (a_k)^q = B(.,x)^q = B(q,x). E.g., (a1+a2+a3)^2=a1^2+a2^2+a3^2+2(a1*a2+a1*a3+a2*a3) = 3*B(2,x)+6*B(1,x)^2 = 9x^2+3x = B(2,3x).
E) P(x)^2 = P(2x) = e^[M*B(.,2x)] = A038207(x), the face vectors of the n-Dim hypercubes.
(End)
As a matrix equivalent of some inversions mentioned above, A008277*A008275 = I, the identity matrix, regarded as lower triangular matrices. - Tom Copeland, Apr 26 2014
O.g.f. for the n-th diagonal of the triangle (n = 0,1,2,...): Sum_{k>=0} k^(k+n)*(x*e^(-x))^k/k!. Cf. the generating functions of the diagonals of A039755. Also cf. A112492. - Peter Bala, Jun 22 2014
Floor(1/(-1 + Sum_{n>=k} 1/S2(n,k))) = A034856(k-1), for k>=2. The fractional portion goes to zero at large k. - Richard R. Forberg, Jan 17 2015
From Daniel Forgues, Jan 16 2016: (Start)
Let x_(n), called a factorial term (Boole, 1970) or a factorial polynomial (Elaydi, 2005: p. 60), denote the falling factorial Product_{k=0..n-1} (x-k). Then, for n >= 1, x_(n) = Sum_{k=1..n} A008275(n,k) * x^k, x^n = Sum_{k=1..n} T(n,k) * x_(k), where A008275(n,k) are Stirling numbers of the first kind.
For n >= 1, the row sums yield the exponential numbers (or Bell numbers): Sum_{k=1..n} T(n,k) = A000110(n), and Sum_{k=1..n} (-1)^(n+k) * T(n,k) = (-1)^n * Sum_{k=1..n} (-1)^k * T(n,k) = (-1)^n * A000587(n), where A000587 are the complementary Bell numbers. (End)
Sum_{k=1..n} k*S2(n,k) = A138378(n). - Alois P. Heinz, Jan 07 2022
O.g.f. for the m-th column: x^m/(Product_{j=1..m} 1-j*x). - Daniel Checa, Aug 25 2022
S2(n,k) ~ (k^n)/k!, for fixed k as n->oo. - Daniel Checa, Nov 08 2022
S2(2n+k, n) ~ (2^(2n+k-1/2) * n^(n+k-1/2)) / (sqrt(Pi*(1-c)) * exp(n) * c^n * (2-c)^(n+k)), where c = -LambertW(-2 * exp(-2)). - Miko Labalan, Dec 21 2024
From Mikhail Kurkov, Mar 05 2025: (Start)
For a general proof of the formulas below via generating functions, see Mathematics Stack Exchange link.
Recursion for the n-th row (independently of other rows): T(n,k) = 1/(n-k)*Sum_{j=2..n-k+1} (j-2)!*binomial(-k,j)*T(n,k+j-1) for 1 <= k < n with T(n,n) = 1 (see Fedor Petrov link).
Recursion for the k-th column (independently of other columns): T(n,k) = 1/(n-k)*Sum_{j=2..n-k+1} binomial(n,j)*T(n-j+1,k)*(-1)^j for 1 <= k < n with T(n,n) = 1. (End)

A008275 Triangle read by rows of Stirling numbers of first kind, s(n,k), n >= 1, 1 <= k <= n.

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: 1

Views

Author

N. J. A. Sloane

Keywords

Comments

The unsigned numbers are also called Stirling cycle numbers: |s(n,k)| = number of permutations of n objects with exactly k cycles.
The unsigned numbers (read from right to left) also give the number of permutations of 1..n with complexity k, where the complexity of a permutation is defined to be the sum of the lengths of the cycles minus the number of cycles. In other words, the complexity equals the sum of (length of cycle)-1 over all cycles. For n=5, the numbers of permutations with complexity 0,1,2,3,4 are 1, 10, 35, 50, 24. - N. J. A. Sloane, Feb 08 2019
The unsigned numbers are also the number of permutations of 1..n with k left to right maxima (see Khovanova and Lewis, Smith).
With P(n) = the number of integer partitions of n, T(i,n) = the number of parts of the i-th partition of n, D(i,n) = the number of different parts of the i-th partition of n, p(j,i,n) = the j-th part of the i-th partition of n, m(j,i,n) = multiplicity of the j-th part of the i-th partition of n, Sum_[T(i,n)=k]{i=1}^{P(n)} = sum running from i=1 to i=p(n) but taking only partitions with T(i,n)=k parts into account, Product{j=1..T(i,n)} = product running from j=1 to j=T(i,n), Product_{j=1..D(i,n)} = product running from j=1 to j=D(i,n) one has S1(n,k) = Sum_[T(i,n)=k]{i=1}^{P(n)} (n!/Product{j=1..T(i,n)} p(j,i,n))* (1/Product_{j=1..D(i,n)} m(j,i,n)!). For example, S1(6,3) = 225 because n=6 has the following partitions with k=3 parts: (114), (123), (222). Their complexions are: (114): (6!/1*1*4)*(1/2!*1!) = 90, (123): (6!/1*2*3)*(1/1!*1!*1!) = 120, (222): (6!/2*2*2)*(1/3!) = 15. The sum of the complexions is 90+120+15 = 225 = S1(6,3). - Thomas Wieder, Aug 04 2005
Row sums equal 0. - Jon Perry, Nov 14 2005
|s(n,k)| enumerates unordered n-vertex forests composed of k increasing non-plane (unordered) trees. Proof from the e.g.f. of the first column and the F. Bergeron et al. reference, especially Table 1, last row (non-plane "recursive"), given in A049029. - Wolfdieter Lang, Oct 12 2007
|s(n,k)| enumerates unordered increasing n-vertex k-forests composed of k unary trees (out-degree r from {0,1}) whose vertices of depth (distance from the root) j >= 0 come in j+1 colors (j=0 for the k roots). - Wolfdieter Lang, Oct 12 2007, Feb 22 2008
A refinement of the unsigned array is A036039. For an association to forests of "naturally grown" rooted non-planar trees, dispositions of flags on flagpoles, and colorings of the vertices of the complete graphs K_n, see A130534. - Tom Copeland, Mar 30 and Apr 05 2014
The Stirling numbers of the first kind were related to the falling factorial and the convolved, or generalized, Bernoulli numbers B_n by Norlund in 1924 through Sum_{k=1..n+1} T(n+1,k) * x^(k-1) = (x-1)!/(x-1-n)! = (x + B.(0))^n = B_n(x), umbrally evaluated with (B.(0))^k = B_k(0) and the associated Appell polynomial B_n(x) defined by the e.g.f. (t/(exp(t) - 1))^(n+1) * exp(x*t) = exp(B.(x)t). - Tom Copeland, Sep 29 2015
With x = e^z, D_x = d/dx, D_z = d/dz, and p_n(x) the row polynomials of this entry, x^n (D_x)^n = p_n(D_z) = (D_z)! / (D_z - n)! = (xD_x)! / (xD_x - n)!. - Tom Copeland, Nov 27 2015
From the operator relation z + Psi(1) + sum_{n > 0} (-1)^n (-1/n) binomial(D,n) = z + Psi(1+D) with D = d/dz and Psi the digamma function, Zeta(n+1) = Sum_{k > n-1} (1/k) |S(k,n)| / k! for n > 0 and Zeta the Riemann zeta function. - Tom Copeland, Aug 12 2016
Let X_1,...,X_n be i.i.d. random variables with exponential distribution having mean = 1. Let Y = max{X_1,...,X_n}. Then (-1)^n*n!/( Sum_{k=1..n+1} a(n+1,k) t^(k-1) ) is the moment generating function of Y. The expectation of Y is the n-th harmonic number. - Geoffrey Critzer, Dec 25 2018
In the Ewens sampling theory describing the multivariate probability distribution of the sizes of the allelic classes in a sample of size n under the Infinite Alleles Model, |s(n,k)| gives the coefficient in the formula for the probability that a sample of n alleles has exactly k distinct types. - Noah A Rosenberg, Feb 10 2019
Named by Nielson (1906) after the Scottish mathematician James Stirling (1692-1770). - Amiram Eldar, Jun 11 2021 and Oct 02 2023
The first few row polynomials along with a recursion formula are found in a manuscript by Newton written in 1664 or 1665 (p. 169 of Turnbull) giving a geometric presentation of the binomial theorem for rational powers. - Tom Copeland, Dec 10 2022

Examples

			|s(3,2)| = 3 for the three unordered 2-forest with 3 vertices and two increasing (nonplane) trees: ((1),(2,3)), ((2),(1,3)), ((3),(1,2)).
Triangle begins:
                                      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
Another version of the same triangle, from _Joerg Arndt_, Oct 05 2009: (Start)
s(n,k) := number of permutations of n elements with exactly k cycles ("Stirling cycle numbers")
  n|  total   m=1      2      3     4     5    6   7  8 9
  -+-----------------------------------------------------
  1|      1     1
  2|      2     1      1
  3|      6     2      3      1
  4|     24     6     11      6     1
  5|    120    24     50     35    10     1
  6|    720   120    274    225    85    15    1
  7|   5040   720   1764   1624   735   175   21   1
  8|  40320  5040  13068  13132  6769  1960  322  28  1
  9| 362880 40320 109584 118124 67284 22449 4536 546 36 1
(End)
|s(4,2)| = 11 for the eleven unordered 2-forest with 4 vertices, composed of two increasing (nonplane) trees: ((1),((23)(24))), ((2),((13)(14))), ((3),((12)(14))), ((4),((12)(13))); ((1),(2,3,4)),((2),(1,2,3)), ((3), (1,2,4)), ((4),(1,2,3)); ((1,2),(3,4)), ((1,3),(2,4)), ((1,4),(2,3)). - _Wolfdieter Lang_, Feb 22 2008

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.
  • Arthur T. Benjamin and Jennifer Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, p. 93ff.
  • Boris A. Bondarenko, Generalized Pascal Triangles and Pyramids (in Russian), FAN, Tashkent, 1990, ISBN 5-648-00738-8.
  • George Boole, Finite Differences, 5th ed. New York, NY: Chelsea, 1970.
  • Louis Comtet, Advanced Combinatorics, Reidel, 1974; Chapter V, also p. 310.
  • John H. Conway and Richard K. Guy, The Book of Numbers, Copernicus Press, NY, 1996, p. 93.
  • Florence Nightingale David, Maurice George Kendall and David Elliot Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 226.
  • Saber N. Elaydi, An Introduction to Difference Equations, 3rd ed. Springer, 2005.
  • Herman H. Goldstine, A History of Numerical Analysis, Springer-Verlag, 1977; Section 2.7.
  • Ronald L. Graham, Donald E. Knuth and Oren Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 245. In the second edition, see Chapter 6, especially p. 259.
  • M. Miyata and J. W. Son, On the complexity of permutations and the metric space of bijections, Tensor, 60 (1998), No. 1, 109-116 (MR1768839).
  • Isaac Newton, A Method whereby to find ye areas of Those Lines wch can be squared, pp. 168-171 of Turnbull below.
  • John Riordan, An Introduction to Combinatorial Analysis, p. 48.
  • Robert Sedgewick and Phillipe Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley, Reading, MA, 1996.
  • H. Turnbull (editor), The Correspondence of Isaac Newton Vol. II 1676-1687, Cambridge Univ. Press, 1960.

Links

Crossrefs

Diagonals: A000217, A000914, A001303, A000915, A053567, etc.
Cf. A048994, A008277 (Stirling numbers of second kind), A039814, A039815, A039816, A039817, A048993, A087748.
Cf. A084938, A094216, A008276 (row reversed), A008277, A008278, A094262, A121632, A130534 (unsigned version), A087755 (triangle mod 2), A000142 (row sums of absolute values).

Programs

  • Haskell
    a008275 n k = a008275_tabl !! (n-1) !! (k-1)
a008275_row n = a008275_tabl !! (n-1)
a008275_tabl = map tail $ tail a048994_tabl
-- Reinhard Zumkeller, Mar 18 2013
  • Maple
    with (combinat):seq(seq(stirling1(n, k), k=1..n), n=1..10); # Zerinvary Lajos, Jun 03 2007
for i from 0 to 9 do seq(stirling1(i, j), j = 1 .. i) od; # Zerinvary Lajos, Nov 29 2007
  • Mathematica
    Flatten[Table[StirlingS1[n, k], {n, 1, 10}, {k, 1, n}]] (* Jean-François Alcover, May 18 2011 *)
Flatten@Table[Coefficient[Product[x-k, {k, 0, n-1}], x, Range[n]], {n, Range[10]}] (* Oliver Seipel, Jun 11 2024 *)
a[n_, n_] := 1; a[n_, 0] := 0; a[0, k_] := 0;
a[n_, k_] := a[n, k] = a[n-1, k-1] + (n-1) a[n-1, k];
Flatten@Table[(-1)^(n-k) a[n, k], {n, 1, 10}, {k, 1, n}] (* Oliver Seipel, Jun 11 2024 *)
  • Maxima
    create_list(stirling1(n+1,k+1),n,0,30,k,0,n); /* Emanuele Munarini, Jun 01 2012 */
  • PARI
    T(n,k)=if(n<1,0,n!*polcoeff(binomial(x,n),k))
  • PARI
    T(n,k)=if(n<1,0,n!*polcoeff(polcoeff((1+x+x*O(x^n))^y,n),k))
  • PARI
    vecstirling(n)=Vec(factorback(vector(n-1,i,1-i*'x))) /* (A function that returns all the s(n,k) as a vector) */ \\ Bill Allombert (Bill.Allombert(AT)math.u-bordeaux1.fr), Mar 16 2009

Formula

s(n, k) = s(n-1, k-1) - (n-1)*s(n-1, k), n, k >= 1; s(n, 0) = s(0, k) = 0; s(0, 0) = 1.
The unsigned numbers a(n, k)=|s(n, k)| satisfy a(n, k) = a(n-1, k-1) + (n-1)*a(n-1, k), n, k >= 1; a(n, 0) = a(0, k) = 0; a(0, 0) = 1.
E.g.f.: for m-th column (unsigned): ((-log(1-x))^m)/m!.
s(n, k) = T(n-1, k-1), n>1 and k>1, where T(n, k) is the triangle [ -1, -1, -2, -2, -3, -3, -4, -4, -5, -5, -6, -6, ...] DELTA [1, 0, 1, 0, 1, 0, 1, 0, 1, ...] and DELTA is Deléham's operator defined in A084938. The unsigned numbers are also |s(n, k)| = T(n-1, k-1), for n>0 and k>0, where T(n, k) = [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, ...] DELTA [1, 0, 1, 0, 1, 0, 1, 0, ...].
Sum_{i=0..n} (-1)^(n-i) * StirlingS1(n, i) * binomial(i, k) = (-1)^(n-k) * StirlingS1(n+1, k+1). - Carlo Wood (carlo(AT)alinoe.com), Feb 13 2007
G.f. for row n: Product_{j=1..n} (x-j) (e.g., (x-1)*(x-2)*(x-3) = x^3 - 6*x^2 + 11*x - 6). - Jon Perry, Nov 14 2005
s(n,k) = A048994(n,k), for k=1..n. - Reinhard Zumkeller, Mar 18 2013 (Corrected by N. J. A. Sloane, May 07 2025 at the suggestion of Manfred Boergens, May 07 2025)
As lower triangular matrices A008277*A008275 = I, the identity matrix. - Tom Copeland, Apr 25 2014
a(n,k) = s(n,k) = lim_{y -> 0} Sum_{j=0..k} (-1)^j*binomial(k,j)*((-j*y)!/(-j*y-n)!)*y^(-k)/k! = Sum_{j=0..k} (-1)^(n-j)*binomial(k,j)*((j*y - 1 + n)!/(j*y-1)!)*y^(-k)/k!. - Tom Copeland, Aug 28 2015
From Daniel Forgues Jan 16 2016: (Start)
Let x_(0) := 1 (empty product), and for n >= 1:
x_(n) := Product_{k=0..n-1} (x-k), called a factorial term (Boole, 1970) or a factorial polynomial (Elaydi, 2005: p. 60), and also x_(-n) := 1 / [Product_{k=0..n-1} (x+k)].
Then, for n >= 1: x_(n) = Sum_{k=1..n} T(n,k) * x^k, 1 / [x_(-n)] = Sum_{k=1..n} |T(n,k)| * x^k, x^n = Sum_{k=1..n} A008277(n,k) * x_(k), where A008277(n,k) are Stirling numbers of the second kind.
The row sums (of either signed or absolute values) are Sum_{k=1..n} T(n,k) = 0^(n-1), Sum_{k=1..n} |T(n,k)| = T(n+1,1) = n!. (End)
s(n,m) = ((-1)^(n-m)/n)*Sum_{i=0..m-1} C(2*n-m-i, m-i-1)*A008517(n-m+1,n-m-i+1). - Vladimir Kruchinin, Feb 14 2018
Orthogonal relation: Sum_{i=0..n} i^p*Sum_{j=k..n} (-1)^(i+j) * binomial(j,i) * Stirling1(j,k)/j! = delta(p,k), i,k,p <= n, n >= 1. - Leonid Bedratyuk, Jul 27 2020
From Zizheng Fang, Dec 28 2020: (Start)
Sum_{k=1..n} (-1)^k * k * T(n, k) = -T(n+1, 2).
Sum_{k=1..n} k * T(n, k) = (-1)^n * (n-2)! = T(n-1, 1) for n>=2. (End)
n-th row polynomial = n!*Sum_{k = 0..2*n} (-1)^(n+k)*binomial(x, k)*binomial(x-1, 2*n-k) = n!*Sum_{k = 0..2*n+1} (-1)^(n+k+1)*binomial(x, k)*binomial(x-1, 2*n+1-k). - Peter Bala, Mar 29 2024

A001296 4-dimensional pyramidal numbers: a(n) = (3*n+1)*binomial(n+2, 3)/4. Also Stirling2(n+2, n).

Original entry on oeis.org

0, 1, 7, 25, 65, 140, 266, 462, 750, 1155, 1705, 2431, 3367, 4550, 6020, 7820, 9996, 12597, 15675, 19285, 23485, 28336, 33902, 40250, 47450, 55575, 64701, 74907, 86275, 98890, 112840, 128216, 145112, 163625, 183855, 205905, 229881, 255892, 284050, 314470
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Permutations avoiding 12-3 that contain the pattern 31-2 exactly once.
Kekulé numbers for certain benzenoids. - Emeric Deutsch, Nov 18 2005
Partial sums of A002411. - Jonathan Vos Post, Mar 16 2006
If Y is a 3-subset of an n-set X then, for n>=6, a(n-5) is the number of 6-subsets of X having at least two elements in common with Y. - Milan Janjic, Nov 23 2007
Starting with 1 = binomial transform of [1, 6, 12, 10, 3, 0, 0, 0, ...]. Equals row sums of triangle A143037. - Gary W. Adamson, Jul 18 2008
Rephrasing the Perry formula of 2003: a(n) is the sum of all products of all two numbers less than or equal to n, including the squares. Example: for n=3 the sum of these products is 1*1 + 1*2 + 1*3 + 2*2 + 2*3 + 3*3 = 25. - J. M. Bergot, Jul 16 2011
Half of the partial sums of A011379. [Jolley, Summation of Series, Dover (1961), page 12 eq (66).] - R. J. Mathar, Oct 03 2011
Also the number of (w,x,y,z) with all terms in {1,...,n+1} and w < x >= y > z (see A211795). - Clark Kimberling, May 19 2012
Convolution of A000027 with A000326. - Bruno Berselli, Dec 06 2012
This sequence is related to A000292 by a(n) = n*A000292(n) - Sum_{i=0..n-1} A000292(i) for n>0. - Bruno Berselli, Nov 23 2017
a(n-2) is the maximum number of intersections made from the perpendicular bisectors of all pair combinations of n points. - Ian Tam, Dec 22 2020

Examples

			G.f. = x + 7*x^2 + 25*x^3 + 65*x^4 + 140*x^5 + 266*x^6 + 462*x^7 + 750*x^8 + 1155*x^9 + ...

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. 835.
  • A. H. Beiler, Recreations in the Theory of Numbers, Dover, NY, 1964, p. 195.
  • L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 227, #16.
  • S. J. Cyvin and I. Gutman, Kekulé structures in benzenoid hydrocarbons, Lecture Notes in Chemistry, No. 46, Springer, New York, 1988 (see p. 166, Table 10.4/I/3).
  • F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 223.
  • 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

a(n)=f(n, 2) where f is given in A034261.
Cf. A000217, A000326, A001297, A001298, A002411, A008277, A008517, A094262.
a(n)= A093560(n+3, 4), (3, 1)-Pascal column.
Cf. A220212 for a list of sequences produced by the convolution of the natural numbers with the k-gonal numbers.
Cf. similar sequences listed in A241765 and A254142.
Cf. A000914.

Programs

  • Magma
    /* A000027 convolved with A000326: */ A000326:=func; [&+[(n-i+1)*A000326(i): i in [0..n]]: n in [0..40]]; // Bruno Berselli, Dec 06 2012
  • Magma
    [(3*n+1)*Binomial(n+2,3)/4: n in [0..40]]; // Vincenzo Librandi, Jul 30 2014
  • Maple
    A001296:=-(1+2*z)/(z-1)**5; # Simon Plouffe in his 1992 dissertation for sequence without the leading zero
  • Mathematica
    Table[n*(1+n)*(2+n)*(1+3*n)/24, {n, 0, 100}]
CoefficientList[Series[x (1 + 2 x)/(1 - x)^5, {x, 0, 40}], x] (* Vincenzo Librandi, Jul 30 2014 *)
Table[StirlingS2[n+2, n], {n, 0, 40}] (* Jean-François Alcover, Jun 24 2015 *)
Table[ListCorrelate[Accumulate[Range[n]],Range[n]],{n,0,40}]//Flatten (* or *) LinearRecurrence[{5,-10,10,-5,1},{0,1,7,25,65},40] (* Harvey P. Dale, Aug 14 2017 *)
  • PARI
    t(n)=n*(n+1)/2
for(i=1,30,print1(","sum(j=1,i,j*t(j))))
  • PARI
    {a(n) = n * (n+1) * (n+2) * (3*n+1) / 24}; /* Michael Somos, Sep 04 2017 */
  • Sage
    [stirling_number2(n+2,n) for n in range(0,38)] # Zerinvary Lajos, Mar 14 2009

Formula

a(n) = n*(1+n)*(2+n)*(1+3*n)/24. - T. D. Noe, Jan 21 2008
G.f.: x*(1+2*x)/(1-x)^5. - Paul Barry, Jul 23 2003
a(n) = Sum_{j=0..n} j*A000217(j). - Jon Perry, Jul 28 2003
E.g.f. with offset -1: exp(x)*(1*(x^2)/2! + 4*(x^3)/3! + 3*(x^4)/4!). For the coefficients [1, 4, 3] see triangle A112493.
E.g.f. x*exp(x)*(24 + 60*x + 28*x^2 + 3*x^3)/24 (above e.g.f. differentiated).
a(n) = 4*a(n-1) - 6*a(n-2) + 4*a(n-3) - a(n-4) + 3. - Kieren MacMillan, Sep 29 2008
a(n) = 5*a(n-1) - 10*a(n-2) + 10*a(n-3) - 5*a(n-4) + a(n-5). - Jaume Oliver Lafont, Nov 23 2008
O.g.f. is D^2(x/(1-x)) = D^3(x), where D is the operator x/(1-x)*d/dx. - Peter Bala, Jul 02 2012
a(n) = A153978(n)/2. - J. M. Bergot, Aug 09 2013
a(n) = A002817(n) + A000292(n-1). - J. M. Bergot, Aug 29 2013; [corrected by Cyril Damamme, Feb 26 2018]
a(n) = A000914(n+1) - 2 * A000330(n+1). - Antal Pinter, Dec 31 2015
a(n) = A080852(3,n-1). - R. J. Mathar, Jul 28 2016
a(n) = 1*(1+2+...+n) + 2*(2+3+...+n) + ... + n*n. For example, a(6) = 266 = 1(1+2+3+4+5+6) + 2*(2+3+4+5+6) + 3*(3+4+5+6) + 4*(4+5+6) + 5*(5+6) + 6*(6).- J. M. Bergot, Apr 20 2017
a(n) = A000914(-2-n) for all n in Z. - Michael Somos, Sep 04 2017
a(n) = A000292(n) + A050534(n+1). - Cyril Damamme, Feb 26 2018
From Amiram Eldar, Jul 02 2020: (Start)
Sum_{n>=1} 1/a(n) = (6/5) * (47 - 3*sqrt(3)*Pi - 27*log(3)).
Sum_{n>=1} (-1)^(n+1)/a(n) = (6/5) * (16*log(2) + 6*sqrt(3)*Pi - 43). (End)

A008278 Reflected triangle of Stirling numbers of 2nd kind, S(n,n-k+1), n >= 1, 1 <= k <= n.

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 6, 7, 1, 1, 10, 25, 15, 1, 1, 15, 65, 90, 31, 1, 1, 21, 140, 350, 301, 63, 1, 1, 28, 266, 1050, 1701, 966, 127, 1, 1, 36, 462, 2646, 6951, 7770, 3025, 255, 1, 1, 45, 750, 5880, 22827, 42525, 34105, 9330, 511, 1
Offset: 1

Views

Author

N. J. A. Sloane

Keywords

Comments

The n-th row also gives the coefficients of the sigma polynomial of the empty graph \bar K_n. - Eric W. Weisstein, Apr 07 2017
The n-th row also gives the coefficients of the independence polynomial of the (n-1)-triangular honeycomb bishop graph. - Eric W. Weisstein, Apr 03 2018
From Gus Wiseman, Aug 11 2020: (Start)
Conjecture: also the number of divisors of the superprimorial A006939(n - 1) that have 0 <= k <= n distinct prime factors, all appearing with distinct multiplicities. For example, row n = 4 counts the following divisors of 360:
1 2 12 360
3 18
4 20
5 24
8 40
9 45
72
Equivalently, T(n,k) is the number of length-n vectors 0 <= v_i <= i with k nonzero values, all of which are distinct.
Crossrefs:
A006939 lists superprimorials or Chernoff numbers.
A022915 counts permutations of prime indices of superprimorials.
A076954 can be used instead of A006939.
A130091 lists numbers with distinct prime multiplicities.
A181796 counts divisors with distinct prime multiplicities.
A336420 is the version counting all prime factors, not just distinct ones.
Cf. A000005, A027423, A095149, A124010, A317829, A327498, A336419, A336421.
(End)
From Leonidas Liponis, Aug 26 2024: (Start)
It appears that this sequence is related to the combinatorial form of Faà di Bruno's formula. Specifically, the number of terms for the n-th derivative of a composite function y = f(g(x)) matches the number of partitions of n.
For example, consider the case where g(x) = e^x, in which all derivatives of g(x) are equal. The first 5 rows of A008278 appear as the factors of derivatives of f(x), highlighted here in brackets:
dy/dx = [ 1 ] * f'(e^x) * e^x
d^2y/dx^2 = [ 1 ] * f''(e^x) * e^{2x} + [ 1 ] * f'(e^x) * e^x
d^3y/dx^3 = [ 1 ] * f'''(e^x) * e^{3x} + [ 3 ] * f''(e^x) * e^{2x} + [ 1 ] * f'(e^x) * e^x
d^4y/dx^4 = [ 1 ] * f''''(e^x) * e^{4x} + [ 6 ] * f'''(e^x) * e^{3x} + [ 7 ] * f''(e^x) * e^{2x} + [ 1 ] * f'(e^x) * e^x
d^5y/dx^5 = [ 1 ] * f'''''(e^x) * e^{5x} + [ 10 ] * f''''(e^x) * e^{4x} + [ 25 ] * f'''(e^x) * e^{3x} + [ 15 ] * f''(e^x) * e^{2x} + [ 1 ] * f'(e^x) * e^x
This pattern is observed in Mathematica for the first 10 cases, using the code below.
(End)

Examples

			The e.g.f. of [0,0,1,7,25,65,...], the k=3 column of A008278, but with offset n=0, is exp(x)*(1*(x^2)/2! + 4*(x^3)/3! + 3*(x^4)/4!).
Triangle starts:
  1;
  1,  1;
  1,  3,   1;
  1,  6,   7,    1;
  1, 10,  25,   15,    1;
  1, 15,  65,   90,   31,    1;
  1, 21, 140,  350,  301,   63,    1;
  1, 28, 266, 1050, 1701,  966,  127,   1;
  1, 36, 462, 2646, 6951, 7770, 3025, 255, 1;
  ...

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. 835.
  • F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 223.
  • R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, 2nd ed., 1994.

Links

Crossrefs

See A008277 and A048993, which are the main entries for this triangle of numbers.
Cf. A094262, A008277, A008276, A003422, A000166, A000110, A000204, A000045, A000108, A213735.

Programs

  • Haskell
    a008278 n k = a008278_tabl !! (n-1) !! (k-1)
a008278_row n = a008278_tabl !! (n-1)
a008278_tabl = iterate st2 [1] where
  st2 row = zipWith (+) ([0] ++ row') (row ++ [0])
            where row' = reverse $ zipWith (*) [1..] $ reverse row
-- Reinhard Zumkeller, Jun 22 2013
  • Mathematica
    rows = 10; Flatten[Table[StirlingS2[n, k], {n, 1, rows}, {k, n, 1, -1}]] (* Jean-François Alcover, Nov 17 2011, *)
Table[CoefficientList[x^n BellB[n, 1/x], x], {n, 10}] // Flatten (* Eric W. Weisstein, Apr 05 2017 *)
n = 5; Grid[Prepend[Transpose[{Range[1, n], Table[D[f[Exp[x]], {x, i}], {i, 1, n}]}], {"Order","Derivative"}], Frame -> All, Spacings -> {2, 1}] (* Leonidas Liponis, Aug 27 2024 *)
  • PARI
    for(n=1,10,for(k=1,n,print1(stirling(n,n-k+1,2),", "))) \\ Hugo Pfoertner, Aug 30 2020

Formula

T(n, k)=0 if n < k, T(n, 0)=0, T(1, 1)=1, T(n, k) = (n-k+1)*T(n-1, k-1) + T(n-1, k) otherwise.
O.g.f. for the k-th column: 1/(1-x) if k=1 and A(k,x):=((x^k)/(1-x)^(2*k+1))*Sum_{m=0..k-1} A008517(k,m+1)*x^m if k >= 2. A008517 is the second-order Eulerian triangle. Cf. p. 257, eq. (6.43) of the R. L. Graham et al. book. - Wolfdieter Lang, Oct 14 2005
E.g.f. for the k-th column (with offset n=0): E(k,x):=exp(x)*Sum_{m=0..k-1} A112493(k-1,m)*(x^(k-1+m))/(k-1+m)! if k >= 1. - Wolfdieter Lang, Oct 14 2005
a(n) = abs(A213735(n-1)). - Hugo Pfoertner, Sep 07 2020

Extensions

Name edited by Gus Wiseman, Aug 11 2020

A094216 Triangle read by rows giving the coefficients of formulas generating each variety of S1(n,k) (unsigned Stirling numbers of first kind). The p-th row (p>=1) contains T(i,p) for i=1 to 2*p, where T(i,p) satisfies Sum_{i=1..2*p} T(i,p) * C(n,i).

Original entry on oeis.org

1, 1, 2, 7, 8, 3, 6, 38, 93, 111, 65, 15, 24, 226, 874, 1821, 2224, 1600, 630, 105, 120, 1524, 8200, 24860, 47185, 58465, 47474, 24430, 7245, 945, 720, 11628, 81080, 326712, 852690, 1522375, 1905168, 1676325, 1018682, 407925, 97020, 10395, 5040
Offset: 1

Views

Author

André F. Labossière, May 27 2004, Feb 21 2007

Keywords

Comments

The formulas S1(n+p,n) obtained are those of S1(n+2,n) { A000914 }, S1(n+3,n) { A001303 }, S1(n+4,n) { A000915 }, S1(n+5,n) { A053567 } and so on.

Examples

			Row 5 contains 120,1524,8200,24860,47185,58465,47474,24430,7245,945, so the formula generating S1(n+5,n) numbers { A053567 } will be the following : 120*n +1524*C(n,2) +8200*C(n,3) +24860*C(n,4) +47185*C(n,5) +58465*C(n,6) +47474*C(n,7) +24430*C(n,8) +7245*C(n,9) +945*C(n,10). And then substituting for the 10th number of such a S1(n+p,n) gives S1(15,10) = 37312275.

References

  • Milton Abramowitz and Irene A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964, 9th Printing (1970), pp. 833-834.

Links

Crossrefs

Cf. A000914, A001303, A000915, A053567, A008275, A008276.
Cf. A000012, A000217, A001147, A000142, A094262.

Programs

  • Mathematica
    row[m_] := Module[{eq, t}, eq[n_] := Array[t, 2 m].Table[Binomial[n, k], {k, 1, 2 m}] == Abs[StirlingS1[n + m, n]]; Array[t, 2 m] /. Solve[ Array[ eq, 2 m]] // First];
Array[row, 7] // Flatten (* Jean-François Alcover, Nov 14 2019 *)

Formula

a(1,k) = k!
...
a(2*k-5,k) = a(2*k,k) * (175000*k^8 -2117500*k^7 +10856650*k^6 -30743377*k^5 +52511770*k^4 -55386931*k^3 +35321832*k^2 -12560580*k+1944000) / (1632960*k^3 -7348320*k^2 +9389520*k -3061800).
a(2*k-4,k) = a(2*k,k) * (2500*k^6 -17400*k^5 +48511*k^4 -69378*k^3 +53929*k^2 -21906*k +3744) / (7776*k^2-15552*k+5832).
a(2*k-3,k) = a(2*k,k) * (1250*k^4-4225*k^3+5023*k^2-2600*k+528) / (1620*k-810).
a(2*k-2,k) = a(2*k,k) * (50*k^3-93*k^2+55*k-12) / (36*k-18).
a(2*k-1,k) = a(2*k,k) * (5*k-2) / 3.
a(2*k,k) = (2*k)! / (k!*2^k).

A001297 Stirling numbers of the second kind S(n+3, n).

Original entry on oeis.org

0, 1, 15, 90, 350, 1050, 2646, 5880, 11880, 22275, 39325, 66066, 106470, 165620, 249900, 367200, 527136, 741285, 1023435, 1389850, 1859550, 2454606, 3200450, 4126200, 5265000, 6654375, 8336601, 10359090, 12774790, 15642600, 19027800
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Examples

			a(2) = 1*1*1 + 1*1*2 + 1*2*2 + 2*2*2 = 15

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. 835.
  • Louis Comtet, Advanced Combinatorics, Reidel, 1974, p. 227, #16.
  • F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 223.
  • 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. A001296, A001298, A008277, A008517, A048993, A062196, A094262.
Cf. A001303.

Programs

  • Magma
    [n^2*(n+1)^2*(n+2)*(n+3)/48: n in [0..40]]; // Vincenzo Librandi, Sep 22 2017
  • Maple
    A001297:=-(1+8*z+6*z**2)/(z-1)**7; # Simon Plouffe in his 1992 dissertation, without the initial 0
  • Mathematica
    lst={};Do[f=StirlingS2[n+3, n];AppendTo[lst, f], {n, 0, 5!}];lst (* Vladimir Joseph Stephan Orlovsky, Sep 27 2008 *)
a[ n_] := n^2 (n + 1)^2 (n + 2) (n + 3) / 48; (* Michael Somos, Sep 04 2017 *)
Table[StirlingS2[n+3,n],{n,0,30}] (* Harvey P. Dale, Dec 30 2019 *)
  • PARI
    {a(n) = n^2 * (n+1)^2 * (n+2) * (n+3) / 48}; /* Michael Somos, Sep 04 2017 */
  • Sage
    [stirling_number2(n+3,n) for n in range(0, 34)] # Zerinvary Lajos, May 16 2009

Formula

G.f.: x*(1 + 8*x + 6*x^2)/(1 - x)^7. - Paul Barry, Aug 05 2004
E.g.f. with offset -2: exp(x)*(1*(x^3)/3! + 11*(x^4)/4! + 25*(x^5)/5! + 15*(x^6)/6!). For the coefficients [1, 11, 25, 15] see triangle A112493. E.g.f.: 1/48*x*exp(x)*(x^5+22*x^4+152*x^3+384*x^2+312*x+48)/48. Above given e.g.f. differentiated twice.
a(n) = (binomial(n+4, n-1) - binomial(n+3, n-2))*(binomial(n+2, n-1) - binomial(n+1, n-2)). - Zerinvary Lajos, May 12 2006
a(n) = binomial(n+1, 2)*binomial(n+3, 4). - Vladimir Shevelev, Dec 18 2011
O.g.f.: D^3(x/(1-x)) = D^4(x), where D is the operator x/(1-x)*d/dx. - Peter Bala, Jul 02 2012
a(n) = A001303(-3-n) for all n in Z. - Michael Somos, Sep 04 2017
a(n) = Sum_{k=1..n} Sum_{i=1..n} i * C(k+2,k-1). - Wesley Ivan Hurt, Sep 21 2017
From Amiram Eldar, Jan 10 2022: (Start)
Sum_{n>=1} 1/a(n) = 16*Pi^2/3 - 464/9.
Sum_{n>=1} (-1)^(n+1)/a(n) = 260/9 - 4*Pi^2/3 - 64*log(2)/3. (End)
a(n) = Sum_{0<=i<=j<=k<=n} i*j*k. - Robert FERREOL, May 25 2022

Extensions

Initial zero added by N. J. A. Sloane, Jan 21 2008
Name corrected by Nathaniel Johnston, Apr 30 2011

A005001 a(n) = Sum_{k=0..n-1} Bell(k), where the Bell numbers Bell(k) are given in A000110.

Original entry on oeis.org

0, 1, 2, 4, 9, 24, 76, 279, 1156, 5296, 26443, 142418, 820988, 5034585, 32679022, 223578344, 1606536889, 12086679036, 94951548840, 777028354999, 6609770560056, 58333928795428, 533203744952179, 5039919483399502, 49191925338483848, 495150794633289137
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Counts rhyme schemes.
Row sums of triangle A137596 starting with offset 1. - Gary W. Adamson, Jan 29 2008
With offset 1 = binomial transform of the Bell numbers, A000110 starting (1, 1, 1, 2, 5, 15, 52, 203, ...). - Gary W. Adamson, Dec 04 2008
a(n) is the number of partitions of the set {1,2,...,n} in which n is either a singleton or it is in a block of consecutive integers. Example: a(3)=4 because we have 123, 1-23, 12-3, and 1-2-3. Deleting the blocks containing n=3, we obtain: empty, 1, 12, 1-2, i.e., all the partitions of the sets: empty, {1}, and {1,2}. - Emeric Deutsch, May 01 2010

References

  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

Partial sums of A000110, partial sums give A029761.
Equals A024716(n-1) + 1.
Cf. A102735, A094262, A000110, A008277, A102639, A003422, A000166, A000204, A000045, A000108.
Cf. A137596.
Cf. A171859.

Programs

  • Maple
    with(combinat): seq(add(bell(j), j = 0 .. n-1), n = 0 .. 22); # Emeric Deutsch, May 01 2010
  • Mathematica
    nn=20;Range[0,nn]!CoefficientList[Series[Exp[-1](-Exp[Exp[x]]+Exp[1+x]-Exp[x]ExpIntegralEi[1]+Exp[x]ExpIntegralEi[Exp[x]]),{x,0,nn}],x] (* Geoffrey Critzer, Feb 04 2014 *)
BellB /@ Range[0, 30] // Accumulate // Prepend[#, 0]& (* Jean-François Alcover, Oct 19 2019 *)
  • Python
    # Python 3.2 or higher required.
from itertools import accumulate
A005001_list, blist, a, b = [0,1,2], [1], 2, 1
for _ in range(30):
    blist = list(accumulate([b]+blist))
    b = blist[-1]
    a += b
    A005001_list.append(a) # Chai Wah Wu, Sep 19 2014

Formula

a(0) = 0; for n >= 0, a(n+1) = 1 + Sum_{j=1..n} (C(n, j)-C(n, j+1))*a(j).
a(n) = A000110(n) - A171859(n). - Emeric Deutsch, May 01 2010
G.f.: x*( 1 + (G(0)+1)*x/(1-x) ) where G(k) = 1 - 2*x*(k+1)/((2*k+1)*(2*x*k+x-1) - x*(2*k+1)*(2*k+3)*(2*x*k+x-1)/(x*(2*k+3) - 2*(k+1)*(2*x*k+2*x-1)/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Dec 20 2012
G.f.: x*G(0)/(1-x^2) where G(k) = 1 - 2*x*(k+1)/((2*k+1)*(2*x*k-1) - x*(2*k+1)*(2*k+3)*(2*x*k-1)/(x*(2*k+3) - 2*(k+1)*(2*x*k+x-1)/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Dec 22 2012
G.f.: x*( G(0) - 1 )/(1-x) where G(k) = 1 + (1-x)/(1-x*k)/(1-x/(x+(1-x)/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jan 21 2013
G.f.: (G(0)-1)*x/(1-x^2) where G(k) = 1 + 1/(1-k*x)/(1-x/(x+1/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Feb 06 2013
G.f.: x/(1-x)/(1-x*Q(0)), where Q(k) = 1 + x/(1 - x + x*(k+1)/(x - 1/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 19 2013
E.g.f. A(x) satisfies: A'(x) = A(x) + exp(exp(x)-1). - Geoffrey Critzer, Feb 04 2014
G.f.: (x/(1 - x)) * Sum_{i>=0} x^i / Product_{j=1..i} (1 - j*x). - Ilya Gutkovskiy, Jun 05 2017
a(n) ~ Bell(n) / (n/LambertW(n) - 1). - Vaclav Kotesovec, Jul 28 2021

A001298 Stirling numbers of the second kind S(n+4, n).

Original entry on oeis.org

0, 1, 31, 301, 1701, 6951, 22827, 63987, 159027, 359502, 752752, 1479478, 2757118, 4910178, 8408778, 13916778, 22350954, 34952799, 53374629, 79781779, 116972779, 168519505, 238929405, 333832005, 460192005, 626551380, 843303006, 1122998436, 1480692556
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

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. 835.
  • F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 223.
  • 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. A001296, A001297, A008277, A008517, A094262.
Cf. A000915.

Programs

  • Magma
    [n*(n+1)*(n+2)*(n+3)*(n+4)*(15*n^3 + 30*n^2 + 5*n - 2)/5760: n in [0..50]]; // G. C. Greubel, Oct 22 2017
  • Maple
    A001298:=-(1+22*z+58*z**2+24*z**3)/(z-1)**9; # Simon Plouffe in his 1992 dissertation, without the leading 0
  • Mathematica
    Table[StirlingS2[n+4, n], {n, 0, 100}] (* Vladimir Joseph Stephan Orlovsky, Sep 27 2008 *)
a[ n_] := n (n + 1) (n + 2) (n + 3) (n + 4) (15 n^3 + 30 n^2 + 5 n - 2) / 5760; (* Michael Somos, Sep 04 2017 *)
  • PARI
    {a(n) = n * (n+1) * (n+2) * (n+3) * (n+4) * (15*n^3 + 30*n^2 + 5*n - 2) / 5760}; /* Michael Somos, Sep 04 2017 */
  • Sage
    [stirling_number2(n+4,n) for n in range(0, 24)] # Zerinvary Lajos, May 16 2009

Formula

G.f.: x(1 + 22x + 58x^2 + 24x^3)/(1 - x)^9. - Paul Barry, Aug 05 2004
a(n) = Stirling2(n+4, n) = Sum_{L=1..n} (Sum_{k=1..L} (Sum_{j=1..k} (Sum_{i=1..j} i*j*k*L))) = (n+4)*(n+3)*(n+2)*(n+1)*n *(15*n^3 + 30*n^2 + 5*n - 2)/5760 = (15*n^3 + 30*n^2 + 5*n - 2)*binomial(n+4, 5)/48. - Vladeta Jovovic, Jan 31 2005
E.g.f. with offset -3: exp(x)*(1*(x^4)/4! + 26*(x^5)/5! + 130*(x^6)/6! + 210*(x^7)/7! +105*(x^8)/8!). For the coefficients [1, 26, 130, 210, 105] see triangle A112493. E.g.f.: x*exp(x)*(15*x^7 + 600*x^6 + 8600*x^5 + 55248*x^4 + 162960*x^3 + 202560*x^2 + 83520*x + 5760)/5760. Above given e.g.f. differentiated three times.
O.g.f. is D^4(x/(1-x)), where D is the operator x/(1-x)*d/dx. - Peter Bala, Jul 02 2012
a(n) = A000915(-4-n) for all n in Z. - Michael Somos, Sep 04 2017

Extensions

Name edited and initial zero added by Nathaniel Johnston, Apr 30 2011

A005173 Number of rooted trees with 3 nodes of disjoint sets of labels with union {1..n}. If a node has an empty set of labels then it must have at least two children.

Original entry on oeis.org

0, 1, 12, 61, 240, 841, 2772, 8821, 27480, 84481, 257532, 780781, 2358720, 7108921, 21392292, 64307941, 193185960, 580082161, 1741295052, 5225982301, 15682141200, 47054812201, 141181213812, 423577195861, 1270798696440, 3812530307041, 11437859356572, 34314114940621
Offset: 1

Views

Author

N. J. A. Sloane

Keywords

Examples

			From _Andrew Howroyd_, Mar 28 2025: (Start)
The a(3) = 12 trees up to relabeling have one of the following 3 forms:
     {}         {1}        {1}
    /  \       /   \        |
  {1} {2,3}   {2}  {3}     {2}
                            |
                           {3}
(End)

References

  • F. R. McMorris and T. Zaslavsky, The number of cladistic characters, Math. Biosciences, 54 (1981), 3-10.
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

Column 3 of A094262.
Cf. A003063.

Programs

  • Maple
    A005173:=-z*(1+6*z)/(z-1)/(3*z-1)/(2*z-1); # conjectured by Simon Plouffe in his 1992 dissertation
  • Mathematica
    CoefficientList[Series[x (1+6 x)/(1-x)/(1-2 x)/(1-3 x),{x,0,30}],x] (* Harvey P. Dale, Jul 03 2023 *)

Formula

G.f.: x*(1 + 6*x) / ((1 - x)*(1 - 2*x)*(1 - 3*x)). [corrected by Ray Chandler, Jun 26 2023]
First differences give A003063, 3^(n-1) - 2^n.
From Andrew Howroyd, Mar 28 2025: (Start)
a(n) = (3^(n+1) - 2^(n+3) + 7)/2.
E.g.f.: (3*exp(x)/2 - 1)*(exp(x) - 1)^2. (End)

Extensions

More terms from Larry Reeves (larryr(AT)acm.org), Feb 06 2001
Name clarified by Andrew Howroyd, Mar 28 2025
Showing 1-10 of 14 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.