A001679 -id:A001679 - cp's OEIS frontend

A331489 Matula-Goebel numbers of topologically series-reduced rooted trees.

1, 2, 7, 8, 16, 19, 28, 32, 43, 53, 56, 64, 76, 98, 107, 112, 128, 131, 152, 163, 172, 196, 212, 224, 227, 256, 263, 266, 304, 311, 343, 344, 383, 392, 424, 428, 443, 448, 512, 521, 524, 532, 577, 602, 608, 613, 652, 686, 688, 719, 722, 742, 751, 784, 848, 856

Offset: 1

Gus Wiseman, Jan 20 2020

nonn

We say that a rooted tree is topologically series-reduced if no vertex (including the root) has degree 2.

The Matula-Goebel number of a rooted tree is the product of primes indexed by the Matula-Goebel numbers of its branches. This gives a bijective correspondence between positive integers and unlabeled rooted trees.

			The sequence of all topologically series-reduced rooted trees together with their Matula-Goebel numbers begins:
    1: o
    2: (o)
    7: ((oo))
    8: (ooo)
   16: (oooo)
   19: ((ooo))
   28: (oo(oo))
   32: (ooooo)
   43: ((o(oo)))
   53: ((oooo))
   56: (ooo(oo))
   64: (oooooo)
   76: (oo(ooo))
   98: (o(oo)(oo))
  107: ((oo(oo)))
  112: (oooo(oo))
  128: (ooooooo)
  131: ((ooooo))
  152: (ooo(ooo))
  163: ((o(ooo)))

Eric Weisstein's World of Mathematics, Series-reduced tree.
Gus Wiseman, Sequences counting series-reduced and lone-child-avoiding trees by number of vertices.

Unlabeled rooted trees are counted by A000081.
Topologically series-reduced trees are counted by A000014.
Topologically series-reduced rooted trees are counted by A001679.
Labeled topologically series-reduced trees are counted by A005512.
Labeled topologically series-reduced rooted trees are counted by A060313.
Matula-Goebel numbers of lone-child-avoiding rooted trees are A291636.
Cf. A000669, A001678, A007097, A007821, A060356, A061775, A109082, A109129, A196050, A254382, A276625, A330943, A331490.

nn=1000;
primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
srQ[n_]:=Or[n==1,With[{m=primeMS[n]},And[Length[m]>1,And@@srQ/@m]]];
Select[Range[nn],PrimeOmega[#]!=2&&And@@srQ/@primeMS[#]&]

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

A246403 Decimal expansion of a constant related to series-reduced trees.

Original entry on oeis.org

2, 1, 8, 9, 4, 6, 1, 9, 8, 5, 6, 6, 0, 8, 5, 0, 5, 6, 3, 8, 8, 7, 0, 2, 7, 5, 7, 7, 1, 1, 4, 5, 4, 4, 9, 6, 7, 3, 3, 1, 7, 0, 8, 7, 4, 4, 2, 3, 8, 4, 9, 0, 3, 0, 1, 0, 5, 0, 2, 7, 3, 4, 2, 5, 3, 5, 7, 1, 5, 6, 2, 5, 7, 0, 4, 2, 2, 1, 2, 2, 6, 3, 0, 0, 8, 5, 8, 6, 0, 7, 8, 4, 8, 1, 9, 3, 3, 3, 0, 8, 3, 2, 0, 3, 8

Offset: 1

Vaclav Kotesovec, Aug 25 2014

			2.189461985660850563887027577114544967331...

Steven R. Finch, Mathematical Constants, Cambridge, 2003, p. 302 and 561.

Cf. A000014, A001678, A001679, A059123, A244456, A198518.

Equals lim n -> infinity A000014(n)^(1/n).
Equals lim n -> infinity A001678(n)^(1/n).
Equals lim n -> infinity A001679(n)^(1/n).
Equals lim n -> infinity A059123(n)^(1/n).
Equals lim n -> infinity A244456(n)^(1/n).
Equals lim n -> infinity A198518(n)^(1/n).

More terms from Vaclav Kotesovec, Sep 03 2014 and Dec 26 2020

A244456 Number of unlabeled rooted trees with n nodes such that the minimal outdegree of inner nodes equals 2.

Original entry on oeis.org

1, 0, 1, 2, 4, 7, 15, 28, 56, 110, 220, 436, 878, 1762, 3560, 7205, 14650, 29838, 60991, 124938, 256628, 528238, 1089834, 2252860, 4666304, 9682422, 20125777, 41900433, 87369029, 182441944, 381499040, 798782945, 1674575394, 3514733683, 7385298837, 15534856067

Offset: 3

Joerg Arndt and Alois P. Heinz, Jun 29 2014

nonn

			a(5) = 1:
      o
     / \
    o   o
   / \
  o   o

Alois P. Heinz, Table of n, a(n) for n = 3..900

Column k=2 of A244454.

Cf. A244531, A246403.

b:= proc(n, i, t, k) option remember; `if`(n=0, `if`(t in [0, k],
      1, 0), `if`(i<1 or t>n, 0, add(binomial(b((i-1)$2, k$2)+j-1, j)*
      b(n-i*j, i-1, max(0,t-j), k), j=0..n/i)))
    end:
a:= n-> b(n-1$2, 2$2) -b(n-1$2, 3$2):
seq(a(n), n=3..40);

b[n_, i_, t_, k_] := b[n, i, t, k] = If[n == 0, If[t == 0 || t == k, 1, 0], If[i < 1, 0, Sum[Binomial[b[i - 1, i - 1, k, k] + j - 1, j]*b[n - i*j, i - 1, Max[0, t - j], k], {j, 0, n/i}]]]; a[n_] := b[n - 1, n - 1, 2, 2] - b[n - 1, n - 1, 3, 3] // FullSimplify; Table[a[n], {n, 3, 40}] (* Jean-François Alcover, Feb 06 2015, after Maple *)

a(n) ~ c * d^n / n^(3/2), where d = A246403 = 2.18946198566085056388702757711..., c = 0.4213018528699249210965028... (constants are same as for A001679). - Vaclav Kotesovec, Jul 02 2014

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

cp's OEIS Frontend

A331489 Matula-Goebel numbers of topologically series-reduced rooted trees.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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

A246403 Decimal expansion of a constant related to series-reduced trees.

Views

Author

Keywords

Examples

References

Crossrefs

Formula

Extensions

A244456 Number of unlabeled rooted trees with n nodes such that the minimal outdegree of inner nodes equals 2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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