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 12 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

A056857 Triangle read by rows: T(n,c) = number of successive equalities in set partitions of n.

Original entry on oeis.org

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, 4140, 7016, 5684, 2912, 1050, 280, 56, 8, 1, 21147, 37260, 31572, 17052, 6552, 1890, 420, 72, 9, 1, 115975, 211470, 186300, 105240, 42630, 13104, 3150, 600, 90, 10, 1
Offset: 1

Views

Author

Winston C. Yang (winston(AT)cs.wisc.edu), Aug 31 2000

Keywords

Comments

Number of successive equalities s_i = s_{i+1} in a set partition {s_1, ..., s_n} of {1, ..., n}, where s_i is the subset containing i, s(1) = 1 and s(i) <= 1 + max of previous s(j)'s.
T(n,c) = number of set partitions of the set {1,2,...,n} in which the size of the block containing the element 1 is k+1. Example: T(4,2)=3 because we have 123|4, 124|3 and 134|2. - Emeric Deutsch, Nov 10 2006
Let P be the lower-triangular Pascal-matrix (A007318), Then this is exp(P) / exp(1). - Gottfried Helms, Mar 30 2007. [This comment was erroneously attached to A011971, but really belongs here. - N. J. A. Sloane, May 02 2015]
From David Pasino (davepasino(AT)yahoo.com), Apr 15 2009: (Start)
As an infinite lower-triangular matrix (with offset 0 rather than 1, so the entries would be B(n - c)*binomial(n, c), B() a Bell number, rather than B(n - 1 - c)*binomial(n - 1, c) as below), this array is S P S^-1 where P is the Pascal matrix A007318, S is the Stirling2 matrix A048993, and S^-1 is the Stirling1 matrix A048994.
Also, S P S^-1 = (1/e)*exp(P). (End)
Exponential Riordan array [exp(exp(x)-1), x]. Equal to A007318*A124323. - Paul Barry, Apr 23 2009
Equal to A049020*A048994 as infinite lower triangular matrices. - Philippe Deléham, Nov 19 2011
Build a superset Q[n] of set partitions of {1,2,...,n} by distinguishing "some" (possibly none or all) of the singletons. Indexed from n >= 0, 0 <= k <= n, T(n,k) is the number of elements in Q[n] that have exactly k distinguished singletons. A singleton is a subset containing one element. T(3,1) = 6 because we have {{1}'{2,3}}, {{1,2}{3}'}, {{1,3}{2}'}, {{1}'{2}{3}}, {{1}{2}'{3}}, {{1}{2}{3}'}. - Geoffrey Critzer, Nov 10 2012
Let Bell(n,x) denote the n-th Bell polynomial, the n-th row polynomial of A048993. Then this is the triangle of connection constants when expressing the basis polynomials Bell(n,x + 1) in terms of the basis polynomials Bell(n,x). For example, row 3 is (5, 6, 3, 1) and 5 + 6*Bell(1,x) + 3*Bell(2,x) + Bell(3,x) = 5 + 6*x + 3*(x + x^2) + (x + 3*x^2 + x^3) = 5 + 10*x + 6*x^2 + x^3 = (x + 1) + 3*(x + 1)^2 + (x + 1)^3 = Bell(3,x + 1). - Peter Bala, Sep 17 2013

Examples

			For example {1, 2, 1, 2, 2, 3} is a set partition of {1, 2, 3, 4, 5, 6} and has 1 successive equality, at i = 4.
Triangle begins:
    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;
  ...
From _Paul Barry_, Apr 23 2009: (Start)
Production matrix is
  1,  1;
  1,  1,  1;
  1,  2,  1,  1;
  1,  3,  3,  1,  1;
  1,  4,  6,  4,  1,  1;
  1,  5, 10, 10,  5,  1,  1;
  1,  6, 15, 20, 15,  6,  1,  1;
  1,  7, 21, 35, 35, 21,  7,  1,  1;
  1,  8, 28, 56, 70, 56, 28,  8,  1,  1; ... (End)

References

  • W. C. Yang, Conjectures on some sequences involving set partitions and Bell numbers, preprint, 2000. [Apparently unpublished]

Links

Crossrefs

Cf. Bell numbers A000110 (column c=0), A052889 (c=1), A105479 (c=2), A105480 (c=3).
Cf. A056858-A056863. Essentially same as A056860, where the rows are read from right to left.
Cf. also A007318, A005493, A270953.
See A259691 for another version.
T(2n+1,n+1) gives A124102.
T(2n,n) gives A297926.

Programs

  • Maple
    with(combinat): A056857:=(n,c)->binomial(n-1,c)*bell(n-1-c): for n from 1 to 11 do seq(A056857(n,c),c=0..n-1) od; # yields sequence in triangular form; Emeric Deutsch, Nov 10 2006
with(linalg): # Yields sequence in matrix form:
A056857_matrix := n -> subs(exp(1)=1, exponential(exponential(
matrix(n,n,[seq(seq(`if`(j=k+1,j,0),k=0..n-1),j=0..n-1)])))):
A056857_matrix(8); # Peter Luschny, Apr 18 2011
  • Mathematica
    t[n_, k_] := BellB[n-1-k]*Binomial[n-1, k]; Flatten[ Table[t[n, k], {n, 1, 11}, {k, 0, n-1}]](* Jean-François Alcover, Apr 25 2012, after Emeric Deutsch *)
  • PARI
    B(n) = sum(k=0, n, stirling(n, k, 2));
tabl(nn)={for(n=1, nn, for(k=0, n - 1, print1(B(n - 1 - k) * binomial(n - 1, k),", ");); print(););};
tabl(12); \\ Indranil Ghosh, Mar 19 2017
  • Python
    from sympy import bell, binomial
for n in range(1,12):
    print([bell(n - 1 - k) * binomial(n - 1, k) for k in range(n)]) # Indranil Ghosh, Mar 19 2017
  • SageMath
    def a(n): return (-1)^n / factorial(n)
@cached_function
def p(n, m):
    R = PolynomialRing(QQ, "x")
    if n == 0: return R(a(m))
    return R((m + x)*p(n - 1, m) - (m + 1)*p(n - 1, m + 1))
for n in range(11): print(p(n, 0).list())  # Peter Luschny, Jun 18 2023

Formula

T(n,c) = B(n-1-c)*binomial(n-1, c), where T(n,c) is the number of set partitions of {1, ..., n} that have c successive equalities and B() is a Bell number.
E.g.f.: exp(exp(x)+x*y-1). - Vladeta Jovovic, Feb 13 2003
G.f.: 1/(1-xy-x-x^2/(1-xy-2x-2x^2/(1-xy-3x-3x^2/(1-xy-4x-4x^2/(1-... (continued fraction). - Paul Barry, Apr 23 2009
Considered as triangle T(n,k), 0 <= k <= n: T(n,k) = A007318(n,k)*A000110(n-k) and Sum_{k=0..n} T(n,k)*x^k = A000296(n), A000110(n), A000110(n+1), A005493(n), A005494(n), A045379(n) for x = -1, 0, 1, 2, 3, 4 respectively. - Philippe Deléham, Dec 13 2009
Let R(n,x) denote the n-th row polynomial of the triangle. Then A000110(n+j) = Bell(n+j,1) = Sum_{k = 1..n} R(j,k)*Stirling2(n,k) (Spivey). - Peter Bala, Sep 17 2013

Extensions

More terms from David Wasserman, Apr 22 2002

A070071 a(n) = n*B(n), where B(n) are the Bell numbers, A000110.

Original entry on oeis.org

0, 1, 4, 15, 60, 260, 1218, 6139, 33120, 190323, 1159750, 7464270, 50563164, 359377681, 2672590508, 20744378175, 167682274352, 1408702786668, 12277382510862, 110822101896083, 1034483164707440, 9972266139291771, 99147746245841106, 1015496134666939958
Offset: 0

Views

Author

Karol A. Penson, Apr 19 2002

Keywords

Comments

a(n) is the total number of successions among all partitions of {1,2,...,n+1}; a succession is a pair (i,i+1) of consecutive integers lying in a block. For example, a(3)=15 because {1,2,3,4} has 6 partitions with 1 succession - 1/2/34, 1/23/4, 12/3/4, 14/23, 134/2, 124/3, 3 partitions with 2 successions - 1/234, 123/4, 12/34 and 1 partition with 3 successions - 1234. Thus a(3) = 6*1 + 3*2 + 1*3 = 15. - Augustine O. Munagi, Jul 01 2008
a(n) is the number of occurrences of integers in a list of all partitions of the set {1,...,n}. For example, the list 123, 1/23, 2/13, 3/12, 1/2/3 of all partitions of the set {1,2,3} requires 15 occurrences of integers each belonging to that set. [From Michael Hardy (hardy(AT)math.umn.edu), Nov 08 2008]
The bijection between the two foregoing characterizations is as follows: Fix x in {1,2,...,n} and associate x with the succession (x,x+1) which appears in some partitions of {1,2,...,n+1}. Replace x,x+1 by x and partition the n-set {1,2,...,x,x+2,...,n+1}, giving B(n) partitions. Thus the succession (x,x+1) occurs among partitions of {1,2,...,n+1} exactly B(n) times. - Augustine O. Munagi, Jun 02 2010

Links

Crossrefs

Cf. A000110, A052889, A105479, A105480, A105481, A175757.
Row sums of A270236, A270701, A270702, A286416, A319298, A319375.

Programs

  • Magma
    [n*Bell(n): n in [0..25]]; // Vincenzo Librandi, Mar 15 2014
  • Maple
    with(combinat): a:=n->sum(numbcomb (n,0)*bell(n), j=1..n): seq(a(n), n=0..21); # Zerinvary Lajos, Apr 25 2007
with(combinat): a:=n->sum(bell(n), j=1..n): seq(a(n), n=0..21); # Zerinvary Lajos, Apr 25 2007
a:=n->sum(sum(Stirling2(n, k), j=1..n), k=1..n): seq(a(n), n=0..21); # Zerinvary Lajos, Jun 28 2007
  • Mathematica
    a[n_] := n!*Coefficient[Series[x E^(E^x+x-1), {x, 0, n}], x, n]
Table[Sum[BellB[n, 1], {i, 1, n}], {n, 0, 21}] (* Zerinvary Lajos, Jul 16 2009 *)
Table[n*BellB[n], {n, 0, 20}] (* Vaclav Kotesovec, Mar 13 2014 *)
  • PARI
    a(n)=local(t); if(n<0,0,t=exp(x+O(x^n)); n!*polcoeff(x*t*exp(t-1),n))
  • Sage
    [bell_number(n)*n for n in range(22) ] # Zerinvary Lajos, Mar 14 2009

Formula

E.g.f: x*exp(x)*exp(exp(x)-1).
Sum_{k=1..n} n*binomial(n-1, k-1)*Bell(n-k), n >= 2. - Zerinvary Lajos, Nov 22 2006
a(n) ~ n^(n+1) * exp(n/LambertW(n)-1-n) / (sqrt(1+LambertW(n)) * LambertW(n)^n). - Vaclav Kotesovec, Mar 13 2014
a(n) = Sum_{k=1..n} k * A175757(n,k). - Alois P. Heinz, Mar 03 2020
a(n) = Sum_{j=0..n} n * Stirling2(n,j). - Detlef Meya, Apr 11 2024

A105488 Number of partitions of {1...n} containing 2 detached pairs of consecutive integers, i.e., partitions in which only 1- or 2-strings of consecutive integers can appear in a block and there are exactly two 2-strings.

Original entry on oeis.org

1, 6, 30, 150, 780, 4263, 24556, 149040, 951615, 6378625, 44785620, 328660566, 2515643767, 20044428810, 165955025400, 1425299331992, 12678325080012, 116635133853189, 1108221018960830, 10862073229428120, 109694927532209481, 1140199081827172719
Offset: 4

Views

Author

Augustine O. Munagi, Apr 10 2005

Keywords

Comments

Number of partitions enumerated by A105479 in which the maximal length of consecutive integers in a block is 2.
With offset 2t, number of partitions of {1...N} containing 2 detached strings of t consecutive integers, where N=n+2j, t=2+j, j = 0,1,2,..., i.e., partitions of [n] in which only v-strings of consecutive integers can appear in a block, where v=1 or v=t and there are exactly two t-strings.
Equals the minimum of the sum of the Rand distances over all A000110(n) set partitions of n elements. E.g. a(3) = 6 because over the 5 set partitions of {1, 2, 3} the sum of Rand distances from {{1}, {2}, {3}} to the rest is 6. - Andrey Goder (andy.goder(AT)gmail.com), Dec 08 2006
a(n+3) = A000110(n) * A000217(n) = Sum_{k=1..n} A285362(n,k) is the sum of the entries in all set partitions of [n]. - Alois P. Heinz, Apr 16 2017

Examples

			a(5)=6 because the partitions of {1,2,3,4,5} with 2 detached pairs of consecutive integers are 145/23,125/34,1245/3,12/34/5,12/3/45,1/23/45.

Links

Crossrefs

Cf. A000110, A000217, A052889, A105479, A105489, A105484, A271023, A285362.

Programs

  • Maple
    seq(binomial(n-2,2)*combinat[bell](n-3),n=4..28);
  • Mathematica
    a[n_] := Binomial[n-2, 2]*BellB[n-3];
Table[a[n], {n, 4, 25}] (* Jean-François Alcover, May 11 2019 *)

Formula

a(n) = binomial(n-2, 2)*Bell(n-3), which is the case r = 2 in the general case of r pairs, d(n, r)=binomial(n-r, r)*Bell(n-r-1), which is the case t=2 of the general formula d(n, r, t)=binomial(n-r*(t-1), r)*B(n-r*(t-1)-1).

A105480 Number of partitions of {1...n} containing 3 pairs of consecutive integers, where each pair is counted within a block and a string of more than 2 consecutive integers are counted two at a time.

Original entry on oeis.org

1, 4, 20, 100, 525, 2912, 17052, 105240, 683100, 4652340, 33168850, 246999480, 1917186635, 15480884720, 129811538960, 1128494172720, 10155257740443, 94465951576560, 907162152191470, 8982422995787780, 91603484234843812
Offset: 4

Views

Author

Augustine O. Munagi, Apr 10 2005

Keywords

Examples

			a(5) = 4 because the partitions of {1,2,3,4,5} with 3 pairs of consecutive integers are 1234/5,123/45,12/345,1/2345.

Links

Crossrefs

Cf. A105479, A105481, A105485, A105490.

Programs

  • Maple
    seq(binomial(n-1,3)*combinat[bell](n-4),n=4..25);

Formula

a(n) = binomial(n-1, 3)*Bell(n-4), the case r = 3 in the general case of r pairs: c(n, r) = binomial(n-1, r)*B(n-r-1).
O.g.f. for c(n,r) is exp(-1)*Sum(x^(r+1)/(n!*(1-n*x)^(r+1)),n=0..infinity). - Vladeta Jovovic, Feb 05 2008
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>=3, a(n+1)=(-1)^(n-3)*coeff(charpoly(A,x),x^3). [Milan Janjic, Jul 08 2010]
E.g.f.: (1/3!) * Integral (x^3 * exp(exp(x) - 1)) dx. - Ilya Gutkovskiy, Jul 10 2020

A192100 Table read by rows of numbers of unordered pairs of partitions of n-element set that have Rand distance k (n>=2, 1 <= k <= n(n-1)/2).

Original entry on oeis.org

1, 3, 6, 1, 12, 30, 32, 24, 6, 1, 50, 150, 280, 300, 240, 220, 60, 15, 10, 1, 225, 780, 1720, 3360, 3426, 4100, 2400, 2700, 1075, 471, 150, 35, 45, 15, 1, 1092, 4200, 10885, 25200, 42672, 56889, 60165, 57750, 46585, 31374, 24528, 14140, 4725, 1890, 1302, 252, 210, 140, 105, 21, 1
Offset: 1

Views

Author

Frank Ruskey and Yuji Yamauchi (eugene.uti(AT)gmail.com), Jul 28 2011

Keywords

Comments

The Rand distance of two set partitions is the number of unordered pairs {x,y} such that there is a block in one partition containing both x and y, but x and y are in different blocks in the other partition. Let R(n,k) denote the number of unordered pairs of partitions of a n-element set that have Rand distance k.
The (n,k) entry contains R(n,k) where n is a row number and k is a column number. Rows are of length C(n,2) = n(n-1)/2 and n is in the range [2..7]. Columns are counted from 1.

Examples

			The table starts:
1
3 6 1
12 30 32 24 6 1
50 150 280 300 240 220 60 15 10 1
225 780 1720 3360 3426 4100 2400 2700 1075 471 150 35 45 15 1
...
One of the 300 pairs of partitions of 5-element set having Rand distance 4:
  {1, 2, 3}{4, 5}
  {1, 2}{3, 4}{5}

References

  • Frank Ruskey and Jennifer Woodcock, The Rand and block distances of pairs of set partitions, Combinatorial algorithms, 287-299, Lecture Notes in Comput. Sci., 7056, Springer, Heidelberg, 2011.
  • 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. - From N. J. A. Sloane, Oct 03 2012

Links

Crossrefs

Cf. A105479 (first column), A193317.

A175757 Triangular array read by rows: T(n,k) is the number of blocks of size k in all set partitions of {1,2,...,n}.

Original entry on oeis.org

1, 2, 1, 6, 3, 1, 20, 12, 4, 1, 75, 50, 20, 5, 1, 312, 225, 100, 30, 6, 1, 1421, 1092, 525, 175, 42, 7, 1, 7016, 5684, 2912, 1050, 280, 56, 8, 1, 37260, 31572, 17052, 6552, 1890, 420, 72, 9, 1, 211470, 186300, 105240, 42630, 13104, 3150, 600, 90, 10, 1
Offset: 1

Views

Author

Geoffrey Critzer, Dec 04 2010

Keywords

Comments

The row sums of this triangle equal A005493. Equals A056857 without its leftmost column.
T(n,k) = binomial(n,k)*B(n-k) where B is the Bell number.

Examples

			The set {1,2,3} has 5 partitions, {{1, 2, 3}}, {{2, 3}, {1}}, {{1, 3}, {2}}, {{1, 2}, {3}}, and {{2}, {3}, {1}}, and there are a total of 3 blocks of size 2, so T(3,2)=3.
Triangle begins:
    1;
    2,   1;
    6,   3,   1;
   20,  12,   4,  1;
   75,  50,  20,  5, 1;
  312, 225, 100, 30, 6, 1;
  ...

Links

Crossrefs

Cf. A000110, A056860, A052889, A070071, A105479, A105480, A105481, A105482, A285595.

Programs

  • Maple
    b:= proc(n) option remember; `if`(n=0, [1, 0],
      add((p-> p+[0, p[1]*x^j])(b(n-j)*
      binomial(n-1, j-1)), j=1..n))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(b(n)[2]):
seq(T(n), n=1..12);  # Alois P. Heinz, Apr 24 2017
  • Mathematica
    Table[Table[Length[Select[Level[SetPartitions[m],{2}],Length[#]==n&]],{n,1,m}],{m,1,10}]//Grid

Formula

E.g.f. for column k is x^k/k!*exp(exp(x)-1).
Sum_{k=1..n} k * T(n,k) = A070071(n). - Alois P. Heinz, Mar 03 2020

A193297 Triangle read by rows: T(n,k) = number of pairs of partitions of n that have block distance k (n >= 2, 2 <= k <= n).

Original entry on oeis.org

1, 3, 7, 12, 28, 65, 50, 140, 325, 811, 225, 700, 1950, 4866, 12762, 1092, 3675, 11375, 34062, 89334, 244588, 5684, 20384, 68250, 227080, 714672, 1956704, 5574956, 31572, 119364, 425880, 1532790, 5360040, 17610336, 50174604, 148332645
Offset: 2

Views

Author

N. J. A. Sloane, Aug 26 2011

Keywords

Examples

			Triangle begins
1
3 7
12 28 65
50 140 325 811
225 700 1950 4866 12762
1092 3675 11375 34062 89334 244588
5684 20384 68250 227080 714672 1956704 5574956
31572 119364 425880 1532790 5360040 17610336 50174604 148332645
...

Links

Crossrefs

Row sums give A193274.
Column k=2 gives A105479.
T(n,n) gives A152525.

A370945 Number T(n,k) of partitions of [n] whose singletons sum to k; triangle T(n,k), n>=0, 0<=k<=A000217(n), read by rows.

Original entry on oeis.org

1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 4, 1, 1, 2, 2, 2, 1, 1, 0, 0, 1, 11, 4, 4, 5, 5, 6, 3, 3, 3, 3, 2, 1, 1, 0, 0, 1, 41, 11, 11, 15, 15, 19, 20, 13, 10, 11, 8, 8, 5, 4, 4, 3, 2, 1, 1, 0, 0, 1, 162, 41, 41, 52, 52, 63, 67, 78, 41, 45, 39, 39, 33, 30, 20, 17, 14, 10, 10, 6, 5, 4, 3, 2, 1, 1, 0, 0, 1
Offset: 0

Views

Author

Alois P. Heinz, Mar 06 2024

Keywords

Examples

			T(4,0) = 4: 1234, 12|34, 13|24, 14|23.
T(4,1) = 1: 1|234.
T(4,2) = 1: 134|2.
T(4,3) = 2: 124|3, 1|2|34.
T(4,4) = 2: 123|4, 1|24|3.
T(4,5) = 2: 1|23|4, 14|2|3.
T(4,6) = 1: 13|2|4.
T(4,7) = 1: 12|3|4.
T(4,10) = 1: 1|2|3|4.
Triangle T(n,k) begins:
   1;
   0, 1;
   1, 0, 0, 1;
   1, 1, 1, 1, 0, 0, 1;
   4, 1, 1, 2, 2, 2, 1, 1, 0, 0, 1;
  11, 4, 4, 5, 5, 6, 3, 3, 3, 3, 2, 1, 1, 0, 0, 1;
  ...

Links

Crossrefs

Column k=0 gives A000296.
Row sums give A000110.
Row lengths give A000124.
Reversed rows converge to A370946.
T(n,n) gives A370947.
Cf. A000217, A053632, A105479, A369596.

Programs

  • Maple
    h:= proc(n) option remember; `if`(n=0, 1,
      add(h(n-j)*binomial(n-1, j-1), j=2..n))
    end:
b:= proc(n, i, m) option remember; `if`(n>i*(i+1)/2, 0,
     `if`(n=0, h(m), b(n, i-1, m)+b(n-i, min(n-i, i-1), m-1)))
    end:
T:= (n, k)-> b(k, min(n, k), n):
seq(seq(T(n, k), k=0..n*(n+1)/2), n=0..7);
  • Mathematica
    h[n_] := h[n] = If[n == 0, 1,
    Sum[h[n-j]*Binomial[n-1, j-1], {j, 2, n}]];
b[n_, i_, m_] := b[n, i, m] = If[n > i*(i + 1)/2, 0,
    If[n == 0, h[m], b[n, i - 1, m] + b[n - i, Min[n - i, i - 1], m - 1]]];
T[n_, k_] := b[k, Min[n, k], n];
Table[Table[T[n, k], { k, 0, n*(n + 1)/2}], {n, 0, 7}] // Flatten (* Jean-François Alcover, Mar 12 2024, after Alois P. Heinz *)

Formula

Sum_{k=0..A000217(n)} k * T(n,k) = A105479(n+1).
T(n,A161680(n)) = A370946(n).
T(n,A000217(n)) = 1.

A124498 Triangle read by rows: T(n,k) is the number of set partitions of the set {1,2,...,n} containing k blocks of size 2 (0 <= k <= floor(n/2)).

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 6, 6, 3, 17, 20, 15, 53, 90, 45, 15, 205, 357, 210, 105, 871, 1484, 1260, 420, 105, 3876, 7380, 6426, 2520, 945, 18820, 39195, 33390, 18900, 4725, 945, 99585, 213180, 202950, 117810, 34650, 10395, 558847, 1242120, 1293435, 734580, 311850
Offset: 0

Views

Author

Emeric Deutsch, Nov 05 2006

Keywords

Comments

Row n contains 1+floor(n/2) terms. Row sums yield the Bell numbers A000110. T(n,0)=A097514(n). Sum(k*T(n,k), k=0..floor(n/2))=A105479(n+1).

Examples

			T(4,1)=6 because we have 12|3|4, 13|2|4, 14|2|3, 1|23|4, 1|24|3 and 1|2|34.
Triangle T(n,k) begins:
:      1;
:      1;
:      1,       1;
:      2,       3;
:      6,       6,       3;
:     17,      20,      15;
:     53,      90,      45,     15;
:    205,     357,     210,    105;
:    871,    1484,    1260,    420,    105;
:   3876,    7380,    6426,   2520,    945;
:  18820,   39195,   33390,  18900,   4725,   945;
:  99585,  213180,  202950, 117810,  34650, 10395;
: 558847, 1242120, 1293435, 734580, 311850, 62370, 10395;

Links

Crossrefs

Cf. A000110, A097514, A105479, A124503.
T(2n,n) gives A001147.

Programs

  • Maple
    G:=exp(exp(z)-1+(t-1)*z^2/2): Gser:=simplify(series(G,z=0,16)): for n from 0 to 13 do P[n]:=sort(n!*coeff(Gser,z,n)) od: for n from 0 to 13 do seq(coeff(P[n],t,k),k=0..floor(n/2)) od; # yields sequence in triangular form
# second Maple program:
with(combinat):
b:= proc(n, i) option remember; expand(`if`(n=0, 1,
      `if`(i<1, 0, add(multinomial(n, n-i*j, i$j)/j!*
      b(n-i*j, i-1)*`if`(i=2, x^j, 1), j=0..n/i))))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n$2)):
seq(T(n), n=0..15);  # Alois P. Heinz, Mar 08 2015
  • Mathematica
    d=Exp[Exp[x]-x^2/2!-1]; f[list_] := Select[list,#>0&]; Map[f, Transpose[Table[Range[0,12]! CoefficientList[Series[ x^(2k)/(k! 2!^k) *d, {x,0,12}], x], {k,0,5}]]]//Flatten (* Geoffrey Critzer, Nov 30 2011 *)

Formula

E.g.f.: exp(exp(z)-1+(t-1)z^2/2).
Generally the e.g.f. for set partitions containing k blocks of size p is: G(z,t) = exp(exp(z)-1+(t-1)z^p/p!) - Geoffrey Critzer, Nov 30 2011
Showing 1-10 of 12 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.