%I A000311 M3613 N1465
%S A000311 0,1,1,4,26,236,2752,39208,660032,12818912,282137824,6939897856,
%T A000311 188666182784,5617349020544,181790703209728,6353726042486272,238513970965257728,
%U A000311 9571020586419012608,408837905660444010496,18522305410364986906624
%N A000311 Schroeder's fourth problem; also number of phylogenetic trees with n 
               nodes; also number of total partitions of n.
%C A000311 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.
%C A000311 Polynomials with coefficients in triangle A008517, evaluated at 2. - 
               Ralf Stephan, Dec 13 2004
%C A000311 Row sums of unsigned A134685. [From Tom Copeland (tcjpn(AT)msn.com), 
               Oct 11 2008]
%D A000311 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%D A000311 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 
               (includes this sequence).
%D A000311 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}).
%D A000311 L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 224.
%D A000311 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.
%D A000311 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
%D A000311 Z. A. Lomnicki, Two-terminal series-parallel networks, Adv. Appl. Prob., 
               4 (1972), 109-150.
%D A000311 J. W. Moon, Some enumerative results on series-parallel networks, Annals 
               Discrete Math., 33 (1987), 199-226.
%D A000311 T. S. Motzkin, Sorting numbers for cylinders and other classification 
               numbers, in Combinatorics, Proc. Symp. Pure Math. 19, AMS, 1971, 
               pp. 167-176.
%D A000311 T. S. Motzkin, Sorting numbers ...: for a link to this paper see A000262.
%D A000311 J. Riordan, Combinatorial Identities, Wiley, 1968, p. 197.
%D A000311 J. Riordan, The blossoming of Schroeder's fourth problem, Acta Math., 
               137 (1976), 1-16.
%D A000311 E. Schroeder, Vier combinatorische Probleme, Z. f. Math. Phys., 15 (1870), 
               361-376.
%D A000311 R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see 
               Example 5.2.5, Equation (5.27). See also the Notes on page 66.
%H A000311 N. J. A. Sloane, <a href="b000311.txt">Table of n, a(n) for n = 0..375</
               a> [Shortened file because terms grow rapidly: see Sloane link below 
               for additional terms]
%H A000311 P. J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/index.html">
               Sequences realized by oligomorphic permutation groups</a>, J. Integ. 
               Seqs. Vol. 3 (2000), #00.1.5.
%H A000311 S. R. Finch, <a href="http://algo.inria.fr/bsolve/">Series-parallel networks</
               a>
%H A000311 Philippe Flajolet, <a href="http://algo.inria.fr/libraries/autocomb/schroeder-html/
               schroeder1.html">A Problem in Statistical Classification Theory</
               a>
%H A000311 Daniel L. Geisler, <a href="http://www.tetration.org/Combinatorics/index.html">
               Combinatorics of Iterated Functions</a>
%H A000311 INRIA Algorithms Project, <a href="http://algo.inria.fr/bin/encyclopedia?Search=ECSnb&argsearch=69">
               Encyclopedia of Combinatorial Structures 69</a>
%H A000311 N. J. A. Sloane, <a href="a000311.txt">Table of n, a(n) for n = 0..500</
               a>
%H A000311 <a href="Sindx_Tra.html#trees">Index entries for sequences related to 
               trees</a>
%H A000311 <a href="Sindx_Ro.html#rooted">Index entries for sequences related to 
               rooted trees</a>
%H A000311 <a href="Sindx_Cor.html#core">Index entries for "core" sequences</a>
%H A000311 <a href="Sindx_Mo.html#Moon87">Index entries for sequences mentioned 
               in Moon (1987)</a>
%H A000311 <a href="Sindx_Par.html#parens">Index entries for sequences related to 
               parenthesizing</a>
%H A000311 P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/
               Publications/books.html">Analytic Combinatorics</a>, 2009; see page 
               129
%F A000311 E.g.f. A(x) satisfies exp A(x) = 2 A(x) - x + 1.
%F A000311 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).
%F A000311 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 (tcjpn(AT)msn.com), Feb 11 2008
%p A000311 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:
%p A000311 Order := 50; t1 := solve(series((exp(A)-2*A-1),A)=-x,A); A000311 := n-> 
               n!*coeff(t1,x,n);
%o A000311 (PARI) a(n)=local(A=0);if(n<0,0, for(i=1,n,A=Pol(exp(A+x*O(x^i))-A+x-1));
               n!*polcoeff(A,n))
%Y A000311 Cf. A000669, A001003, A007827, A005804, A005805, A006351, A000084.
%Y A000311 For n >= 2, A000311(n) = A006351(n)/2 = A005640(n)/2^(n+1).
%Y A000311 Cf. A000110, A000669 = unlabeled hierarchies, A119649.
%Y A000311 Row sums of A064060.
%Y A000311 Sequence in context: A000310 A054360 A124824 this_sequence A001863 A115416 
               A052577
%Y A000311 Adjacent sequences: A000308 A000309 A000310 this_sequence A000312 A000313 
               A000314
%K A000311 nonn,core,easy,nice
%O A000311 0,4
%A A000311 N. J. A. Sloane (njas(AT)research.att.com).