Displaying 1-10 of 20 results found.
Number of rooted trees with n nodes with every leaf at the same height.
+10
40
1, 1, 2, 3, 5, 7, 12, 17, 28, 42, 68, 103, 168, 260, 420, 665, 1075, 1716, 2787, 4489, 7304, 11849, 19333, 31504, 51561, 84347, 138378, 227096, 373445, 614441, 1012583, 1669774, 2756951, 4555183, 7533988, 12469301, 20655523, 34238310, 56795325, 94270949
EXAMPLE
See Arndt link.
The a(1) = 1 through a(7) = 12 balanced rooted trees with n nodes:
o (o) (oo) (ooo) (oooo) (ooooo) (oooooo)
((o)) ((oo)) ((ooo)) ((oooo)) ((ooooo))
(((o))) (((oo))) (((ooo))) (((oooo)))
((o)(o)) ((o)(oo)) ((o)(ooo))
((((o)))) ((((oo)))) ((oo)(oo))
(((o)(o))) ((((ooo))))
(((((o))))) (((o)(oo)))
((o)(o)(o))
(((((oo)))))
((((o)(o))))
(((o))((o)))
((((((o))))))
(End)
MATHEMATICA
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_] := Sum[ T[n, k], {k, 0, n-1}]; Array[a, 40] (* Jean-François Alcover, Jan 08 2016, after Alois P. Heinz *)
Number of series-reduced balanced rooted trees whose leaves form an integer partition of n.
+10
20
1, 2, 3, 6, 9, 19, 31, 63, 110, 215, 391, 773, 1451, 2879, 5594, 11173, 22041, 44136, 87631, 175155, 348186, 694013, 1378911, 2743955, 5452833, 10853541, 21610732, 43122952, 86192274, 172753293, 347114772, 699602332, 1414033078, 2866580670, 5826842877, 11874508385
COMMENTS
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.
Also the number of balanced unlabeled phylogenetic rooted trees with n leaves.
EXAMPLE
The a(1) = 1 through a(6) = 19 rooted trees:
1 2 3 4 5 6
(11) (12) (13) (14) (15)
(111) (22) (23) (24)
(112) (113) (33)
(1111) (122) (114)
((11)(11)) (1112) (123)
(11111) (222)
((11)(12)) (1113)
((11)(111)) (1122)
(11112)
(111111)
((11)(13))
((11)(22))
((12)(12))
((11)(112))
((12)(111))
((11)(1111))
((111)(111))
((11)(11)(11))
MATHEMATICA
sps[{}]:={{}}; sps[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]&/@sps[Complement[set, s]]]/@Cases[Subsets[set], {i, ___}];
mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
phy2[labs_]:=If[Length[labs]==1, labs, Union@@Table[Sort/@Tuples[phy2/@ptn], {ptn, Select[mps[Sort[labs]], Length[#1]>1&]}]];
Table[Sum[Length[Select[phy2[ptn], SameQ@@Length/@Position[#, _Integer]&]], {ptn, IntegerPartitions[n]}], {n, 8}]
PROG
(PARI) EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
seq(n)={my(u=vector(n, n, 1), v=vector(n)); while(u, v+=u; u=EulerT(u)-u); v} \\ Andrew Howroyd, Oct 25 2018
CROSSREFS
Cf. A000081, A000311, A000669, A001678, A005804, A048816, A079500, A119262, A120803, A141268, A244925, A319312.
Number of series-reduced balanced trees with n leaves.
+10
17
1, 1, 1, 2, 2, 4, 4, 8, 9, 16, 20, 37, 47, 80, 111, 183, 256, 413, 591, 940, 1373, 2159, 3214, 5067, 7649, 12054, 18488, 29203, 45237, 71566, 111658, 176710, 276870, 437820, 687354, 1085577, 1705080, 2688285, 4221333, 6644088, 10425748
COMMENTS
In other words, rooted trees with all leaves at the same level and no node having exactly one child; the order of children is not significant.
FORMULA
Let s_0(n) = 1 if n = 1, 0 otherwise; s_{k+1}(n) = EULER(s_k)(n) - s_k(n), where EULER is the Euler transform. Then a_n = sum_k s_k(n). (s_k(n) is the number of such trees of height k.) Note that s_k(n) = 0 for n < 2^k.
EXAMPLE
The a(10) = 16 series-reduced balanced rooted trees:
(oooooooooo)
((ooooo)(ooooo))
((oooo)(oooooo))
((ooo)(ooooooo))
((oo)(oooooooo))
((ooo)(ooo)(oooo))
((oo)(oooo)(oooo))
((oo)(ooo)(ooooo))
((oo)(oo)(oooooo))
((oo)(oo)(ooo)(ooo))
((oo)(oo)(oo)(oooo))
((oo)(oo)(oo)(oo)(oo))
(((oo)(ooo))((oo)(ooo)))
(((oo)(oo))((ooo)(ooo)))
(((oo)(oo))((oo)(oooo)))
(((oo)(oo))((oo)(oo)(oo)))
(End)
PROG
(PARI) EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
seq(n)={my(u=vector(n), v=vector(n)); u[1]=1; while(u, v+=u; u=EulerT(u)-u); v} \\ Andrew Howroyd, Oct 26 2018
CROSSREFS
Cf. A000081, A000669, A001003, A001678, A007059, A048816, A079500, A119262, A244925, A316624, A320154, A320160, A320169, A320179.
Number of series-reduced balanced rooted trees whose leaves form a set partition of {1,...,n}.
+10
17
1, 2, 5, 18, 92, 588, 4328, 35920, 338437, 3654751, 45105744, 625582147, 9539374171, 157031052142, 2757275781918, 51293875591794, 1007329489077804, 20840741773898303, 453654220906310222, 10380640686263467204, 249559854371799622350, 6301679967177242849680
COMMENTS
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.
Also the number of balanced phylogenetic rooted trees on n distinct labels.
EXAMPLE
The a(1) = 1 through a(4) = 18 rooted trees:
(1) (12) (123) (1234)
((1)(2)) ((1)(23)) ((1)(234))
((2)(13)) ((12)(34))
((3)(12)) ((13)(24))
((1)(2)(3)) ((14)(23))
((2)(134))
((3)(124))
((4)(123))
((1)(2)(34))
((1)(3)(24))
((1)(4)(23))
((2)(3)(14))
((2)(4)(13))
((3)(4)(12))
((1)(2)(3)(4))
(((1)(2))((3)(4)))
(((1)(3))((2)(4)))
(((1)(4))((2)(3)))
MATHEMATICA
sps[{}]:={{}}; sps[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]&/@sps[Complement[set, s]]]/@Cases[Subsets[set], {i, ___}];
gug[m_]:=Prepend[Join@@Table[Union[Sort/@Tuples[gug/@mtn]], {mtn, Select[sps[m], Length[#]>1&]}], m];
Table[Length[Select[gug[Range[n]], SameQ@@Length/@Position[#, _Integer]&]], {n, 9}]
PROG
(PARI) 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; u=EulerT(u); 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
CROSSREFS
Cf. A000081, A000311, A000669, A001678, A005804, A048816, A079500, A119262, A120803, A141268, A244925, A292504, A300660, A319312.
Number of rooted trees with n nodes with every leaf at height 3.
+10
11
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
FORMULA
Euler transform of A002865 (with a(0)=0) shifted right.
MATHEMATICA
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];
The Matula-Goebel number of rooted trees having all leaves at the same level.
+10
9
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
COMMENTS
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.
REFERENCES
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.
FORMULA
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.
EXAMPLE
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.
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)
MAPLE
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;
MATHEMATICA
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 *)
CROSSREFS
Cf. A000081, A003238, A004111, A007097, A048816, A061775, A109082, A184154, A214577, A244925, A276625, A290689, A290760, A290822, A298422, A298424, A298426.
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.
+10
9
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
EXAMPLE
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)))
MATHEMATICA
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}]
PROG
(PARI) 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
Number of series-reduced balanced rooted trees with n labeled leaves.
+10
8
1, 1, 1, 4, 11, 41, 162, 1030, 7205, 55522, 442443, 3810852, 35272030, 351697516, 3735838550, 42719792640, 529195988635, 7128835815387, 103651381499810, 1610812109555323, 26489497655582729, 457497408108551450, 8248899117402701046, 154624472715479106919
COMMENTS
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.
FORMULA
E.g.f. A(x) satisfies A(x) = x + A(exp(x)-x-1). - Ira M. Gessel, Nov 17 2021
EXAMPLE
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))
MATHEMATICA
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}]
PROG
(PARI) 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
CROSSREFS
Cf. A000081, A000311, A000669, A001678, A005804, A048816, A079500, A119262, A120803, A141268, A244925, A319312.
Number of inequivalent colorings of series-reduced balanced rooted trees with n leaves.
+10
8
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
COMMENTS
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.
EXAMPLE
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))
PROG
(PARI) \\ 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
Number of rooted trees with n nodes with every leaf at height 4.
+10
4
1, 1, 2, 3, 6, 8, 15, 23, 39, 61, 102, 161, 265, 420, 682, 1087, 1753, 2790, 4476, 7120, 11376, 18075, 28785, 45666, 72530, 114882, 182040, 287878, 455231, 718755, 1134491, 1788461, 2818140, 4436000, 6978932, 10969695, 17232572, 27049320
FORMULA
Euler transform of A048808 shifted right.
Search completed in 0.011 seconds
| 