A206429 -id:A206429 - cp's OEIS frontend

A319376 Triangle read by rows: T(n,k) is the number of lone-child-avoiding rooted trees with n leaves of exactly k colors.

1, 1, 1, 2, 6, 4, 5, 30, 51, 26, 12, 146, 474, 576, 236, 33, 719, 3950, 8572, 8060, 2752, 90, 3590, 31464, 108416, 175380, 134136, 39208, 261, 18283, 245916, 1262732, 3124650, 4014348, 2584568, 660032, 766, 94648, 1908858, 14047288, 49885320, 95715728, 101799712, 56555904, 12818912

Offset: 1

Andrew Howroyd, Sep 17 2018

Lone-child-avoiding rooted trees are also called planted series-reduced trees in some other sequences.

			Triangle begins:
    1;
    1,     1;
    2,     6,      4;
    5,    30,     51,      26;
   12,   146,    474,     576,     236;
   33,   719,   3950,    8572,    8060,   2752;
   90,  3590,  31464,  108416,  175380,  134136,   39208;
  261, 18283, 245916, 1262732, 3124650, 4014348, 2584568, 660032;
  ...
From _Gus Wiseman_, Dec 31 2020: (Start)
The 12 trees counted by row n = 3:
  (111)    (112)    (123)
  (1(11))  (122)    (1(23))
           (1(12))  (2(13))
           (1(22))  (3(12))
           (2(11))
           (2(12))
(End)

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (first 50 rows)

Columns k=1..2 are A000669, A319377.
Main diagonal is A000311.
Row sums are A316651.
Cf. A141610, A242249, A255517, A256064, A256068, A319254, A319541, A326396.
The unlabeled version, counting inequivalent leaf-colorings of lone-child-avoiding rooted trees, is A330465.
Lone-child-avoiding rooted trees are counted by A001678 (shifted left once).
Labeled lone-child-avoiding rooted trees are counted by A060356.
Matula-Goebel numbers of lone-child-avoiding rooted trees are A291636.
Cf. A000014, A000081, A000169, A005804, A206429, A330951.

b:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(binomial(A(i, k)+j-1, j)*b(n-i*j, i-1, k), j=0..n/i)))
    end:
A:= (n, k)-> `if`(n<2, n*k, b(n, n-1, k)):
T:= (n, k)-> add(A(n, k-j)*(-1)^j*binomial(k, j), j=0..k-1):
seq(seq(T(n, k), k=1..n), n=1..10);  # Alois P. Heinz, Sep 18 2018

b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i < 1, 0, Sum[Binomial[A[i, k] + j - 1, j] b[n - i j, i - 1, k], {j, 0, n/i}]]];
A[n_, k_] := If[n < 2, n k, b[n, n - 1, k]];
T[n_, k_] := Sum[(-1)^(k - i)*Binomial[k, i]*A[n, i], {i, 1, k}];
Table[T[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* Jean-François Alcover, Sep 24 2019, after Alois P. Heinz *)
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
mtot[m_]:=Prepend[Join@@Table[Tuples[mtot/@p],{p,Select[mps[m],1Gus Wiseman, Dec 31 2020 *)

\\ here R(n,k) is k-th column of A319254.
EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
R(n, k)={my(v=[k]); for(n=2, n, v=concat(v, EulerT(concat(v, [0]))[n])); v}
M(n)={my(v=vector(n, k, R(n,k)~)); Mat(vector(n, k, sum(i=1, k, (-1)^(k-i)*binomial(k,i)*v[i])))}
{my(T=M(10)); for(n=1, #T~, print(T[n, ][1..n]))}

T(n,k) = Sum_{i=1..k} (-1)^(k-i)*binomial(k,i)*A319254(n,i).

Sum_{k=1..n} k * T(n,k) = A326396(n). - Alois P. Heinz, Sep 11 2019

A331578 Number of labeled series-reduced rooted trees with n vertices and more than two branches of the root.

Original entry on oeis.org

0, 0, 0, 4, 5, 186, 847, 17928, 166833, 3196630, 45667391, 925287276, 17407857337, 393376875906, 8989368580935, 229332484742416, 6094576250570849, 174924522900914094, 5271210321949744111, 168792243040279327860, 5674164658298121248361, 200870558472768096534490

Offset: 1

Gus Wiseman, Jan 21 2020

nonn

A rooted tree is series-reduced if no vertex (including the root) has degree 2.

Also labeled lone-child-avoiding rooted trees with n vertices and more than two branches, where a rooted tree is lone-child-avoiding if no vertex has exactly one child.

			Non-isomorphic representatives of the a(7) = 847 trees (in the format root[branches]) are:
  1[2,3,4[5,6,7]]
  1[2,3,4,5[6,7]]
  1[2,3,4,5,6,7]

Andrew Howroyd, Table of n, a(n) for n = 1..200

The non-series-reduced version is A331577.
The unlabeled version is A331488.
Lone-child-avoiding rooted trees are counted by A001678.
Topologically series-reduced rooted trees are counted by A001679.
Labeled topologically series-reduced rooted trees are counted by A060313.
Labeled lone-child-avoiding rooted trees are counted by A060356.
Matula-Goebel numbers of lone-child-avoiding rooted trees are A291636.
Matula-Goebel numbers of series-reduced rooted trees are A331489.
Cf. A000014, A000169, A000669, A005512, A108919, A206429, A331233, A331490.

lrt[set_]:=If[Length[set]==0,{},Join@@Table[Apply[root,#]&/@Join@@Table[Tuples[lrt/@stn],{stn,sps[DeleteCases[set,root]]}],{root,set}]];
Table[Length[Select[lrt[Range[n]],Length[#]>2&&FreeQ[#,[]]&]],{n,6}]

a(n) = {if(n<=1, 0, sum(k=1, n, (-1)^(n-k)*k^(k-2)*n*(n-2)!*binomial(n-1,k-1)*(2*k*n - n - k^2)/k!))} \\ Andrew Howroyd, Dec 09 2020

seq(n)={my(w=lambertw(-x/(1+x) + O(x*x^n))); Vec(serlaplace(-x - w - (x/2)*w^2), -n)} \\ Andrew Howroyd, Dec 09 2020

From Andrew Howroyd, Dec 09 2020: (Start)
a(n) = A060313(n) - n*A060356(n-1) for n > 1.
a(n) = Sum_{k=1..n} (-1)^(n-k)*k^(k-2)*n*(n-2)!*binomial(n-1,k-1)*(2*k*n - n - k^2)/k! for n > 1.
E.g.f.: -x - LambertW(-x/(1+x)) - (x/2)*LambertW(-x/(1+x))^2.
(End)

Terms a(9) and beyond from Andrew Howroyd, Dec 09 2020

A331233 Number of unlabeled rooted trees with n vertices and more than two branches of the root.

Original entry on oeis.org

0, 0, 0, 1, 2, 5, 12, 30, 75, 194, 501, 1317, 3485, 9302, 24976, 67500, 183290, 500094, 1369939, 3766831, 10391722, 28756022, 79794407, 221987348, 619019808, 1729924110, 4844242273, 13590663071, 38195831829, 107523305566, 303148601795, 855922155734, 2419923253795

Offset: 1

Gus Wiseman, Jan 21 2020

nonn

			The a(4) = 1 through a(7) = 12 rooted trees:
  (ooo)  (oooo)   (ooooo)    (oooooo)
         (oo(o))  (oo(oo))   (oo(ooo))
                  (ooo(o))   (ooo(oo))
                  (o(o)(o))  (oooo(o))
                  (oo((o)))  (o(o)(oo))
                             (oo((oo)))
                             (oo(o)(o))
                             (oo(o(o)))
                             (ooo((o)))
                             ((o)(o)(o))
                             (o(o)((o)))
                             (oo(((o))))

Alois P. Heinz, Table of n, a(n) for n = 1..1000 (first 500 terms from Andrew Howroyd)

The Matula-Goebel numbers of these trees are given by A033942.
The series-reduced case is A331488.
The lone-child-avoiding case is (also) A331488.
The labeled version is A331577.
Unlabeled rooted trees are counted by A000081.
Cf. A001678, A001679, A004111, A033185, A060313, A206429, A331490, A331578.

g:= proc(n, i, t) option remember; `if`(n=0, `if`(t=0, 1, 0),
      `if`(i<1, 0, add(binomial(g(i-1$2, 0)+j-1, j)*
         g(n-i*j, i-1, max(0, t-j)), j=0..n/i)))
    end:
a:= n-> g(n-1$2, 3):
seq(a(n), n=1..40);  # Alois P. Heinz, Jan 22 2020

urt[n_]:=Join@@Table[Union[Sort/@Tuples[urt/@ptn]],{ptn,IntegerPartitions[n-1]}];
Table[Length[Select[urt[n],Length[#]>2&]],{n,10}]
(* Second program: *)
g[n_, i_, t_] := g[n, i, t] = If[n == 0, If[t == 0, 1, 0],
     If[i < 1, 0, Sum[Binomial[g[i - 1, i - 1, 0] + j - 1, j]*
     g[n - i*j, i - 1, Max[0, t - j]], {j, 0, n/i}]]];
a[n_] := g[n-1, n-1, 3];
Array[a, 40] (* Jean-François Alcover, May 20 2021, after Alois P. Heinz *)

\\ TreeGf gives gf of A000081.
TreeGf(N)={my(A=vector(N, j, 1)); for (n=1, N-1, A[n+1] = 1/n * sum(k=1, n, sumdiv(k, d, d*A[d]) * A[n-k+1] ) ); x*Ser(A)}
seq(n)={my(g=TreeGf(n)); Vec(g - x*(1 + g + (g^2 + subst(g, x, x^2))/2), -n)} \\ Andrew Howroyd, Jan 22 2020

For n > 1, a(n) = Sum_{k > 2} A033185(n - 1, k).

G.f.: f(x) - x*(1 + f(x) + (f(x)^2 + f(x^2))/2) where f(x) is the g.f. of A000081. - Andrew Howroyd, Jan 22 2020

A331577 Number of labeled rooted trees with n vertices and more than two branches of the root.

Original entry on oeis.org

0, 0, 0, 4, 65, 1026, 17857, 349224, 7657281, 186895270, 5037424601, 148805552556, 4784793219505, 166458635341194, 6231891513395745, 249886992888096976, 10686839817678846209, 485632267141865950926, 23370062118676064101801, 1187393725239246382405140

Offset: 1

Gus Wiseman, Jan 21 2020

nonn

			Non-isomorphic representatives of the a(6) = 1026 trees (in the format root[branches]) are:
  1[2,3,4[5[6]]]
  1[2,3[4],5[6]]
  1[2,3,4[5,6]]
  1[2,3,4,5[6]]
  1[2,3,4,5,6]

Andrew Howroyd, Table of n, a(n) for n = 1..200

The series-reduced version is A331578.
The unlabeled version is A331233.
Labeled rooted trees are counted by A000169.
Cf. A000081, A033185, A060313, A060356, A206429, A331488, A331490.

lrt[set_]:=If[Length[set]==0,{},Join@@Table[Apply[root,#]&/@Join@@Table[Tuples[lrt/@stn],{stn,sps[DeleteCases[set,root]]}],{root,set}]];
Table[Length[Select[lrt[Range[n]],Length[#]>2&]],{n,6}]

seq(n)={my(f=serreverse(x*exp(O(x^n) -x ))); Vec(serlaplace(f - x*(1 + f + f^2/2)), -n)} \\ Andrew Howroyd, Jan 23 2020

For n > 1, a(n) = Sum_{k > 2} A206429(n, k).

E.g.f.: f(x) - x*(1 + f(x) + f(x)^2/2), where f(x) is the e.g.f. of A000169. - Andrew Howroyd, Jan 23 2020

A300402 Smallest integer i such that TREE(i) >= n.

Original entry on oeis.org

1, 1, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3

Offset: 0

Felix Fröhlich, Mar 05 2018

nonn

The sequence grows very slowly.
A rooted tree is a tree containing one special node labeled the "root".
TREE(n) gives the largest integer k such that a sequence T(1), T(2), ..., T(k) of vertex-colored (using up to n colors) rooted trees, each one T(i) having at most i vertices, exists such that T(i) <= T(j) does not hold for any i < j <= k. - Edited by Gus Wiseman, Jul 06 2020

			TREE(1) = 1, so a(n) = 1 for n <= 1.
TREE(2) = 3, so a(n) = 2 for 2 <= n <= 3.
TREE(3) > A(A(...A(1)...)), where A(x) = 2[x+1]x is a variant of Ackermann's function, a[n]b denotes a hyperoperation and the number of nested A() functions is 187196, so a(n) = 3 for at least 4 <= n <= A^A(187196)(1).

Priyabrata Biswas, Towards Data Science: How Big Is The Number — Tree(3)
Eric Weisstein's World of Mathematics, Rooted Tree
Wikipedia, Hyperoperation - Notations
Wikipedia, Kruskal's tree theorem

Cf. A090529, A300403, A300404.
Labeled rooted trees are counted by A000169 and A206429.
Cf. A000081, A000311, A060313, A060356, A317713.

A206855 The sum of the degree of each root node over all rooted labeled trees on n nodes.

Original entry on oeis.org

0, 0, 2, 12, 96, 1000, 12960, 201684, 3670016, 76527504, 1800000000, 47158953820, 1362182012928, 43011849456888, 1474041721757696, 54493461914062500, 2161727821137838080, 91597537648314105376, 4128944057284204560384, 197293926880252878693804, 9961472000000000000000000

Offset: 0

Geoffrey Critzer, Feb 13 2012

The mean root degree approaches 2 as n -> infinity.

Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge Univ. Press, 2009, page 179.

nn=15;t=Sum[n^(n-1)x^n/n!,{n,1,nn}];D[ Range[0,nn]!CoefficientList[Series[x Exp[y t],{x,0,nn}],x],y]/.y->1

a(n) = Sum_{k=0..n} A206429(n,k)*k.
E.g.f.: T(x)^2 where T(x) is the e.g.f. for A000169.
a(n) = 2*(n^(n-1) - n^(n-2)).
a(n) = 2*A053506(n). - R. J. Mathar, Nov 07 2014

a(10) corrected by Georg Fischer, Mar 23 2023

cp's OEIS Frontend

A319376 Triangle read by rows: T(n,k) is the number of lone-child-avoiding rooted trees with n leaves of exactly k colors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A331578 Number of labeled series-reduced rooted trees with n vertices and more than two branches of the root.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A331233 Number of unlabeled rooted trees with n vertices and more than two branches of the root.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A331577 Number of labeled rooted trees with n vertices and more than two branches of the root.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A300402 Smallest integer i such that TREE(i) >= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A206855 The sum of the degree of each root node over all rooted labeled trees on n nodes.

Views

Author

Keywords

Comments

Links

Programs

Mathematica

Formula

Extensions