A339645
Triangle read by rows: T(n,k) is the number of inequivalent colorings of lone-child-avoiding rooted trees with n colored leaves using exactly k colors.
Original entry on oeis.org
1, 1, 1, 2, 3, 2, 5, 17, 12, 5, 12, 73, 95, 44, 12, 33, 369, 721, 512, 168, 33, 90, 1795, 5487, 5480, 2556, 625, 90, 261, 9192, 41945, 58990, 36711, 12306, 2342, 261, 766, 47324, 321951, 625088, 516952, 224241, 57155, 8702, 766, 2312, 249164, 2483192, 6593103, 7141755, 3965673, 1283624, 258887, 32313, 2312
Offset: 1
Triangle begins:
1;
1, 1;
2, 3, 2;
5, 17, 12, 5;
12, 73, 95, 44, 12;
33, 369, 721, 512, 168, 33;
90, 1795, 5487, 5480, 2556, 625, 90;
261, 9192, 41945, 58990, 36711, 12306, 2342, 261;
766, 47324, 321951, 625088, 516952, 224241, 57155, 8702, 766;
...
From _Gus Wiseman_, Jan 02 2021: (Start)
Non-isomorphic representatives of the 39 = 5 + 17 + 12 + 5 trees with four colored leaves:
(1111) (1112) (1123) (1234)
(1(111)) (1122) (1(123)) (1(234))
(11(11)) (1(112)) (11(23)) (12(34))
((11)(11)) (11(12)) (12(13)) ((12)(34))
(1(1(11))) (1(122)) (2(113)) (1(2(34)))
(11(22)) (23(11))
(12(11)) ((11)(23))
(12(12)) (1(1(23)))
(2(111)) ((12)(13))
((11)(12)) (1(2(13)))
(1(1(12))) (2(1(13)))
((11)(22)) (2(3(11)))
(1(1(22)))
(1(2(11)))
((12)(12))
(1(2(12)))
(2(1(11)))
(End)
The case with only one color is
A000669.
A000311 counts singleton-reduced phylogenetic trees.
A001678 counts unlabeled lone-child-avoiding rooted trees.
A005804 counts phylogenetic rooted trees with n labels.
A060356 counts labeled lone-child-avoiding rooted trees.
A141268 counts lone-child-avoiding rooted trees with leaves summing to n.
A291636 lists Matula-Goebel numbers of lone-child-avoiding rooted trees.
A316651 counts lone-child-avoiding rooted trees with normal leaves.
A316652 counts lone-child-avoiding rooted trees with strongly normal leaves.
A330465 counts inequivalent leaf-colorings of phylogenetic rooted trees.
-
\\ See link above for combinatorial species functions.
cycleIndexSeries(n)={my(v=vector(n)); v[1]=sv(1); for(n=2, #v, v[n] = polcoef( sExp(x*Ser(v[1..n])), n )); x*Ser(v)}
{my(A=InequivalentColoringsTriangle(cycleIndexSeries(10))); for(n=1, #A~, print(A[n,1..n]))}
A291636
Matula-Goebel numbers of lone-child-avoiding rooted trees.
Original entry on oeis.org
1, 4, 8, 14, 16, 28, 32, 38, 49, 56, 64, 76, 86, 98, 106, 112, 128, 133, 152, 172, 196, 212, 214, 224, 256, 262, 266, 301, 304, 326, 343, 344, 361, 371, 392, 424, 428, 448, 454, 512, 524, 526, 532, 602, 608, 622, 652, 686, 688, 722, 742, 749, 766, 784, 817
Offset: 1
The sequence of all lone-child-avoiding rooted trees together with their Matula-Goebel numbers begins:
1: o
4: (oo)
8: (ooo)
14: (o(oo))
16: (oooo)
28: (oo(oo))
32: (ooooo)
38: (o(ooo))
49: ((oo)(oo))
56: (ooo(oo))
64: (oooooo)
76: (oo(ooo))
86: (o(o(oo)))
98: (o(oo)(oo))
106: (o(oooo))
112: (oooo(oo))
128: (ooooooo)
133: ((oo)(ooo))
152: (ooo(ooo))
172: (oo(o(oo)))
These trees are counted by
A001678.
The case with more than two branches is
A331490.
Unlabeled rooted trees are counted by
A000081.
Topologically series-reduced rooted trees are counted by
A001679.
Labeled lone-child-avoiding rooted trees are counted by
A060356.
Labeled lone-child-avoiding unrooted trees are counted by
A108919.
MG numbers of singleton-reduced rooted trees are
A330943.
MG numbers of topologically series-reduced rooted trees are
A331489.
Cf.
A007097,
A061775,
A109082,
A109129,
A111299,
A196050,
A198518,
A276625,
A291441,
A291442,
A331488.
-
nn=2000;
primeMS[n_]:=If[n===1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
srQ[n_]:=Or[n===1,With[{m=primeMS[n]},And[Length[m]>1,And@@srQ/@m]]];
Select[Range[nn],srQ]
Updated with corrected terminology by
Gus Wiseman, Jan 20 2020
A298422
Number of rooted trees with n nodes in which all positive outdegrees are the same.
Original entry on oeis.org
1, 1, 2, 2, 3, 2, 5, 2, 6, 4, 9, 2, 20, 2, 26, 12, 53, 2, 120, 2, 223, 43, 454, 2, 1100, 11, 2182, 215, 4902, 2, 11446, 2, 24744, 1242, 56014, 58, 131258, 2, 293550, 7643, 676928, 2, 1582686, 2, 3627780, 49155, 8436382, 2, 19809464, 50, 46027323, 321202
Offset: 1
The a(9) = 6 trees: ((((((((o)))))))), (o(o(o(oo)))), (o((oo)(oo))), ((oo)(o(oo))), (ooo(oooo)), (oooooooo).
Cf.
A000005,
A000081,
A000598,
A001190,
A001678,
A003238,
A004111,
A008864,
A032305,
A067538,
A111299,
A124343,
A143773,
A289078,
A289079,
A295461,
A298118,
A298204,
A298423,
A298424,
A298426.
-
srut[n_]:=srut[n]=If[n===1,{{}},Select[Join@@Function[c,Union[Sort/@Tuples[srut/@c]]]/@Select[IntegerPartitions[n-1],Function[ptn,And@@(Divisible[#-1,Length[ptn]]&/@ptn)]],SameQ@@Length/@Cases[#,{},{0,Infinity}]&]];
Table[srut[n]//Length,{n,20}]
A301700
Number of aperiodic rooted trees with n nodes.
Original entry on oeis.org
1, 1, 1, 2, 4, 10, 21, 52, 120, 290, 697, 1713, 4200, 10446, 26053, 65473, 165257, 419357, 1068239, 2732509, 7013242, 18059960, 46641983, 120790324, 313593621, 816046050, 2128101601, 5560829666, 14557746453, 38177226541, 100281484375, 263815322761, 695027102020
Offset: 1
The a(6) = 10 aperiodic trees are (((((o))))), (((o(o)))), ((o((o)))), ((oo(o))), (o(((o)))), (o(o(o))), ((o)((o))), (oo((o))), (o(o)(o)), (ooo(o)).
Cf.
A000081,
A000740,
A000837,
A001678,
A003238,
A004111,
A007716,
A007916,
A100953,
A276625,
A284639,
A290689,
A298422,
A303386,
A303431.
-
arut[n_]:=arut[n]=If[n===1,{{}},Join@@Function[c,Select[Union[Sort/@Tuples[arut/@c]],GCD@@Length/@Split[#]===1&]]/@IntegerPartitions[n-1]];
Table[Length[arut[n]],{n,20}]
-
EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
MoebiusT(v)={vector(#v, n, sumdiv(n,d,moebius(n/d)*v[d]))}
seq(n)={my(v=[1]); for(n=2, n, v=concat([1], MoebiusT(EulerT(v)))); v} \\ Andrew Howroyd, Sep 01 2018
A048816
Number of rooted trees with n nodes with every leaf at the same height.
Original entry on oeis.org
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
Offset: 1
See Arndt link.
From _Gus Wiseman_, Oct 08 2018: (Start)
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)
-
T[n_, k_] := T[n, k] = If[n==1, 1, If[k==0, 0, Sum[Sum[If[dJean-François Alcover, Jan 08 2016, after Alois P. Heinz *)
A300660
Number of unlabeled rooted phylogenetic trees with n (leaf-) nodes such that for each inner node all children are either leaves or roots of distinct subtrees.
Original entry on oeis.org
0, 1, 1, 2, 3, 6, 13, 30, 72, 182, 467, 1222, 3245, 8722, 23663, 64758, 178459, 494922, 1380105, 3867414, 10884821, 30756410, 87215419, 248117618, 707952902, 2025479210, 5809424605, 16700811214, 48113496645, 138884979562, 401645917999, 1163530868090
Offset: 0
: a(3) = 2: : a(4) = 3: :
: o o : o o o :
: / \ /|\ : / \ / \ /( )\ :
: o N N N N : o N o N N N N N :
: ( ) : / \ /|\ :
: N N : o N N N N :
: : ( ) :
: : N N :
From _Gus Wiseman_, Feb 06 2020: (Start)
The a(2) = 1 through a(6) = 13 unlabeled rooted phylogenetic semi-identity trees:
(oo) (ooo) (oooo) (ooooo) (oooooo)
((o)(oo)) ((o)(ooo)) ((o)(oooo)) ((o)(ooooo))
((o)((o)(oo))) ((oo)(ooo)) ((oo)(oooo))
((o)((o)(ooo))) ((o)(oo)(ooo))
((oo)((o)(oo))) (((o)(oo))(ooo))
((o)((o)((o)(oo)))) ((o)((o)(oooo)))
((o)((oo)(ooo)))
((oo)((o)(ooo)))
((o)(oo)((o)(oo)))
((o)((o)((o)(ooo))))
((o)((oo)((o)(oo))))
((oo)((o)((o)(oo))))
((o)((o)((o)((o)(oo)))))
(End)
The locally disjoint case is
A316694.
-
b:= proc(n,i) option remember; `if`(n=0, 1, `if`(i<1, 0,
add(b(n-i*j, i-1)*binomial(a(i), j), j=0..n/i)))
end:
a:= n-> `if`(n=0, 0, 1+b(n, n-1)):
seq(a(n), n=0..30);
-
b[0, ] = 1; b[, _?NonPositive] = 0;
b[n_, i_] := b[n, i] = Sum[b[n-i*j, i-1]*Binomial[a[i], j], {j, 0, n/i}];
a[0] = 0; a[n_] := a[n] = 1 + b[n, n-1];
Table[a[n], {n, 0, 31}] (* Jean-François Alcover, May 03 2019, from Maple *)
ursit[n_]:=Prepend[Join@@Table[Select[Union[Sort/@Tuples[ursit/@ptn]],UnsameQ@@#&],{ptn,Select[IntegerPartitions[n],Length[#]>1&]}],n];
Table[Length[ursit[n]],{n,10}] (* Gus Wiseman, Feb 06 2020 *)
A319312
Number of series-reduced rooted trees whose leaves are integer partitions whose multiset union is an integer partition of n.
Original entry on oeis.org
1, 3, 7, 22, 67, 242, 885, 3456, 13761, 56342, 234269, 989335, 4225341, 18231145, 79321931, 347676128, 1533613723, 6803017863, 30328303589, 135808891308, 610582497919, 2755053631909, 12472134557093, 56630659451541, 257841726747551, 1176927093597201
Offset: 1
The a(3) = 7 trees:
(3) (21) (111)
((1)(2)) ((1)(11))
((1)(1)(1))
((1)((1)(1)))
Cf.
A000081,
A000311,
A000669,
A001678,
A005804,
A141268,
A292504,
A300660,
A316653,
A316654,
A316656.
-
facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
phyfacs[n_]:=Prepend[Join@@Table[Union[Sort/@Tuples[phyfacs/@f]],{f,Select[facs[n],Length[#]>1&]}],n];
Table[Sum[Length[phyfacs[Times@@Prime/@m]],{m,IntegerPartitions[n]}],{n,6}]
-
EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
seq(n)={my(v=[]); for(n=1, n, v=concat(v, numbpart(n) + EulerT(concat(v,[0]))[n])); v} \\ Andrew Howroyd, Sep 18 2018
A060356
Expansion of e.g.f.: -LambertW(-x/(1+x)).
Original entry on oeis.org
0, 1, 0, 3, 4, 65, 306, 4207, 38424, 573057, 7753510, 134046671, 2353898196, 47602871329, 1013794852266, 23751106404495, 590663769125296, 15806094859299329, 448284980183376078, 13515502344669830287
Offset: 0
From _Gus Wiseman_, Dec 31 2019: (Start)
Non-isomorphic representatives of the a(7) = 4207 trees, written as root[branches], are:
1[2,3[4,5[6,7]]]
1[2,3[4,5,6,7]]
1[2[3,4],5[6,7]]
1[2,3,4[5,6,7]]
1[2,3,4,5[6,7]]
1[2,3,4,5,6,7]
(End)
The unlabeled version is
A001678(n + 1).
The case where the root is fixed is
A108919.
Unlabeled rooted trees are counted by
A000081.
Lone-child-avoiding rooted trees with labeled leaves are
A000311.
Matula-Goebel numbers of lone-child-avoiding rooted trees are
A291636.
Singleton-reduced rooted trees are counted by
A330951.
Cf.
A000669,
A004111,
A005121,
A048816,
A292504,
A316651,
A316652,
A318231,
A318813,
A330465,
A330624.
-
List([0..20],n->Sum([1..n],k->(-1)^(n-k)*Factorial(n)/Factorial(k) *Binomial(n-1,k-1)*k^(k-1))); # Muniru A Asiru, Feb 19 2018
-
seq(coeff(series( -LambertW(-x/(1+x)), x, n+1), x, n)*n!, n = 0..20); # G. C. Greubel, Mar 16 2020
-
CoefficientList[Series[-LambertW[-x/(1+x)], {x, 0, 20}], x]* Range[0, 20]! (* Vaclav Kotesovec, Nov 27 2012 *)
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
a[n_]:=If[n==1,1,n*Sum[Times@@a/@Length/@stn,{stn,Select[sps[Range[n-1]],Length[#]>1&]}]];
Array[a,10] (* Gus Wiseman, Dec 31 2019 *)
-
{ for (n=0, 100, f=n!; a=sum(k=1, n, (-1)^(n - k)*f/k!*binomial(n - 1, k - 1)*k^(k - 1)); write("b060356.txt", n, " ", a); ) } \\ Harry J. Smith, Jul 04 2009
-
my(x='x+O('x^20)); concat([0], Vec(serlaplace(-lambertw(-x/(1+x))))) \\ G. C. Greubel, Feb 19 2018
A316651
Number of series-reduced rooted trees with n leaves spanning an initial interval of positive integers.
Original entry on oeis.org
1, 2, 12, 112, 1444, 24086, 492284, 11910790, 332827136, 10546558146, 373661603588, 14636326974270, 628032444609396, 29296137817622902, 1476092246351259964, 79889766016415899270, 4622371378514020301740, 284719443038735430679268, 18601385258191195218790756
Offset: 1
The a(3) = 12 trees:
(1(11)), (111),
(1(12)), (2(11)), (112),
(1(22)), (2(12)), (122),
(1(23)), (2(13)), (3(12)), (123).
-
b:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0,
add(binomial(A(i, k)+j-1, j)*b(n-i*j, i-1, k), j=0..n/i)))
end:
A:= (n, k)-> `if`(n<2, n*k, b(n, n-1, k)):
a:= n-> add(add(A(n, k-j)*(-1)^j*binomial(k, j), j=0..k-1), k=1..n):
seq(a(n), n=1..20); # Alois P. Heinz, Sep 18 2018
-
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]]]];
gro[m_]:=If[Length[m]==1,m,Union[Sort/@Join@@(Tuples[gro/@#]&/@Select[mps[m],Length[#]>1&])]];
allnorm[n_Integer]:=Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1];
Table[Sum[Length[gro[m]],{m,allnorm[n]}],{n,5}]
(* Second program: *)
b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i < 1, 0,
Sum[Binomial[A[i, k] + j - 1, j] b[n - i*j, i - 1, k], {j, 0, n/i}]]];
A[n_, k_] := If[n < 2, n*k, b[n, n - 1, k]];
a[n_] := Sum[Sum[A[n, k-j]*(-1)^j*Binomial[k, j], {j, 0, k-1}], {k, 1, n}];
Array[a, 20] (* Jean-François Alcover, May 09 2021, after Alois P. Heinz *)
-
\\ here R(n,k) is A000669, A050381, A220823, ...
EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
R(n,k)={my(v=[k]); for(n=2, n, v=concat(v, EulerT(concat(v,[0]))[n])); v}
seq(n)={sum(k=1, n, R(n,k)*sum(r=k, n, binomial(r,k)*(-1)^(r-k)) )} \\ Andrew Howroyd, Sep 14 2018
A316652
Number of series-reduced rooted trees whose leaves span an initial interval of positive integers with multiplicities an integer partition of n.
Original entry on oeis.org
1, 2, 9, 69, 623, 7793, 110430, 1906317, 36833614, 816101825, 19925210834, 541363267613, 15997458049946, 515769374925576, 17905023985615254, 669030297769291562, 26689471638523499483, 1134895275721374771655, 51161002326406795249910, 2440166138715867838359915
Offset: 1
The a(3) = 9 trees:
(1(11)), (111),
(1(12)), (2(11)), (112),
(1(23)), (2(13)), (3(12)), (123).
-
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]]]];
gro[m_]:=If[Length[m]==1,m,Union[Sort/@Join@@(Tuples[gro/@#]&/@Select[mps[m],Length[#]>1&])]];
Table[Sum[Length[gro[m]],{m,Flatten[MapIndexed[Table[#2,{#1}]&,#]]&/@IntegerPartitions[n]}],{n,4}]
-
\\ See A339645 for combinatorial species functions.
cycleIndexSeries(n)={my(v=vector(n)); v[1]=sv(1); for(n=2, #v, v[n] = polcoef( sExp(x*Ser(v[1..n])), n )); x*Ser(v)}
StronglyNormalLabelingsSeq(cycleIndexSeries(15)) \\ Andrew Howroyd, Jan 04 2021
Comments