A055277 -id:A055277 - cp's OEIS frontend

A317097 Number of rooted trees with n nodes where the number of distinct branches under each node is <= 2.

1, 1, 2, 4, 9, 20, 46, 106, 248, 583, 1393, 3343, 8111, 19801, 48719, 120489, 299787, 749258, 1881216, 4741340, 11993672, 30436507, 77471471, 197726053, 505917729, 1297471092, 3334630086, 8587369072, 22155278381, 57259037225, 148222036272, 384272253397

Offset: 1

Gus Wiseman, Aug 01 2018

nonn

There can be more than two branches as long as there are not three distinct branches.

			The a(5) = 9 trees:
  ((((o))))
  (((oo)))
  ((o(o)))
  ((ooo))
  (o((o)))
  (o(oo))
  ((o)(o))
  (oo(o))
  (oooo)

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

Cf. A000081, A000598, A001190, A003238, A055277, A111299, A292050, A298204, A301344, A317098.

semisameQ[u_]:=Length[Union[u]]<=2;
nms[n_]:=nms[n]=If[n==1,{{}},Join@@Table[Select[Union[Sort/@Tuples[nms/@ptn]],semisameQ],{ptn,IntegerPartitions[n-1]}]];
Table[Length[nms[n]],{n,10}]

seq(n)={my(v=vector(n)); v[1]=1; for(n=1, n-1, v[n+1]=sum(k=1, n-1, sumdiv(k, d, v[d])*sumdiv(n-k, d, v[d])/2) + sumdiv(n, d, v[n/d]*(1 - (d-1)/2)) ); v} \\ Andrew Howroyd, Aug 28 2018

Terms a(20) and beyond from Andrew Howroyd, Aug 28 2018

A317098 Number of series-reduced rooted trees with n unlabeled leaves where the number of distinct branches under each node is <= 2.

Original entry on oeis.org

1, 1, 2, 5, 12, 31, 80, 214, 576, 1595, 4448, 12625, 36146, 104662, 305251, 897417, 2654072, 7895394, 23601441, 70871693, 213660535, 646484951, 1962507610, 5975425743, 18243789556, 55841543003, 171320324878, 526738779846, 1622739134873, 5008518981670

Offset: 1

Gus Wiseman, Aug 01 2018

nonn

There can be more than two branches as long as there are not three distinct branches.

			The a(5) = 12 trees:
  (o(o(o(oo))))
  (o(o(ooo)))
  (o((oo)(oo)))
  (o(oo(oo)))
  (o(oooo))
  ((oo)(o(oo)))
  ((oo)(ooo))
  (oo(o(oo)))
  (oo(ooo))
  (o(oo)(oo))
  (ooo(oo))
  (ooooo)

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

Cf. A000081, A000598, A001190, A055277, A111299, A292050, A298204, A301344, A317097.

semisameQ[u_]:=Length[Union[u]]<=2;
nms[n_]:=nms[n]=If[n==1,{{1}},Join@@Table[Select[Union[Sort/@Tuples[nms/@ptn]],semisameQ],{ptn,Rest[IntegerPartitions[n]]}]];
Table[Length[nms[n]],{n,10}]

seq(n)={my(v=vector(n)); v[1]=1; for(n=2, n, v[n]=sum(k=1, n-1, sumdiv(k, d, v[d])*sumdiv(n-k, d, v[d])/2) + sumdiv(n, d, v[n/d]*(1 - (d-1)/2)) ); v} \\ Andrew Howroyd, Aug 19 2018

Terms a(21) and beyond from Andrew Howroyd, Aug 19 2018

A358554 Least Matula-Goebel number of a rooted tree with n internal (non-leaf) nodes.

Original entry on oeis.org

1, 2, 3, 5, 11, 25, 55, 121, 275, 605, 1331, 3025, 6655, 14641, 33275, 73205

Offset: 1

Gus Wiseman, Nov 27 2022

Positions of first appearances in A342507.

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

			The terms together with their corresponding rooted trees begin:
      1: o
      2: (o)
      3: ((o))
      5: (((o)))
     11: ((((o))))
     25: (((o))((o)))
     55: (((o))(((o))))
    121: ((((o)))(((o))))
    275: (((o))((o))(((o))))
    605: (((o))(((o)))(((o))))
   1331: ((((o)))(((o)))(((o))))
   3025: (((o))((o))(((o)))(((o))))
   6655: (((o))(((o)))(((o)))(((o))))
  14641: ((((o)))(((o)))(((o)))(((o))))
  33275: (((o))((o))(((o)))(((o)))(((o))))
  73205: (((o))(((o)))(((o)))(((o)))(((o))))

For height instead of internals we have A007097, firsts of A109082.
For leaves instead of internals we have A151821, firsts of A109129.
Positions of first appearances in A342507.
The ordered version gives firsts of A358553.
A000081 counts rooted trees, ordered A000108.
A034781 counts rooted trees by nodes and height.
A055277 counts rooted trees by nodes and leaves.
MG statistics: A061775, A109082, A109129, A196050, A342507, A358552.
Cf. A000040, A000720, A001222, A007097, A056239, A112798.
Cf. A001263, A206487, A358578, A358592.

MGTree[n_]:=If[n==1,{},MGTree/@Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
seq=Table[Count[MGTree[n],[_],{0,Infinity}],{n,1000}];
Table[Position[seq,n][[1,1]],{n,Union[seq]}]

A358727 Matula-Goebel numbers of rooted trees with greater number of leaves (width) than node-height.

Original entry on oeis.org

8, 16, 24, 28, 32, 36, 38, 42, 48, 49, 53, 54, 56, 57, 63, 64, 72, 76, 80, 81, 84, 96, 98, 104, 106, 108, 112, 114, 120, 126, 128, 131, 133, 136, 140, 144, 147, 148, 152, 156, 159, 160, 162, 168, 171, 172, 178, 180, 182, 184, 189, 190, 192, 196, 200, 204, 208

Offset: 1

Gus Wiseman, Dec 01 2022

nonn

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

Node-height is the number of nodes in the longest path from root to leaf.

			The terms together with their corresponding rooted trees begin:
   8: (ooo)
  16: (oooo)
  24: (ooo(o))
  28: (oo(oo))
  32: (ooooo)
  36: (oo(o)(o))
  38: (o(ooo))
  42: (o(o)(oo))
  48: (oooo(o))
  49: ((oo)(oo))
  53: ((oooo))
  54: (o(o)(o)(o))
  56: (ooo(oo))
  57: ((o)(ooo))
  63: ((o)(o)(oo))
  64: (oooooo)
  72: (ooo(o)(o))
  76: (oo(ooo))

Gus Wiseman, The first 64 rooted trees with greater width than height.

Positions of negative terms in A358726.
These trees are counted by A358728.
Differences: A358580, A358724, A358726, A358729.
A000081 counts rooted trees, ordered A000108.
A034781 counts rooted trees by nodes and height, ordered A080936.
A055277 counts rooted trees by nodes and leaves, ordered A001263.
MG statistics: A061775, A109082, A109129, A196050, A342507, A358552.
MG core: A000040, A000720, A001222, A007097, A056239, A112798.
Cf. A185650, A206487, A209638, A358576, A358577, A358578, A358587, A358730.

MGTree[n_]:=If[n==1,{},MGTree/@Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[1000],Depth[MGTree[#]]-1

A055280 Number of rooted trees with n nodes and 5 leaves.

Original entry on oeis.org

1, 5, 21, 72, 214, 563, 1344, 2958, 6086, 11820, 21854, 38713, 66069, 109109, 175019, 273540, 417672, 624472, 916038, 1320609, 1873896, 2620552, 3615923, 4927965, 6639493, 8850628, 11681631, 15275970, 19803834, 25465914, 32497699

Offset: 6

Christian G. Bower, May 09 2000

nonn

Georg Fischer, Table of n, a(n) for n = 6..172
Index entries for sequences related to rooted trees

Column 5 of A055277.

A055281 Number of rooted trees with n nodes and 6 leaves.

Original entry on oeis.org

1, 6, 30, 120, 416, 1268, 3499, 8833, 20730, 45625, 95052, 188638, 358822, 657169, 1163791, 1999495, 3343038, 5452829, 8696613, 13587910, 20834487, 31396728, 46563312, 68041054, 98068941, 139551650, 196226198, 272854810, 375461896

Offset: 7

Christian G. Bower, May 09 2000

nonn

Georg Fischer, Table of n, a(n) for n = 7..159
Index entries for sequences related to rooted trees

Column 6 of A055277.

A055282 Number of rooted trees with n nodes and 7 leaves.

Original entry on oeis.org

1, 7, 40, 185, 732, 2544, 7949, 22668, 59773, 147228, 341653, 752182, 1580470, 3185224, 6183637, 11606151, 21127675, 37405050, 64561161, 108866382, 179684155, 290762751, 461978659, 721658992, 1109643254, 1681275261

Offset: 8

Christian G. Bower, May 09 2000

nonn

Georg Fischer, Table of n, a(n) for n = 8..163
Index entries for sequences related to rooted trees

Column 7 of A055277.

A055283 Number of rooted trees with n nodes and 8 leaves.

Original entry on oeis.org

1, 8, 52, 270, 1203, 4682, 16346, 51901, 151945, 414116, 1059945, 2565394, 5907070, 13005279, 27498902, 56052155, 110506991, 211327231, 393002091, 712326630, 1260881177, 2183476067, 3705027759, 6169083918, 10092371963

Offset: 9

Christian G. Bower, May 09 2000

nonn

Georg Fischer, Table of n, a(n) for n = 9..155
Index entries for sequences related to rooted trees

Column 8 of A055277.

A055284 Number of rooted trees with n nodes and 9 leaves.

Original entry on oeis.org

1, 9, 65, 378, 1867, 8056, 31061, 108692, 349703, 1044990, 2924863, 7722047, 19346165, 46229029, 105831924, 233008811, 495046641, 1017948120, 2031186319, 3942115307, 7457028087, 13774178034, 24885909121, 44043512380

Offset: 10

Christian G. Bower, May 09 2000

nonn

Georg Fischer, Table of n, a(n) for n = 10..172
Index entries for sequences related to rooted trees

Column 9 of A055277.

A055285 Number of rooted trees with n nodes and 10 leaves.

Original entry on oeis.org

1, 10, 80, 511, 2777, 13138, 55445, 211891, 743088, 2415348, 7339040, 20991721, 56861553, 146612710, 361446211, 855299399, 1949299497, 4291731308, 9152560382, 18951522986, 38182512974, 74995707572, 143850260880

Offset: 11

Christian G. Bower, May 09 2000

nonn

Georg Fischer, Table of n, a(n) for n = 11..179
Index entries for sequences related to rooted trees

Column 10 of A055277.

cp's OEIS Frontend

A317097 Number of rooted trees with n nodes where the number of distinct branches under each node is <= 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A317098 Number of series-reduced rooted trees with n unlabeled leaves where the number of distinct branches under each node is <= 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A358554 Least Matula-Goebel number of a rooted tree with n internal (non-leaf) nodes.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A358727 Matula-Goebel numbers of rooted trees with greater number of leaves (width) than node-height.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A055280 Number of rooted trees with n nodes and 5 leaves.

Views

Author

Keywords

Links

Crossrefs

A055281 Number of rooted trees with n nodes and 6 leaves.

Views

Author

Keywords

Links

Crossrefs

A055282 Number of rooted trees with n nodes and 7 leaves.

Views

Author

Keywords

Links

Crossrefs

A055283 Number of rooted trees with n nodes and 8 leaves.

Views

Author

Keywords

Links

Crossrefs

A055284 Number of rooted trees with n nodes and 9 leaves.

Views

Author

Keywords

Links

Crossrefs

A055285 Number of rooted trees with n nodes and 10 leaves.

Views

Author

Keywords

Links

Crossrefs