login
This site is supported by donations to The OEIS Foundation.

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. - Tom Copeland, Oct 11 2008

REFERENCES

Cameron, Peter J. Some treelike objects. Quart. J. Math. Oxford Ser. (2) 38 (1987), no. 150, 155--183. MR0891613 (89a:05009). See p. 155. - N. J. A. Sloane, Apr 18 2014

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 224.

J. Felsenstein, Inferring phyogenies, Sinauer Associates, 2004; see p. 25ff.

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

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]

A. Blass, N. Dobrinen, D. Raghavan, The next best thing to a P-point, arXiv preprint arXiv:1308.3790, 2013

P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

P. J. Cameron, Some treelike objects, Quart. J. Math. Oxford, 38 (1987), 155-183. See p. 159

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}).

Brian Drake, Ira M. Gessel, and Guoce Xin, Three Proofs and a Generalization of the Goulden-Litsyn-Shevelev Conjecture on a Sequence Arising in Algebraic Geometry, J. of Integer Sequences, Vol. 10 (2007), Article 07.3.7

J. Felsenstein, The number of evolutionary trees, Systematic Biology, 27 (1978), pp. 27-33, 1978.

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

V. P. Johnson, Enumeration Results on Leaf Labeled Trees, Ph. D. Dissertation, Univ. Southern Calif., 2012. - From N. J. A. Sloane, Jan 02 2013

Vladimir V. Kruchinin, The method for obtaining expressions for coefficients of reverse generating functions, arXiv:1211.3244

Z. A. Lomnicki, Two-terminal series-parallel networks, Adv. Appl. Prob., 4 (1972), 109-150.

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

G.f.: x*Q(0), where Q(k) = 1 - x*(k+1)/(x*(k+1) - (1-k*x)*(1-x-k*x)/Q(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Oct 11 2013

a(n) ~ n^(n-1) / (sqrt(2) * exp(n) * (2*log(2)-1)^(n-1/2)). - Vaclav Kotesovec, Jan 05 2014

EXAMPLE

G.f. = x + x^2 + 4*x^3 + 26*x^4 + 236*x^5 + 2752*x^6 + 39208*x^7 + ...

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]]; (* 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 formula 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 * A244451 A001863 A209923

Adjacent sequences:  A000308 A000309 A000310 * A000312 A000313 A000314

KEYWORD

nonn,core,easy,nice

AUTHOR

N. J. A. Sloane

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified July 30 20:52 EDT 2014. Contains 245075 sequences.