|
| |
|
|
A000311
|
|
Schroeder's fourth problem; also number of phylogenetic trees with n nodes; also number of total partitions of n.
(Formerly M3613 N1465)
|
|
35
|
|
|
|
0, 1, 1, 4, 26, 236, 2752, 39208, 660032, 12818912, 282137824, 6939897856, 188666182784, 5617349020544, 181790703209728, 6353726042486272, 238513970965257728, 9571020586419012608, 408837905660444010496, 18522305410364986906624
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,4
|
|
|
COMMENTS
|
a(n) = number of labeled series-reduced rooted trees with n leaves (root has degree 0 or >= 2); a(n-1) = number of labeled series-reduced trees with n leaves. Also number of series-parallel networks with n labeled edges, divided by 2.
Polynomials with coefficients in triangle A008517, evaluated at 2. - Ralf Stephan, Dec 13 2004
Row sums of unsigned A134685. [From Tom Copeland, Oct 11 2008]
|
|
|
REFERENCES
|
L. Carlitz and J. Riordan, The number of labeled two-terminal series-parallel networks, Duke Math. J. 23 (1956), 435-445 (the sequence called {A_n}).
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 224.
B. Drake, I. M. Gessel and G. Xin, Three proofs and a generalization of the Goulden-Litsyn-Shevelev conjecture ..., J. Integer Sequences, Vol. 10 (2007), #07.3.7.
J. Felsenstein, Inferring phyogenies, Sinauer Associates, 2004; see p. 25ff.
J. Felsenstein, The number of evolutionary trees, Systematic Biology, 27 (1978), pp. 27-33, 1978.
L. R. Foulds and R. W. Robinson, Enumeration of phylogenetic trees without points of degree two. Ars Combin. 17 (1984), A, 169-183. Math. Rev. 85f:05045
V. P. Johnson, Enumeration Results on Leaf Labeled Trees, Ph. D. Dissertation, Univ. Southern Calif., 2012; http://www.math.sc.edu/~czabarka/JohnsonThesis.pdf. - From N. J. A. Sloane, Jan 02 2013
Z. A. Lomnicki, Two-terminal series-parallel networks, Adv. Appl. Prob., 4 (1972), 109-150.
J. W. Moon, Some enumerative results on series-parallel networks, Annals Discrete Math., 33 (1987), 199-226.
T. S. Motzkin, Sorting numbers for cylinders and other classification numbers, in Combinatorics, Proc. Symp. Pure Math. 19, AMS, 1971, pp. 167-176.
T. S. Motzkin, Sorting numbers ...: for a link to this paper see A000262.
J. Riordan, Combinatorial Identities, Wiley, 1968, p. 197.
J. Riordan, The blossoming of Schroeder's fourth problem, Acta Math., 137 (1976), 1-16.
E. Schroeder, Vier combinatorische Probleme, Z. 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 Example 5.2.5, Equation (5.27). See also the Notes on page 66.
|
|
|
LINKS
|
N. J. A. Sloane, Table of n, a(n) for n = 0..375 [Shortened file because terms grow rapidly: see Sloane link below for additional terms]
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
S. R. Finch, Series-parallel networks
Philippe Flajolet, A Problem in Statistical Classification Theory
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 129
Daniel L. Geisler, Combinatorics of Iterated Functions
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 69
Vladimir V. Kruchinin, The method for obtaining expressions for coefficients of reverse generating functions, arXiv:1211.3244
P. Regner, Phylogenetic Trees: Selected Combinatorial Problems, Master Thesis, 2012, Institute of Discrete Mathematics and Geometry, TU Vienna, pp. 50-59
N. J. A. Sloane, Table of n, a(n) for n = 0..500
Index entries for sequences related to trees
Index entries for sequences related to rooted trees
Index entries for "core" sequences
Index entries for sequences mentioned in Moon (1987)
Index entries for sequences related to parenthesizing
|
|
|
FORMULA
|
E.g.f. A(x) satisfies exp A(x) = 2*A(x) - x + 1.
a(0)=0, a(1)=a(2)=1; for n >= 2, a(n+1) = (n+2)*a(n) + 2*Sum_{k=2..n-1} binomial(n, k)*a(k)*a(n-k+1).
a(1)=1; for n>1, a(n) = -(n-1) * a(n-1) + Sum_{k=1..n-1} binomial(n, k) * a(k) * a(n-k). - Michael Somos, Jun 04 2012
From the umbral operator L in A135494 acting on x^n comes, umbrally, (a(.) + x)^n = (n * x^(n-1) / 2) - (x^n / 2) + sum(j=1,...) [ j^(j-1) * 2^(-j) / j! * exp(-j/2) * (x+j/2)^n ] giving a(n) = 2^(-n) * sum(j=1,...) { j^(n-1) * [ (j/2) * exp(-1/2) ]^j / j! } for n > 1. - Tom Copeland, Feb 11 2008
Let h(x) = 1/(2-exp(x)), an e.g.f. for A000670, then the n-th term of A000311 is given by ((h(x)*d/dx)^n)x evaluated at x=0, i.e., A(x) = exp(x*a(.)) = exp(x*h(u)*d/du) u evaluated at u=0. Also, dA(x)/dx = h(A(x)). - Tom Copeland, Sep 05 2011
A134991 gives (b.+c.)^n = 0^n , for (b_n)=A000311(n+1) and (c_0)=1, (c_1)=-1, and (c_n)=-2* A000311(n) = -A006351(n) otherwise. E.g., umbrally, (b.+c.)^2 = b_2*c_0 + 2 b_1*c_1 + b_0*c_2 =0. - Tom Copeland, Oct 19 2011
a(n)=sum(k=1..n-1, (n+k-1)!*sum(j=1..k, 1/(k-j)!*sum(i=0..j, (2^i*(-1)^(i)*stirling2(n+j-i-1,j-i))/((n+j-i-1)!*i!)))), n>1, a(0)=0, a(1)=1. [From Vladimir Kruchinin, Jan 28 2012]
Using L. Comet's identity and D. Wasserman's explicit formula for the associated Stirling numbers of second kind (A008299) one gets: a(n) = sum(m=1..n-1, sum(i=0..m, (-1)^i * Binomial(n+m-1,i) * sum(j=0..m-i, (-1)^j * ((m-i-j)^(n+m-1-i))/(j! * (m-i-j)!)))) - Peter Regner, Oct 08 2012
G.f.: x/Q(0), where Q(k)= 1 - k*x - x*(k+1)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, May 01 2013
|
|
|
MAPLE
|
M:=499; a:=array(0..500); a[0]:=0; a[1]:=1; a[2]:=1; for n from 0 to 2 do lprint(n, a[n]); od: for n from 2 to M do a[n+1]:=(n+2)*a[n]+2*add(binomial(n, k)*a[k]*a[n-k+1], k=2..n-1); lprint(n+1, a[n+1]); od:
Order := 50; t1 := solve(series((exp(A)-2*A-1), A)=-x, A); A000311 := n-> n!*coeff(t1, x, n);
|
|
|
MATHEMATICA
|
nn = 19; CoefficientList[ InverseSeries[ Series[1+2a-E^a, {a, 0, nn}], x], x]*Range[0, nn]! (* Jean-François Alcover, Jul 21 2011 *)
a[ n_] := If[ n < 1, 0, n! SeriesCoefficient[ InverseSeries[ Series[ 1 + 2 x - Exp[x], {x, 0, n}]], n]]; Table[a[n], {n, 0, 20}] (* Michael Somos, Jun 04 2012 *)
a[n_] := (If[n < 2, n, (column = ConstantArray[0, n - 1]; column[[1]] = 1; For[j = 3, j <= n, j++, column = column * Flatten[{Range[j - 2], ConstantArray[0, (n - j) + 1]}] + Drop[Prepend[column, 0], -1] * Flatten[{Range[j - 1, 2*j - 3], ConstantArray[0, n - j]}]; ]; Sum[column[[i]], {i, n - 1}] )]); Table[a[n], {n, 0, 20}] (* Peter Regner, Oct 05 2012, after a formular by Felsenstein (1978) *)
|
|
|
PROG
|
(PARI) {a(n) = local(A); if( n<0, 0, for( i=1, n, A = Pol(exp(A + x * O(x^i)) - A + x - 1)); n! * polcoeff(A, n))} /* Michael Somos, Jan 15 2004 */
(Maxima) a(n):=if n=1 then 1 else sum((n+k-1)!*sum(1/(k-j)!*sum((2^i*(-1)^(i)*stirling2(n+j-i-1, j-i))/((n+j-i-1)!*i!), i, 0, j), j, 1, k), k, 1, n-1); [Vladimir Kruchinin, Jan 28 2012]
|
|
|
CROSSREFS
|
Cf. A000669, A001003, A007827, A005804, A005805, A006351, A000084.
For n >= 2, A000311(n) = A006351(n)/2 = A005640(n)/2^(n+1).
Cf. A000110, A000669 = unlabeled hierarchies, A119649.
Row sums of A064060.
Sequence in context: A000310 A054360 A124824 * A001863 A209923 A115416
Adjacent sequences: A000308 A000309 A000310 * A000312 A000313 A000314
|
|
|
KEYWORD
|
nonn,core,easy,nice
|
|
|
AUTHOR
|
N. J. A. Sloane.
|
|
|
STATUS
|
approved
|
| |
|
|
