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

A000111 Euler or up/down numbers: e.g.f. sec(x) + tan(x). Also for n >= 2, half the number of alternating permutations on n letters (A001250).

Original entry on oeis.org

1, 1, 1, 2, 5, 16, 61, 272, 1385, 7936, 50521, 353792, 2702765, 22368256, 199360981, 1903757312, 19391512145, 209865342976, 2404879675441, 29088885112832, 370371188237525, 4951498053124096, 69348874393137901, 1015423886506852352, 15514534163557086905, 246921480190207983616, 4087072509293123892361
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Number of linear extensions of the "zig-zag" poset. See ch. 3, prob. 23 of Stanley. - Mitch Harris, Dec 27 2005
Number of increasing 0-1-2 trees on n vertices. - David Callan, Dec 22 2006
Also the number of refinements of partitions. - Heinz-Richard Halder (halder.bichl(AT)t-online.de), Mar 07 2008
The ratio a(n)/n! is also the probability that n numbers x1,x2,...,xn randomly chosen uniformly and independently in [0,1] satisfy x1 > x2 < x3 > x4 < ... xn. - Pietro Majer, Jul 13 2009
For n >= 2, a(n-2) = number of permutations w of an ordered n-set {x_1 < ... x_n} with the following properties: w(1) = x_n, w(n) = x_{n-1}, w(2) > w(n-1), and neither any subword of w, nor its reversal, has the first three properties. The count is unchanged if the third condition is replaced with w(2) < w(n-1). - Jeremy L. Martin, Mar 26 2010
A partition of zigzag permutations of order n+1 by the smallest or the largest, whichever is behind. This partition has the same recurrent relation as increasing 1-2 trees of order n, by induction the bijection follows. - Wenjin Woan, May 06 2011
As can be seen from the asymptotics given in the FORMULA section, one has lim_{n->oo} 2*n*a(n-1)/a(n) = Pi; see A132049/A132050 for the simplified fractions. - M. F. Hasler, Apr 03 2013
a(n+1) is the sum of row n in triangle A008280. - Reinhard Zumkeller, Nov 05 2013
M. Josuat-Verges, J.-C. Novelli and J.-Y. Thibon (2011) give a far-reaching generalization of the bijection between Euler numbers and alternating permutations. - N. J. A. Sloane, Jul 09 2015
Number of treeshelves avoiding pattern T321. Treeshelves are ordered binary (0-1-2) increasing trees where every child is connected to its parent by a left or a right link, see A278678 for more definitions and examples. - Sergey Kirgizov, Dec 24 2016
Number of sequences (e(1), ..., e(n-1)), 0 <= e(i) < i, such that no three terms are equal. [Theorem 7 of Corteel, Martinez, Savage, and Weselcouch] - Eric M. Schmidt, Jul 17 2017
Number of self-dual edge-labeled trees with n vertices under "mind-body" duality. Also number of self-dual rooted edge-labeled trees with n vertices. See my paper linked below. - Nikos Apostolakis, Aug 01 2018
The ratio a(n)/n! is the volume of the convex polyhedron defined as the set of (x_1,...,x_n) in [0,1]^n such that x_i + x_{i+1} <= 1 for every 1 <= i <= n-1; see the solutions by Macdonald and Nelsen to the Amer. Math. Monthly problem referenced below. - Sanjay Ramassamy, Nov 02 2018
Number of total cyclic orders on {0,1,...,n} such that the triple (i-1,i,i+1) is positively oriented for every 1 <= i <= n-1; see my paper on cyclic orders linked below. - Sanjay Ramassamy, Nov 02 2018
The number of binary, rooted, unlabeled histories with n+1 leaves (following the definition of Rosenberg 2006). Also termed Tajima trees, Tajima genealogies, or binary, rooted, unlabeled ranked trees (Palacios et al. 2015). See Disanto & Wiehe (2013) for a proof. - Noah A Rosenberg, Mar 10 2019
From Gus Wiseman, Dec 31 2019: (Start)
Also the number of non-isomorphic balanced reduced multisystems with n + 1 distinct atoms and maximum depth. A balanced reduced multisystem is either a finite multiset, or a multiset partition with at least two parts, not all of which are singletons, of a balanced reduced multisystem. The labeled version is A006472. For example, non-isomorphic representatives of the a(0) = 1 through a(4) = 5 multisystems are (commas elided):
{1} {12} {{1}{23}} {{{1}}{{2}{34}}} {{{{1}}}{{{2}}{{3}{45}}}}
{{{12}}{{3}{4}}} {{{{1}}}{{{23}}{{4}{5}}}}
{{{{1}{2}}}{{{3}}{{45}}}}
{{{{1}{23}}}{{{4}}{{5}}}}
{{{{12}}}{{{3}}{{4}{5}}}}
Also the number of balanced reduced multisystems with n + 1 equal atoms and maximum depth. This is possibly the meaning of Heinz-Richard Halder's comment (see also A002846, A213427, A265947). The non-maximum-depth version is A318813. For example, the a(0) = 1 through a(4) = 5 multisystems are (commas elided):
{1} {11} {{1}{11}} {{{1}}{{1}{11}}} {{{{1}}}{{{1}}{{1}{11}}}}
{{{11}}{{1}{1}}} {{{{1}}}{{{11}}{{1}{1}}}}
{{{{1}{1}}}{{{1}}{{11}}}}
{{{{1}{11}}}{{{1}}{{1}}}}
{{{{11}}}{{{1}}{{1}{1}}}}
(End)
With s_n denoting the sum of n independent uniformly random numbers chosen from [-1/2,1/2], the probability that the closest integer to s_n is even is exactly 1/2 + a(n)/(2*n!). (See Hambardzumyan et al. 2023, Appendix B.) - Suhail Sherif, Mar 31 2024
The number of permutations of size n+1 that require exactly n passes through a stack (i.e. have reverse-tier n-1) with an algorithm that prioritizes outputting the maximum possible prefix of the identity in a given pass and reverses the remainder of the permutation for prior to the next pass. - Rebecca Smith, Jun 05 2024

Examples

			G.f. = 1 + x + x^2 + 2*x^3 + 5*x^4 + 16*x^5 + 61*x^6 + 272*x^7 + 1385*x^8 + ...
Sequence starts 1,1,2,5,16,... since possibilities are {}, {A}, {AB}, {ACB, BCA}, {ACBD, ADBC, BCAD, BDAC, CDAB}, {ACBED, ADBEC, ADCEB, AEBDC, AECDB, BCAED, BDAEC, BDCEA, BEADC, BECDA, CDAEB, CDBEA, CEADB, CEBDA, DEACB, DEBCA}, etc. - _Henry Bottomley_, Jan 17 2001

References

  • M. D. Atkinson: Partial orders and comparison problems, Sixteenth Southeastern Conference on Combinatorics, Graph Theory and Computing, (Boca Raton, Feb 1985), Congressus Numerantium 47, 77-88.
  • Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, pages 34, 932.
  • L. Comtet, Advanced Combinatorics, Reidel, 1974, pp. 258-260, section #11.
  • John H. Conway and Richard K. Guy, The Book of Numbers, New York: Springer-Verlag, 1996. See p. 110.
  • F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 262.
  • H. Doerrie, 100 Great Problems of Elementary Mathematics, Dover, NY, 1965, p. 66.
  • O. Heimo and A. Karttunen, Series help-mates in 8, 9 and 10 moves (Problems 2901, 2974-2976), Suomen Tehtavaniekat (Proceedings of the Finnish Chess Problem Society) vol. 60, no. 2/2006, pp. 75, 77.
  • L. B. W. Jolley, Summation of Series. 2nd ed., Dover, NY, 1961, p. 238.
  • S. Mukai, An Introduction to Invariants and Moduli, Cambridge, 2003; see p. 444.
  • E. Netto, Lehrbuch der Combinatorik. 2nd ed., Teubner, Leipzig, 1927, p. 110.
  • C. A. Pickover, The Math Book, Sterling, NY, 2009; see p. 184.
  • 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, Vol. 1, 1997 and Vol. 2, 1999; see Problem 5.7.

Links

Crossrefs

Cf. A000364 (secant numbers), A000182 (tangent numbers).
Related triangles: A008280, A008281, A008282, A008970, A010094, A059720, A177762.
Cf. A181937 for n-alternating permutations.
Cf. A109449 for an extension to an exponential Riordan array.
Column k=1 of A010094, A229892, A258829, A262124, A275784.
Column k=2 of A250261.
Cf. A002105, A186365.
For 0-1-2 trees with n nodes and k leaves, see A301344.
Matula-Goebel numbers of 0-1-2 trees are A292050.
An overview over generalized Euler numbers gives A349264.
Cf. A000258, A000311, A002846, A005121, A318813, A320270, A330474, A330665, A330679, A340315.

Programs

  • Haskell
    a000111 0 = 1
a000111 n = sum $ a008280_row (n - 1)
-- Reinhard Zumkeller, Nov 01 2013
  • Maple
    A000111 := n-> n!*coeff(series(sec(x)+tan(x),x,n+1), x, n);
s := series(sec(x)+tan(x), x, 100): A000111 := n-> n!*coeff(s, x, n);
A000111:=n->piecewise(n mod 2=1,(-1)^((n-1)/2)*2^(n+1)*(2^(n+1)-1)*bernoulli(n+1)/(n+1),(-1)^(n/2)*euler(n)):seq(A000111(n),n=0..30); A000111:=proc(n) local k: k:=floor((n+1)/2): if n mod 2=1 then RETURN((-1)^(k-1)*2^(2*k)*(2^(2*k)-1)*bernoulli(2*k)/(2*k)) else RETURN((-1)^k*euler(2*k)) fi: end:seq(A000111(n),n=0..30); (C. Ronaldo)
T := n -> 2^n*abs(euler(n,1/2)+euler(n,1)): # Peter Luschny, Jan 25 2009
S := proc(n,k) option remember; if k=0 then RETURN(`if`(n=0,1,0)) fi; S(n,k-1)+S(n-1,n-k) end:
A000364 := n -> S(2*n,2*n);
A000182 := n -> S(2*n+1,2*n+1);
A000111 := n -> S(n,n); # Peter Luschny, Jul 29 2009
a := n -> 2^(n+2)*n!*(sum(1/(4*k+1)^(n+1), k = -infinity..infinity))/Pi^(n+1):
1, seq(a(n), n = 1..22); # Emeric Deutsch, Aug 17 2009
# alternative Maple program:
b:= proc(u, o) option remember;
      `if`(u+o=0, 1, add(b(o-1+j, u-j), j=1..u))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..30);  # Alois P. Heinz, Nov 29 2015
  • Mathematica
    n=22; CoefficientList[Series[(1+Sin[x])/Cos[x], {x, 0, n}], x] * Table[k!, {k, 0, n}] (* Jean-François Alcover, May 18 2011, after Michael Somos *)
a[n_] := If[EvenQ[n], Abs[EulerE[n]], Abs[(2^(n+1)*(2^(n+1)-1)*BernoulliB[n+1])/(n+1)]]; Table[a[n], {n, 0, 26}] (* Jean-François Alcover, Oct 09 2012, after C. Ronaldo *)
ee = Table[ 2^n*EulerE[n, 1] + EulerE[n] - 1, {n, 0, 26}]; Table[ Differences[ee, n] // First // Abs, {n, 0, 26}] (* Jean-François Alcover, Mar 21 2013, after Paul Curtz *)
a[ n_] := If[ n < 0, 0, (2 I)^n If[ EvenQ[n], EulerE[n, 1/2], EulerE[n, 0] I]]; (* Michael Somos, Aug 15 2015 *)
a[ n_] := If[ n < 1, Boole[n == 0], With[{m = n - 1}, m! SeriesCoefficient[ 1 / (1 - Sin[x]), {x, 0, m}]]]; (* Michael Somos, Aug 15 2015 *)
s[0] = 1; s[] = 0; t[n, 0] := s[n]; t[n_, k_] := t[n, k] = t[n, k-1] + t[n-1, n-k]; a[n_] := t[n, n]; Array[a, 30, 0](* Jean-François Alcover, Feb 12 2016 *)
a[n_] := If[n == 0, 1, 2*Abs[PolyLog[-n, I]]]; (* Jean-François Alcover, Dec 02 2023, after M. F. Hasler *)
a[0] := 1; a[1] := 1; a[n_] := a[n] = Sum[Binomial[n - 2, k] a[k] a[n - 1 - k], {k, 0, n - 2}]; Map[a, Range[0, 26]] (* Oliver Seipel, May 24 2024 after Peter Bala *)
a[0] := 1; a[1] := 1; a[n_] := a[n] = 1/(n (n-1)) Sum[a[n-1-k] a[k] k, {k, 1, n-1}]; Map[#! a[#]&, Range[0, 26]] (* Oliver Seipel, May 27 2024 *)
  • Maxima
    a(n):=sum((if evenp(n+k) then (-1)^((n+k)/2)*sum(j!*stirling2(n,j)*2^(1-j)*(-1)^(n+j-k)*binomial(j-1,k-1),j,k,n) else 0),k,1,n); /* Vladimir Kruchinin, Aug 19 2010 */
  • Maxima
    a(n):=if n<2 then 1 else 2*sum(4^m*(sum((i-(n-1)/2)^(n-1)*binomial(n-2*m-1,i-m)*(-1)^(n-i-1),i,m,(n-1)/2)),m,0,(n-2)/2); /* Vladimir Kruchinin, Aug 09 2011 */
  • PARI
    {a(n) = if( n<1, n==0, n--; n! * polcoeff( 1 / (1 - sin(x + x * O(x^n))), n))}; \\ Michael Somos, Feb 03 2004
  • PARI
    {a(n) = local(v=[1], t); if( n<0, 0, for(k=2, n+2, t=0; v = vector(k, i, if( i>1, t+= v[k+1-i]))); v[2])}; \\ Michael Somos, Feb 03 2004
  • PARI
    {a(n) = local(an); if( n<1, n>=0, an = vector(n+1, m, 1); for( m=2, n, an[m+1] = sum( k=0, m-1, binomial(m-1, k) * an[k+1] * an[m-k]) / 2); an[n+1])}; \\ Michael Somos, Feb 03 2004
  • PARI
    z='z+O('z^66); egf = (1+sin(z))/cos(z); Vec(serlaplace(egf)) \\ Joerg Arndt, Apr 30 2011
  • PARI
    A000111(n)={my(k);sum(m=0,n\2,(-1)^m*sum(j=0,k=n+1-2*m,binomial(k,j)*(-1)^j*(k-2*j)^(n+1))/k>>k)}  \\ M. F. Hasler, May 19 2012
  • PARI
    A000111(n)=if(n,2*abs(polylog(-n,I)),1)  \\ M. F. Hasler, May 20 2012
  • Python
    # requires python 3.2 or higher
from itertools import accumulate
A000111_list, blist = [1,1], [1]
for n in range(10**2):
    blist = list(reversed(list(accumulate(reversed(blist))))) + [0] if n % 2 else [0]+list(accumulate(blist))
    A000111_list.append(sum(blist)) # Chai Wah Wu, Jan 29 2015
  • Python
    from mpmath import *
mp.dps = 150
l = chop(taylor(lambda x: sec(x) + tan(x), 0, 26))
[int(fac(i) * li) for i, li in enumerate(l)]  # Indranil Ghosh, Jul 06 2017
  • Python
    from sympy import bernoulli, euler
def A000111(n): return abs(((1<Chai Wah Wu, Nov 13 2024
  • Sage
    # Algorithm of L. Seidel (1877)
def A000111_list(n) :
    R = []; A = {-1:0, 0:1}; k = 0; e = 1
    for i in (0..n) :
        Am = 0; A[k + e] = 0; e = -e
        for j in (0..i) : Am += A[k]; A[k] = Am; k += e
        R.append(Am)
    return R
A000111_list(22) # Peter Luschny, Mar 31 2012 (revised Apr 24 2016)

Formula

E.g.f.: (1+sin(x))/cos(x) = tan(x) + sec(x).
E.g.f. for a(n+1) is 1/(cos(x/2) - sin(x/2))^2 = 1/(1-sin(x)) = d/dx(sec(x) + tan(x)).
E.g.f. A(x) = -log(1-sin(x)), for a(n+1). - Vladimir Kruchinin, Aug 09 2010
O.g.f.: A(x) = 1+x/(1-x-x^2/(1-2*x-3*x^2/(1-3*x-6*x^2/(1-4*x-10*x^2/(1-... -n*x-(n*(n+1)/2)*x^2/(1- ...)))))) (continued fraction). - Paul D. Hanna, Jan 17 2006
E.g.f. A(x) = y satisfies 2y' = 1 + y^2. - Michael Somos, Feb 03 2004
a(n) = P_n(0) + Q_n(0) (see A155100 and A104035), defining Q_{-1} = 0. Cf. A156142.
2*a(n+1) = Sum_{k=0..n} binomial(n, k)*a(k)*a(n-k).
Asymptotics: a(n) ~ 2^(n+2)*n!/Pi^(n+1). For a proof, see for example Flajolet and Sedgewick.
a(n) = (n-1)*a(n-1) - Sum_{i=2..n-2} (i-1)*E(n-2, n-1-i), where E are the Entringer numbers A008281. - Jon Perry, Jun 09 2003
a(2*k) = (-1)^k euler(2k) and a(2k-1) = (-1)^(k-1)2^(2k)(2^(2k)-1) Bernoulli(2k)/(2k). - C. Ronaldo (aga_new_ac(AT)hotmail.com), Jan 17 2005
|a(n+1) - 2*a(n)| = A000708(n). - Philippe Deléham, Jan 13 2007
a(n) = 2^n|E(n,1/2) + E(n,1)| where E(n,x) are the Euler polynomials. - Peter Luschny, Jan 25 2009
a(n) = 2^(n+2)*n!*S(n+1)/(Pi)^(n+1), where S(n) = Sum_{k = -inf..inf} 1/(4k+1)^n (see the Elkies reference). - Emeric Deutsch, Aug 17 2009
a(n) = i^(n+1) Sum_{k=1..n+1} Sum_{j=0..k} binomial(k,j)(-1)^j (k-2j)^(n+1) (2i)^(-k) k^{-1}. - Ross Tang (ph.tchaa(AT)gmail.com), Jul 28 2010
a(n) = sum((if evenp(n+k) then (-1)^((n+k)/2)*sum(j!*Stirling2(n,j)*2^(1-j)*(-1)^(n+j-k)*binomial(j-1,k-1),j,k,n) else 0),k,1,n), n>0. - Vladimir Kruchinin, Aug 19 2010
If n==1(mod 4) is prime, then a(n)==1(mod n); if n==3(mod 4) is prime, then a(n)==-1(mod n). - Vladimir Shevelev, Aug 31 2010
For m>=0, a(2^m)==1(mod 2^m); If p is prime, then a(2*p)==1(mod 2*p). - Vladimir Shevelev, Sep 03 2010
From Peter Bala, Jan 26 2011: (Start)
a(n) = A(n,i)/(1+i)^(n-1), where i = sqrt(-1) and {A(n,x)}n>=1 = [1,1+x,1+4*x+x^2,1+11*x+11*x^2+x^3,...] denotes the sequence of Eulerian polynomials.
Equivalently, a(n) = i^(n+1)*Sum_{k=1..n} (-1)^k*k!*Stirling2(n,k) * ((1+i)/2)^(k-1) = i^(n+1)*Sum_{k = 1..n} (-1)^k*((1+i)/2)^(k-1)* Sum_{j = 0..k} (-1)^(k-j)*binomial(k,j)*j^n.
This explicit formula for a(n) can be used to obtain congruence results. For example, for odd prime p, a(p) = (-1)^((p-1)/2) (mod p), as noted by Vladimir Shevelev above.
For the corresponding type B results see A001586. For the corresponding results for plane increasing 0-1-2 trees see A080635.
For generalized Eulerian, Stirling and Bernoulli numbers associated with the zigzag numbers see A145876, A147315 and A185424, respectively. For a recursive triangle to calculate a(n) see A185414.
(End)
a(n) = I^(n+1)*2*Li_{-n}(-I) for n > 0. Li_{s}(z) is the polylogarithm. - Peter Luschny, Jul 29 2011
a(n) = 2*Sum_{m=0..(n-2)/2} 4^m*(Sum_{i=m..(n-1)/2} (i-(n-1)/2)^(n-1)*binomial(n-2*m-1,i-m)*(-1)^(n-i-1)), n > 1, a(0)=1, a(1)=1. - Vladimir Kruchinin, Aug 09 2011
a(n) = D^(n-1)(1/(1-x)) evaluated at x = 0, where D is the operator sqrt(1-x^2)*d/dx. Cf. A006154. a(n) equals the alternating sum of the nonzero elements of row n-1 of A196776. This leads to a combinatorial interpretation for a(n); for example, a(4*n+2) gives the number of ordered set partitions of 4*n+1 into k odd-sized blocks, k = 1 (mod 4), minus the number of ordered set partitions of 4*n+1 into k odd-sized blocks, k = 3 (mod 4). Cf A002017. - Peter Bala, Dec 06 2011
From Sergei N. Gladkovskii, Nov 14 2011 - Dec 23 2013: (Start)
Continued fractions:
E.g.f.: tan(x) + sec(x) = 1 + x/U(0); U(k) = 4k+1-x/(2-x/(4k+3+x/(2+x/U(k+1)))).
E.g.f.: for a(n+1) is E(x) = 1/(1-sin(x)) = 1 + x/(1 - x + x^2/G(0)); G(k) = (2*k+2)*(2*k+3)-x^2+(2*k+2)*(2*k+3)*x^2/G(k+1).
E.g.f.: for a(n+1) is E(x) = 1/(1-sin(x)) = 1/(1 - x/(1 + x^2/G(0))) ; G(k) = 8*k+6-x^2/(1 + (2*k+2)*(2*k+3)/G(k+1)).
E.g.f.: for a(n+1) is E(x) = 1/(1 - sin(x)) = 1/(1 - x*G(0)); G(k) = 1 - x^2/(2*(2*k+1)*(4*k+3) - 2*x^2*(2*k+1)*(4*k+3)/(x^2 - 4*(k+1)*(4*k+5)/G(k+1))).
E.g.f.: for a(n+1) is E(x) = 1/(1 - sin(x)) = 1/(1 - x*G(0)) where G(k)= 1 - x^2/( (2*k+1)*(2*k+3) - (2*k+1)*(2*k+3)^2/(2*k+3 - (2*k+2)/G(k+1))).
E.g.f.: tan(x) + sec(x) = 1 + 2*x/(U(0)-x) where U(k) = 4k+2 - x^2/U(k+1).
E.g.f.: tan(x) + sec(x) = 1 + 2*x/(2*U(0)-x) where U(k) = 4*k+1 - x^2/(16*k+12 - x^2/U(k+1)).
E.g.f.: tan(x) + sec(x) = 4/(2-x*G(0))-1 where G(k) = 1 - x^2/(x^2 - 4*(2*k+1)*(2*k+3)/G(k+1)).
G.f.: 1 + x/Q(0), m=+4, u=x/2, where Q(k) = 1 - 2*u*(2*k+1) - m*u^2*(k+1)*(2*k+1)/(1 - 2*u*(2*k+2) - m*u^2*(k+1)*(2*k+3)/Q(k+1)).
G.f.: conjecture: 1 + T(0)*x/(1-x), where T(k) = 1 - x^2*(k+1)*(k+2)/(x^2*(k+1)*(k+2) - 2*(1-x*(k+1))*(1-x*(k+2))/T(k+1)).
E.g.f.: 1+ 4*x/(T(0) - 2*x), where T(k) = 4*(2*k+1) - 4*x^2/T(k+1):
E.g.f.: T(0)-1, where T(k) = 2 + x/(4*k+1 - x/(2 - x/( 4*k+3 + x/T(k+1)))). (End)
E.g.f.: tan(x/2 + Pi/4). - Vaclav Kotesovec, Nov 08 2013
Asymptotic expansion: 4*(2*n/(Pi*e))^(n+1/2)*exp(1/2+1/(12*n) -1/(360*n^3) + 1/(1260*n^5) - ...). (See the Luschny link.) - Peter Luschny, Jul 14 2015
From Peter Bala, Sep 10 2015: (Start)
The e.g.f. A(x) = tan(x) + sec(x) satisfies A''(x) = A(x)*A'(x), hence the recurrence a(0) = 1, a(1) = 1, else a(n) = Sum_{i = 0..n-2} binomial(n-2,i)*a(i)*a(n-1-i).
Note, the same recurrence, but with the initial conditions a(0) = 0 and a(1) = 1, produces the sequence [0,1,0,1,0,4,0,34,0,496,...], an aerated version of A002105. (End)
a(n) = A186365(n)/n for n >= 1. - Anton Zakharov, Aug 23 2016
From Peter Luschny, Oct 27 2017: (Start)
a(n) = abs(2*4^n*(H(((-1)^n - 3)/8, -n) - H(((-1)^n - 7)/8, -n))) where H(z, r) are the generalized harmonic numbers.
a(n) = (-1)^binomial(n + 1, 2)*2^(2*n + 1)*(zeta(-n, 1 + (1/8)*(-7 + (-1)^n)) - zeta(-n, 1 + (1/8)*(-3 + (-1)^n))). (End)
a(n) = i*(i^n*Li_{-n}(-i) - (-i)^n*Li_{-n}(i)), where i is the imaginary unit and Li_{s}(z) is the polylogarithm. - Peter Luschny, Aug 28 2020
Sum_{n>=0} 1/a(n) = A340315. - Amiram Eldar, May 29 2021
a(n) = n!*Re([x^n](1 + I^(n^2 - n)*(2 - 2*I)/(exp(x) + I))). - Peter Luschny, Aug 09 2021

Extensions

Edited by M. F. Hasler, Apr 04 2013
Title corrected by Geoffrey Critzer, May 18 2013

A001003 Schroeder's second problem (generalized parentheses); also called super-Catalan numbers or little Schroeder numbers.

Original entry on oeis.org

1, 1, 3, 11, 45, 197, 903, 4279, 20793, 103049, 518859, 2646723, 13648869, 71039373, 372693519, 1968801519, 10463578353, 55909013009, 300159426963, 1618362158587, 8759309660445, 47574827600981, 259215937709463, 1416461675464871
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

If you are looking for the Schroeder numbers (a.k.a. large Schroder numbers, or big Schroeder numbers), see A006318.
Yang & Jiang (2021) call these the small 2-Schroeder numbers. - N. J. A. Sloane, Mar 28 2021
There are two schools of thought about the index for the first term. I prefer the indexing a(0) = a(1) = 1, a(2) = 3, a(3) = 11, etc.
a(n) is the number of ways to insert parentheses in a string of n+1 symbols. The parentheses must be balanced but there is no restriction on the number of pairs of parentheses. The number of letters inside a pair of parentheses must be at least 2. Parentheses enclosing the whole string are ignored.
Also length of list produced by a variant of the Catalan producing iteration: replace each integer k with the list 0,1,..,k,k+1,k,...,1,0 and get the length a(n) of the resulting (flattened) list after n iterations. - Wouter Meeussen, Nov 11 2001
Stanley gives several other interpretations for these numbers.
Number of Schroeder paths of semilength n (i.e., lattice paths from (0,0) to (2n,0), with steps H=(2,0), U=(1,1) and D(1,-1) and not going below the x-axis) with no peaks at level 1. Example: a(2)=3 because among the six Schroeder paths of semilength two HH, UHD, UUDD, HUD, UDH and UDUD, only the first three have no peaks at level 1. - Emeric Deutsch, Dec 27 2003
a(n+1) is the number of Dyck n-paths in which the interior vertices of the ascents are colored white or black. - David Callan, Mar 14 2004
Number of possible schedules for n time slots in the first-come first-served (FCFS) printer policy.
Also row sums of A086810, A033282, A126216. - Philippe Deléham, May 09 2004
a(n+1) is the number of pairs (u,v) of same-length compositions of n, 0's allowed in u but not in v and u dominates v (meaning u_1 >= v_1, u_1 + u_2 >= v_1 + v_2 and so on). For example, with n=2, a(3) counts (2,2), (1+1,1+1), (2+0,1+1). - David Callan, Jul 20 2005
The big Schroeder number (A006318) is the number of Schroeder paths from (0,0) to (n,n) (subdiagonal paths with steps (1,0) (0,1) and (1,1)). These paths fall in two classes: those with steps on the main diagonal and those without. These two classes are equinumerous and the number of paths in either class is the little Schroeder number a(n) (half the big Schroeder number). - Marcelo Aguiar (maguiar(AT)math.tamu.edu), Oct 14 2005
With offset 0, a(n) = number of (colored) Motzkin (n-1)-paths with each upstep U getting one of 2 colors and each flatstep F getting one of 3 colors. Example. With their colors immediately following upsteps/flatsteps, a(2) = 3 counts F1, F2, F3 and a(3)=11 counts U1D, U2D, F1F1, F1F2, F1F3, F2F1, F2F2, F2F3, F3F1, F3F2, F3F3. - David Callan, Aug 16 2006
Shifts left when INVERT transform applied twice. - Alois P. Heinz, Apr 01 2009
Number of increasing tableaux of shape (n,n). An increasing tableau is a semistandard tableaux with strictly increasing rows and columns, and set of entries an initial segment of the positive integers. Example: a(2) = 3 because of the three tableaux (12)(34), (13)(24), (12)(23). - Oliver Pechenik, Apr 22 2014
Number of ordered trees with no vertex of outdegree 1 and having n+1 leaves (called sometimes Schröder trees). - Emeric Deutsch, Dec 13 2014
Number of dissections of a convex (n+2)-gon by nonintersecting diagonals. Example: a(2)=3 because for a square ABCD we have (i) no diagonal, (ii) dissection with diagonal AC, and (iii) dissection with diagonal BD. - Emeric Deutsch, Dec 13 2014
The little Schroeder numbers are the moments of the Marchenko-Pastur law for the case c=2 (although the moment m0 is 1/2 instead of 1): 1/2, 1, 3, 11, 45, 197, 903, ... - Jose-Javier Martinez, Apr 07 2015
Number of generalized Motzkin paths with no level steps at height 0, from (0,0) to (2n,0), and consisting of steps U=(1,1), D=(1,-1) and H2=(2,0). For example, for n=3, we have the 11 paths: UDUDUD, UUDDUD, UDUUDD, UH2DUD, UDUH2D, UH2H2D, UUDUDD, UUUDDD, UUH2DD, UUDH2D, UH2UDD. - José Luis Ramírez Ramírez, Apr 20 2015
REVERT transform of A225883. - Vladimir Reshetnikov, Oct 25 2015
Total number of (nonempty) faces of all dimensions in the associahedron K_{n+1} of dimension n-1. For example, K_4 (a pentagon) includes 5 vertices and 5 edges together with K_4 itself (5 + 5 + 1 = 11), while K_5 includes 14 vertices, 21 edges and 9 faces together with K_5 itself (14 + 21 + 9 + 1 = 45). - Noam Zeilberger, Sep 17 2018
a(n) is the number of interval posets of permutations with n minimal elements that have exactly two realizers, up to a shift by 1 in a(4). See M. Bouvel, L. Cioni, B. Izart, Theorem 17 page 13. - Mathilde Bouvel, Oct 21 2021
a(n) is the number of sequences of nonnegative integers (u_1, u_2, ..., u_n) such that (i) u_1 = 1, (ii) u_i <= i for all i, (iii) the nonzero u_i are weakly increasing. For example, a(2) = 3 counts 10, 11, 12, and a(3) = 11 counts 100, 101, 102, 103, 110, 111, 112, 113, 120, 122, 123. See link below. - David Callan, Dec 19 2021
a(n) is the number of parking functions of size n avoiding the patterns 132 and 213. - Lara Pudwell, Apr 10 2023
a(n+1) is the number of Schroeder paths from (0,0) to (2n,0) in which level steps at height 0 come in 2 colors. - Alexander Burstein, Jul 23 2023

Examples

			G.f. = 1 + x + 3*x^2 + 11*x^3 + 45*x^4 + 197*x^5 + 903*x^6 + 4279*x^7 + ...
a(2) = 3: abc, a(bc), (ab)c; a(3) = 11: abcd, (ab)cd, a(bc)d, ab(cd), (ab)(cd), a(bcd), a(b(cd)), a((bc)d), (abc)d, (a(bc))d, ((ab)c)d.
Sum over partitions formula: a(3) = 2*a(0)*a(2) + 1*a(1)^2 + 3*(a(0)^2)*a(1) + 1*a(0)^4 = 6 + 1 + 3 + 1 = 11.
a(4) = 45 since the top row of Q^3 = (11, 14, 12, 8, 0, 0, 0, ...); (11 + 14 + 12 + 8) = 45.

References

  • D. Arques and A. Giorgetti, Une bijection géometrique entre une famille d'hypercartes et une famille de polygones énumérées par la série de Schroeder, Discrete Math., 217 (2000), 17-32.
  • Paul Barry, Riordan arrays, generalized Narayana triangles, and series reversion, Linear Algebra and its Applications, 491 (2016) 343-385.
  • N. Bernasconi et al., On properties of random dissections and triangulations, Combinatorica, 30 (6) (2010), 627-654.
  • Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 618.
  • Peter J. Cameron, Some treelike objects. Quart. J. Math. Oxford Ser. (2) 38 (1987), no. 150, 155--183. MR0891613 (89a:05009). See p. 155, also p. 179, line -9. - N. J. A. Sloane, Apr 18 2014
  • C. Coker, A family of eigensequences, Discrete Math. 282 (2004), 249-250.
  • L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 57.
  • D. E. Davenport, L. W. Shapiro and L. C. Woodson, The Double Riordan Group, The Electronic Journal of Combinatorics, 18(2) (2012), #P33. - From N. J. A. Sloane, May 11 2012
  • Emeric Deutsch, A bijective proof of an equation linking the Schroeder numbers, large and small, Discrete Math., 241 (2001), 235-240.
  • Tomislav Doslic and Darko Veljan, Logarithmic behavior of some combinatorial sequences. Discrete Math. 308 (2008), no. 11, 2182--2212. MR2404544 (2009j:05019) - From N. J. A. Sloane, May 01 2012
  • Michael Drmota, Anna de Mier, and Marc Noy, Extremal statistics on non-crossing configurations. Discrete Math. 327 (2014), 103--117. MR3192420. See Eq. (2). - N. J. A. Sloane, May 18 2014
  • I. M. H. Etherington, On non-associative combinations, Proc. Royal Soc. Edinburgh, 59 (Part 2, 1938-39), 153-162.
  • I. M. H. Etherington, Some problems of non-associative combinations (I), Edinburgh Math. Notes, 32 (1940), pp. i-vi. Part II is by A. Erdelyi and I. M. H. Etherington, and is on pages vii-xiv of the same issue.
  • P. Flajolet and M. Noy, Analytic combinatorics of non-crossing permutations, Discrete Math., 204 (1999), 203-229, Section 3.1.
  • D. Foata and D. Zeilberger, A classic proof of a recurrence for a very classical sequence, J. Comb Thy A 80 380-384 1997.
  • Wolfgang Gatterbauer and Dan Suciu, Dissociation and propagation for approximate lifted inference with standard relational database management systems, The VLDB Journal, February 2017, Volume 26, Issue 1, pp. 5-30; DOI 10.1007/s00778-016-0434-5
  • Ivan Geffner and Marc Noy, Counting Outerplanar Maps, Electronic Journal of Combinatorics 24(2) (2017), #P2.3.
  • D. Gouyou-Beauchamps and B. Vauquelin, Deux propriétés combinatoires des nombres de Schroeder, Theor. Inform. Appl., 22 (1988), 361-388.
  • N. S. S. Gu, N. Y. Li and T. Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221.
  • P.-Y. Huang, S.-C. Liu, and Y.-N. Yeh, Congruences of Finite Summations of the Coefficients in certain Generating Functions, The Electronic Journal of Combinatorics, 21 (2014), #P2.45.
  • M. Klazar, On numbers of Davenport-Schinzel sequences, Discr. Math., 185 (1998), 77-87.
  • D. E. Knuth, The Art of Computer Programming, Vol. 1, various sections (e.g. p. 534 of 2nd ed.).
  • D. E. Knuth, The Art of Computer Programming, Vol. 1, (p. 539 of 3rd ed.).
  • D. E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7.2.1.6, Problem 66, p. 479.
  • J. S. Lew, Polynomial enumeration of multidimensional lattices, Math. Systems Theory, 12 (1979), 253-270.
  • Ana Marco and J.-J. Martinez, A total positivity property of the Marchenko-Pastur Law, Electronic Journal of Linear Algebra, 30 (2015), #7.
  • T. S. Motzkin, Relations between hypersurface cross ratios and a combinatorial formula for partitions of a polygon, for permanent preponderance and for non-associative products, Bull. Amer. Math. Soc., 54 (1948), 352-360.
  • L. Ozsvart, Counting ordered graphs that avoid certain subgraphs, Discr. Math., 339 (2016), 1871-1877.
  • R. C. Read, On general dissections of a polygon, Aequat. Mathem. 18 (1978) 370-388, Table 6
  • J. Riordan, Combinatorial Identities, Wiley, 1968, p. 168.
  • E. Schroeder, Vier combinatorische Probleme, Zeit. f. Math. Phys., 15 (1870), 361-376.
  • 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, Vol. 2, 1999; see page 178; see page 239, Exercise 6.39b.
  • H. N. V. Temperley and D. G. Rogers, A note on Baxter's generalization of the Temperley-Lieb operators, pp. 324-328 of Combinatorial Mathematics (Canberra, 1977), Lect. Notes Math. 686, 1978.
  • I. Vardi, Computational Recreations in Mathematica. Addison-Wesley, Redwood City, CA, 1991, p. 198.
  • Sheng-Liang Yang and Mei-yang Jiang, The m-Schröder paths and m-Schröder numbers, Disc. Math. (2021) Vol. 344, Issue 2, 112209. doi:10.1016/j.disc.2020.112209. See Table 1.

Links

Crossrefs

See A000081, A000108, A001190, A001699, for other ways to count parentheses.
Row sums of A033282, A033877, A086810, A126216.
Right-hand column 1 of convolution triangle A011117.
Column 1 of A336573. Column 0 of A104219.
The sequences listed in Yang-Jiang's Table 1 appear to be A006318, this sequence, A027307, A034015, A144097, A243675, A260332, A243676. - N. J. A. Sloane, Mar 28 2021
Cf. A000041, A000311, A001263, A003480, A006125, A010683, A025240, A035011.
Cf. A048996, A054726, A059435, A065096, A080243, A085403, A086456, A086616.
Cf. A086810, A088617, A104858, A110440, A111785, A114710, A118376, A126216.
Cf. A139685, A144156, A144944, A153881, A186826.
Cf. A006318 (Schroeder numbers).

Programs

  • Haskell
    a001003 = last . a144944_row  -- Reinhard Zumkeller, May 11 2013
  • Magma
    R:=PowerSeriesRing(Rationals(), 50);
Coefficients(R!( (1+x -Sqrt(1-6*x+x^2) )/(4*x) )); // G. C. Greubel, Oct 27 2024
  • Maple
    t1 := (1/(4*x))*(1+x-sqrt(1-6*x+x^2)); series(t1,x,40);
invtr:= proc(p) local b; b:= proc(n) option remember; local i; `if`(n<1, 1, add(b(n-i) *p(i-1), i=1..n+1)) end end: a:='a': f:= (invtr@@2)(a): a:= proc(n) if n<0 then 1 else f(n-1) fi end: seq(a(n), n=0..30); # Alois P. Heinz, Apr 01 2009
# Computes n -> [a[0],a[1],..,a[n]]
A001003_list := proc(n) local j,a,w; a := array(0..n); a[0] := 1;
for w from 1 to n do a[w] := a[w-1]+2*add(a[j]*a[w-j-1],j=1..w-1) od;
convert(a,list) end: A001003_list(100); # Peter Luschny, May 17 2011
  • Mathematica
    Table[Length[Flatten[Nest[ #/.a_Integer:> Join[Range[0, a + 1], Range[a, 0, -1]] &, {0}, n]]], {n, 0, 10}]; Sch[ 0 ] = Sch[ 1 ] = 1; Sch[ n_Integer ] := Sch[ n ] = (3(2n - 1)Sch[ n - 1 ] - (n - 2)Sch[ n - 2 ])/(n + 1); Array[ Sch, 24, 0]
(* Second program: *)
a[n_] := Hypergeometric2F1[-n + 1, n + 2, 2, -1]; a[0] = 1; Table[a[n], {n, 0, 23}] (* Jean-François Alcover, Nov 09 2011, after Vladeta Jovovic *)
a[ n_] := SeriesCoefficient[ (1 + x - Sqrt[1 - 6 x + x^2]) / (4 x), {x, 0, n}]; (* Michael Somos, Aug 26 2015 *)
Table[(KroneckerDelta[n] - GegenbauerC[n+1, -1/2, 3])/4, {n, 0, 20}] (* Vladimir Reshetnikov, Oct 25 2015 *)
a[n_] := -LegendreP[n, -1, 2, 3] I / Sqrt[2]; a[0] = 1;
Table[a[n], {n, 0, 23}] (* Jean-François Alcover, Feb 16 2019 *)
a[1]:=1; a[2]:=1; a[n_]:=a[n] = a[n-1]+2 Sum[a[k] a[n-k], {k,2,n-1}]; Map[a, Range[24]] (* Oliver Seipel, Nov 03 2024, after Schröder 1870 *)
CoefficientList[InverseSeries[Series[x/(Series[(1 - x)/(1 - 2  x), {x, 0, 24}]), {x, 0, 24}]]/x, x] (* Mats Granvik, Jun 30 2025 *)
  • PARI
    {a(n) = if( n<1, n==0, sum( k=0, n, 2^k * binomial(n, k) * binomial(n, k-1) ) / (2*n))}; /* Michael Somos, Mar 31 2007 */
  • PARI
    {a(n) = my(A); if( n<1, n==0, n--; A = x * O(x^n); n! * simplify( polcoef( exp(3*x + A) * besseli(1, 2*x * quadgen(8) + A), n)))}; /* Michael Somos, Mar 31 2007 */
  • PARI
    {a(n) = if( n<0, 0, n++; polcoef( serreverse( (x - 2*x^2) / (1 - x) + x * O(x^n)), n))}; /* Michael Somos, Mar 31 2007 */
  • PARI
    N=30; x='x+O('x^N); Vec( (1+x-(1-6*x+x^2)^(1/2))/(4*x) ) \\ Hugo Pfoertner, Nov 19 2018
  • Python
    # The objective of this implementation is efficiency.
# n -> [a(0), a(1), ..., a(n)]
def A001003_list(n):
    a = [0 for i in range(n)]
    a[0] = 1
    for w in range(1, n):
        s = 0
        for j in range(1, w):
            s += a[j]*a[w-j-1]
        a[w] = a[w-1]+2*s
    return a
# Peter Luschny, May 17 2011
  • Python
    from gmpy2 import divexact
A001003 = [1, 1]
for n in range(3,10**3):
    A001003.append(divexact(A001003[-1]*(6*n-9)-(n-3)*A001003[-2],n))
# Chai Wah Wu, Sep 01 2014
  • Sage
    # Generalized algorithm of L. Seidel
def A001003_list(n) :
    D = [0]*(n+1); D[1] = 1/2
    b = True; h = 2; R = [1]
    for i in range(2*n-2) :
        if b :
            for k in range(h,0,-1) : D[k] += D[k-1]
            h += 1;
        else :
            for k in range(1,h, 1) : D[k] += D[k-1]
            R.append(D[h-1]);
        b = not b
    return R
A001003_list(24) # Peter Luschny, Jun 02 2012

Formula

D-finite with recurrence: (n+1) * a(n) = (6*n-3) * a(n-1) - (n-2) * a(n-2) if n>1. a(0) = a(1) = 1.
a(n) = 3*a(n-1) + 2*A065096(n-2) (n>2). If g(x) = 1 + 3*x + 11*x^2 + 45*x^3 + ... + a(n)*x^n + ..., then g(x) = 1 + 3(x*g(x)) + 2(x*g(x))^2, g(x)^2 = 1 + 6*x + 31*x^2 + 156*x^3 + ... + A065096(n)*x^n + ... - Paul D. Hanna, Jun 10 2002
a(n+1) = -a(n) + 2*Sum_{k=1..n} a(k)*a(n+1-k). - Philippe Deléham, Jan 27 2004
a(n-2) = (1/(n-1))*Sum_{k=0..n-3} binomial(n-1,k+1)*binomial(n-3,k)*2^(n-3-k) for n >= 3 [G. Polya, Elemente de Math., 12 (1957), p. 115.] - N. J. A. Sloane, Jun 13 2015
G.f.: (1 + x - sqrt(1 - 6*x + x^2) )/(4*x) = 2/(1 + x + sqrt(1 - 6*x + x^2)).
a(n) ~ W*(3+sqrt(8))^n*n^(-3/2) where W = (1/4)*sqrt((sqrt(18)-4)/Pi) [See Knuth I, p. 534, or Perez. Note that the formula on line 3, page 475 of Flajolet and Sedgewick seems to be wrong - it has to be multiplied by 2^(1/4).] - N. J. A. Sloane, Apr 10 2011
The correct asymptotic for this sequence is a(n) ~ W*(3+sqrt(8))^n*n^(-3/2), where W = (1+sqrt(2))/(2*2^(3/4)*sqrt(Pi)) = 0.404947065905750651736243... Result in book by D. Knuth (p. 539 of 3rd edition, exercise 12) is for sequence b(n), but a(n) = b(n+1)/2. Therefore is asymptotic a(n) ~ b(n) * (3+sqrt(8))/2. - Vaclav Kotesovec, Sep 09 2012
The Hankel transform of this sequence gives A006125 = 1, 1, 2, 8, 64, 1024, ...; example: det([1, 1, 3, 11; 1, 3, 11, 45; 3, 11, 45, 197; 11, 45, 197, 903]) = 2^6 = 64. - Philippe Deléham, Mar 02 2004
a(n+1) = Sum_{k=0..floor((n-1)/2)} 2^k * 3^(n-1-2k) * binomial(n-1, 2k) * Catalan(k). This formula counts colored Dyck paths by the same parameter by which Touchard's identity counts ordinary Dyck paths: number of DDUs (U=up step, D=down step). See also Gouyou-Beauchamps reference. - David Callan, Mar 14 2004
From Paul Barry, May 24 2005: (Start)
a(n) = (1/(n+1))*Sum_{k=0..n} C(n+1, k)*C(2n-k, n)*(-1)^k*2^(n-k) [with offset 0].
a(n) = (1/(n+1))*Sum_{k=0..n} C(n+1, k+1)*C(n+k, k)*(-1)^(n-k)*2^k [with offset 0].
a(n) = Sum_{k=0..n} (1/(k+1))*C(n, k)*C(n+k, k)*(-1)^(n-k)*2^k [with offset 0].
a(n) = Sum_{k=0..n} A088617(n, k)*(-1)^(n-k)*2^k [with offset 0]. (End)
E.g.f. of a(n+1) is exp(3*x)*BesselI(1, 2*sqrt(2)*x)/(sqrt(2)*x). - Vladeta Jovovic, Mar 31 2004
Reversion of (x-2*x^2)/(1-x) is g.f. offset 1.
For n>=1, a(n) = Sum_{k=0..n} 2^k*N(n, k) where N(n, k) = (1/n)*C(n, k)*C(n, k+1) are the Narayana numbers (A001263). - Benoit Cloitre, May 10 2003 [This formula counts colored Dyck paths by number of peaks, which is easy to see because the Narayana numbers count Dyck paths by number of peaks and the number of peaks determines the number of interior ascent vertices.]
a(n) = Sum_{k=0..n} A088617(n, k)*2^k*(-1)^(n-k). - Philippe Deléham, Jan 21 2004
For n > 0, a(n) = (1/(n+1)) * Sum_{k = 0 .. n-1} binomial(2*n-k, n) * binomial(n-1, k). This formula counts colored Dyck paths (as above) by number of white vertices. - David Callan, Mar 14 2004
a(n-1) = (d^(n-1)/dx^(n-1))((1-x)/(1-2*x))^n/n!|_{x=0}. (For a proof see the comment on the unsigned row sums of triangle A111785.)
From Wolfdieter Lang, Sep 12 2005: (Start)
a(n) = (1/n)*Sum_{k=1..n} binomial(n, k)*binomial(n+k, k-1).
a(n) = hypergeom([1-n, n+2], [2], -1), n>=1. (End)
a(n) = hypergeom([1-n, -n], [2], 2) for n>=0. - Peter Luschny, Sep 22 2014
a(m+n+1) = Sum_{k>=0} A110440(m, k)*A110440(n, k)*2^k = A110440(m+n, 0). - Philippe Deléham, Sep 14 2005
Sum over partitions formula (reference Schroeder paper p. 362, eq. (1) II). Number the partitions of n according to Abramowitz-Stegun pp. 831-832 (see reference under A105805) with k=1..p(n)= A000041(n). For n>=1: a(n-1) = Sum_{k=2..p(n)} A048996(n,k)*a(1)^e(k, 1)*a(1)^e(k, 2)*...*a(n-2)^e(k, n-1) if the k-th partition of n in the mentioned order is written as (1^e(k, 1), 2^e(k, 2), ..., (n-1)e(k, n-1)). Note that the first (k=1) partition (n^1) has to be omitted. - Wolfdieter Lang, Aug 23 2005
Starting (1, 3, 11, 45, ...), = row sums of triangle A126216 = A001263 * [1, 2, 4, 8, 16, ...]. - Gary W. Adamson, Nov 30 2007
From Paul Barry, May 15 2009: (Start)
G.f.: 1/(1+x-2x/(1+x-2x/(1+x-2x/(1+x-2x/(1-.... (continued fraction).
G.f.: 1/(1-x/(1-x-x/(1-x-x/(1-x-x/(1-... (continued fraction).
G.f.: 1/(1-x-2x^2/(1-3x-2x^2/(1-3x-2x^2/(1-... (continued fraction). (End)
G.f.: 1 / (1 - x / (1 - 2*x / (1 - x / (1 - 2*x / ... )))). - Michael Somos, May 19 2013
a(n) = (LegendreP(n+1,3)-3*LegendreP(n,3))/(4*n) for n>0. - Mark van Hoeij, Jul 12 2010 [This formula is mentioned in S.-J. Kettle's 1982 letter - see link. N. J. A. Sloane, Jun 13 2015]
From Gary W. Adamson, Jul 08 2011: (Start)
a(n) = upper left term in M^n, where M is the production matrix:
1, 1, 0, 0, 0, 0, ...
2, 2, 2, 0, 0, 0, ...
1, 1, 1, 1, 0, 0, ...
2, 2, 2, 2, 2, 0, ...
1, 1, 1, 1, 1, 1, ...
... (End)
From Gary W. Adamson, Aug 23 2011: (Start)
a(n) is the sum of top row terms of Q^(n-1), where Q is the infinite square production matrix:
1, 2, 0, 0, 0, ...
1, 1, 2, 0, 0, ...
1, 1, 1, 2, 0, ...
1, 1, 1, 1, 2, ...
... (End)
Let h(t) = (1-t)^2/(2*(1-t)^2-1) = 1/(1-(2*t+3*t^2+4*t^3+...)), an o.g.f. for A003480, then for A001003 a(n) = (1/n!)*((h(t)*d/dt)^n) t, evaluated at t=0, with initial n=1. (Cf. A086810.) - Tom Copeland, Sep 06 2011
A006318(n) = 2*a(n) if n>0. - Michael Somos, Mar 31 2007
BINOMIAL transform is A118376 with offset 0. REVERT transform is A153881. INVERT transform is A006318. INVERT transform of A114710. HANKEL transform is A139685. PSUM transform is A104858. - Michael Somos, May 19 2013
G.f.: 1 + x/(Q(0) - x) where Q(k) = 1 + k*(1-x) - x - x*(k+1)*(k+2)/Q(k+1) ; (continued fraction). - Sergei N. Gladkovskii, Mar 14 2013
a(n) = A144944(n,n) = A186826(n,0). - Reinhard Zumkeller, May 11 2013
a(n)=(-1)^n*LegendreP(n,-1,-3)/sqrt(2), n > 0, LegendreP(n,a,b) is the Legendre function. - Karol A. Penson, Jul 06 2013
Integral representation as n-th moment of a positive weight function W(x) = W_a(x) + W_c(x), where W_a(x) = Dirac(x)/2, is the discrete (atomic) part, and W_c(x) = sqrt(8-(x-3)^2)/(4*Pi*x) is the continuous part of W(x) defined on (3 sqrt(8),3+sqrt(8)): a(n) = int( x^n*W_a(x), x=-eps..eps ) + int( x^n*W_c(x), x = 3-sqrt(8)..3+sqrt(8) ), for any eps>0, n>=0. W_c(x) is unimodal, of bounded variation and W_c(3-sqrt(8)) = W_c(3+sqrt(8)) = 0. Note that the position of the Dirac peak (x=0) lies outside support of W_c(x). - Karol A. Penson and Wojciech Mlotkowski, Aug 05 2013
G.f.: 1 + x/G(x) with G(x) = 1 - 3*x - 2*x^2/G(x) (continued fraction). - Nikolaos Pantelidis, Dec 17 2022

A000669 Number of series-reduced planted trees with n leaves. Also the number of essentially series series-parallel networks with n edges; also the number of essentially parallel series-parallel networks with n edges.

Original entry on oeis.org

1, 1, 2, 5, 12, 33, 90, 261, 766, 2312, 7068, 21965, 68954, 218751, 699534, 2253676, 7305788, 23816743, 78023602, 256738751, 848152864, 2811996972, 9353366564, 31204088381, 104384620070, 350064856815, 1176693361956, 3963752002320
Offset: 1

Views

Author

N. J. A. Sloane and John Riordan

Keywords

Comments

Also the number of unlabeled connected cographs on n nodes. - N. J. A. Sloane and Eric W. Weisstein, Oct 21 2003
A cograph is a simple graph which contains no path of length 3 as an induced subgraph. - Michael Somos, Apr 19 2014
Also called "hierarchies" by Genitrini (2016). - N. J. A. Sloane, Mar 24 2017

Examples

			G.f. = x + x^2 + 2*x^3 + 5*x^4 + 12*x^5 + 33*x^6 + 90*x^7 + 261*x^8 + ...
a(4)=5 with the following series-reduced planted trees: (oooo), (oo(oo)), (o(ooo)), (o(o(oo))), ((oo)(oo)). - _Michael Somos_, Jul 25 2003

References

  • N. L. Biggs et al., Graph Theory 1736-1936, Oxford, 1976, p. 43.
  • A. Brandstaedt, V. B. Le and J. P. Spinrad, Graph Classes: A Survey, SIAM Publications, 1999. (For definition of cograph)
  • A. Cayley, Collected Mathematical Papers. Vols. 1-13, Cambridge Univ. Press, London, 1889-1897, Vol. 3, p. 246.
  • D. E. Knuth, The Art of Computer Programming, 3rd ed. 1997, Vol. 1, p. 589, Answers to Exercises Section 2.3.4.4 5.
  • L. F. Meyers, Corrections and additions to Tree Representations in Linguistics. Report 3, 1966, p. 138. Project on Linguistic Analysis, Ohio State University Research Foundation, Columbus, Ohio.
  • L. F. Meyers and W. S.-Y. Wang, Tree Representations in Linguistics. Report 3, 1963, pp. 107-108. Project on Linguistic Analysis, Ohio State University Research Foundation, Columbus, Ohio.
  • J. Riordan and C. E. Shannon, The number of two-terminal series-parallel networks, J. Math. Phys., 21 (1942), 83-93 (the numbers called a_n in this paper). Reprinted in Claude Elwood Shannon: Collected Papers, edited by N. J. A. Sloane and A. D. Wyner, IEEE Press, NY, 1993, pp. 560-570.
  • N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

Equals (1/2)*A000084 for n >= 2.
Cf. A000055, A000311, A001678, A007827, A363064.
Cf. A000311, labeled hierarchies on n points.
Column 1 of A319254.
Main diagonal of A292085.
Row sums of A292086.

Programs

  • Maple
    Method 1: a := [1,1]; for n from 3 to 30 do L := series( mul( (1-x^k)^(-a[k]),k=1..n-1)/(1-x^n)^b, x,n+1); t1 := coeff(L,x,n); R := series( 1+2*add(a[k]*x^k,k=1..n-1)+2*b*x^n, x, n+1); t2 := coeff(R,x,n); t3 := solve(t1-t2,b); a := [op(a),t3]; od: A000669 := n-> a[n];
Method 2, more efficient: with(numtheory): M := 1001; a := array(0..M); p := array(0..M); a[1] := 1; a[2] := 1; a[3] := 2; p[1] := 1; p[2] := 3; p[3] := 7;
Method 2, cont.: for m from 4 to M do t1 := divisors(m); t3 := 0; for d in t1 minus {m} do t3 := t3+d*a[d]; od: t4 := p[m-1]+2*add(p[k]*a[m-k],k=1..m-2)+t3; a[m] := t4/m; p[m] := t3+t4; od: # A000669 := n-> a[n]; A058757 := n->p[n];
# Method 3:
b:= proc(n, i) option remember; `if`(n=0, 1,
      `if`(i<1, 0, add(binomial(a(i)+j-1, j)*
       b(n-i*j, i-1), j=0..n/i)))
    end:
a:= n-> `if`(n<2, n, b(n, n-1)):
seq(a(n), n=1..40);  # Alois P. Heinz, Jan 28 2016
  • Mathematica
    b[n_, i_] := b[n, i] = If[n==0, 1, If[i<1, 0, Sum[Binomial[a[i]+j-1, j]* b[n-i*j, i-1], {j, 0, n/i}]]];
a[n_] := If[n<2, n, b[n, n-1]];
Array[a, 40] (* Jean-François Alcover, Jan 08 2021, after Alois P. Heinz *)
  • PARI
    {a(n) = my(A, X); if( n<2, n>0, X = x + x * O(x^n); A = 1 / (1 - X); for(k=2, n, A /= (1 - X^k)^polcoeff(A, k)); polcoeff(A, n)/2)}; /* Michael Somos, Jul 25 2003 */
  • Sage
    from collections import Counter
def A000669_list(n):
    list = [1] + [0] * (n - 1)
    for i in range(1, n):
        for p in Partitions(i + 1, min_length=2):
            m = Counter(p)
            list[i] += prod(binomial(list[s - 1] + m[s] - 1, m[s]) for s in m)
    return list
print(A000669_list(20)) # M. Eren Kesim, Jun 21 2021

Formula

Product_{k>0} 1/(1-x^k)^a_k = 1+x+2*Sum_{k>1} a_k*x^k.
a(n) ~ c * d^n / n^(3/2), where d = 3.560839309538943329526129172709667..., c = 0.20638144460078903185013578707202765... [Ravelomanana and Thimonier, 2001]. - Vaclav Kotesovec, Aug 25 2014
Consider a nontrivial partition p of n. For each size s of a part occurring in p, compute binomial(a(s)+m-1, m) where m is the multiplicity of s. Take the product of this expression over all s. Take the sum of this new expression over all p to obtain a(n). - Thomas Anton, Nov 22 2018

Extensions

Sequence crossreference fixed by Sean A. Irvine, Sep 15 2009

A141268 Number of phylogenetic rooted trees with n unlabeled objects.

Original entry on oeis.org

1, 2, 4, 11, 30, 96, 308, 1052, 3648, 13003, 47006, 172605, 640662, 2402388, 9082538, 34590673, 132566826, 510904724, 1978728356, 7697565819, 30063818314, 117840547815, 463405921002, 1827768388175, 7228779397588, 28661434308095, 113903170011006, 453632267633931
Offset: 1

Views

Author

Thomas Wieder, Jun 20 2008

Keywords

Comments

Unlabeled analog of A005804 = Phylogenetic trees with n labels.
From Gus Wiseman, Jul 31 2018: (Start)
a(n) is the number of series-reduced rooted trees whose leaves form an integer partition of n. For example, the following are the a(4) = 11 series-reduced rooted trees whose leaves form an integer partition of 4.
4,
(13),
(22),
(112), (1(12)), (2(11)),
(1111), (11(11)), (1(1(11))), (1(111)), ((11)(11)).
(End)

Examples

			For n=4 we have A141268(4)=11 because
Set(Set(Z),Set(Z),Set(Z,Z)),
Set(Set(Z),Set(Set(Z),Set(Z,Z))),
Set(Z,Z,Z,Z),
Set(Set(Z,Z),Set(Z,Z)),
Set(Set(Set(Z),Set(Z)),Set(Z,Z)),
Set(Set(Z),Set(Z),Set(Set(Z),Set(Z))),
Set(Set(Z),Set(Z),Set(Z),Set(Z)),
Set(Set(Z),Set(Set(Z),Set(Z),Set(Z))),
Set(Set(Set(Z),Set(Z)),Set(Set(Z),Set(Z))),
Set(Set(Z),Set(Z,Z,Z)),
Set(Set(Z),Set(Set(Z),Set(Set(Z),Set(Z))))

Links

Crossrefs

Cf. A000081, A000311, A000669, A001678, A005804, A141268, A292504, A300660, A316655.

Programs

  • Maple
    with(combstruct): A141268 := [H, {H=Union(Set(Z,card>=1),Set(H,card>=2))}, unlabelled]; seq(count(A141268, size=j), j=1..20);
# second Maple program:
b:= proc(n,i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(b(n-i*j, i-1)*binomial(a(i)+j-1, j), j=0..n/i)))
    end:
a:= n-> `if`(n<2, n, 1+b(n, n-1)):
seq(a(n), n=1..30);  # Alois P. Heinz, Jun 18 2018
  • Mathematica
    facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
t[n_]:=t[n]=If[PrimeQ[n],{n},Join@@Table[Union[Sort/@Tuples[t/@fac]],{fac,Select[facs[n],Length[#]>1&]}]];
Table[Sum[Length[t[Times@@Prime/@ptn]],{ptn,IntegerPartitions[n]}],{n,7}] (* Gus Wiseman, Jul 31 2018 *)
b[n_, i_] := b[n, i] = If[n == 0, 1, If[i < 1, 0,
     Sum[b[n-i*j, i-1]*Binomial[a[i]+j-1, j], {j, 0, n/i}]]];
a[n_] := If[n < 2, n, 1 + b[n, n-1]];
Array[a, 30] (* Jean-François Alcover, May 21 2021, after Alois P. Heinz *)
  • PARI
    EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
seq(n)={my(v=vector(n)); for(n=1, n, v[n]=1 + EulerT(v[1..n])[n]); v} \\ Andrew Howroyd, Oct 26 2018

Formula

a(n) ~ c * d^n / n^(3/2), where d = 4.210216501727104448901818751..., c = 0.21649387167268793159311306... . - Vaclav Kotesovec, Sep 04 2014

Extensions

Offset corrected and more terms from Alois P. Heinz, Apr 21 2012

A005804 Number of phylogenetic rooted trees with n labels.

Original entry on oeis.org

1, 2, 8, 58, 612, 8374, 140408, 2785906, 63830764, 1658336270, 48169385024, 1546832023114, 54413083601268, 2080827594898342, 85948745163598088, 3813417859420469410, 180876816831806597500, 9133309115320844870078, 489156459621633161274704, 27696066472039561313329018
Offset: 1

Views

Author

N. J. A. Sloane

Keywords

Comments

These are series-reduced rooted trees where each leaf is a nonempty subset of the set of n labels.
See A141268 for phylogenetic rooted trees with n unlabeled objects. - Thomas Wieder, Jun 20 2008

Examples

			a(3)=8 because we have:
  Set(Set(Z[3]),Set(Z[1]),Set(Z[2])),
  Set(Z[3],Z[2],Z[1]),
  Set(Set(Z[3],Z[1]),Set(Z[2])),
  Set(Set(Set(Z[3]),Set(Z[2])),Set(Z[1])),
  Set(Set(Set(Z[3]),Set(Z[1])),Set(Z[2])),
  Set(Set(Z[3]),Set(Set(Z[1]),Set(Z[2]))),
  Set(Set(Z[3]),Set(Z[2],Z[1])),
  Set(Set(Z[3],Z[2]),Set(Z[1])).
From _Gus Wiseman_, Jul 31 2018: (Start)
The 8 series-reduced rooted trees whose leaves are a set partition of {1,2,3}:
  {1,2,3}
  ({1}{2,3})
  ({1}({2}{3}))
  ({2}{1,3})
  ({2}({1}{3}))
  ({3}{1,2})
  ({3}({1}{2}))
  ({1}{2}{3})
(End)

References

  • Foulds, L. R.; Robinson, R. W. Enumeration of phylogenetic trees without points of degree two. Ars Combin. 17 (1984), A, 169-183. Math. Rev. 85f:05045
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

Cf. A000081, A000311, A000669, A001678, A005805, A141268, A292504, A300660, A316656.

Programs

  • Maple
    # From Thomas Wieder, Jun 20 2008: (Start)
ser := series(-LambertW(-1/2*exp(1/2*exp(z)-1)) + 1/2*exp(z)-1, z=0, 10);
seq(n!*coeff(ser, z, n), n = 1..9);
# Alternative:
with(combstruct):
A005804 := [H, {H=Union(Set(Z,card>=1), Set(H,card>=2))}, labelled];
seq(count(A005804,size=j), j=1..20);
# (End)
  • Mathematica
    numSetPtnsOfType[ptn_]:=Total[ptn]!/Times@@Factorial/@ptn/Times@@Factorial/@Length/@Split[ptn];
a[n_]:=a[n]=If[n==1,1,1+Sum[numSetPtnsOfType[ptn]*Times@@a/@ptn,{ptn,Rest[IntegerPartitions[n]]}]];
Array[a,20] (* Gus Wiseman, Jul 31 2018 *)
  • PARI
    EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
b(n,k)={my(v=vector(n)); for(n=1, n, v[n]=binomial(n+k-1, n) + EulerT(v[1..n])[n]); v}
seq(n)={my(M=Mat(vectorv(n, k, b(n,k)))); vector(n, k, sum(i=1, k, binomial(k, i)*(-1)^(k-i)*M[i,k]))} \\ Andrew Howroyd, Oct 26 2018

Formula

Stirling transform of [ 1, 1, 4, 26, 236, ... ] = A000311 [ Foulds and Robinson ].
E.g.f.: -LambertW(-(1/2)*exp((1/2)*exp(z) - 1)) + (1/2)*exp(z) - 1. - Thomas Wieder, Jun 20 2008
a(n) ~ sqrt(log(2))*(log(2)+log(log(2)))^(1/2-n)*n^(n-1)/exp(n). - Vaclav Kotesovec, Aug 07 2013
E.g.f. f(x) satisfies 2*f(x) - exp(f(x)) = exp(x) - 2. - Gus Wiseman, Jul 31 2018

Extensions

More terms, comment from Christian G. Bower, Dec 15 1999

A008517 Second-order Eulerian triangle T(n,k), 1 <= k <= n.

Original entry on oeis.org

1, 1, 2, 1, 8, 6, 1, 22, 58, 24, 1, 52, 328, 444, 120, 1, 114, 1452, 4400, 3708, 720, 1, 240, 5610, 32120, 58140, 33984, 5040, 1, 494, 19950, 195800, 644020, 785304, 341136, 40320, 1, 1004, 67260, 1062500, 5765500, 12440064, 11026296, 3733920, 362880
Offset: 1

Views

Author

N. J. A. Sloane

Keywords

Comments

Second-order Eulerian numbers <> = T(n,k+1) count the permutations of the multiset {1,1,2,2,...,n,n} with k ascents with the restriction that for all m, all integers between the two copies of m are less than m. In particular, the two 1s are always next to each other.
When seen as coefficients of polynomials with descending exponents, evaluations are in A000311 (x=2) and A001662 (x=-1).
The row reversed triangle is A112007. There one can find comments on the o.g.f.s for the diagonals of the unsigned Stirling1 triangle |A008275|.
Stirling2(n,n-k) = Sum_{m=0..k-1} T(k,m+1)*binomial(n+k-1+m, 2*k), k>=1. See the Graham et al. reference p. 271 eq. (6.43).
This triangle is the coefficient triangle of the numerator polynomials appearing in the o.g.f. for the k-th diagonal (k >= 1) of the Stirling2 triangle A048993.
The o.g.f. for column k satisfies the recurrence G(k,x) = x*(2*x*(d/dx)G(k-1,x) + (2-k)*G(k-1,x))/(1-k*x), k >= 2, with G(1,x) = 1/(1-x). - Wolfdieter Lang, Oct 14 2005
This triangle is in some sense generated by the differential equation y' = 1 - 2/(1+x+y). (This is the differential equation satisfied by the function defined implicitly as x+y=exp(x-y).) If we take y = a(0) + a(1)x + a(2)x^2 + a(3)x^3 + ... and assume a(0)=c then all the a's may be calculated formally in terms of c and we have a(1) = (c-1)/(c+1) and, for n > 1, a(n) = 2^n/n! (1+c)^(1-2n)( T(n,1)c - T(n,2)c^2 + T(n,3)c^3 - ... + (-1)^(n-1) T(n,n)c^n ). - Moshe Shmuel Newman, Aug 08 2007
From the recurrence relation, the generating function F(x,y) := 1 + Sum_{n>=1, 1<=k<=n} [T(n,k)x^n/n!*y^k] satisfies the partial differential equation F = (1/y-2x)F_x + (y-1)F_y, with (non-elementary) solution F(x,y) = (1-y)/(1-Phi(w)) where w = y*exp(x(y-1)^2-y) and Phi(x) is defined by Phi(x) = x*exp(Phi(x)). By Lagrange inversion (see Wilf's book "generatingfunctionology", page 168, Example 1), Phi(x) = Sum_{n>=1} n^(n-1)*x^n/n!. Thus Phi(x) can alternatively be described as the e.g.f. for rooted labeled trees on n vertices A000169. - David Callan, Jul 25 2008
A method for solving PDEs such as the one above for F(x,y) is described in the Klazar reference (see pages 207-208). In his case, the auxiliary ODE dy/dx = b(x,y)/a(x,y) is exact; in this case it is not exact but has an integrating factor depending on y alone, namely y-1. The e.g.f. for the row sums A001147 is 1/sqrt(1-2*x) and the demonstration that F(x,1) = 1/sqrt(1-2*x) is interesting: two applications of l'Hopital's rule to lim_{y->1}F(x,y) yield F(x,1) = 1/(1-2x)*1/F(x,1). So l'Hopital's rule doesn't directly yield F(x,1) but rather an equation to be solved for F(x,1)!. - David Callan, Jul 25 2008
From Tom Copeland, Oct 12 2008; May 19 2010: (Start)
Let P(0,t)= 0, P(1,t)= 1, P(2,t)= t, P(3,t)= t + 2 t^2, P(4,t)= t + 8 t^2 + 6 t^3, ... be the row polynomials of the present array, then
exp(x*P(.,t)) = ( u + Tree(t*exp(u)) ) / (1-t) = WD(x*(1-t), t/(1-t)) / (1-t)
where u = x*(1-t)^2 - t, Tree(x) is the e.g.f. of A000169 and WD(x,t) is the e.g.f. for A134991, relating the Ward and 2-Eulerian polynomials by a simple transformation.
Note also apparently P(4,t) / (1-t)^3 = Ward Poly(4, t/(1-t)) = essentially an e.g.f. for A093500.
The compositional inverse of f(x,t) = exp(P(.,t)*x) about x=0 is
g(x,t) = ( x - (t/(1-t)^2)*(exp(x*(1-t))-x*(1-t)-1) )
= x - t*x^2/2! - t*(1-t)*x^3/3! - t*(1-t)^2*x^4/4! - t*(1-t)^3*x^5/5! - ... .
Can apply A134685 to these coefficients to generate f(x,t). (End)
Triangle A163936 is similar to the one given above except for an extra right hand column [1, 0, 0, 0, ... ] and that its row order is reversed. - Johannes W. Meijer, Oct 16 2009
From Tom Copeland, Sep 04 2011: (Start)
Let h(x,t) = 1/(1-(t/(1-t))*(exp(x*(1-t))-1)), an e.g.f. in x for row polynomials in t of A008292, then the n-th row polynomial in t of the table A008517 is given by ((h(x,t)*D_x)^(n+1))x with the derivative evaluated at x=0.
Also, df(x,t)/dx = h(f(x,t),t) where f(x,t) is an e.g.f. in x of the row polynomials in t of A008517, i.e., exp(x*P(.,t)) in Copeland's 2008 comment. (End)
The rows are the h-vectors of A134991. - Tom Copeland, Oct 03 2011
Hilbert series of the pre-WDVV ring, thus h-vectors of the Whitehouse simplicial complex (cf. Readdy, Table 1). - Tom Copeland, Sep 20 2014
Arises in Buckholtz's analysis of the error term in the series for exp(nz). - N. J. A. Sloane, Jul 05 2016

Examples

			Triangle begins:
  1;
  1,   2;
  1,   8,   6;
  1,  22,  58,  24;
  1,  52, 328, 444, 120; ...
Row 3: There are three plane increasing 0-1-2-3 trees on 3 vertices. The number of colors are shown to the right of a vertex.
.
    1o (2*t+1)         1o t*(t+2)      1o t*(t+2)
     |                 / \             / \
     |                /   \           /   \
    2o (2*t+1)      2o    3o        3o    2o
     |
     |
    3o
.
The total number of trees is (2*t+1)^2 + t*(t+2) + t*(t+2) = 1 + 8*t + 6*t^2.

References

  • R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, 2nd ed. Addison-Wesley, Reading, MA, 1994, p. 270. [with offsets [0,0]: see A201637]

Links

Crossrefs

Columns include A005803, A004301, A006260.
Right-hand columns include A000142, A002538, A002539.
Row sums are A001147.
For a (0,0) based version as used in 'Concrete Mathematics' and by Maple see A201637. For a (0,0) based version which has this triangle as a subtriangle see A340556.

Programs

  • Maple
    with(combinat): A008517 := proc(n, m) local k: add((-1)^(n+k)* binomial(2*n+1, k)* stirling1(2*n-m-k+1, n-m-k+1), k=0..n-m) end: seq(seq(A008517(n, m), m=1..n), n=1..8);
# Johannes W. Meijer, Oct 16 2009, revised Nov 22 2012
A008517 := proc(n,k) option remember; `if`(n=1,`if`(k=0,1,0), A008517(n-1,k)* (k+1) + A008517(n-1,k-1)*(2*n-k-1)) end: seq(print(seq(A008517(n,k), k=0..n-1)), n=1..9);
# Peter Luschny, Apr 20 2011
  • Mathematica
    a[n_, m_] = Sum[(-1)^(n + k)*Binomial[2 n + 1, k]*StirlingS1[2n-m-k+1, n-m-k+1], {k, 0, n-m}]; Flatten[Table[a[n, m], {n, 1, 9}, {m, 1, n}]][[1 ;; 44]] (* Jean-François Alcover, May 18 2011, after Johannes W. Meijer *)
  • PARI
    {T(n, k) = my(z); if( n<1, 0, z = 1 + O(x); for( k=1, n, z = 1 + intformal( z^2 * (z+y-1))); n! * polcoeff( polcoeff(z, n),k))}; /* Michael Somos, Oct 13 2002 */
  • PARI
    {T(n,k)=polcoeff((1-x)^(2*n+1)*sum(j=0,2*n+1,j^(n+j)*x^j/j!*exp(-j*x +x*O(x^k))),k)} \\ Paul D. Hanna, Oct 31 2012
for(n=1,10,for(k=1,n,print1(T(n,k),", "));print(""))
  • PARI
    T(n, m) = sum(k=0, n-m, (-1)^(n+k)*binomial(2*n+1, k)*stirling(2*n-m-k+1, n-m-k+1, 1)); \\ Michel Marcus, Dec 07 2021
  • Sage
    @CachedFunction
def A008517(n, k):
    if n==1: return 1 if k==0 else 0
    return A008517(n-1,k)*(k+1)+A008517(n-1,k-1)*(2*n-k-1)
for n in (1..9): [A008517(n, k) for k in(0..n-1)] # Peter Luschny, Oct 31 2012

Formula

T(n,k) = 0 if n < k, T(1,1) = 1, T(n,-1) = 0, T(n,k) = k*T(n-1,k) + (2*n-k)*T(n-1,k-1).
a(n,m) = Sum_{k=0..n-m} (-1)^(n+k)*binomial(2*n+1, k)*Stirling1(2*n-m-k+1, n-m-k+1). - Johannes W. Meijer, Oct 16 2009
From Peter Bala, Sep 29 2011: (Start)
For k = 0,1,2,... put G(k,x,t) := x-(1+2^k*t)*x^2/2+(1+2^k*t+3^k*t^2)*x^3/3-(1+2^k*t+3^k*t^2+4^k*t^3)*x^4/4+.... Then the series reversion of G(k,x,t) with respect to x gives an e.g.f. for the present table when k = 1 and for the Eulerian numbers A008292 when k = 0.
Let v = -t*exp((1-t)^2*x-t) and let B(x,t) = -(1+1/t*LambertW(v))/(1+LambertW(v)). From the e.g.f. given by Copeland above we find B(x,t) = compositional inverse with respect to x of G(1,x,t) = Sum_{n>=1} R(n,t)*x^n/n! = x+(1+2*t)*x^2/2!+(1+8*t+6*t^2)*x^3/3!+.... The function B(x,t) satisfies the differential equation dB/dx = (1+B)*(1+t*B)^2 = 1 + (2*t+1)*B + t*(t+2)*B^2 + t^2*B^3.
Applying [Bergeron et al., Theorem 1] gives a combinatorial interpretation for the row generating polynomials R(n,t): R(n,t) counts plane increasing trees where each vertex has outdegree <= 3, the vertices of outdegree 1 come in 2*t+1 colors, the vertices of outdegree 2 come in t*(t+2) colors and the vertices of outdegree 3 come in t^2 colors. An example is given below. Cf. A008292. Applying [Dominici, Theorem 4.1] gives the following method for calculating the row polynomials R(n,t): Let f(x,t) = (1+x)*(1+t*x)^2 and let D be the operator f(x,t)*d/dx. Then R(n+1,t) = D^n(f(x,t)) evaluated at x = 0. (End)
From Tom Copeland, Oct 03 2011: (Start)
a(n,k) = Sum_{i=0..k} (-1)^(k-i) binomial(n-i,k-i) A134991(n,i), offsets 0.
P(n+1,t) = (1-t)^(2n+1) Sum_{k>=1} k^(n+k) [t*exp(-t)]^k / k! for n>0; consequently, Sum_{k>=1} (-1)^k k^(n+k) x^k/k!= [1+LW(x)]^(-(2n+1))P[n+1,-LW(x)] where LW(x) is the Lambert W-Function and P(n,t), for n > 0, are the row polynomials as given in Copeland's 2008 comment. (End)
The e.g.f. A(x,t) = -v * { Sum_{j>=1} D(j-1,u) (-z)^j / j! } where u=x*(1-t)^2-t, v=(1+u)/(1-t), z=(t+u)/[(1+u)^2] and D(j-1,u) are the polynomials of A042977. dA(x,t)/dx=(1-t)/[1+u-(1-t)A(x,t)]=(1-t)/{1+LW[-t exp(u)]}, (Copeland's e.g.f. in 2008 comment). - Tom Copeland, Oct 06 2011
A133314 applied to the derivative of A(x,t) implies (a.+b.)^n = 0^n, for (b_n)=P(n+1,t) and (a_0)=1, (a_1)=-t, and (a_n)=-P(n,t) otherwise. E.g., umbrally, (a.+b.)^2 = a_2*b_0 + 2 a_1*b_1 + a_0*b_2 = 0. - Tom Copeland, Oct 08 2011
The compositional inverse (with respect to x) of y = y(t;x) = (x-t*(exp(x)-1)) is 1/(1-t)*y + t/(1-t)^3*y^2/2! + (t+2*t^2)/(1-t)^5*y^3/3! + (t+8*t^2+6*t^3)/(1-t)^7*y^4/4! + .... The numerator polynomials of the rational functions in t are the row polynomials of this triangle. As observed in the Comments section, the rational functions in t are the generating functions for the diagonals of the triangle of Stirling numbers of the second kind (A048993). See the Bala link for a proof. Cf. A112007 and A134991. - Peter Bala, Dec 04 2011
O.g.f. of row n: (1-x)^(2*n+1) * Sum_{k>=0} k^(n+k) * exp(-k*x) * x^k/k!. - Paul D. Hanna, Oct 31 2012
T(n, k) = n!*[x^n][t^k](egf) where egf = (1-t)/(1 + LambertW(-exp(t^2*x - 2*t*x - t + x)*t)) and after expansion W(-exp(-t)t) is substituted by (-t). - Shamil Shakirov, Feb 17 2025

A292504 Number of orderless tree-factorizations of n.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 1, 4, 2, 2, 1, 6, 1, 2, 2, 11, 1, 6, 1, 6, 2, 2, 1, 20, 2, 2, 4, 6, 1, 8, 1, 30, 2, 2, 2, 27, 1, 2, 2, 20, 1, 8, 1, 6, 6, 2, 1, 74, 2, 6, 2, 6, 1, 20, 2, 20, 2, 2, 1, 38, 1, 2, 6, 96, 2, 8, 1, 6, 2, 8, 1, 114, 1, 2, 6, 6, 2, 8, 1, 74, 11, 2, 1
Offset: 1

Views

Author

Gus Wiseman, Sep 17 2017

Keywords

Comments

A factorization of n is a finite multiset of positive integers greater than 1 with product n. An orderless tree-factorization of n is either (case 1) the number n itself or (case 2) a finite multiset of two or more orderless tree-factorizations, one of each factor in a factorization of n.
a(n) depends only on the prime signature of n. - Andrew Howroyd, Nov 18 2018

Examples

			The a(16)=11 orderless tree-factorizations are: 16, (28), (2(24)), (2(2(22))), (2(222)), (44), (4(22)), ((22)(22)), (224), (22(22)), (2222).

Links

Crossrefs

Cf. A000311, A001055, A050336, A141268, A281118, A292505.

Programs

  • Mathematica
    postfacs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[postfacs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
oltfacs[n_]:=If[n<=1,{{}},Prepend[Union@@Function[q,Sort/@Tuples[oltfacs/@q]]/@DeleteCases[postfacs[n],{n}],n]];
Table[Length[oltfacs[n]],{n,83}]
  • PARI
    seq(n)={my(v=vector(n), w=vector(n)); w[1]=v[1]=1; for(k=2, n, w[k]=v[k]+1; forstep(j=n\k*k, k, -k, my(i=j, e=0); while(i%k==0, i/=k; e++; v[j] += binomial(e+w[k]-1, e)*v[i]))); w} \\ Andrew Howroyd, Nov 18 2018

Formula

a(p^n) = A141268(n) for prime p. - Andrew Howroyd, Nov 18 2018

A000084 Number of series-parallel networks with n unlabeled edges. Also called yoke-chains by Cayley and MacMahon.

Original entry on oeis.org

1, 2, 4, 10, 24, 66, 180, 522, 1532, 4624, 14136, 43930, 137908, 437502, 1399068, 4507352, 14611576, 47633486, 156047204, 513477502, 1696305728, 5623993944, 18706733128, 62408176762, 208769240140, 700129713630, 2353386723912
Offset: 1

Views

Author

N. J. A. Sloane

Keywords

Comments

This is a series-parallel network: o-o; all other series-parallel networks are obtained by connecting two series-parallel networks in series or in parallel.
Also the number of unlabeled cographs on n nodes. - N. J. A. Sloane and Eric W. Weisstein, Oct 21 2003
Also the number of P_4-free graphs on n nodes. - Gordon F. Royle, Jul 04 2008
Equals row sums of triangle A144962 and the INVERT transform of A001572. - Gary W. Adamson, Sep 27 2008
See Cameron (1987) p. 165 for a bijection between series-parallel networks and cographs. - Michael Somos, Apr 19 2014

Examples

			G.f. = x + 2*x^2 + 4*x^3 + 10*x^4 + 24*x^5 + 66*x^6 + 180*x^7 + 522*x^8 + ...
The series-parallel networks with 1, 2 and 3 edges are:
1 edge: o-o
2 edges: o-o-o o=o
....................... /\
3 edges: o-o-o-o o-o=o o--o o-o-o
....................... \/ ..\_/

References

  • D. E. Knuth, The Art of Computer Programming, 3rd ed. 1997, Vol. 1, p. 589, Answers to Exercises Section 2.3.4.4 5.
  • J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 142.
  • J. Riordan and C. E. Shannon, The number of two-terminal series-parallel networks, J. Math. Phys., 21 (1942), 83-93. Reprinted in Claude Elwood Shannon: Collected Papers, edited by N. J. A. Sloane and A. D. Wyner, IEEE Press, NY, 1993, pp. 560-570.
  • 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, Vol. 2, 1999; see Problem 5.40, notes on p. 133.

Links

Crossrefs

Cf. A058351, A058352, A058353, A000311, A006351 (labeled version).
See also A058964, A058965, A363065.
Cf. A144962, A001572. - Gary W. Adamson, Sep 27 2008
Cf. A176500, A176502. - Sameen Ahmed Khan, Apr 27 2010

Programs

  • Maple
    # (continue from A000669):
A000084 := n-> if n=1 then 1 else 2*A000669(n); fi;
# N denotes all series-parallel networks, S = series networks, P = parallel networks; spec84 := [ N,{N=Union(Z,S,P),S=Set(Union(Z,P),card>=2),P=Set(Union(Z,S),card>=2)} ]: A000084 := n->combstruct[count](spec84,size=n);
  • Mathematica
    n = 27; s = 1/(1-x) + O[x]^(n+1); Do[s = s/(1-x^k)^Coefficient[s, x^k] + O[x]^(n+1), {k, 2, n}]; CoefficientList[s, x] // Rest (* Jean-François Alcover, Jun 20 2011, updated Jun 30 2015 *)
(* faster method: *)
sequenceA000084[n_] := Module[{product, x}, product[1] = Series[1/(1 - x), {x, 0, n}]; product[k_] := product[k] = Series[product[k - 1]/(1 - x^k)^Coefficient[ product[k - 1], x^k], {x, 0, n}]; Quiet[Rest[CoefficientList[product[n], x]]]]; sequenceA000084[27] (* Faris Nasybulin, Apr 29 2015 *)
n = 27; Rest@
CoefficientList[ Fold[ #1/(1 - x^#2)^Coefficient[#1, x, #2] &, 1/(1 - x) + O[x]^(n + 1), Range[2, n]], x] (* Oliver Seipel, Sep 19 2021 *)
  • PARI
    {a(n) = my(A); if( n<1, 0, A = 1 / (1 - x + x * O(x^n)); for(k=2, n, A /= (1 - x^k + x * O(x^n))^polcoeff(A, k)); polcoeff(A, n))}; /* Michael Somos, Oct 11 2006 */

Formula

The sequence satisfies Product_{k>=1} 1/(1-x^k)^A000669(k) = 1 + Sum_{k>=1} a(k)*x^k.
a(n) = 2*A000669(n) if n>0. - Michael Somos, Apr 17 2014
a(n) ~ C d^n/n^(3/2) where C = 0.412762889201578063700271574144..., d = 3.56083930953894332952612917270966777... is a root of Product_{n>=1} (1-1/x^n)^(-a(n)) = 2. - Riordan, Shannon, Moon, Rains, Sloane
Consider the free algebraic system with two commutative associative operators (x+y) and (x*y) and one generator A. The number of elements with n occurrences of the generator is a(n). - Michael Somos, Oct 11 2006 Examples: n=1: A. n=2: A+A, A*A. n=3: A+A+A, A+(A*A), A*(A+A), A*A*A.

Extensions

More decimal places in the third formula added by Vaclav Kotesovec, Jun 24 2014

A079500 Number of compositions of the integer n in which the first part is >= the other parts.

Original entry on oeis.org

1, 1, 2, 3, 5, 8, 14, 24, 43, 77, 140, 256, 472, 874, 1628, 3045, 5719, 10780, 20388, 38674, 73562, 140268, 268066, 513350, 984911, 1892875, 3643570, 7023562, 13557020, 26200182, 50691978, 98182666, 190353370, 369393466, 717457656, 1394632365, 2713061899
Offset: 0

Views

Author

Arnold Knopfmacher, Jan 21 2003

Keywords

Comments

Essentially the same as A007059: a(n) = A007059(n+1).
In lunar arithmetic in base 2, this is the number of lunar divisors of the number 111...1 (with n 1's). E.g., 1111 has a(4) = 5 divisors (see A048888). - N. J. A. Sloane, Feb 23 2011.
First differences of A186537. - N. J. A. Sloane, Feb 23 2011
Number of balanced ordered rooted trees with n non-root nodes (see A048816 for unordered balanced trees); see example. The compositions are obtained from the level sequences by identifying a length-k run of (non-root) levels [t, t+1, t+2, ..., t+k-1] with a part k. - Joerg Arndt, Jul 20 2014

Examples

			From _Joerg Arndt_, Dec 29 2012: (Start)
There are a(7)=24 compositions p(1)+p(2)+...+p(m)=7 such that p(k) <= p(1):
[ 1]  [ 1 1 1 1 1 1 1 ]
[ 2]  [ 2 1 1 1 1 1 ]
[ 3]  [ 2 1 1 1 2 ]
[ 4]  [ 2 1 1 2 1 ]
[ 5]  [ 2 1 2 1 1 ]
[ 6]  [ 2 1 2 2 ]
[ 7]  [ 2 2 1 1 1 ]
[ 8]  [ 2 2 1 2 ]
[ 9]  [ 2 2 2 1 ]
[10]  [ 3 1 1 1 1 ]
[11]  [ 3 1 1 2 ]
[12]  [ 3 1 2 1 ]
[13]  [ 3 1 3 ]
[14]  [ 3 2 1 1 ]
[15]  [ 3 2 2 ]
[16]  [ 3 3 1 ]
[17]  [ 4 1 1 1 ]
[18]  [ 4 1 2 ]
[19]  [ 4 2 1 ]
[20]  [ 4 3 ]
[21]  [ 5 1 1 ]
[22]  [ 5 2 ]
[23]  [ 6 1 ]
[24]  [ 7 ]
(End)
From _Joerg Arndt_, Jul 20 2014: (Start)
The a(7) = 24 balanced ordered rooted trees with 7 non-root nodes are, as level sequences (of the pre-order walk):
01:  [ 0 1 1 1 1 1 1 1 ]
02:  [ 0 1 2 1 2 1 2 2 ]
03:  [ 0 1 2 1 2 2 1 2 ]
04:  [ 0 1 2 1 2 2 2 2 ]
05:  [ 0 1 2 2 1 2 1 2 ]
06:  [ 0 1 2 2 1 2 2 2 ]
07:  [ 0 1 2 2 2 1 2 2 ]
08:  [ 0 1 2 2 2 2 1 2 ]
09:  [ 0 1 2 2 2 2 2 2 ]
10:  [ 0 1 2 3 1 2 3 3 ]
11:  [ 0 1 2 3 2 3 2 3 ]
12:  [ 0 1 2 3 2 3 3 3 ]
13:  [ 0 1 2 3 3 1 2 3 ]
14:  [ 0 1 2 3 3 2 3 3 ]
15:  [ 0 1 2 3 3 3 2 3 ]
16:  [ 0 1 2 3 3 3 3 3 ]
17:  [ 0 1 2 3 4 2 3 4 ]
18:  [ 0 1 2 3 4 3 4 4 ]
19:  [ 0 1 2 3 4 4 3 4 ]
20:  [ 0 1 2 3 4 4 4 4 ]
21:  [ 0 1 2 3 4 5 4 5 ]
22:  [ 0 1 2 3 4 5 5 5 ]
23:  [ 0 1 2 3 4 5 6 6 ]
24:  [ 0 1 2 3 4 5 6 7 ]
(End)
From _Gus Wiseman_, Oct 07 2018: (Start)
The a(0) = 1 through a(6) = 14 balanced rooted plane trees:
  o  (o)  (oo)   (ooo)    (oooo)     (ooooo)      (oooooo)
          ((o))  ((oo))   ((ooo))    ((oooo))     ((ooooo))
                 (((o)))  (((oo)))   (((ooo)))    (((oooo)))
                          ((o)(o))   ((o)(oo))    ((o)(ooo))
                          ((((o))))  ((oo)(o))    ((oo)(oo))
                                     ((((oo))))   ((ooo)(o))
                                     (((o)(o)))   ((((ooo))))
                                     (((((o)))))  (((o)(oo)))
                                                  (((oo)(o)))
                                                  ((o)(o)(o))
                                                  (((((oo)))))
                                                  ((((o)(o))))
                                                  (((o))((o)))
                                                  ((((((o))))))
(End)

References

  • Arnold Knopfmacher and Neville Robbins, Compositions with parts constrained by the leading summand, Ars Combin. 76 (2005), 287-295.

Links

Crossrefs

Cf. A188541.
Cf. A000081 A000311, A001678, A120803, A320154, A320160, A316624, A320169.
Cf. A092921.

Programs

  • Maple
    M:=101:
t1:=add( (1-x)*x^k/(1-2*x+x^k), k=1..M):
series(t1,x,M-1);
seriestolist(%);
# second Maple program:
b:= proc(n, m) option remember; `if`(n=0, 1,
      `if`(m=0, add(b(n-j, j), j=1..n),
      add(b(n-j, min(n-j, m)), j=1..min(n, m))))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..40);  # Alois P. Heinz, May 01 2014
  • Mathematica
    nn=36;CoefficientList[Series[Sum[x^i/(1-(x-x^(i+1))/(1-x)),{i,0,nn}],{x,0,nn}],x]  (* Geoffrey Critzer, Mar 12 2013 *)
b[n_, m_] := b[n, m] = If[n==0, 1, If[m==0, Sum[b[n-j, j], {j, 1, n}], Sum[ b[n-j, Min[n-j, m]], {j, 1, Min[n, m]}]]]; a[n_] := b[n, 0]; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Nov 23 2015, after Alois P. Heinz *)

Formula

G.f.: (1-z) * Sum_{k>=0} z^k/(1 - 2*z + z^(k+1)).
a(n) = A048888(n) - 1.
This is a subsequence of A067399: a(n) = A067399(2^n-1).
G.f.: -((1 + x^2 + 1/(x-1))/x)*( 1 + x*(x-1)^3*(1-x+x^3)/( Q(0) - x*(x-1)^3*(1-x+x^3)) ), where Q(k) = (x+1)*(2*x-1)*(1-x)^2 + x^(k+2)*(x+x^2+x^3-2*x^4-1 - x^(k+3) + x^(k+5)) - x*(-1+2*x-x^(k+3))*(1-2*x+x^2+x^(k+4)-x^(k+5))*(-1+4*x-5*x^2+2*x^3 - x^(k+2)- x^(k+5) + 2*x^(k+3) - x^(2*k+5) + x^(2*k+6))/Q(k+1) ; (continued fraction). - Sergei N. Gladkovskii, Dec 14 2013
a(n) = Sum_{j=1..n} F(j, n+1-j), where F(n,k) is the n-th k-generalized Fibonacci number A092921(k,n). - Gregory L. Simay, Aug 21 2022

Extensions

Offset corrected by N. J. A. Sloane, Feb 23 2011
More terms from N. J. A. Sloane, Feb 24 2011
Further edits (required in order to clarify the definition - is the first part >= the rest. or only > the rest? Answer: the former; for the latter, see A007059) by N. J. A. Sloane, May 08 2011
Showing 1-10 of 105 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.