|
|
A000311
|
|
Schroeder's fourth problem; also series-reduced rooted trees with n labeled leaves; also number of total partitions of n.
(Formerly M3613 N1465)
|
|
105
|
|
|
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) is the 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.
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
Row sums of A134991, which contains an e.g.f. for this sequence and its compositional inverse. - Tom Copeland, Jan 24 2018
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:
{1,2,3,4} {{1},{2},{3,4}} {{1},{2,3,4}}
{{1},{2,3},{4}} {{1,2},{3,4}}
{{1,2},{3},{4}} {{1,2,3},{4}}
{{1},{2,4},{3}} {{1,2,4},{3}}
{{1,3},{2},{4}} {{1,3},{2,4}}
{{1,4},{2},{3}} {{1,3,4},{2}}
{{1,4},{2,3}}
{{{1},{2,3}},{4}}
{{{1,2},{3}},{4}}
{{1},{{2},{3,4}}}
{{1},{{2,3},{4}}}
{{{1},{2,4}},{3}}
{{{1,2},{4}},{3}}
{{1},{{2,4},{3}}}
{{{1,3},{2}},{4}}
{{{1},{3,4}},{2}}
{{{1,3},{4}},{2}}
{{{1,4},{2}},{3}}
{{{1,4},{3}},{2}}
(End)
|
|
REFERENCES
|
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
T. S. Motzkin, Sorting numbers for cylinders and other classification numbers, in Combinatorics, Proc. Symp. Pure Math. 19, AMS, 1971, pp. 167-176.
J. Riordan, Combinatorial Identities, Wiley, 1968, p. 197.
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 "total partitions", Example 5.2.5, Equation (5.27), and also Fig. 5-3 on page 14. See also the Notes on page 66.
|
|
LINKS
|
P. J. Cameron, Some treelike objects, Quart. J. Math. Oxford, 38 (1987), 155-183. MR0891613 (89a:05009). See p. 155 and 159.
Steven R. Finch, Mathematical Constants II, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, 2018.
|
|
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 (The autonomous differential eqn. here is also on p. 59 of Jones. - Tom Copeland, Dec 16 2019)
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. Comtet'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
E.g.f. A(x) satisfies d/dx A(x) = 1 / (1 + x - 2 * A(x)). - Michael Somos, Oct 25 2014
O.g.f.: Sum_{n>=0} x / Product_{k=0..n} (2 - k*x). - Paul D. Hanna, Oct 27 2014
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, the entry alluded to in my 2008 formula, and in A134991 along with its compositional inverse. - Tom Copeland, Jan 24 2018)
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
|
|
EXAMPLE
|
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! + ...
where exp(A(x)) = 1 - x + 2*A(x), and thus
Series_Reversion(A(x)) = x - x^2/2! - x^3/3! - x^4/4! - x^5/5! - x^6/6! + ...
O.g.f.: G(x) = x + x^2 + 4*x^3 + 26*x^4 + 236*x^5 + 2752*x^6 + 39208*x^7 + ...
where
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)) + ...
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.
(1234) ((12)34) ((123)4)
(1(23)4) (1(234))
(12(34)) ((124)3)
(1(24)3) ((134)2)
((13)24) (((12)3)4)
((14)23) ((1(23))4)
((12)(34))
(1((23)4))
(1(2(34)))
(((12)4)3)
((1(24))3)
(1((24)3))
(((13)2)4)
((13)(24))
(((13)4)2)
((1(34))2)
(((14)2)3)
((14)(23))
(((14)3)2)
(End)
|
|
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);
# second Maple program:
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
add(combinat[multinomial](n, n-i*j, i$j)/j!*
a(i)^j*b(n-i*j, i-1), j=0..n/i)))
end:
a:= n-> `if`(n<2, n, b(n, n-1)):
# faster program:
b:= proc(n, i) option remember;
`if`(i=0 and n=0, 1, `if`(i<=0 or i>n, 0,
i*b(n-1, i) + (n+i-1)*b(n-1, i-1))) end:
a:= n -> `if`(n<2, n, add(b(n-1, i), i=0..n-1)):
|
|
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) *)
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 *)
sps[{}]:={{}}; sps[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]&/@sps[Complement[set, s]]]/@Cases[Subsets[set], {i, ___}];
mtot[m_]:=Prepend[Join@@Table[Tuples[mtot/@p], {p, Select[sps[m], 1<Length[#]<Length[m]&]}], m];
Table[Length[mtot[Range[n]]], {n, 0, 6}] (* Gus Wiseman, Dec 28 2019 *)
(* Lengthy but easy to follow *)
lead[_, n_ /; n < 3] := 0
lead[h_, n_] := Module[{p, i},
p = Position[h, {___}];
Sum[MapAt[{#, n} &, h, p[[i]]], {i, Length[p]}]
]
follow[h_, n_] := Module[{r, i},
r = Replace[Position[h, {___}], {a__} -> {a, -1}, 1];
Sum[Insert[h, n, r[[i]]], {i, Length[r]}]
]
marry[_, n_ /; n < 3] := 0
marry[h_, n_] := Module[{p, i},
p = Position[h, _Integer];
Sum[MapAt[{#, n} &, h, p[[i]]], {i, Length[p]}]
]
extend[a_ + b_, n_] := extend[a, n] + extend[b, n]
extend[a_, n_] := lead[a, n] + follow[a, n] + marry[a, n]
hierarchies[1] := hierarchies[1] = extend[hier[{}], 1]
hierarchies[n_] := hierarchies[n] = extend[hierarchies[n - 1], n] (* Daniel Geisler, Aug 22 2022 *)
|
|
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 */
(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 */
(PARI) {a(n) = n! * polcoeff(serreverse(1+2*x - exp(x +x^2*O(x^n))), n)}
(PARI) \p100 \\ set precision
{A=Vec(sum(n=0, 600, 1.*x/prod(k=0, n, 2 - k*x + O(x^31))))}
for(n=0, 25, print1(if(n<1, 0, round(A[n])), ", ")) \\ Paul D. Hanna, Oct 27 2014
(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 */
(Python)
from functools import lru_cache
from math import comb
@lru_cache(maxsize=None)
|
|
CROSSREFS
|
Unlabeled phylogenetic trees are A141268.
Phylogenetic trees with n labels are A005804.
Inequivalent leaf-colorings of series-reduced rooted trees are A318231.
|
|
KEYWORD
|
nonn,core,easy,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|