A036656 -id:A036656 - cp's OEIS frontend

A111299 Numbers whose Matula tree is a binary tree (i.e., root has degree 2 and all nodes except root and leaves have degree 3).

4, 14, 49, 86, 301, 454, 886, 1589, 1849, 3101, 3986, 6418, 9761, 13766, 13951, 19049, 22463, 26798, 31754, 48181, 51529, 57026, 75266, 85699, 93793, 100561, 111139, 128074, 137987, 196249, 199591, 203878, 263431, 295969, 298154, 302426, 426058, 448259, 452411

Offset: 1

Keith Briggs, Nov 02 2005

nonn

This sequence should probably start with 1. Then a number k is in the sequence iff k = 1 or k = prime(x) * prime(y) with x and y already in the sequence. - Gus Wiseman, May 04 2021

			From _Gus Wiseman_, May 04 2021: (Start)
The sequence of trees (starting with 1) begins:
     1: o
     4: (oo)
    14: (o(oo))
    49: ((oo)(oo))
    86: (o(o(oo)))
   301: ((oo)(o(oo)))
   454: (o((oo)(oo)))
   886: (o(o(o(oo))))
  1589: ((oo)((oo)(oo)))
  1849: ((o(oo))(o(oo)))
  3101: ((oo)(o(o(oo))))
  3986: (o((oo)(o(oo))))
  6418: (o(o((oo)(oo))))
  9761: ((o(oo))((oo)(oo)))
(End)

Kevin Ryde, Table of n, a(n) for n = 1..5000 (terms 1..186 from Charles R Greathouse IV)
Keith Briggs, Matula numbers and rooted trees
F. Goebel, On a 1-1-correspondence between rooted trees and natural numbers, J. Combin. Theory, B 29 (1980), 141-143.
D. Matula, A natural rooted tree enumeration by prime factorization, SIAM Rev. 10 (1968) 273.
Kevin Ryde, PARI/GP Code
Index entries for sequences related to Matula-Goebel numbers

Cf. A245824 (by number of leaves).
Cf. A005517, A005518, A061773, A245824.
These trees are counted by 2*A001190 - 1.
The semi-binary version is A292050 (counted by A001190).
The semi-identity case is A339193 (counted by A063895).
A000081 counts unlabeled rooted trees with n nodes.
A007097 ranks rooted chains.
A276625 ranks identity trees, counted by A004111.
A306202 ranks semi-identity trees, counted by A306200.
A306203 ranks balanced semi-identity trees, counted by A306201.
A331965 ranks lone-child avoiding semi-identity trees, counted by A331966.
Cf. A036656, A061775, A196050, A291636, A320230, A331935, A331965.

nn=20000;
primeMS[n_]:=If[n===1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
binQ[n_]:=Or[n===1,With[{m=primeMS[n]},And[Length[m]===2,And@@binQ/@m]]];
Select[Range[2,nn],binQ] (* Gus Wiseman, Aug 28 2017 *)

i(n)=n==2 || is(primepi(n))
is(n)=if(n<14,return(n==4)); my(f=factor(n),t=#f[,1]); if(t>1, t==2 && f[1,2]==1 && f[2,2]==1 && i(f[1,1]) && i(f[2,1]), f[1,2]==2 && i(f[1,1])) \\ Charles R Greathouse IV, Mar 29 2013

list(lim)=my(v=List(), t); forprime(p=2, sqrt(lim), t=p; forprime(q=p, lim\t, if(i(p)&&i(q), listput(v, t*q)))); vecsort(Vec(v)) \\ Charles R Greathouse IV, Mar 29 2013

PARI
```
\\ Also see links.
```

The Matula tree of k is defined as follows:
matula(k):
    create a node labeled k
    for each prime factor m of k:
       add the subtree matula(prime(m)), by an edge labeled m
    return the node

Definition corrected by Charles R Greathouse IV, Mar 29 2013

a(27)-a(39) from Charles R Greathouse IV, Mar 29 2013

A292050 Matula-Goebel numbers of semi-binary rooted trees.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 15, 17, 21, 22, 23, 25, 26, 29, 31, 33, 34, 35, 39, 41, 43, 46, 47, 49, 51, 55, 58, 59, 62, 65, 69, 73, 77, 79, 82, 83, 85, 86, 87, 91, 93, 94, 97, 101, 109, 115, 118, 119, 121, 123, 127, 129, 137, 139, 141, 143, 145

Offset: 1

Gus Wiseman, Sep 08 2017

nonn

An unlabeled rooted tree is semi-binary if all out-degrees are <= 2. The number of semi-binary trees with n nodes is equal to the number of binary trees with n+1 leaves; see A001190.

Cf. A000081, A001190, A007097, A036656, A061773, A111299, A214577, A291636.

nn=200;
primeMS[n_]:=If[n===1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
semibinQ[n_]:=Or[n===1,With[{m=primeMS[n]},And[Length[m]<=2,And@@semibinQ/@m]]];
Select[Range[nn],semibinQ]

A000671 Number of boron trees with n nodes, i.e. n-node rooted trees with degree <= 3 at root and out-degree <= 2 elsewhere.

Original entry on oeis.org

0, 1, 1, 2, 4, 7, 14, 29, 60, 127, 275, 598, 1320, 2936, 6584, 14858, 33744, 76999, 176557, 406456, 939241, 2177573, 5064150, 11809632, 27610937, 64705623, 151966597, 357623905, 843176524, 1991439229, 4711115672, 11162025770, 26484061667, 62923251955

Offset: 0

N. J. A. Sloane

The subsequence of primes begins: 2, 7, 29, 127, 176557, 2177573, 151966597.

A. Cayley, On the analytical forms called trees, with application to the theory of chemical combinations, Reports British Assoc. Advance. Sci. 45 (1875), 257-305 = Math. Papers, Vol. 9, 427-460 (see p. 450).
R. C. Read, personal communication.
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).

T. D. Noe, Table of n, a(n) for n = 0..200
S. J. Cyvin, J. Brunvoll, and B. N. Cyvin, Enumeration of constitutional isomers of polyenes, J. Molec. Struct. (Theochem) 357, no. 3 (1995) 255-261.
R. C. Read, Letter to N. J. A. Sloane, Oct. 29, 1976
Index entries for sequences related to trees
Index entries for sequences related to rooted trees

Cf. A001190, A036657, A036658.

N := 40: t1 := G001190/x: G000671 := series(x*(1/3!)*(t1^3+3*subs(x=x^2,t1)*t1+2*subs(x=x^3,t1)), x, N); A000671 := n->coeff(G000671,x,n);
CI2 := proc(f) (1/2)*(f^2+subs(x=x^2,f)); end; CI3 := proc(f) (1/6)*(f^3+3*subs(x=x^2,f)*f+2*subs(x=x^3,f)); end;
N := 40: B0 := series(1 + x,x,N): G000671 := series(x*(CI3(B0) + CI3(G036656) + CI3(G036657) + CI2(B0)*(G036656 + G036657) + CI2(G036656)*(G036657 + B0) + CI2(G036657)*(B0 + G036656) + B0*G036656*G036657),x,N); A036658 := n->coeff(G036658,x,n);

terms = 32; (* B = g.f. for A001190 *) B[] = 0; Do[B[x] = x + (1/2)*(B[x]^2 + B[x^2]) + O[x]^terms // Normal, terms];
f[x_] = B[x]/x;
A[x_] = x*(1/3!)*(f[x]^3 + 3*f[x^2]*f[x] + 2*f[x^3]) + O[x]^terms;
CoefficientList[A[x], x] (* Jean-François Alcover, May 29 2012, from first g.f., updated Jan 10 2018 *)

G.f.: A(x) = x*(1/3!)*(f^3+3*subs(x=x^2, f)*f+2*subs(x=x^3, f)), where f = G001190(x)/x, G001190 = g.f. for A001190.
a(n) = A001190(n) + A036657(n) + A036658(n).
Another g.f.: let B0(x) = 1+x, G036656(x) = g.f. for A036656, G036657(x) = g.f. for A036657.
Then g.f.: x*(cycle_index(S3, B0)+cycle_index(S3, G036656)+cycle_index(S3, G036657)+cycle_index(S2, B0)*(G036656+G036657)+cycle_index(S2, G036656)*(G036657+B0)+cycle_index(S2, G036657)*(B0+G036656)+B0*G036656*G036657), where cycle_index(Sk, f) means apply the cycle index for the symmetric group S_k to f(x).
E.g., cycle_index(S2, f) = (1/2!)*(f^2+subs(x=x^2, f), cycle_index(S3, f) = (1/3!)*(f^3+3*subs(x=x^2, f)*f+2*subs(x=x^3, f)).

A036658 Number of n-node rooted unlabeled trees with exactly 3 edges at root and otherwise out-degree <= 2.

Original entry on oeis.org

0, 0, 0, 0, 1, 1, 3, 6, 14, 29, 68, 147, 337, 757, 1734, 3953, 9113, 20988, 48645, 112909, 263084, 614201, 1438001, 3373253, 7930660, 18679005, 44075988, 104173194, 246604137, 584620470, 1387879434, 3299067379, 7851736348, 18708682855, 44627133541, 106563177864

Offset: 0

N. J. A. Sloane

Index entries for sequences related to rooted trees

Cf. A088326, A036656.

CI2 := proc(f) (1/2)*(f^2+subs(x=x^2,f)); end; CI3 := proc(f) (1/6)*(f^3+3*subs(x=x^2,f)*f+2*subs(x=x^3,f)); end;
N := 40: G036658 := series(x^3*CI3(G036656),x,N); A036658 := n->coeff(G036658,x,n);

terms = 35;
CI3[f_] := (1/3!)*(f^3 + 3*(f /. x -> x^2)*f + 2*(f /. x -> x^3));
G036656[] = 0; Do[G036656[x] = x + (1/2)*(G036656[x]^2 + G036656[x^2]) + O[x]^terms // Normal, terms];
G036658[x_] = x^3*CI3[G036656[x] - x] + O[x]^(terms+5);
Drop[CoefficientList[G036658[x], x], 5] (* Jean-François Alcover, Jan 24 2018, adapted from Maple *)

Let G036656(x) = g.f. for A036656. G.f.: x^3*cycle_index(S3, G036656), where cycle_index(Sk, f) means apply the cycle index for the symmetric group S_k to f(x).

E.g., cycle_index(S2, f) = (1/2!)*(f^2+subs(x=x^2, f), cycle_index(S3, f) = (1/3!)*(f^3+3*subs(x=x^2, f)*f+2*subs(x=x^3, f)).

Corrected by N. J. A. Sloane, May 03 2000

A244399 Number of unlabeled rooted trees with n nodes and maximal outdegree (branching factor) 3.

Original entry on oeis.org

1, 2, 6, 16, 43, 113, 300, 787, 2074, 5460, 14391, 37960, 100275, 265187, 702307, 1862463, 4945952, 13152441, 35023003, 93385548, 249330208, 666539949, 1784102735, 4781254117, 12828545419, 34459732110, 92668129050, 249469906115, 672296028786, 1813606782459

Offset: 4

Joerg Arndt and Alois P. Heinz, Jun 27 2014

nonn

Alois P. Heinz, Table of n, a(n) for n = 4..1000

Column k=3 of A244372.

Cf. A000598, A001190, A036656.

b:= proc(n, i, t, k) option remember; `if`(n=0, 1,
      `if`(i<1, 0, add(binomial(b((i-1)$2, k$2)+j-1, j)*
       b(n-i*j, i-1, t-j, k), j=0..min(t, n/i))))
    end:
a:= n-> b(n-1$2, 3$2) -`if`(k=0, 0, b(n-1$2, 2$2)):
seq(a(n), n=4..35);

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

a(n) = A000598(n) - A001190(n+1) = A000598(n) - A036656(n+1).

a(n) ~ c * d^n / n^(3/2), where d = 1/A261340 = 2.81546003317615... and c = 0.5178759064... . - Vaclav Kotesovec, Jun 27 2014

A244398 Number of unlabeled rooted trees with n nodes and maximal outdegree (branching factor) 2.

Original entry on oeis.org

1, 2, 5, 10, 22, 45, 97, 206, 450, 982, 2178, 4849, 10904, 24630, 56010, 127911, 293546, 676156, 1563371, 3626148, 8436378, 19680276, 46026617, 107890608, 253450710, 596572386, 1406818758, 3323236237, 7862958390, 18632325318, 44214569099, 105061603968

Offset: 3

Joerg Arndt and Alois P. Heinz, Jun 27 2014

nonn

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

Column k=2 of A244372.

Cf. A001190, A036656, A086317, A086318.

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

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

a(n) = A001190(n+1)-1 = A036656(n+1)-1.

a(n) ~ c * d^n / n^(3/2), where d = 2.4832535361726368... = A086317 and c = 0.7916031835775118... = A086318. - Vaclav Kotesovec, Jun 27 2014

cp's OEIS Frontend

A111299 Numbers whose Matula tree is a binary tree (i.e., root has degree 2 and all nodes except root and leaves have degree 3).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

Formula

Extensions

A292050 Matula-Goebel numbers of semi-binary rooted trees.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

A000671 Number of boron trees with n nodes, i.e. n-node rooted trees with degree <= 3 at root and out-degree <= 2 elsewhere.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A036658 Number of n-node rooted unlabeled trees with exactly 3 edges at root and otherwise out-degree <= 2.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A244399 Number of unlabeled rooted trees with n nodes and maximal outdegree (branching factor) 3.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A244398 Number of unlabeled rooted trees with n nodes and maximal outdegree (branching factor) 2.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula