login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000311 Schroeder's fourth problem; also series-reduced rooted trees with n labeled leaves; also number of total partitions of n.
(Formerly M3613 N1465)
99

%I M3613 N1465

%S 0,1,1,4,26,236,2752,39208,660032,12818912,282137824,6939897856,

%T 188666182784,5617349020544,181790703209728,6353726042486272,

%U 238513970965257728,9571020586419012608,408837905660444010496,18522305410364986906624

%N Schroeder's fourth problem; also series-reduced rooted trees with n labeled leaves; also number of total partitions of n.

%C 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 A total partition of n is essentially what is meant by the first part of the previous line: take the numbers 12...n, and partition them into at least two blocks. Partition each block with at least 2 elements into at least two blocks. Repeat until only blocks of size 1 remain. (See the reference to Stanley, Vol. 2.) - _N. J. A. Sloane_, Aug 03 2016

%C Polynomials with coefficients in triangle A008517, evaluated at 2. - _Ralf Stephan_, Dec 13 2004

%C Row sums of unsigned A134685. - _Tom Copeland_, Oct 11 2008

%C Row sums of A134991, which contains an e.g.f. for this sequence and its compositional inverse. - _Tom Copeland_, Jan 24 2018

%C From _Gus Wiseman_, Dec 28 2019: (Start)

%C Also the number of singleton-reduced phylogenetic trees with n labels. A phylogenetic tree is a series-reduced rooted tree whose leaves are (usually disjoint) nonempty sets. It is singleton-reduced if no non-leaf node covers only singleton branches. For example, the a(4) = 26 trees are:

%C {1,2,3,4} {{1},{2},{3,4}} {{1},{2,3,4}}

%C {{1},{2,3},{4}} {{1,2},{3,4}}

%C {{1,2},{3},{4}} {{1,2,3},{4}}

%C {{1},{2,4},{3}} {{1,2,4},{3}}

%C {{1,3},{2},{4}} {{1,3},{2,4}}

%C {{1,4},{2},{3}} {{1,3,4},{2}}

%C {{1,4},{2,3}}

%C {{{1},{2,3}},{4}}

%C {{{1,2},{3}},{4}}

%C {{1},{{2},{3,4}}}

%C {{1},{{2,3},{4}}}

%C {{{1},{2,4}},{3}}

%C {{{1,2},{4}},{3}}

%C {{1},{{2,4},{3}}}

%C {{{1,3},{2}},{4}}

%C {{{1},{3,4}},{2}}

%C {{{1,3},{4}},{2}}

%C {{{1,4},{2}},{3}}

%C {{{1,4},{3}},{2}}

%C (End)

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

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

%D 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 T. S. Motzkin, Sorting numbers for cylinders and other classification numbers, in Combinatorics, Proc. Symp. Pure Math. 19, AMS, 1971, pp. 167-176.

%D J. Riordan, Combinatorial Identities, Wiley, 1968, p. 197.

%D E. Schroeder, Vier combinatorische Probleme, Z. f. Math. Phys., 15 (1870), 361-376.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see "total partitions", Example 5.2.5, Equation (5.27), and also Fig. 5-3 on page 14. See also the Notes on page 66.

%H N. J. A. Sloane, <a href="/A000311/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 Mohamed Barakat, Reimer Behrends, Christopher Jefferson, Lukas Kühne, Martin Leuner, <a href="https://arxiv.org/abs/1907.01073">On the generation of rank 3 simple matroids with an application to Terao's freeness conjecture</a>, arXiv:1907.01073 [math.CO], 2019.

%H Frédérique Bassino, Mathilde Bouvel, Valentin Féray, Lucas Gerin, Mickaël Maazoun, Adeline Pierrot, <a href="https://arxiv.org/abs/1907.08517">Random cographs: Brownian graphon limit and asymptotic degree distribution</a>, arXiv:1907.08517 [math.CO], 2019.

%H A. Blass, N. Dobrinen, D. Raghavan, <a href="http://arxiv.org/abs/1308.3790">The next best thing to a P-point</a>, arXiv preprint arXiv:1308.3790 [math.LO], 2013.

%H P. J. Cameron, <a href="http://dx.doi.org/10.1093/qmath/38.2.155">Some treelike objects</a>, Quart. J. Math. Oxford, 38 (1987), 155-183. MR0891613 (89a:05009). See p. 155 and 159.

%H P. J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/groups.html">Sequences realized by oligomorphic permutation groups</a>, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

%H L. Carlitz and J. Riordan, <a href="http://dx.doi.org/10.1215/S0012-7094-56-02340-7">The number of labeled two-terminal series-parallel networks</a>, Duke Math. J. 23 (1956), 435-445 (the sequence called {A_n}).

%H Brian Drake, Ira M. Gessel, and Guoce Xin, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL10/Gessel/gessel20.html">Three Proofs and a Generalization of the Goulden-Litsyn-Shevelev Conjecture on a Sequence Arising in Algebraic Geometry,</a> J. of Integer Sequences, Vol. 10 (2007), Article 07.3.7

%H John Engbers, David Galvin, Clifford Smyth, <a href="https://arxiv.org/abs/1610.05803">Restricted Stirling and Lah numbers and their inverses</a>, arXiv:1610.05803 [math.CO], 2016.

%H J. Felsenstein, <a href="/A005373/a005373.pdf">The number of evolutionary trees</a>, Systematic Zoology, 27 (1978), 27-33. (Annotated scanned copy)

%H J. Felsenstein, <a href="http://www.jstor.org/stable/2412810">The number of evolutionary trees</a>, Systematic Biology, 27 (1978), pp. 27-33, 1978.

%H S. R. Finch, <a href="/A000084/a000084_2.pdf">Series-parallel networks</a>, July 7, 2003. [Cached copy, with permission of the author]

%H Steven R. Finch, <a href="https://doi.org/10.1017/9781316997741">Mathematical Constants II</a>, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, 2018.

%H Philippe Flajolet, <a href="http://algo.inria.fr/libraries/autocomb/schroeder-html/schroeder1.html">A Problem in Statistical Classification Theory</a>

%H P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 129

%H Daniel L. Geisler, <a href="http://www.iteratedfunctions.com/Combinatorics/index.html">Combinatorics of Iterated Functions</a>

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=69">Encyclopedia of Combinatorial Structures 69</a>

%H D. Jackson, A. Kempf, A. Morales, <a href="http://arxiv.org/abs/1612.00462">A robust generalization of the Legendre transform for QFT</a>, arXiv:1612.0046 [hep-th], 2017.

%H V. P. Johnson, <a href="http://www.math.sc.edu/~czabarka/JohnsonThesis.pdf">Enumeration Results on Leaf Labeled Trees</a>, Ph. D. Dissertation, Univ. Southern Calif., 2012.

%H B. R. Jones, <a href="http://summit.sfu.ca/item/14554">On tree hook length formulas, Feynman rules and B-series</a>, Master's thesis, Simon Fraser University, 2014.

%H Vladimir V. Kruchinin, <a href="http://arxiv.org/abs/1211.3244">The method for obtaining expressions for coefficients of reverse generating functions</a>, arXiv:1211.3244 [math.CO], 2012.

%H Z. A. Lomnicki, <a href="http://www.jstor.org/stable/1425808">Two-terminal series-parallel networks</a>, Adv. Appl. Prob., 4 (1972), 109-150.

%H Arnau Mir, Francesc Rossello, Lucia Rotger, <a href="https://arxiv.org/abs/1805.01329">Sound Colless-like balance indices for multifurcating trees</a>, arXiv:1805.01329 [q-bio.PE], 2018.

%H J. W. Moon, <a href="https://doi.org/10.1016/S0304-0208(08)73057-3">Some enumerative results on series-parallel networks</a>, Annals Discrete Math., 33 (1987), 199-226.

%H T. S. Motzkin, <a href="/A000262/a000262.pdf">Sorting numbers for cylinders and other classification numbers</a>, in Combinatorics, Proc. Symp. Pure Math. 19, AMS, 1971, pp. 167-176. [Annotated, scanned copy]

%H F. Murtagh, <a href="http://dx.doi.org/10.1016/0166-218X(84)90066-0">Counting dendrograms: a survey</a>, Discrete Appl. Math., 7 (1984), 191-199.

%H P. Regner, <a href="http://suuf.cc/phyl-trees/">Phylogenetic Trees: Selected Combinatorial Problems</a>, Master's Thesis, 2012, Institute of Discrete Mathematics and Geometry, TU Vienna, pp. 50-59

%H J. Riordan, <a href="/A000311/a000311.pdf">Letter to N. J. A. Sloane, Jul. 1970</a>

%H J. Riordan, <a href="https://doi.org/10.1007/BF02392410">The blossoming of Schröder's fourth problem</a>, Acta Math., 137 (1976), 1-16.

%H E. Schröder, <a href="/A000108/a000108_9.pdf">Vier combinatorische Probleme</a>, Z. f. Math. Phys., 15 (1870), 361-376. [Annotated scanned copy]

%H J. Taylor, <a href="https://digital.lib.washington.edu/researchworks/handle/1773/36757">Formal group laws and hypergraph colorings</a>, doctoral thesis, Univ. of Wash., 2016, p. 95. [_Tom Copeland_, Dec 20 2018]

%H N. J. A. Sloane, <a href="/A000311/a000311.txt">Table of n, a(n) for n = 0..500</a>

%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>

%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>

%H <a href="/index/Cor#core">Index entries for "core" sequences</a>

%H <a href="/index/Mo#Moon87">Index entries for sequences mentioned in Moon (1987)</a>

%H <a href="/index/Par#parens">Index entries for sequences related to parenthesizing</a>

%F E.g.f. A(x) satisfies exp A(x) = 2*A(x) - x + 1.

%F 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 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

%F 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

%F 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 (The autonomous differential eqn. here is also on p. 59 of Jones. - _Tom Copeland_, Dec 16 2019)

%F 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

%F 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

%F 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

%F 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

%F 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

%F a(n) ~ n^(n-1) / (sqrt(2) * exp(n) * (2*log(2)-1)^(n-1/2)). - _Vaclav Kotesovec_, Jan 05 2014

%F E.g.f. A(x) satisfies d/dx A(x) = 1 / (1 + x - 2 * A(x)). - _Michael Somos_, Oct 25 2014

%F O.g.f.: Sum_{n>=0} x / Product_{k=0..n} (2 - k*x). - _Paul D. Hanna_, Oct 27 2014

%F E.g.f.: (x - 1 - 2 LambertW(-exp((x-1)/2) / 2)) / 2. - _Vladimir Reshetnikov_, Oct 16 2015 (This e.g.f. is given in A135494, alluded to in my 2008 formula, and in A134991 along with its compositional inverse. - _Tom Copeland_, Jan 24 2018)

%F a(0) = 0, a(1) = 1; a(n) = n! * [x^n] exp(Sum_{k=1..n-1} a(k)*x^k/k!). - _Ilya Gutkovskiy_, Oct 17 2017

%e E.g.f.: A(x) = x + x^2/2! + 4*x^3/3! + 26*x^4/4! + 236*x^5/5! + 2752*x^6/6! +...

%e where exp(A(x)) = 1-x + 2*A(x), and thus

%e Series_Reversion(A(x)) = x - x^2/2! - x^3/3! - x^4/4! - x^5/5! - x^6/6! +...

%e O.g.f.: G(x) = x + x^2 + 4*x^3 + 26*x^4 + 236*x^5 + 2752*x^6 + 39208*x^7 + ...

%e where

%e G(x) = x/2 + x/(2*(2-x)) + x/(2*(2-x)*(2-2*x)) + x/(2*(2-x)*(2-2*x)*(2-3*x)) + x/(2*(2-x)*(2-2*x)*(2-3*x)*(2-4*x)) + x/(2*(2-x)*(2-2*x)*(2-3*x)*(2-4*x)*(2-5*x)) +...

%e From _Gus Wiseman_, Dec 28 2019: (Start)

%e A rooted tree is series-reduced if it has no unary branchings, so every non-leaf node covers at least two other nodes. The a(4) = 26 series-reduced rooted trees with 4 labeled leaves are the following. Each bracket (...) corresponds to a non-leaf node.

%e (1234) ((12)34) ((123)4)

%e (1(23)4) (1(234))

%e (12(34)) ((124)3)

%e (1(24)3) ((134)2)

%e ((13)24) (((12)3)4)

%e ((14)23) ((1(23))4)

%e ((12)(34))

%e (1((23)4))

%e (1(2(34)))

%e (((12)4)3)

%e ((1(24))3)

%e (1((24)3))

%e (((13)2)4)

%e ((13)(24))

%e (((13)4)2)

%e ((1(34))2)

%e (((14)2)3)

%e ((14)(23))

%e (((14)3)2)

%e (End)

%p 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 Order := 50; t1 := solve(series((exp(A)-2*A-1),A)=-x,A); A000311 := n-> n!*coeff(t1,x,n);

%p # second Maple program:

%p b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,

%p add(combinat[multinomial](n, n-i*j, i$j)/j!*

%p a(i)^j*b(n-i*j, i-1), j=0..n/i)))

%p end:

%p a:= n-> `if`(n<2, n, b(n, n-1)):

%p seq(a(n), n=0..40); # _Alois P. Heinz_, Jan 28 2016

%t nn = 19; CoefficientList[ InverseSeries[ Series[1+2a-E^a, {a, 0, nn}], x], x]*Range[0, nn]! (* _Jean-François Alcover_, Jul 21 2011 *)

%t a[ n_] := If[ n < 1, 0, n! SeriesCoefficient[ InverseSeries[ Series[ 1 + 2 x - Exp[x], {x, 0, n}]], n]]; (* _Michael Somos_, Jun 04 2012 *)

%t 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) *)

%t multinomial[n_, k_List] := n!/Times @@ (k!); b[n_, i_] := b[n, i] = If[n == 0, 1, If[i<1, 0, Sum[multinomial[n, Join[{n-i*j}, Array[i&,j]]]/j!*a[i]^j *b[n-i*j, i-1], {j, 0, n/i}]]]; a[n_] := If[n<2, n, b[n, n-1]]; Table[ a[n], {n, 0, 40}] (* _Jean-François Alcover_, Feb 07 2016, after _Alois P. Heinz_ *)

%t sps[{}]:={{}};sps[set:{i_,___}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,___}];

%t mtot[m_]:=Prepend[Join@@Table[Tuples[mtot/@p],{p,Select[sps[m],1<Length[#]<Length[m]&]}],m];

%t Table[Length[mtot[Range[n]]],{n,0,6}] (* _Gus Wiseman_, Dec 28 2019 *)

%o (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 */

%o (PARI) {a(n) = my(A); if( n<0, 0, A = O(x); for( i=1, n, A = intformal( 1 / (1 + x - 2*A))); n! * polcoeff(A, n))}; /* _Michael Somos_, Oct 25 2014 */

%o (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 */

%o (PARI) {a(n) = n! * polcoeff(serreverse(1+2*x - exp(x +x^2*O(x^n))), n)}

%o for(n=0, 30, print1(a(n), ", ")) \\ _Paul D. Hanna_, Oct 27 2014

%o (PARI) \p100 \\ set precision

%o {A=Vec(sum(n=0, 600, 1.*x/prod(k=0, n, 2 - k*x + O(x^31))))}

%o for(n=0, 25, print1(if(n<1,0,round(A[n])),", ")) \\ _Paul D. Hanna_, Oct 27 2014

%Y Row sums of A064060.

%Y The unlabeled version is A000669.

%Y Unlabeled phylogenetic trees are A141268.

%Y The node-counting version is A060356, with unlabeled version A001678.

%Y Phylogenetic trees with n labels are A005804.

%Y Chains of set partitions are A005121, with maximal version A002846.

%Y Inequivalent leaf-colorings of series-reduced rooted trees are A318231.

%Y Cf. A001003, A007827, A005805, A006351, A000084.

%Y For n >= 2, A000311(n) = A006351(n)/2 = A005640(n)/2^(n+1).

%Y Cf. A000110, A000669 = unlabeled hierarchies, A119649.

%Y Cf. A000670, A135494.

%Y Cf. A134685, A134991.

%Y Cf. A048816, A196545, A213427, A316651, A316652, A330626, A330627.

%K nonn,core,easy,nice

%O 0,4

%A _N. J. A. Sloane_

%E Name edited by _Gus Wiseman_, Dec 28 2019

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 18 15:30 EST 2020. Contains 332019 sequences. (Running on oeis4.)