A048816 -id:A048816 - cp's OEIS frontend

A048808 Number of rooted trees with n nodes with every leaf at height 3.

1, 1, 2, 3, 5, 7, 12, 18, 27, 42, 64, 96, 146, 219, 327, 491, 730, 1084, 1608, 2376, 3500, 5154, 7563, 11076, 16193, 23625, 34395, 50005, 72550, 105089, 151984, 219448, 316362, 455434, 654661, 939736, 1347137, 1928593, 2757449, 3937675

Offset: 4

Christian G. Bower, Apr 15 1999

nonn

Vaclav Kotesovec, Table of n, a(n) for n = 4..10000 (terms 4..1000 from Alois P. Heinz)
N. J. A. Sloane, Transforms
Index entries for sequences related to rooted trees

Cf. A048809-A048816.

Column k=3 of A244925.

T[n_, k_] := T[n, k] = If[n == 1, 1, If[k == 0, 0, Sum[Sum[If[d < k, 0, T[d, k - 1]*d], {d, Divisors[j]}]*T[n - j, k], {j, 1, n - 1}]/(n - 1)]];
a[n_] := T[n, 3];
Table[a[n], {n, 4, 50}] (* Jean-François Alcover, May 11 2019, after Alois P. Heinz in A244925 *)

Euler transform of A002865 (with a(0)=0) shifted right.

A306201 Number of unlabeled balanced rooted semi-identity trees with n nodes.

Original entry on oeis.org

0, 1, 1, 2, 3, 4, 6, 8, 12, 16, 25, 35, 53, 77, 117, 173, 265, 396, 605, 919, 1408, 2147, 3305, 5070, 7819, 12049, 18635, 28811, 44672, 69264, 107618, 167292, 260446, 405686, 632743, 987441, 1542555, 2411208, 3772247, 5905002, 9250436, 14499234, 22740910, 35686092

Offset: 0

Gus Wiseman, Jan 29 2019

nonn

A rooted tree is a semi-identity tree if the non-leaf branches of the root are all distinct and are themselves semi-identity trees. It is balanced if all leaves are the same distance from the root. The only balanced identity trees are rooted paths.

			The a(1) = 1 through a(7) = 8 balanced rooted semi-identity trees:
  o  (o)  (oo)   (ooo)    (oooo)     (ooooo)      (oooooo)
          ((o))  ((oo))   ((ooo))    ((oooo))     ((ooooo))
                 (((o)))  (((oo)))   (((ooo)))    (((oooo)))
                          ((((o))))  ((o)(oo))    ((o)(ooo))
                                     ((((oo))))   ((((ooo))))
                                     (((((o)))))  (((o)(oo)))
                                                  (((((oo)))))
                                                  ((((((o))))))

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

Cf. A000081, A004111, A048816, A079500, A120803, A306200, A316624, A317712, A320169, A320270.

Row sums of A306269.

ursit[n_]:=Join@@Table[Select[Union[Sort/@Tuples[ursit/@ptn]],UnsameQ@@DeleteCases[#,{}]&],{ptn,IntegerPartitions[n-1]}];
Table[Length[Select[ursit[n],SameQ@@Length/@Position[#,{}]&]],{n,10}]

More terms from Alois P. Heinz, Jan 29 2019

A330663 Number of non-isomorphic balanced reduced multisystems of weight n and maximum depth.

Original entry on oeis.org

1, 1, 2, 4, 20, 140, 1411

Offset: 0

Gus Wiseman, Dec 27 2019

A balanced reduced multisystem is either a finite multiset, or a multiset partition with at least two parts, not all of which are singletons, of a balanced reduced multisystem. The weight of an atom is 1, while the weight of a multiset is the sum of weights of its elements.

			Non-isomorphic representatives of the a(2) = 2 through a(4) = 20 multisystems:
  {1,1}  {{1},{1,1}}  {{{1}},{{1},{1,1}}}
  {1,2}  {{1},{1,2}}  {{{1,1}},{{1},{1}}}
         {{1},{2,3}}  {{{1}},{{1},{1,2}}}
         {{2},{1,1}}  {{{1,1}},{{1},{2}}}
                      {{{1}},{{1},{2,2}}}
                      {{{1,1}},{{2},{2}}}
                      {{{1}},{{1},{2,3}}}
                      {{{1,1}},{{2},{3}}}
                      {{{1}},{{2},{1,1}}}
                      {{{1,2}},{{1},{1}}}
                      {{{1}},{{2},{1,2}}}
                      {{{1,2}},{{1},{2}}}
                      {{{1}},{{2},{1,3}}}
                      {{{1,2}},{{1},{3}}}
                      {{{1}},{{2},{3,4}}}
                      {{{1,2}},{{3},{4}}}
                      {{{2}},{{1},{1,1}}}
                      {{{2}},{{1},{1,3}}}
                      {{{2}},{{3},{1,1}}}
                      {{{2,3}},{{1},{1}}}

The non-maximal version is A330474.
Labeled versions are A330675 (strongly normal) and A330676 (normal).
The case where the leaves are sets (as opposed to multisets) is A330677.
The case with all atoms distinct is A000111.
The case with all atoms equal is (also) A000111.
Cf. A000311, A004114, A005121, A006472, A007716, A048816, A141268, A306186, A330470, A330655, A330664.

A184155 The Matula-Goebel number of rooted trees having all leaves at the same level.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 8, 9, 11, 16, 17, 19, 21, 23, 25, 27, 31, 32, 49, 53, 57, 59, 63, 64, 67, 73, 81, 83, 85, 97, 103, 115, 121, 125, 127, 128, 131, 133, 147, 159, 171, 189, 227, 241, 243, 256, 269, 277, 289, 307, 311, 331, 335, 343, 361, 365, 367, 371, 391, 393, 399, 419, 425, 431, 439, 441, 477

Offset: 1

Emeric Deutsch, Oct 07 2011

nonn

The Matula-Goebel number of a rooted tree can be defined in the following recursive manner: to the one-vertex tree there corresponds the number 1; to a tree T with root degree 1 there corresponds the t-th prime number, where t is the Matula-Goebel number of the tree obtained from T by deleting the edge emanating from the root; to a tree T with root degree m>=2 there corresponds the product of the Matula-Goebel numbers of the m branches of T.

The sequence is infinite.

			7 is in the sequence because the rooted tree with Matula-Goebel number 7 is the rooted tree Y, having all leaves at level 2.
2^m is in the sequence for each positive integer m because the rooted tree with Matula-Goebel number 2^m is a star with m edges.
From _Gus Wiseman_, Mar 30 2018: (Start)
Sequence of trees begins:
01 o
02 (o)
03 ((o))
04 (oo)
05 (((o)))
07 ((oo))
08 (ooo)
09 ((o)(o))
11 ((((o))))
16 (oooo)
17 (((oo)))
19 ((ooo))
21 ((o)(oo))
23 (((o)(o)))
25 (((o))((o)))
27 ((o)(o)(o))
31 (((((o)))))
(End)

F. Goebel, On a 1-1-correspondence between rooted trees and natural numbers, J. Combin. Theory, B 29 (1980), 141-143.
I. Gutman and A. Ivic, On Matula numbers, Discrete Math., 150, 1996, 131-142.
I. Gutman and Yeong-Nan Yeh, Deducing properties of trees from their Matula numbers, Publ. Inst. Math., 53 (67), 1993, 17-22.
D. W. Matula, A natural rooted tree enumeration by prime factorization, SIAM Review, 10, 1968, 273.

Index entries for sequences related to Matula-Goebel numbers

Cf. A000081, A003238, A004111, A007097, A048816, A061775, A109082, A184154, A214577, A244925, A276625, A290689, A290760, A290822, A298422, A298424, A298426.

with(numtheory): P := proc (n) local r, s: r := proc (n) options operator, arrow: op(1, factorset(n)) end proc: s := proc (n) options operator, arrow: n/r(n) end proc: if n = 1 then 1 elif bigomega(n) = 1 then sort(expand(x*P(pi(n)))) else sort(P(r(n))+P(s(n))) end if end proc: A := {}: for n to 500 do if degree(numer(subs(x = 1/x, P(n)))) = 0 then A := `union`(A, {n}) else  end if end do: A;

primeMS[n_]:=If[n===1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
dep[n_]:=If[n===1,0,1+Max@@dep/@primeMS[n]];
rnkQ[n_]:=And[SameQ@@dep/@primeMS[n],And@@rnkQ/@primeMS[n]];
Select[Range[2000],rnkQ] (* Gus Wiseman, Mar 30 2018 *)

In A184154 one constructs for each n the generating polynomial P(n,x) of the leaves of the rooted tree with Matula-Goebel number n, according to their levels. The Maple program finds those n (between 1 and 500) for which P(n,x) is a monomial.

A320169 Number of balanced enriched p-trees of weight n.

Original entry on oeis.org

1, 2, 3, 6, 9, 20, 31, 70, 114, 243, 415, 961, 1603, 3564, 6559, 14913, 26630, 60037, 110160, 248859, 458445, 1001190, 1882350, 4220358, 7765303, 16822107, 32307240, 70081784, 133716083, 291788153, 561823990, 1230204229, 2396185727, 5176454708, 10220127290

Offset: 1

Gus Wiseman, Oct 07 2018

nonn

An enriched p-tree of weight n is either the number n itself or a finite sequence of enriched p-trees whose weights are weakly decreasing and sum to n.

A tree is balanced if all leaves have the same height.

			The a(1) = 1 through a(6) = 20 balanced enriched p-trees:
  1  2     3      4           5            6
     (11)  (21)   (22)        (32)         (33)
           (111)  (31)        (41)         (42)
                  (211)       (221)        (51)
                  (1111)      (311)        (222)
                  ((11)(11))  (2111)       (321)
                              (11111)      (411)
                              ((21)(11))   (2211)
                              ((111)(11))  (3111)
                                           (21111)
                                           (111111)
                                           ((21)(21))
                                           ((22)(11))
                                           ((31)(11))
                                           ((111)(21))
                                           ((21)(111))
                                           ((211)(11))
                                           ((111)(111))
                                           ((1111)(11))
                                           ((11)(11)(11))

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

Cf. A000311, A000669, A001678, A005804, A048816, A079500, A119262, A120803, A141268, A196545, A289501, A319312.

Cf. A316624, A320154, A320155, A320160, A320179.

eptrs[n_]:=Prepend[Join@@Table[Tuples[eptrs/@p],{p,Rest[IntegerPartitions[n]]}],n];
Table[Length[Select[eptrs[n],SameQ@@Length/@Position[#,_Integer]&]],{n,12}]

seq(n)={my(p=x/(1-x) + O(x*x^n), q=0); while(p, q+=p; p = 1/prod(k=1, n, 1 - polcoef(p,k)*x^k + O(x*x^n)) - 1 - p); Vec(q)} \\ Andrew Howroyd, Oct 26 2018

Terms a(16) and beyond from Andrew Howroyd, Oct 26 2018

A320179 Regular triangle where T(n,k) is the number of unlabeled series-reduced rooted trees with n leaves in which every leaf is at height k.

Original entry on oeis.org

1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 3, 0, 0, 0, 0, 1, 3, 0, 0, 0, 0, 0, 1, 6, 1, 0, 0, 0, 0, 0, 1, 7, 1, 0, 0, 0, 0, 0, 0, 1, 11, 4, 0, 0, 0, 0, 0, 0, 0, 1, 13, 6, 0, 0, 0, 0, 0, 0, 0, 0, 1, 20, 16, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 23, 23, 0, 0, 0

Offset: 1

Gus Wiseman, Oct 07 2018

			Triangle begins:
  1
  0  1
  0  1  0
  0  1  1  0
  0  1  1  0  0
  0  1  3  0  0  0
  0  1  3  0  0  0  0
  0  1  6  1  0  0  0  0
  0  1  7  1  0  0  0  0  0
  0  1 11  4  0  0  0  0  0  0
  0  1 13  6  0  0  0  0  0  0  0
  0  1 20 16  0  0  0  0  0  0  0  0
  0  1 23 23  0  0  0  0  0  0  0  0  0
  0  1 33 46  0  0  0  0  0  0  0  0  0  0
The T(10,3) = 4 rooted trees:
   (((oo)(oo))((oo)(oooo)))
   (((oo)(oo))((ooo)(ooo)))
   (((oo)(ooo))((oo)(ooo)))
  (((oo)(oo))((oo)(oo)(oo)))

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

Row sums are A120803. Third column is A083751. An irregular version is A320221.
Cf. A000669, A001678, A048816, A079500, A119262, A244925, A316655, A319312.
Cf. A316624, A320154, A320155, A320160, A320172, A320173.

qurt[n_]:=If[n==1,{{}},Join@@Table[Union[Sort/@Tuples[qurt/@ptn]],{ptn,Select[IntegerPartitions[n],Length[#]>1&]}]];
Table[Length[Select[qurt[n],SameQ[##,k]&@@Length/@Position[#,{}]&]],{n,14},{k,0,n-1}]

EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
T(n)={my(u=vector(n), v=vector(n), h=1); u[1]=1; while(u, v+=u*h; h*=x; u=EulerT(u)-u); vector(n, n, Vecrev(v[n], n))}
{ my(A=T(15)); for(n=1, #A, print(A[n])) } \\ Andrew Howroyd, Dec 09 2020

A320155 Number of series-reduced balanced rooted trees with n labeled leaves.

Original entry on oeis.org

1, 1, 1, 4, 11, 41, 162, 1030, 7205, 55522, 442443, 3810852, 35272030, 351697516, 3735838550, 42719792640, 529195988635, 7128835815387, 103651381499810, 1610812109555323, 26489497655582729, 457497408108551450, 8248899117402701046, 154624472715479106919

Offset: 1

Gus Wiseman, Oct 06 2018

nonn

A rooted tree is series-reduced if every non-leaf node has at least two branches, and balanced if all leaves are the same distance from the root.

			The a(1) = 1 through a(5) = 11 rooted trees:
  1  (12)  (123)    (1234)      (12345)
                  ((12)(34))  ((12)(345))
                  ((13)(24))  ((13)(245))
                  ((14)(23))  ((14)(235))
                              ((15)(234))
                              ((23)(145))
                              ((24)(135))
                              ((25)(134))
                              ((34)(125))
                              ((35)(124))
                              ((45)(123))

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

Cf. A000081, A000311, A000669, A001678, A005804, A048816, A079500, A119262, A120803, A141268, A244925, A319312.

Cf. A320154, A320160, A316624, A320169, A320173, A320179.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
phy2[labs_]:=If[Length[labs]==1,labs,Union@@Table[Sort/@Tuples[phy2/@ptn],{ptn,Select[sps[Sort[labs]],Length[#1]>1&]}]];
Table[Length[Select[phy2[Range[n]],SameQ@@Length/@Position[#,_Integer]&]],{n,7}]

EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
b(n,k)={my(u=vector(n), v=vector(n)); u[1]=k; while(u, v+=u; u=EulerT(u)-u); v}
seq(n)={my(M=Mat(vectorv(n,k,b(n,k)))); vector(n, k, sum(i=1, k, binomial(k,i)*(-1)^(k-i)*M[i,k]))} \\ Andrew Howroyd, Oct 26 2018

E.g.f. A(x) satisfies A(x) = x + A(exp(x)-x-1). - Ira M. Gessel, Nov 17 2021

Terms a(10) and beyond from Andrew Howroyd, Oct 26 2018

A320173 Number of inequivalent colorings of series-reduced balanced rooted trees with n leaves.

Original entry on oeis.org

1, 2, 3, 12, 23, 84, 204, 830, 2940, 13397, 58794, 283132, 1377302, 7087164, 37654377, 209943842, 1226495407, 7579549767, 49541194089, 341964495985, 2476907459261, 18703210872343, 146284738788714, 1179199861398539, 9760466433602510, 82758834102114911, 717807201648148643

Offset: 1

Gus Wiseman, Oct 07 2018

nonn

A rooted tree is series-reduced if every non-leaf node has at least two branches, and balanced if all leaves are the same distance from the root.

			Inequivalent representatives of the a(1) = 1 through a(5) = 23 colorings:
  1  (11)  (111)    (1111)      (11111)
     (12)  (112)    (1112)      (11112)
           (123)    (1122)      (11122)
                    (1123)      (11123)
                    (1234)      (11223)
                  ((11)(11))    (11234)
                  ((11)(12))    (12345)
                  ((11)(22))  ((11)(111))
                  ((11)(23))  ((11)(112))
                  ((12)(12))  ((11)(122))
                  ((12)(13))  ((11)(123))
                  ((12)(34))  ((11)(223))
                              ((11)(234))
                              ((12)(111))
                              ((12)(112))
                              ((12)(113))
                              ((12)(123))
                              ((12)(134))
                              ((12)(345))
                              ((13)(122))
                              ((22)(111))
                              ((23)(111))
                              ((23)(114))

Cf. A000669, A005804, A048816, A079500, A119262, A120803, A141268, A244925, A319312.

Cf. A320154, A320155, A320160, A320174, A320175, A320179, A339645.

\\ See links in A339645 for combinatorial species functions.
cycleIndexSeries(n)={my(p=x*sv(1) + O(x*x^n), q=0); while(p, q+=p; p=sEulerT(p)-1-p); q}
InequivalentColoringsSeq(cycleIndexSeries(15)) \\ Andrew Howroyd, Dec 11 2020

Terms a(8) and beyond from Andrew Howroyd, Dec 11 2020

A330664 Number of non-isomorphic balanced reduced multisystems of maximum depth whose degrees (atom multiplicities) are the weakly decreasing prime indices of n.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 2, 1, 4, 5, 5, 7, 16, 16, 27, 2, 61, 33, 272, 27, 123, 61, 1385, 27, 78, 272, 95, 123, 7936, 362

Offset: 1

Gus Wiseman, Dec 28 2019

A balanced reduced multisystem is either a finite multiset, or a multiset partition with at least two parts, not all of which are singletons, of a balanced reduced multisystem.

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798. A multiset whose multiplicities are the prime indices of n (such as row n of A305936) is generally not the same as the multiset of prime indices of n. For example, the prime indices of 12 are {1,1,2}, while a multiset whose multiplicities are {1,1,2} is {1,1,2,3}.

			Non-isomorphic representatives of the a(n) multisystems for n = 2, 3, 6, 9, 10, 12 (commas and outer brackets elided):
  1  11  {1}{12}  {{1}}{{1}{22}}  {{1}}{{1}{12}}  {{1}}{{1}{23}}
         {2}{11}  {{11}}{{2}{2}}  {{11}}{{1}{2}}  {{11}}{{2}{3}}
                  {{1}}{{2}{12}}  {{1}}{{2}{11}}  {{1}}{{2}{13}}
                  {{12}}{{1}{2}}  {{12}}{{1}{1}}  {{12}}{{1}{3}}
                                  {{2}}{{1}{11}}  {{2}}{{1}{13}}
                                                  {{2}}{{3}{11}}
                                                  {{23}}{{1}{1}}

The non-maximal version is A330666.
The case of constant or strict atoms is A000111.
Labeled versions are A330728, A330665 (prime indices), and A330675 (strongly normal).
Non-isomorphic multiset partitions whose degrees are the prime indices of n are A318285.
Cf. A004114, A005121, A007716, A048816, A141268, A306186, A318846, A318848, A330470, A330474, A330663.

For n > 1, a(2^n) = a(prime(n)) = A000111(n - 1).

A306203 Matula-Goebel numbers of balanced rooted semi-identity trees.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 8, 11, 16, 17, 19, 21, 31, 32, 53, 57, 59, 64, 67, 73, 85, 127, 128, 131, 133, 159, 241, 256, 269, 277, 311, 331, 335, 365, 367, 371, 393, 399, 439, 512, 649, 709, 719, 739, 751, 917, 933, 937, 1007, 1024, 1113, 1139, 1205, 1241, 1345, 1523

Offset: 1

Gus Wiseman, Jan 29 2019

nonn

A rooted tree is a semi-identity tree if the non-leaf branches of the root are all distinct and are themselves semi-identity trees. It is balanced if all leaves are the same distance from the root. The only balanced rooted identity trees are rooted paths.

			The sequence of all unlabeled balanced rooted semi-identity trees together with their Matula-Goebel numbers begins:
   1: o
   2: (o)
   3: ((o))
   4: (oo)
   5: (((o)))
   7: ((oo))
   8: (ooo)
  11: ((((o))))
  16: (oooo)
  17: (((oo)))
  19: ((ooo))
  21: ((o)(oo))
  31: (((((o)))))
  32: (ooooo)
  53: ((oooo))
  57: ((o)(ooo))
  59: ((((oo))))
  64: (oooooo)
  67: (((ooo)))
  73: (((o)(oo)))
  85: (((o))((oo)))

Cf. A000081, A004111, A007097, A048816, A184155, A276625, A306200, A306201, A306202, A316467, A317710.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
psidQ[n_]:=And[UnsameQ@@DeleteCases[primeMS[n],1],And@@psidQ/@primeMS[n]];
mgtree[n_]:=If[n==1,{},mgtree/@primeMS[n]];
Select[Range[100],And[psidQ[#],SameQ@@Length/@Position[mgtree[#],{}]]&]

cp's OEIS Frontend

A048808 Number of rooted trees with n nodes with every leaf at height 3.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A306201 Number of unlabeled balanced rooted semi-identity trees with n nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A330663 Number of non-isomorphic balanced reduced multisystems of weight n and maximum depth.

Views

Author

Keywords

Comments

Examples

Crossrefs

A184155 The Matula-Goebel number of rooted trees having all leaves at the same level.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A320169 Number of balanced enriched p-trees of weight n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A320179 Regular triangle where T(n,k) is the number of unlabeled series-reduced rooted trees with n leaves in which every leaf is at height k.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A320155 Number of series-reduced balanced rooted trees with n labeled leaves.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A320173 Number of inequivalent colorings of series-reduced balanced rooted trees with n leaves.

Views

Author

Keywords