Displaying 1-10 of 13 results found.
Fourth right hand column of triangle A163940.
+20
4
1, 9, 52, 246, 1039, 4083, 15274, 55152, 193957, 668397, 2266816, 7589418, 25143355, 82571751, 269173078, 871958244, 2809322833, 9008574945, 28768068460, 91532284830, 290283189991, 917912770779, 2894936303362
FORMULA
G.f.: 1/((1-x)*(1-2*x)*(1-3*x)^2).
a(n) = (1/4)*(2^(n+5) + (2*n - 3)*3^(n+2) - 1).
a(n) = 9*a(n-1) - 29*a(n-2) + 39*a(n-3) - 18*a(n-4).
E.g.f.: (1/4)*(32*exp(2*x) + 27*(2*x-1)*exp(3*x) - exp(x)). - G. C. Greubel, Aug 13 2017
MATHEMATICA
LinearRecurrence[{9, -29, 39, -18}, {1, 9, 52, 246}, 30] (* or *) CoefficientList[ Series[1/((1-x)(1-2x)(1-3x)^2), {x, 0, 30}], x] (* Harvey P. Dale, Aug 14 2011 *)
PROG
(PARI) Vec(1/((1-x)*(1-2*x)*(1-3*x)^2) + O(x^30)) \\ Michel Marcus, Feb 12 2015
CROSSREFS
Equals the fourth right hand column of A163940. A163942 is another right hand column.
Fifth right hand column of triangle A163940.
+20
4
1, 14, 121, 834, 5037, 27918, 145777, 728858, 3526933, 16640262, 76952793, 350167122, 1572467389, 6984206846, 30735634369, 134202204426, 582040933605, 2509672804470, 10766469841705, 45982221941570, 195609944400781
FORMULA
G.f.: 1/((1-x)*(1-2*x)*(1-3*x)*(1-4*x)^2).
a(n) = (1/18)*(3^(n+6) + (3*n-10)*4^(n+3) - 9*2^(n+3) + 1).
a(n) = 14*a(n-1) - 75*a(n-2) + 190*a(n-3) - 224*a(n-4) + 96*a(n-5).
E.g.f.: (1/18)*( 729*exp(3*x) + 128*(6*x-5)*exp(4*x) - 72*exp(2*x) + exp(x)). - G. C. Greubel, Aug 13 2017
MATHEMATICA
CoefficientList[Series[1/((1 - x)*(1 - 2*x)*(1 - 3*x)*(1 - 4*x)^2), {x, 0, 50}], x] (* G. C. Greubel, Aug 13 2017 *) LinearRecurrence[{14, -75, 190, -224, 96}, {1, 14, 121, 834, 5037}, 30] (* Harvey P. Dale, Mar 09 2023 *)
PROG
(PARI) Vec(1/((1-x)*(1-2*x)*(1-3*x)*(1-4*x)^2) + O(x^30)) \\ Michel Marcus, Feb 12 2015
CROSSREFS
Equals the fifth right hand column of A163940. A163941 is another right hand column.
Third left hand column of triangle A163940.
+20
4
0, 3, 17, 52, 121, 240, 428, 707, 1102, 1641, 2355, 3278, 4447, 5902, 7686, 9845, 12428, 15487, 19077, 23256, 28085, 33628, 39952, 47127, 55226, 64325, 74503, 85842, 98427, 112346, 127690, 144553, 163032, 183227, 205241, 229180, 255153
FORMULA
G.f.: x*(3 + 2*x - 3*x^2 + x^3)/(1-x)^5.
a(n)= (2*n + 45*n^2 + 22*n^3 + 3*n^4)/24.
a(n) = 5*a(n-1) - 10*a(n-2) + 10*a(n-3) - 5*a(n-4) + a(n-5).
E.g.f.: (1/24)*x*(72 + 132*x + 40*x^2 + 3*x^3)*exp(x). - G. C. Greubel, Aug 13 2017
MATHEMATICA
LinearRecurrence[{5, -10, 10, -5, 1}, {0, 3, 17, 52, 121}, 40] (* Harvey P. Dale, Feb 25 2017 *)
PROG
(PARI) x='x+O('x^50); concat([0], Vec(x*(3 +2*x -3*x^2 +x^3)/(1-x)^5)) \\ G. C. Greubel, Aug 13 2017
CROSSREFS
Equals the third left hand column of A163940. A163944 is another left hand column.
Fourth left hand column of triangle A163940.
+20
4
0, 4, 49, 246, 834, 2250, 5214, 10829, 20696, 37044, 62875, 102124, 159834, 242346, 357504, 514875, 725984, 1004564, 1366821, 1831714, 2421250, 3160794, 4079394, 5210121, 6590424, 8262500, 10273679, 12676824, 15530746, 18900634, 22858500
FORMULA
G.f.: x*(4 +21*x -13*x^2 +x^3 +3*x^4 -x^5)/(1-x)^7.
a(n) = (10*n^2 +107*n^3 +61*n^4 +13*n^5 +n^6)/48.
a(n) = 7*a(n-1)-21*a(n-2)+35*a(n-3)-35*a(n-4)+21*a(n-5)-7*a(n-6)+a(n-7).
E.g.f.: (1/48)*x*(192 + 984*x + 888*x^2 + 256*x^3 + 28*x^4 + x^5)*exp(x). - G. C. Greubel, Aug 13 2017
MATHEMATICA
CoefficientList[Series[x*(4 + 21*x - 13*x^2 + x^3 + 3*x^4 - x^5)/(1 - x)^7, {x, 0, 50}], x] (* G. C. Greubel, Aug 13 2017 *) LinearRecurrence[{7, -21, 35, -35, 21, -7, 1}, {0, 4, 49, 246, 834, 2250, 5214}, 40] (* Harvey P. Dale, Apr 29 2019 *)
PROG
(PARI) x='x+O('x^50); concat([0], Vec(x*(4 +21*x -13*x^2 +x^3 +3*x^4 -x^5)/(1-x)^7)) \\ G. C. Greubel, Aug 13 2017
CROSSREFS
Equals the fourth left hand column of A163940. A163943 is another left hand column.
Bell or exponential numbers: number of ways to partition a set of n labeled elements.
(Formerly M1484 N0585)
+10
1335
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
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 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
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 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)
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)
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 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 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)
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 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
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_{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
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.
J. 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.
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
S. Ainley, Problem 19, QARCH, No. IV, Nov 03, 1980. [Annotated scanned copy] H. W. Becker, Rooks and rhymes, Math. Mag., 22 (1948/49), 23-26. [Annotated scanned copy] M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, arXiv:math/0205301 [math.CO], 2002; Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to arXiv version] M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to Lin. Alg. Applic. version together with omitted figures] David Callan and Emeric Deutsch, The Run Transform, arXiv preprint arXiv:1112.3639 [math.CO], 2011. A. M. Odlyzko, Asymptotic enumeration methods, pp. 1063-1229 of R. L. Graham et al., eds., Handbook of Combinatorics, 1995; see Examples 5.4 and 12.2. ( pdf, ps) Z.-W. Sun, Conjectures involving arithmetical sequences, Number Theory: Arithmetic in Shangrila (eds., S. Kanemitsu, H.-Z. Li and J.-Y. Liu), Proc. the 6th China-Japan Sem. Number Theory (Shanghai, August 15-17, 2011), World Sci., Singapore, 2013, pp. 244-258. - From N. J. A. Sloane, Dec 28 2012 Dekai Wu, K. Addanki and M. Saers, Modeling Hip Hop Challenge Response Lyrics as Machine Translation, in Sima'an, K., Forcada, M.L., Grasmick, D., Depraetere, H., Way, A. (eds.) Proceedings of the XIV Machine Translation Summit (Nice, September 2-6, 2013), p. 109-116.
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).
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 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) = (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 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 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 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.: 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/LambertW(n)-1-n) / (sqrt(1+LambertW(n)) * LambertW(n)^n). - Vaclav Kotesovec, Nov 13 2015 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(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 a(n) is the n-th derivative of e^e^x divided by e at point x=0. - Joan Ludevid, Nov 05 2024
EXAMPLE
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)
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
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 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 *) 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 *)
PROG
(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 (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 (Python) # The objective of this implementation is efficiency.
# m -> [a(0), a(1), ..., a(m)] for m > 0.
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
(Python)
# requires python 3.2 or higher. Otherwise use def'n of accumulate in python docs.
from itertools import accumulate
for _ in range(20):
blist = list(accumulate([b]+blist))
b = blist[-1]
(Python)
from sympy import bell
(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)
(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]
(Haskell)
(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
(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
CROSSREFS
Equals row sums of triangle A008277 (Stirling subset numbers). 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. Cf. A054767 (period of this sequence mod n).
a(n) = n*a(n-1) + (n-1)*a(n-2), a(0) = 1, a(1) = 1.
(Formerly M2905 N1166)
+10
112
1, 1, 3, 11, 53, 309, 2119, 16687, 148329, 1468457, 16019531, 190899411, 2467007773, 34361893981, 513137616783, 8178130767479, 138547156531409, 2486151753313617, 47106033220679059, 939765362752547227, 19690321886243846661, 432292066866171724421
COMMENTS
a(n) counts permutations of [1,...,n+1] having no substring [k,k+1]. - Len Smiley, Oct 13 2001 Also, for n > 0, determinant of the tridiagonal n X n matrix M such that M(i,i)=i and for i=1..n-1, M(i,i+1)=-1, M(i+1,i)=i. - Mario Catalani (mario.catalani(AT)unito.it), Feb 04 2003
Also, for n > 0, maximal permanent of a nonsingular n X n (0,1)-matrix, which is achieved by the matrix with just n-1 0's, all on main diagonal. [For proof, see next entry.] - W. Edwin Clark, Oct 28 2003 Proof from Richard Brualdi and W. Edwin Clark, Nov 15 2003: Let n >= 4. Take an n X n (0,1)-matrix A which is nonsingular. It has t >= n-1, 0's, otherwise there will be two rows of all 1's. Let B be the matrix obtained from A by replacing t-(n-1) of A's 0's with 1's. Let D be the matrix with all 1's except for 0's in the first n-1 positions on the diagonal. This matrix is easily seen to be non-singular. Now we have per(A) < = per(B) < = per (D), where the first inequality follows since replacing 0's by 1's cannot decrease the permanent and the second from Corollary 4.4 in the Brualdi et al. reference, which shows that per(D) is the maximum permanent of ANY n X n matrix with n -1 0's. Corollary 4.4 requires n >= 4. a(n) for n < 4 can be computed directly. With offset 1, permanent of (0,1)-matrix of size n X (n+d) with d=1 and n zeros not on a line. This is a special case of Theorem 2.3 of Seok-Zun Song et al., Extremes of permanents of (0,1)-matrices, pp. 201-202. - Jaap Spies, Dec 12 2003 Number of fixed-point-free permutations of n+2 that begin with a 2; e.g., for 1234, we have 2143, 2341, 2413, so a(2)=3. Also number of permutations of 2..n+2 that have no agreements with 1..n+1. E.g., for 123 against permutations of 234, we have 234, 342 and 432. Compare A047920. - Jon Perry, Jan 23 2004. [This can be proved by the standard argument establishing that d(n+2) = (n+1)(d(n+1)+d(n)) for derangements A000166 (n+1 choices of where 1 goes, then either 1 is in a transposition, or in a cycle of length at least 3, etc.). - D. G. Rogers, Aug 28 2006] Stirling transform of A006252(n+1)=[1,1,2,4,14,38,...] is a(n)=[1,3,11,53,309,...]. - Michael Somos, Mar 04 2004 a(n+1) is the sequence of numerators of the self-convergents to 1/(e-2); see A096654. - Clark Kimberling, Jul 01 2004 Euler's interpretation was "fixedpoint-free permutations beginning with 2" and he listed the terms up to 148329 (although he was blind at the time). - Don Knuth, Jan 25 2007 This sequence appears in the analysis of Euler's divergent series 1 - 1! + 2! - 3! + 4! ... by Lacroix, see Hardy. For information about this and related divergent series see A163940. - Johannes W. Meijer, Oct 16 2009 a(n), n >= 1, enumerates also the ways to distribute n beads, labeled differently from 1 to n, over a set of (unordered) necklaces, excluding necklaces with exactly one bead, and one open cord allowed to have any number of beads. Each beadless necklace as well as the beadless cord contributes a factor 1 in the counting, e.g., a(0):=1*1=1. There are k! possibilities for the cord with k>=0 beads, which means that the two ends of the cord should be considered as fixed, in short: a fixed cord. This produces for a(n) the exponential (aka binomial) convolution of the sequences {n!= A000142(n)} and the subfactorials { A000166(n)}. See the formula below. Alternatively, the e.g.f. for this problem is seen to be (exp(-x)/(1-x))*(1/(1-x)), namely the product of the e.g.f.s for the subfactorials (from the unordered necklace problem, without necklaces with exactly one bead) and the factorials (from the fixed cord problem). Therefore the recurrence with inputs holds also. a(0):=1. This comment derives from a family of recurrences found by Malin Sjodahl for a combinatorial problem for certain quark and gluon diagrams (Feb 27 2010). - Wolfdieter Lang, Jun 02 2010 a(n) = (n-1)a(n-1) + (n-2)a(n-2) gives the same sequence offset by a 1. - Jon Perry, Sep 20 2012 Also, number of reduced 2 X (n+2) Latin rectangles. - A.H.M. Smeets, Nov 03 2013 If we partition the permutations of [n+2] in A000166 according to their starting digit, we will get (n+1) equinumerous classes each of size a(n) (the class starting with the digit 1 is empty since no derangement starts with 1). Hence, A000166(n+2)=(n+1)*a(n), so a(n) is the size of each nonempty class of permutations of [n+2] in A000166. For example, for n=3 we have 44=4*11 (see link). - Enrique Navarrete, Jan 11 2017 For n >= 1, the number of circular permutations (in cycle notation) on [n+2] that avoid substrings (j,j+2), 1 <= j <= n. For example, for n=2, the 3 circular permutations in S4 that avoid substrings {13,24} are (1234),(1423),(1432). Note that each of these circular permutations represent 4 permutations in one-line notation (see link 2017). - Enrique Navarrete, Feb 15 2017 The sequence a(n) taken modulo a positive integer k is periodic with exact period dividing k when k is even and dividing 2*k when k is odd. This follows from the congruence a(n+k) = (-1)^k*a(n) (mod k) holding for all n and k, which in turn is easily proved by induction making use of the given recurrences. - Peter Bala, Nov 21 2017
REFERENCES
Richard A. Brualdi and Herbert J. Ryser, Combinatorial Matrix Theory, Camb. Univ. Press, 1991, Section 7.2, p. 202.
Charalambos A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC, Boca Raton, Florida, 2002, p. 179, Table 5.4 and p. 177 (5.1).
CRC Handbook of Combinatorial Designs, 1996, p. 104.
F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, pp. 263-264. See Table 7.5.1, row 0; also Table 7.6.1, row 0.
John Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 188.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
N. Ya. Vilenkin, Combinatorics, pp. 54 - 56, Academic Press, 1971. Caravan in the Desert, E_n = a(n-1), n >= 1.
LINKS
Leonhard Euler, Recherches sur une nouvelle espèce des quarrés magiques, Verhandelingen uitgegeven door het zeeuwsch Genootschap der Wetenschappen te Vlissingen, 9 (1782), 85-239, on page 235 in section 152. This is paper E530 in Enestrom's index of Euler's works. The sequence appears on page 389 of Euler's Opera Omnia, series I, volume 7. [From D. E. Knuth] Florian Herzig, Problem 2330, Crux Mathematicorum, Vol. 24, No. 3 (1998), p. 176; Solution to Problem 2330, by Con Amore Problem Group, ibid., Vol. 25, No. 3 (1999), pp. 183-185. Brian Hopkins, Euler's Enumerations, Enumerative Combinatorics and Applications, Vol. 1, No. 1 (2021), Article #S1H1.
FORMULA
E.g.f.: exp(-x)/(1-x)^2.
a(n) = Sum_{k=0..n} (-1)^k * (n-k+1) * n!/k!. - Len SmileyInverse binomial transform of (n+1)!. - Robert A. Stump (bee_ess107(AT)yahoo.com), Dec 09 2001
Apparently lim_{n->infinity} log(n) - log(a(n))/n = 1. - Gerald McGarvey, Jun 12 2004 a(n) = (n*(n+2)*a(n-1) + (-1)^n)/(n+1) for n >= 1, a(0)=1. See the Charalambides reference.
a(n) = GAMMA(n+3,-1)*exp(-1)/(n+1) (incomplete Gamma function). - Mark van Hoeij, Nov 11 2009 If we take b(n) = (-1)^(n+1)*a(n) for n > 0, then for n > 1 the arithmetic mean of the first n terms is -b(n-1). - Franklin T. Adams-Watters, May 20 2010 a(n) = hypergeometric([2,-n],[],1)*(-1)^n = KummerU(2,3+n,-1)*(-1)^n. See the Abramowitz-Stegun handbook (for the reference see e.g. A103921) p. 504, 13.1.10, and for the recurrence p. 507, 13.4.16. - Wolfdieter Lang, May 20 2010 a(n) = n!*(1 + Sum_{k=0..n-2} sf(n-k)/(n-k)!) with the subfactorials sf(n):= A000166(n) (this follows from the exponential convolution). - Wolfdieter Lang, Jun 02 2010 a(n) = 1/(n+1)*floor(((n+1)!+1)/e). - Gary Detlefs, Jul 11 2010 G.f.: 1/(1-x-2x^2/(1-3x-6x^2/(1-5x-12x^2/(1-7x-20x^2/(1-.../(1-(2n+1)x-(n+1)(n+2)x^2/(1-... (continued fraction). - Paul Barry, Apr 11 2011 G.f.: hypergeom([1,2],[],x/(x+1))/(x+1). - Mark van Hoeij, Nov 07 2011 Continued fractions:
E.g.f. 1/E(0) where E(k) = 1 - 2*x/(1 + x/(2 - x - 2/(1 + x*(k+1)/E(k+1)))).
G.f.: S(x)/x - 1/x = Q(0)/x - 1/x where S(x) = Sum_{k>=0} k!*(x/(1+x))^k, Q(k) = 1 + (2*k + 1)*x/(1 + x - 2*x*(1+x)*(k+1)/(2*x*(k+1) + (1+x)/Q(k+1))).
G.f.: 1/Q(0) where Q(k) = 1 + x - x*(k+2)/(1 - x*(k+1)/Q(k+1)).
G.f.: 1/x/Q(0) where Q(k) = 1/x - (2*k+1) - (k+2)*(k+1)/Q(k+1).
G.f.: (1+x)/(x*Q(0)) - 1/x where Q(k) = 1 - 2*k*x - x^2*(k + 1)^2/Q(k+1).
G.f.: 2/x/G(0) - 1/x where G(k) = 1 + 1/(1 - x*(2*k+2)/(x*(2*k+1) - 1 + x*(2*k+2)/ G(k+1))).
G.f.: ((Sum_{k>=0} k!*(x/(1+x))^k) - 1)/x = Q(0)/(2*x) - 1/x where Q(k) = 1 + 1/(1 - x*(k+1)/(x*(k+1) + (1+x)/Q(k+1))).
G.f.: W(0) where W(k) = 1 - x*(k+1)/(x*(k+1) - 1/(1 - x*(k+2)/(x*(k+1) - 1/W(k+1)))).
G.f.: G(0)/(1-x) where G(k) = 1 - x^2*(k+1)*(k+2)/(x^2*(k+1)*(k+2) - (1-x*(1+2*k))*(1-x*(3+2*k))/G(k+1)). (End)
The sequence b(n) := n!*(n + 2) satisfies the defining recurrence for a(n) but with the starting values b(0) = 2 and b(1) = 3. This leads to the finite continued fraction expansion a(n) = n!*(n+2)*( 1/(2 + 1/(1 + 1/(2 + 2/(3 + ... + (n-1)/n)))) ), valid for n >= 2.
Also a(n) = n!*(n+2)*( Sum_{k = 0..n} (-1)^k/(k+2)! ). Letting n -> infinity gives the infinite continued fraction expansion 1/e = 1/(2 + 1/(1 + 1/(2 + 2/(3 + ... + (n-1)/(n + ...)))) ) due to Euler. (End)
0 = a(n)*(+a(n+1) + 2*a(n+2) - a(n+3)) + a(n+1)*(+2*a(n+2) - a(n+3)) + a(n+2)*(+a(n+2)) if n >= 0. - Michael Somos, May 06 2014 a(n) = A000240(n) + A000240(n+1), n >= 1. Let D(n) = A000240(n) be the permutations of [n] having no substring in {12,23,...,(n-1)n,n1}. Let d(n) = a(n-1) be the permutations of [n] having no substring in {12,23,...,(n-1)n}. Let d_n1 = A000240(n-1) be the permutations of [n] that have the substring n1 but no substring in {12,23,...,(n-1)n}. Then the link "Forbidden Patterns" shows the bijection d_n1 ~ D(n-1) and since dn = d_n1 U D(n), we get dn = D(n-1) U D(n). Taking cardinalities we get the result for n-1, i.e., a(n-1) = A000240(n-1) + A000240(n). For example, for n=4 in this last equation, we get a(4) = 11 = 3+8. - Enrique Navarrete, Jan 16 2017 a(n) = (n+1)!*hypergeom([-n], [-n-1], -1). - Peter Luschny, Nov 02 2018 Sum_{n>=0} (-1)^n*n!/(a(n)*a(n+1)) = e - 2 (Herzig, 1998). - Amiram Eldar, Mar 07 2022
EXAMPLE
a(3)=11: 1 3 2 4; 1 4 3 2; 2 1 4 3; 2 4 1 3; 3 2 1 4; 3 2 4 1; 4 1 3 2; 4 2 1 3; 4 3 2 1; 2 4 3 1; 3 1 4 2. The last two correspond to (n-1)*a(n-2) since they contain a [j,n+1,j+1].
Cord-necklaces problem. For n=4 one considers the following weak two part compositions of 4: (4,0), (2,2), (1,3), and (0,4), where (3,1) does not appear because there are no necklaces with 1 bead. These compositions contribute respectively 4!*1, (binomial(4,2)*2)*sf(2), (binomial(4,1)*1)*sf(3), and 1*sf(4) with the subfactorials sf(n):= A000166(n) (see the necklace comment there). This adds up as 24 + 6*2 + 4*2 + 9 = 53 = a(4). - Wolfdieter Lang, Jun 02 2010 G.f. = 1 + x + 3*x^2 + 11*x^3 + 53*x^4 + 309*x^5 + 2119*x^6 + 16687*x^7 + ...
MAPLE
a := n -> hypergeom([2, -n], [], 1)*(-1)^n:
seq(simplify(KummerU(-n, -n-1, -1)), n=0..21); # Peter Luschny, May 10 2022
MATHEMATICA
c = CoefficientList[Series[Exp[ -z]/(1 - z)^2, {z, 0, 30}], z]; For[n = 0, n < 31, n++; Print[c[[n]]*(n - 1)! ]]
Table[Subfactorial[n] + Subfactorial[n + 1], {n, 0, 20}] (* Zerinvary Lajos, Jul 09 2009 *) RecurrenceTable[{a[n]==n a[n-1]+(n-1)a[n-2], a[0]==1, a[1]==1}, a[n], {n, 20}] (* Harvey P. Dale, May 10 2011 *) a[ n_] := If[ n < 0, 0, Round[ n! (n + 2) / E]] (* Michael Somos, Jun 01 2013 *) a[ n_] := If[ n < 0, 0, n! SeriesCoefficient[ Exp[ -x] / (1 - x)^2, {x, 0, n}]] (* Michael Somos, Jun 01 2013 *) a[ n_] := If[ n < 0, 0, (-1)^n HypergeometricPFQ[ {- n, 2}, {}, 1]] (* Michael Somos, Jun 01 2013 *) sa[k_Integer]/; k>=2 := SparseArray[{{i_, i_} -> i, Band[{2, 1}] -> -1, {i_, j_} /; (i == j - 1) :> i}, {k, k}]; {1, 1}~Join~Array[Det[sa[#]] &, 20, 2] (* Shenghui Yang, Oct 15, 2024 *)
PROG
(PARI) {a(n) = if( n<0, 0, contfracpnqn( matrix( 2, n, i, j, j - (i==1)))[1, 1])};
(PARI) {a(n) = if( n<0, 0, n! * polcoeff( exp( -x + x * O(x^n)) / (1 - x)^2, n))};
(Sage) from sage.combinat.sloane_functions import ExtremesOfPermanentsSequence2
e = ExtremesOfPermanentsSequence2()
it = e.gen(1, 1, 1)
[next(it) for i in range(20)]
(Haskell)
a000255 n = a000255_list !! n
a000255_list = 1 : 1 : zipWith (+) zs (tail zs) where
zs = zipWith (*) [1..] a000255_list
(Magma) I:=[1, 3]; [1] cat [n le 2 select I[n] else n*Self(n-1)+(n-1)*Self(n-2): n in [1..30]]; // Vincenzo Librandi, Aug 09 2018
CROSSREFS
A052655 gives occurrence count for non-singular (0, 1)-matrices with maximal permanent, A089475 number of different values of permanent, A089480 occurrence counts for permanents all non-singular (0, 1)-matrices, A087982, A087983.
1, 1, 3, 9, 31, 121, 523, 2469, 12611, 69161, 404663, 2512769, 16485691, 113842301, 824723643, 6249805129, 49416246911, 406754704841, 3478340425563, 30845565317189, 283187362333331, 2687568043654521, 26329932233283223, 265946395403810289, 2766211109503317451
COMMENTS
Number of permutations beginning with 21 and avoiding 1-23. - Ralf Stephan, Apr 25 2004 Originally defined as main diagonal of an array of binomial recurrence coefficients (see Gould and Quaintance). Also second-from-right diagonal of triangle A121207. The divergent series g(x=1,m) = 1^m*1! - 2^m*2! + 3^m*3! - 4^m*4! + ..., m=>-1, is related to the sequence given above. For m=-1 this series dates back to Euler. We discovered that g(x=1,m) = (-1)^m * ( A040027(m) - A000110(m+1) * A073003) with A073003 Gompertz's constant and A000110 the Bell numbers, see A163940; A040027(m = -1) = 0. - Johannes W. Meijer, Oct 16 2009 Compare the o.g.f. to the o.g.f. B(x) of the Bell numbers, where B(x) = 1 + x*B(x/(1-x))/(1-x). - Paul D. Hanna, Mar 23 2012 a(n) is the number of set partitions of {1,2,...,n+1} in which the last block is a singleton: the blocks are arranged in order of their least element. An example is given below. - Peter Bala, Dec 17 2014
LINKS
Walaa Asakly, Aubrey Blecher, Charlotte Brennan, Arnold Knowfmacher, Toufik Mansour, and Stephan Wagner, Set partition asymptotics and a conjecture of Gould and Quaintance, Journal of Mathematical Analysis and Applications, Volume 416, Issue 2, 15 August 2014, Pages 672-682.
FORMULA
a(n) = b(n-2), n>1, b(n) = Sum_{k = 1..n} binomial(n, k-1)*b(n-k), b(0) = 1. - Vladeta Jovovic, Apr 28 2001 With offset 0, e.g.f.: x + exp(exp(x)) * Integral_{t=0..x} t*exp(-exp(t)+t) dt (fits the recurrence up to n=215). - Ralf Stephan, Apr 25 2004 Recurrence: a(1)=1, a(2)=1, for n > 2, a(n) = n - 1 + Sum_{j=2..n-1} binomial(n-1, j)*a(j)) [gives a(n+1)]. - Jon Perry, Apr 26 2005 O.g.f. satisfies: A(x) = 1 + x*A( x/(1-x) ) / (1-x)^2. - Paul D. Hanna, Mar 23 2012 Starting from A(x) = 1 + O(x) (big Oh notation) we can get a series expansion for the o.g.f. by repeatedly applying the above functional equation of Hanna: A(x) = 1 + O(x) = 1 + x/(1-x)^2 + O(x^2) = 1 + x/(1-x)^2 + x^2/((1-x)*(1-2*x)^2) + O(x^3) = ... = 1 + x/(1-x)^2 + x^2/((1-x)*(1-2*x)^2) + x^3/((1-x)*(1-2*x)*(1-3*x)^2) + x^4/((1-x)*(1-2*x)*(1-3*x)*(1-4*x)^2) + ....
a(n) = Sum_{k = 0..n} ( Sum_{j = k..n} Stirling2(j,k)*k^(n-j) ).
EXAMPLE
a(3) = 9: Arranging the blocks of the 15 set partitions of {1,2,3,4} in order of their least element we find 9 set partitions for which the last block is a singleton, namely, 123|4, 124|3, 134|2, 1|24|3, 1|23|4, 12|3|4, 13|2|4, 14|2|3, and 1|2|3|4. - Peter Bala, Dec 17 2014
MAPLE
option remember;
if n = 0 then
1;
else
add(binomial(n, k-1)*procname(n-k), k=1..n) ;
end if;
MATHEMATICA
a[0] = a[1] = 1; a[n_] := a[n] = Sum[Binomial[n, k + 1]*a[k], {k, 0, n - 1}]; Table[a[n], {n, 0, 22}] (* Jean-François Alcover, Jul 02 2013 *) Rest[CoefficientList[Assuming[Element[x, Reals], Series[E^E^x*(ExpIntegralEi[-E^x] - ExpIntegralEi[-1]), {x, 0, 20}]], x] * Range[0, 20]!] (* Vaclav Kotesovec, Feb 28 2014 *)
PROG
(PARI) {a(n)=local(A=1+x); for(i=1, n, A=1+x*subst(A, x, x/(1-x+x*O(x^n)))/(1-x)^2); polcoeff(A, n)} /* Paul D. Hanna, Mar 23 2012 */ (Haskell)
(Python)
# The function Gould_diag is defined in A121207. A040027_list = lambda size: Gould_diag(2, size)
Decimal expansion of -Ei(-1), negated exponential integral at -1.
+10
45
2, 1, 9, 3, 8, 3, 9, 3, 4, 3, 9, 5, 5, 2, 0, 2, 7, 3, 6, 7, 7, 1, 6, 3, 7, 7, 5, 4, 6, 0, 1, 2, 1, 6, 4, 9, 0, 3, 1, 0, 4, 7, 2, 9, 3, 4, 0, 6, 9, 0, 8, 2, 0, 7, 5, 7, 7, 9, 7, 8, 6, 1, 3, 0, 7, 3, 5, 6, 8, 6, 9, 8, 5, 5, 9, 1, 4, 1, 5, 4, 4, 7, 2, 2, 2, 1, 0, 2, 5, 1, 0, 3, 5, 1, 3, 7, 2, 4, 9, 9, 5, 4, 7, 5, 8
COMMENTS
The divergent series g(x=1,m) = 1^m*1! - 2^m*2! + 3^m*3! - 4^m*4! + ..., m=>-1, is closely related to the value of -Ei(-1). We discovered that g(x=1,m) = (-1)^m*( A040027(m) - A000110(m+1)*Ei(1,1)*exp(1)), see A163940. We observe that Ei(1,1) = E(1,1,1) = -Ei(-1) is the constant given above and that Ei(1,1)*exp(1) = A073003 is Gompertz's constant. - Johannes W. Meijer, Oct 16 2009
FORMULA
-Ei(-n) = Integral_{a=n..oo} ( Integral_{b=1..oo} 1/e^(a*b) db ) da , n>0 (According to Mathematica). - Mats Granvik, May 25 2013 Equals Integral_{x=1..oo} log(x)/exp(x) dx.
Equals Integral_{x=0..oo} exp(-exp(x)) dx.
Equals Integral_{x=0..oo} x*exp(x-exp(x)) dx. (End)
Equals lim_{n -> oo} Integral_{x = 0..n} x^(n-1)/(1 + x)^n dx = lim_{n -> oo} ( log(n+1) + Sum_{k = 0..n-2} (-1)^(n-k-1)* binomial(n-1, k)*((n + 1)^(k+1-n) - 1)/(k + 1 - n) ).
Alternatively, equals lim_{n -> oo} Sum_{k >= n} (n/(n + 1))^k/k = lim_{n -> oo} ( log(1/(1 - x)) - Sum_{k = 1..n-1} x^k/k ), where x = n/(n+1).
More generally, for alpha > 0, -Ei(-alpha) = lim_{n -> oo} Integral_{x = 0..n/alpha} x^(n-1)/(1 + x)^n dx. (End)
EXAMPLE
0.219383934395520273677163775460121649031047293406908207577978613...
With n := 10^6, Integral_{x = 0..n} x^(n-1)/(1 + x)^n dx = 0.21938(43...). - Peter Bala, Jun 19 2024
MATHEMATICA
RealDigits[ ExpIntegralE[1, 1], 10, 105][[1]]
a(n) = Product_{p prime} p^{ Sum_{k>=0} floor[(n-1)/((p-1)p^k)]}.
+10
38
1, 2, 24, 48, 5760, 11520, 2903040, 5806080, 1393459200, 2786918400, 367873228800, 735746457600, 24103053950976000, 48206107901952000, 578473294823424000, 1156946589646848000, 9440684171518279680000, 18881368343036559360000, 271211974879377138647040000
COMMENTS
LCM of denominators of the coefficients of x^n*z^k in {-log(1-x)/x}^z as k=0..n, as described by triangle A075264. Denominators of integer-valued polynomials on prime numbers (with degree n): 1/a(n) is a generator of the ideal formed by the leading coefficients of integer-valued polynomials on prime numbers with degree less than or equal to n.
Also the least common multiple of the orders of all finite subgroups of GL_n(Q) [Minkowski]. Schur's notation for the sequence is M_n = a(n+1). - Martin Lorenz (lorenz(AT)math.temple.edu), May 18 2005
This sequence also occurs in algebraic topology where it gives the denominators of the Laurent polynomials forming a regular basis for K*K, the hopf algebroid of stable cooperations for complex K-theory. Several different equivalent formulas for the terms of the sequence occur in the literature. An early reference is K. Johnson, Illinois J. Math. 28(1), 1984, pp.57-63 where it occurs in lines 1-5, page 58. A summary of some of the other formulas is given in the appendix to K. Johnson, Jour. of K-theory 2(1), 2008, 123-145. - Keith Johnson (johnson(AT)mscs.dal.ca), Nov 03 2008
a(n) is divisible by n!, by Legendre's formula for the highest power of a prime that divides n!. Also, a(n) is divisible by (n+1)! if and only if n+1 is not prime. - Jonathan Sondow, Jul 23 2009 Triangle A163940 is related to the divergent series 1^m*1! - 2^m*2! + 3^m*3! - 4^m*4! + ... for m =>-1. The left hand columns of this triangle can be generated with the MC polynomials, see A163972. The Minkowski numbers appear in the denominators of these polynomials. - Johannes W. Meijer, Oct 16 2009 Unsigned Stirling numbers of the first kind as [s + k, k] (Karamata's notation) where k = {0, 1, 2, ...} and s is in general complex results in Pochhammer[s,k]*(integer coefficient polynomial of (k-1) degree in s) / M[k], where M[k] is the least common multiple of the orders of all finite groups of n x n-matrices over rational numbers (Minkowiski's theorem) which is sequence A053657. - Lorenz H. Menke, Jr., Feb 02 2010 Given a subset S of the integers Z, Bhargava has shown how to associate with S a generalized factorial function, denoted n!_S, which shares many properties of the classical factorial function n!.
The present sequence is the generalized factorial function n!_S associated with the set of primes S = {2,3,5,7,...}. The associated generalized exponential function E(x) = Sum_{n>=1} x^(n-1)/a(n) vanishes at x = -2: i.e. Sum_{n>=1} (-2)^n/a(n) = 0.
For the table of associated generalized binomial coefficients n!_S/(k!_S*(n-k)!_S) see A186430. This sequence is related to the Bernoulli polynomials in two ways [Chabert and Cahen]:
(2) (t/(exp(t)-1))^x = sum {n = 0..inf} P(n,x)*t^n/a(n+1),
where the P(n,x) are primitive polynomials in the ring Z[x].
If p_1,...,p_n are any n primes then the product of their pairwise differences Product_{i<j} (p_i - p_j) is a multiple of a(1)*a(2)*...*a(n-1).
(End)
LCM of denominators of the coefficients of S(m+n-1,m) as polynomial in m of degree 2*(n-1), as described by triangle A202339. - Vladimir Shevelev, Dec 17 2011 Sometimes called "Minkowski numbers" (e.g., by Guralnick and Lorenz), after the German mathematician Hermann Minkowski (1864-1909). - Amiram Eldar, Aug 24 2024
REFERENCES
Jean-Luc Chabert, Scott T. Chapman, and William W. Smith, A basis for the ring of polynomials integer-valued on prime numbers, in: Daniel Anderson (ed.), Factorization in integral domains, Lecture Notes in Pure and Appl. Math. 189, Dekker, New York, 1997.
LINKS
Robert M. Guralnick and Martin Lorenz, Orders of Finite Groups of Matrices, in: William Chin, James Osterburg and Declan Quinn (eds.), Groups, Rings and Algebras, Contemporary Mathematics, Vol. 420 (2006), pp. 141-161; arXiv preprint, arXiv:math/0511191 [math.GR], 2005; author's link.
FORMULA
a(n) = denominator([y^(n-1)] (y/(exp(y)-1))^x). - Peter Luschny, May 13 2019
MAPLE
A053657 := proc(n) local P, p, q, s, r;
P := select(isprime, [$2..n]); r:=1;
for p in P do s := 0; q := p-1;
do if q > (n-1) then break fi;
s := s + iquo(n-1, q); q := q*p; od;
ser := series((y/(exp(y)-1))^x, y, 20): a := n -> denom(coeff(ser, y, n-1)):
MATHEMATICA
m = 16; s = Expand[Normal[Series[(-Log[1-x]/x)^z, {x, 0, m}]]];
a[n_, k_] := Denominator[ Coefficient[s, x^n*z^k]];
Prepend[Apply[LCM, Table[a[n, k], {n, m}, {k, n}], {1}], 1]
a[n_] := Product[p^Sum[Floor[(n-1)/((p-1) p^k)], {k, 0, n}], {p, Prime[ Range[n] ]}]; Array[a, 30] (* Jean-François Alcover, Nov 22 2016 *)
PROG
(PARI) {a(n)=local(X=x+x^2*O(x^n), D); D=1; for(j=0, n-1, D=lcm(D, denominator( polcoeff(polcoeff((-log(1-X)/x)^z+z*O(z^j), j, z), n-1, x)))); return(D)} /* Paul D. Hanna, Jun 27 2005 */ (PARI) {a(n)=prod(i=1, #factor(n!)~, prime(i)^sum(k=0, #binary(n), floor((n-1)/((prime(i)-1)*prime(i)^k))))} /* Paul D. Hanna, Jun 27 2005 */ (PARI)
S(n, p) = {
my(acc = 0, tmp = p-1);
while (tmp < n, acc += floor((n-1)/tmp); tmp *= p);
return(acc);
};
a(n) = {
my(rv = 1);
forprime(p = 2, n, rv *= p^S(n, p));
return(rv);
};
a(n) = n*a(n-1) + (n-2)*a(n-2), with a(0) = 0, a(1) = 1.
(Formerly M1791 N0706)
+10
34
0, 1, 2, 7, 32, 181, 1214, 9403, 82508, 808393, 8743994, 103459471, 1328953592, 18414450877, 273749755382, 4345634192131, 73362643649444, 1312349454922513, 24796092486996338, 493435697986613143, 10315043624498196944
COMMENTS
With offset 1, permanent of (0,1)-matrix of size n X (n+d) with d=2 and n zeros not on a line. This is a special case of Theorem 2.3 of Seok-Zun Song et al. Extremes of permanents of (0,1)-matrices, pp. 201-202. - Jaap Spies, Dec 12 2003 Starting (1, 2, 7, 32, ...) = inverse binomial transform of A001710 starting (1, 3, 12, 60, 360, 2520, ...). - Gary W. Adamson, Dec 25 2008 This sequence appears in Euler's analysis of the divergent series 1 - 1! + 2! - 3! + 4! ..., see Sandifer. For information about this and related divergent series see A163940. - Johannes W. Meijer, Oct 16 2009 a(n+1)=:b(n), n>=1, enumerates the ways to distribute n beads labeled differently from 1 to n, over a set of (unordered) necklaces, excluding necklaces with exactly one bead, and two indistinguishable, ordered, fixed cords, each allowed to have any number of beads. Beadless necklaces as well as beadless cords contribute each a factor 1 in the counting, e.g., b(0):= 1*1 = 1. See A000255 for the description of a fixed cord with beads. This produces for b(n) the exponential (aka binomial) convolution of the subfactorial sequence { A000166(n)} and {(n+1)!}={ A000042(n+1)}. This follows from the general problem with only k indistinguishable, ordered, fixed cords which has e.g.f. 1/(1-x)^k, and the pure necklace problem (no necklaces with one bead allowed) with e.g.f. for the subfactorials. Therefore also the recurrence b(n) = (n+1)*b(n-1) + (n-1)*b(n-2) with b(-1)=0 and b(0)=1 holds. This comment derives from a family of recurrences found by Malin Sjodahl for a combinatorial problem for certain quark and gluon diagrams (Feb 27 2010). - Wolfdieter Lang, Jun 02 2010 a(n) is a function of the subfactorials..sf... A000166(n) a(n) = (n*sf(n+1) - (n+1)*sf(n))/(2*n*(n-1)*(n+1)),n>1, with offset 1. - Gary Detlefs, Nov 06 2010 For even k the sequence a(n) (mod k) is purely periodic with exact period a divisor of k, while for odd k the sequence a(n) (mod k) is purely periodic with exact period a divisor of 2*k. See A047974. - Peter Bala, Dec 04 2017
REFERENCES
Brualdi, Richard A. and Ryser, Herbert J., Combinatorial Matrix Theory, Cambridge NY (1991), Chapter 7.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 188.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
FORMULA
E.g.f.: ( 1 - x )^(-3)*exp(-x), for offset 1.
a(n) = round(1/2*(n^2 + 3*n + 1)*n!/exp(1))/n , n>=1. - Simon Plouffe, March 1993 G.f.: hypergeom([1,3],[],x/(x+1))/(x+1). - Mark van Hoeij, Nov 07 2011 G.f.: (1+x)^2/(2*x*Q(0)) - 1/(2*x) - 1, where Q(k) = 1 - 2*k*x - x^2*(k + 1)^2/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, May 08 2013 G.f.: -1/G(0), where G(k) = 1 + 1/(1 - (1+x)/(1 + x*(k+1)/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Aug 01 2013 G.f.: x/Q(0), where Q(k) = 1 - 2*x*(k+1) - x^2*(k+1)*(k+3)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Oct 02 2013 a(n) = hypergeom([3, -n+1], [], 1)*(-1)^(n+1) for n>=1. - Peter Luschny, Sep 20 2014 a(n) = KummerU(-n + 1, -n - 1, -1) for n >= 1. - Peter Luschny, May 10 2022 a(n) = (n^2 + 3*n + 1)*Gamma(n,-1)/(2*exp(1)) + (1 + n/2)*(-1)^n for n >= 1. - Martin Clever, Apr 06 2023
EXAMPLE
Necklaces and 2 cords problem. For n=4 one considers the following weak 2 part compositions of 4: (4,0), (3,1), (2,2), and (0,4), where (1,3) does not appear because there are no necklaces with 1 bead. These compositions contribute respectively sf(4)*1,binomial(4,3)*sf(3)*c2(1), (binomial(4,2)*sf(2))*c2(2), and 1*c2(4) with the subfactorials sf(n):= A000166(n) (see the necklace comment there) and the c2(n):=(n+1)! numbers for the pure 2 cord problem (see the above given remark on the e.g.f. for the k cords problem; here for k=2: 1/(1-x)^2). This adds up as 9 + 4*2*2 + (6*1)*6 + 120 = 181 = b(4) = A000153(5). - Wolfdieter Lang, Jun 02 2010 G.f. = x + 2*x^2 + 7*x^3 + 32*x^4 + 181*x^5 + 1214*x^6 + 9403*x^7 + 82508*x^8 + ...
MAPLE
f:= n-> floor(((n+1)!+1)/e): g:=n-> (n*f(n+1)-(n+1)*f(n))/(2*n*(n-1)*(n+1)):seq( g(n), n=2..20); # Gary Detlefs, Nov 06 2010 a := n -> `if`(n=0, 0, hypergeom([3, -n+1], [], 1))*(-1)^(n+1); seq(simplify(a(n)), n=0..20); # Peter Luschny, Sep 20 2014 0, seq(simplify(KummerU(-n + 1, -n - 1, -1)), n = 1..20); # Peter Luschny, May 10 2022
MATHEMATICA
nn = 20; Prepend[Range[0, nn]!CoefficientList[Series[Exp[-x]/(1 - x)^3, {x, 0, nn}], x], 0] (* Geoffrey Critzer, Oct 28 2012 *) RecurrenceTable[{a[0]==0, a[1]==1, a[n]==n a[n-1]+(n-2)a[n-2]}, a, {n, 20}] (* Harvey P. Dale, May 08 2013 *) a[ n_] := If[ n < 1, 0, (n - 1)! SeriesCoefficient[ Exp[ -x] / (1 - x)^3, {x, 0, n - 1}]]; (* Michael Somos, Jun 01 2013 *) a[ n_] := SeriesCoefficient[ HypergeometricPFQ[ {1, 3}, {}, x / (x + 1)] x / (x + 1), {x, 0, n}]; (* Michael Somos, Jun 01 2013 *)
PROG
(Haskell)
a000153 n = a000153_list !! n
a000153_list = 0 : 1 : zipWith (+)
(zipWith (*) [0..] a000153_list) (zipWith (*) [2..] $ tail a000153_list)
(PARI) x='x+O('x^66); concat([0], Vec(x*serlaplace(exp(-x)/(1-x)^3))) \\ Joerg Arndt, May 08 2013
Search completed in 0.042 seconds
|