A055277 -id:A055277 - cp's OEIS frontend

A358724 Difference between the number of internal (non-leaf) nodes and the edge-height of the rooted tree with Matula-Goebel number n.

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

Offset: 1

Gus Wiseman, Nov 29 2022

nonn

Edge-height (A109082) is the number of edges in the longest path from root to leaf.

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 tree (o(o)((o))(oo)) with Matula-Goebel number 210 has edge-height 3 and 5 internal nodes, so a(210) = 2.

Positions of 0's are A209638, complement A358725.
Positions of 1's are A358576, counted by A358587.
Other differences: A358580, 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, A316321, A358577, A358578, A358592, A358730.

MGTree[n_]:=If[n==1,{},MGTree/@Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Table[Count[MGTree[n],[_],{0,Infinity}]-(Depth[MGTree[n]]-2),{n,100}]

a(n) = A342507(n) - A109082(n).

A358726 Difference between the node-height and the number of leaves in the rooted tree with Matula-Goebel number n.

Original entry on oeis.org

0, 1, 2, 0, 3, 1, 1, -1, 1, 2, 4, 0, 2, 0, 2, -2, 2, 0, 0, 1, 0, 3, 2, -1, 2, 1, 0, -1, 3, 1, 5, -3, 3, 1, 1, -1, 1, -1, 1, 0, 3, -1, 1, 2, 1, 1, 3, -2, -1, 1, 1, 0, -1, -1, 3, -2, -1, 2, 3, 0, 1, 4, -1, -4, 1, 2, 1, 0, 1, 0, 2, -2, 1, 0, 1, -2, 2, 0, 4, -1

Offset: 1

Gus Wiseman, Nov 29 2022

sign

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

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 tree (oo(oo(o))) with Matula-Goebel number 148 has node-height 4 and 5 leaves, so a(148) = -1.

Positions of first appearances are A007097 and latter terms of A000079.
Positions of 0's are A358577.
Other differences: A358580, A358724, 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, A056239, A112798.
Cf. A185650, A206487, A209638, A358576, A358578, A358587, A358730.

MGTree[n_]:=If[n==1,{},MGTree/@Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Table[(Depth[MGTree[n]]-1)-Count[MGTree[n],{},{0,Infinity}],{n,1000}]

a(n) = A358552(n) - A109129(n).

A298535 Number of unlabeled rooted trees with n vertices such that every branch of the root has a different number of leaves.

Original entry on oeis.org

1, 1, 1, 2, 5, 13, 32, 80, 200, 511, 1323, 3471, 9183, 24491, 65715, 177363, 481135, 1311340, 3589023, 9860254, 27181835, 75165194, 208439742, 579522977, 1615093755, 4511122964, 12625881944, 35405197065, 99459085125, 279861792874, 788712430532, 2226015529592

Offset: 1

Gus Wiseman, Jan 20 2018

nonn

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

Cf. A000081, A003238, A004111, A032305, A289079, A290689, A291443, A297791, A298422, A298533, A298536.

rut[n_]:=rut[n]=If[n===1,{{}},Join@@Function[c,Union[Sort/@Tuples[rut/@c]]]/@IntegerPartitions[n-1]];
Table[Length[Select[rut[n],UnsameQ@@(Count[#,{},{0,Infinity}]&/@#)&]],{n,15}]

\\ here R is A055277 as vector of polynomials
R(n) = {my(A = O(x)); for(j=1, n, A = x*(y - 1  + exp( sum(i=1, j, 1/i * subst( subst( A + x * O(x^(j\i)), x, x^i), y, y^i) ) ))); Vec(A)};
seq(n) = {my(M=Mat(apply(p->Colrev(p,n), R(n-1)))); Vec(prod(i=2, #M, 1 + x*Ser(M[i,])))} \\ Andrew Howroyd, May 20 2018

Terms a(19) and beyond from Andrew Howroyd, May 20 2018

A358725 Matula-Goebel numbers of rooted trees with a greater number of internal (non-leaf) vertices than edge-height.

Original entry on oeis.org

9, 15, 18, 21, 23, 25, 27, 30, 33, 35, 36, 39, 42, 45, 46, 47, 49, 50, 51, 54, 55, 57, 60, 61, 63, 65, 66, 69, 70, 72, 73, 75, 77, 78, 81, 83, 84, 85, 87, 90, 91, 92, 93, 94, 95, 97, 98, 99, 100, 102, 103, 105, 108, 110, 111, 113, 114, 115, 117, 119, 120, 121

Offset: 1

Gus Wiseman, Nov 29 2022

nonn

Edge-height (A109082) is the number of edges in the longest path from root to leaf.

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 trees begin:
   9: ((o)(o))
  15: ((o)((o)))
  18: (o(o)(o))
  21: ((o)(oo))
  23: (((o)(o)))
  25: (((o))((o)))
  27: ((o)(o)(o))
  30: (o(o)((o)))
  33: ((o)(((o))))
  35: (((o))(oo))
  36: (oo(o)(o))
  39: ((o)(o(o)))
  42: (o(o)(oo))
  45: ((o)(o)((o)))
  46: (o((o)(o)))
  47: (((o)((o))))
  49: ((oo)(oo))
  50: (o((o))((o)))

Gus Wiseman, The first 64 ordered trees with a greater number of internal vertices than edge-height.

Complement of A209638 (the case of equality).
These trees are counted by A316321.
Positions of positive terms in A358724.
The case of equality for node-height is A358576.
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.
Differences: A358580, A358724, A358726, A358729.
MG statistics: A061775, A109082, A109129, A196050, A342507, A358552.
MG core: A000040, A000720, A001222, A007097, A056239, A112798.
Cf. A185650, A206487, A358577, A358578, A358581-A358586, A358587, A358592, A358730.

MGTree[n_]:=If[n==1,{},MGTree/@Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[100],Count[MGTree[#],[_],{0,Infinity}]>Depth[MGTree[#]]-2&]

A342507(a(n)) > A109082(a(n)).

A358730 Positions of first appearances in A358729 (number of nodes minus node-height).

Original entry on oeis.org

1, 4, 8, 16, 27, 54, 81, 162, 243, 486, 729, 1458, 2187, 4374, 6561, 13122, 19683, 39366, 59049

Offset: 1

Gus Wiseman, Dec 01 2022

First differs from A334198 in having 13122 instead of 12005.
Node-height is the number of nodes in the longest path from root to leaf.
After initial terms, this appears to become A038754.

			The terms together with their corresponding rooted trees begin:
      1: o
      4: (oo)
      8: (ooo)
     16: (oooo)
     27: ((o)(o)(o))
     54: (o(o)(o)(o))
     81: ((o)(o)(o)(o))
    162: (o(o)(o)(o)(o))
    243: ((o)(o)(o)(o)(o))
    486: (o(o)(o)(o)(o)(o))
    729: ((o)(o)(o)(o)(o)(o))

Positions of first appearances in A358729.
A000081 counts rooted trees, ordered A000108.
A034781 counts rooted trees by nodes and height.
A055277 counts rooted trees by nodes and leaves.
MG differences: A358580, A358724, A358726, A358729.
MG statistics: A061775, A109082, A109129, A196050, A342507, A358552.
MG core: A000040, A000720, A001222, A007097, A056239, A112798.
Cf. A080936, A206487, A209638, A316321, A358576, A358577, A358592, A358725, A358731.

MGTree[n_]:=If[n==1,{},MGTree/@Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
rd=Table[Count[MGTree[n],_,{0,Infinity}]-(Depth[MGTree[n]]-1),{n,10000}];
Table[Position[rd,k][[1,1]],{k,Union[rd]}]

A301470 Signed recurrence over enriched r-trees: a(n) = (-1)^n + Sum_y Product_{i in y} a(y) where the sum is over all integer partitions of n - 1.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 2, 3, 5, 9, 15, 27, 47, 87, 155, 288, 524, 983, 1813, 3434, 6396, 12174, 22891, 43810, 82925, 159432, 303559, 585966, 1121446, 2171341, 4172932, 8106485, 15635332, 30445899, 58925280, 115014681, 223210718, 436603718, 849480835, 1664740873

Offset: 0

Gus Wiseman, Mar 21 2018

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..3266

Cf. A032305, A055277, A093637, A127524, A196545, A220418, A273866, A273873, A289501, A290261, A290971, A301342-A301345, A301364-A301368, A301422, A301462, A301467, A301469.

b:= proc(n, i) option remember; `if`(n=0, 1,
     `if`(i<1, 0, b(n, i-1)+a(i)*b(n-i, min(n-i, i))))
    end:
a:= n-> `if`(n<2, 1-n, b(n-2$2)+b(n-1, n-2)):
seq(a(n), n=0..45);  # Alois P. Heinz, Jun 23 2018

a[n_]:=a[n]=(-1)^n+Sum[Times@@a/@y,{y,IntegerPartitions[n-1]}];
Array[a,30]
(* Second program: *)
b[n_, i_] := b[n, i] = If[n == 0, 1,
     If[i < 1, 0, b[n, i - 1] + a[i] b[n - i, Min[n - i, i]]]];
a[n_] := If[n < 2, 1 - n, b[n - 2, n - 2] + b[n - 1, n - 2]];
a /@ Range[0, 45] (* Jean-François Alcover, May 20 2021, after Alois P. Heinz *)

O.g.f.: 1/(1 + x) + x Product_{i > 0} 1/(1 - a(i) x^i).

a(n) = Sum_t (-1)^w(t) where the sum is over all enriched r-trees of size n and w(t) is the sum of leaves of t.

A302915 Number of relatively prime enriched p-trees of weight n.

Original entry on oeis.org

1, 2, 4, 8, 28, 56, 256, 656, 2480, 6688, 30736, 73984, 366560, 1006720, 3966976, 12738560, 58427648, 148069632, 764473600, 2133585664, 8939502080, 28705390592, 136987259648, 356634376704, 1780025034240, 5455065263104, 23215437079552, 73123382895616

Offset: 1

Gus Wiseman, Apr 15 2018

nonn

A relatively prime enriched p-tree of weight n is either a single node of weight n, or a finite sequence of two or more relatively prime enriched p-trees whose weights are weakly decreasing, relatively prime, and sum to n.

			The a(4) = 8 relatively prime enriched p-trees are 4, (31), ((21)1), (((11)1)1), ((111)1), (211), ((11)11), (1111). Missing from this list are the enriched p-trees ((11)(11)), ((11)2), (2(11)), (22).

Cf. A000081, A000837, A003238, A004111, A055277, A093637, A196545, A289501, A290689, A300486, A301462, A301467, A302094, A302916, A302917.

a[n_]:=a[n]=1+Sum[Times@@a/@y,{y,Rest[Select[IntegerPartitions[n],Or[Length[#]===1,GCD@@#===1]&]]}];
Array[a,20]

A302916 Number of relatively prime p-trees of weight n.

Original entry on oeis.org

1, 1, 2, 4, 11, 22, 74, 174, 530, 1302, 4713, 10639, 40877, 101795, 325609, 925733, 3432819, 8078511, 32542036, 82226383, 279096823, 795532677, 3066505569, 7374764180, 28946183035, 79313174765, 275507514909, 772692247626, 3049937788372, 7071057261148

Offset: 1

Gus Wiseman, Apr 15 2018

nonn

A relatively prime p-tree of weight n is either a single node, or a finite sequence of two or more relatively prime p-trees whose weights are weakly decreasing, relatively prime, and sum to n.

			The a(4) = 4 relatively prime p-trees are (((oo)o)o), ((ooo)o), ((oo)oo), (oooo). Missing from this list is the p-tree ((oo)(oo)).

Cf. A000081, A000837, A003238, A004111, A055277, A093637, A196545, A289501, A290689, A300486, A301462, A301467, A302094, A302915, A302917.

a[n_]:=a[n]=If[n===1,1,Sum[Times@@a/@y,{y,Rest[Select[IntegerPartitions[n],Or[Length[#]===1,GCD@@#===1]&]]}]];
Array[a,20]

A055278 Number of rooted trees with n nodes and 3 leaves.

Original entry on oeis.org

1, 3, 8, 18, 35, 62, 103, 161, 241, 348, 487, 664, 886, 1159, 1491, 1890, 2364, 2922, 3574, 4329, 5198, 6192, 7322, 8600, 10039, 11651, 13450, 15450, 17665, 20110, 22801, 25753, 28983, 32508, 36345, 40512, 45028, 49911, 55181, 60858, 66962, 73514, 80536

Offset: 4

Christian G. Bower, May 09 2000

			G.f. = x^4 + 3*x^5 + 8*x^6 + 18*x^7 + 35*x^8 + 62*x^9 + 103*x^10 + ...

Georg Fischer, Table of n, a(n) for n = 4..200
Index entries for sequences related to rooted trees
Index entries for linear recurrences with constant coefficients, signature (3,-2,-1,0,1,2,-3,1).

Column 3 of A055277.

Cf. A055364.

a[ n_] := Quotient[ 3 n^4 - 20 n^3 + 54 n^2 - 60 n + 32, 144];

{a(n) = (3*n^4 - 20*n^3 + 54*n^2 - 60*n + 32) \ 144}; /* Michael Somos, Jun 29 2015 */

{a(n) = if( n<0, n = -1-n; polcoeff( (1 + x + x^3) / ((1 - x)^3 * (1 - x^2) * (1 - x^3)) + x * O(x^n), n), polcoeff( x^4 * (1 + x^2 + x^3) / ((1 - x)^3 * (1 - x^2) * (1 - x^3)) + x * O(x^n), n))}; /* Michael Somos, Jun 29 2015 */

G.f.: x^4*(x^3+x^2+1)/((1-x^2)*(1-x^3)*(1-x)^3) (conjectured). - Ralf Stephan, Mar 07 2004

a(n) = A055364(4 - n) for all n in Z. - Michael Somos, Jun 29 2015

A301469 Signed recurrence over enriched r-trees: a(n) = 2 * (-1)^n + Sum_y Product_{i in y} a(y) where the sum is over all integer partitions of n - 1.

Original entry on oeis.org

2, -1, 1, 0, 0, 1, 0, 1, 1, 1, 2, 3, 3, 6, 7, 11, 17, 23, 35, 53, 75, 119, 173, 264, 398, 603, 911, 1411, 2114, 3279, 4977, 7696, 11760, 18253, 27909, 43451, 66675, 103945, 160096, 249904, 385876, 603107, 933474, 1461967, 2266384, 3553167, 5521053, 8664117, 13485744

Offset: 0

Gus Wiseman, Mar 21 2018

sign

Cf. A032305, A055277, A093637, A127524, A196545, A220418, A273866, A273873, A289501, A290261, A290973, A301342-A301345, A301364-A301368, A301422, A301462, A301467, A301470.

a[n_]:=a[n]=2(-1)^n+Sum[Times@@a/@y,{y,IntegerPartitions[n-1]}];
Array[a,30]

O.g.f.: 2/(1 + x) + x Product_{i > 0} 1/(1 - a(i) x^i).

a(n) = Sum_t 2^k * (-1)^w where the sum is over all enriched r-trees of size n, k is the number of leaves, and w is the sum of leaves.

cp's OEIS Frontend

A358724 Difference between the number of internal (non-leaf) nodes and the edge-height of the rooted tree with Matula-Goebel number n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A358726 Difference between the node-height and the number of leaves in the rooted tree with Matula-Goebel number n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A298535 Number of unlabeled rooted trees with n vertices such that every branch of the root has a different number of leaves.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A358725 Matula-Goebel numbers of rooted trees with a greater number of internal (non-leaf) vertices than edge-height.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A358730 Positions of first appearances in A358729 (number of nodes minus node-height).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A301470 Signed recurrence over enriched r-trees: a(n) = (-1)^n + Sum_y Product_{i in y} a(y) where the sum is over all integer partitions of n - 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A302915 Number of relatively prime enriched p-trees of weight n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A302916 Number of relatively prime p-trees of weight n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A055278 Number of rooted trees with n nodes and 3 leaves.