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]))}
A318813
Number of balanced reduced multisystems with n atoms all equal to 1.
Original entry on oeis.org
1, 1, 2, 6, 20, 90, 468, 2910, 20644, 165874, 1484344, 14653890, 158136988, 1852077284, 23394406084, 317018563806, 4587391330992, 70598570456104, 1151382852200680, 19835976878704628, 359963038816096924, 6863033015330999110, 137156667020252478684, 2867083618970831936826
Offset: 1
The a(5) = 20 balanced reduced multisystems (with n written in place of 1^n):
5 (14) (23) (113) (122) (1112)
((1)(13)) ((1)(22)) ((1)(112))
((3)(11)) ((2)(12)) ((2)(111))
((11)(12))
((1)(1)(12))
((1)(2)(11))
(((1))((1)(12)))
(((1))((2)(11)))
(((2))((1)(11)))
(((12))((1)(1)))
(((11))((1)(2)))
Cf.
A000311,
A001055,
A002846,
A005121,
A213427,
A281118,
A281119,
A317145,
A318812,
A318846,
A320154,
A330474,
A330679.
-
normize[m_]:=m/.Rule@@@Table[{Union[m][[i]],i},{i,Length[Union[m]]}];
facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
totfact[n_]:=totfact[n]=1+Sum[totfact[Times@@Prime/@normize[f]],{f,Select[facs[n],1
-
EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
seq(n)={my(v=vector(n, i, i==1), u=vector(n)); for(r=1, #v, u += v*sum(j=r, #v, (-1)^(j-r)*binomial(j-1, r-1)); v=EulerT(v)); u} \\ Andrew Howroyd, Dec 30 2019
A330465
Number of non-isomorphic series-reduced rooted trees whose leaves are multisets with a total of n elements.
Original entry on oeis.org
1, 4, 14, 87, 608, 5573, 57876, 687938, 9058892, 130851823, 2048654450, 34488422057, 620046639452, 11839393796270, 238984150459124, 5079583100918338, 113299159314626360, 2644085918303683758, 64393240540265515110, 1632731130253043991252, 43013015553755764179000
Offset: 1
Non-isomorphic representatives of the a(3) = 14 trees:
((1)((1)(1))) ((1)((1)(2))) ((1)((2)(3))) ((2)((1)(1)))
((1)(1)(1)) ((1)(1)(2)) ((1)(2)(3)) ((2)(1,1))
((1)(1,1)) ((1)(1,2)) ((1)(2,3))
(1,1,1) (1,1,2) (1,2,3)
The version where leaves are atoms is
A318231.
The case with sets as leaves is
A330624.
The case with disjoint sets as leaves is
A141268.
The singleton-reduced version is
A330470.
Cf.
A000311,
A000669,
A004114,
A005804,
A007716,
A281118,
A289501,
A292504,
A316651,
A316652,
A318812,
A319312,
A330471,
A330474,
A330625,
A339645.
-
\\ See links in A339645 for combinatorial species functions.
cycleIndexSeries(n)={my(v=vector(n), p=sEulerT(x*sv(1) + O(x*x^n))); v[1]=sv(1); for(n=2, #v, v[n] = polcoef( sEulerT(x*Ser(v[1..n])), n ) + polcoef(p,n)); x*Ser(v)}
InequivalentColoringsSeq(cycleIndexSeries(15)) \\ Andrew Howroyd, Dec 13 2020
A323787
Number of non-isomorphic multiset partitions of strict multiset partitions of weight n.
Original entry on oeis.org
1, 1, 4, 14, 56, 219, 1001, 4588
Offset: 0
Non-isomorphic representatives of the a(1) = 1 through a(3) = 14 multiset partitions:
{{1}} {{11}} {{111}}
{{12}} {{112}}
{{1}{2}} {{123}}
{{1}}{{2}} {{1}{11}}
{{1}{12}}
{{1}{23}}
{{2}{11}}
{{1}}{{11}}
{{1}}{{12}}
{{1}}{{23}}
{{1}{2}{3}}
{{2}}{{11}}
{{1}}{{2}{3}}
{{1}}{{2}}{{3}}
Cf.
A002846,
A005121,
A007716,
A050343,
A213427,
A269134,
A283877,
A306186,
A316980,
A317791,
A318564,
A318565,
A318566,
A318812.
A330475
Number of balanced reduced multisystems whose atoms constitute a strongly normal multiset of size n.
Original entry on oeis.org
1, 1, 2, 9, 85, 1143, 25270
Offset: 0
The a(0) = 1 through a(3) = 9 multisystems:
{} {1} {1,1} {1,1,1}
{1,2} {1,1,2}
{1,2,3}
{{1},{1,1}}
{{1},{1,2}}
{{1},{2,3}}
{{2},{1,1}}
{{2},{1,3}}
{{3},{1,2}}
The (weakly) normal version is
A330655.
The case where the atoms are {1..n} is
A005121.
The case where the atoms are all 1's is
A318813.
Multiset partitions of strongly normal multisets are
A035310.
-
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]]]];
strnorm[n_]:=Flatten[MapIndexed[Table[#2,{#1}]&,#]]&/@IntegerPartitions[n];
totm[m_]:=Prepend[Join@@Table[totm[p],{p,Select[mps[m],1
A330679
Number of balanced reduced multisystems whose atoms constitute an integer partition of n.
Original entry on oeis.org
1, 1, 2, 4, 12, 40, 180, 936, 5820, 41288, 331748, 2968688, 29307780, 316273976, 3704154568, 46788812168, 634037127612, 9174782661984, 141197140912208, 2302765704401360, 39671953757409256, 719926077632193848, 13726066030661998220, 274313334040504957368
Offset: 0
The a(0) = 1 through a(4) = 12 multisystems:
{} {1} {2} {3} {4}
{1,1} {1,2} {1,3}
{1,1,1} {2,2}
{{1},{1,1}} {1,1,2}
{1,1,1,1}
{{1},{1,2}}
{{2},{1,1}}
{{1},{1,1,1}}
{{1,1},{1,1}}
{{1},{1},{1,1}}
{{{1}},{{1},{1,1}}}
{{{1,1}},{{1},{1}}}
The case where the atoms are all 1's is
A318813 = a(n)/2.
The version where the atoms constitute a strongly normal multiset is
A330475.
The version where the atoms cover an initial interval is
A330655.
The maximum-depth version is
A330726.
Cf.
A000041,
A000111,
A000669,
A001970,
A002846,
A005121,
A141268,
A196545,
A213427,
A318812,
A320160,
A330474.
-
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]]]];
totm[m_]:=Prepend[Join@@Table[totm[p],{p,Select[mps[m],1
A330470
Number of non-isomorphic series/singleton-reduced rooted trees on a multiset of size n.
Original entry on oeis.org
1, 1, 2, 7, 39, 236, 1836, 16123, 162008, 1802945, 22012335, 291290460, 4144907830, 62986968311, 1016584428612, 17344929138791, 311618472138440, 5875109147135658, 115894178676866576, 2385755803919949337, 51133201045333895149, 1138659323863266945177, 26296042933904490636133
Offset: 0
Non-isomorphic representatives of the a(4) = 39 trees, with singleton leaves (x) replaced by just x:
(1111) (1112) (1122) (1123) (1234)
(1(111)) (1(112)) (1(122)) (1(123)) (1(234))
(11(11)) (11(12)) (11(22)) (11(23)) (12(34))
((11)(11)) (12(11)) (12(12)) (12(13)) ((12)(34))
(1(1(11))) (2(111)) ((11)(22)) (2(113)) (1(2(34)))
((11)(12)) (1(1(22))) (23(11))
(1(1(12))) ((12)(12)) ((11)(23))
(1(2(11))) (1(2(12))) (1(1(23)))
(2(1(11))) ((12)(13))
(1(2(13)))
(2(1(13)))
(2(3(11)))
The case with all atoms equal or all atoms different is
A000669.
Not requiring singleton-reduction gives
A330465.
Labeled versions are
A316651 (normal orderless) and
A330471 (strongly normal).
The case where the leaves are sets is
A330626.
Cf.
A000311,
A005121,
A005804,
A141268,
A213427,
A292504,
A292505,
A318812,
A318848,
A318849,
A330467,
A330469,
A330474,
A330624.
-
\\ See links in A339645 for combinatorial species functions.
cycleIndexSeries(n)={my(v=vector(n)); v[1]=sv(1); for(n=2, #v, v[n] = polcoef( sEulerT(x*Ser(v[1..n])), n )); x*Ser(v)}
InequivalentColoringsSeq(cycleIndexSeries(15)) \\ Andrew Howroyd, Dec 11 2020
A323790
Number of non-isomorphic weight-n sets of sets of sets.
Original entry on oeis.org
1, 1, 3, 9, 33, 113, 474, 1985
Offset: 0
Non-isomorphic representatives of the a(1) = 1 through a(3) = 9 sets of sets of sets:
{{1}} {{12}} {{123}}
{{1}{2}} {{1}{12}}
{{1}}{{2}} {{1}{23}}
{{1}}{{12}}
{{1}}{{23}}
{{1}{2}{3}}
{{1}}{{1}{2}}
{{1}}{{2}{3}}
{{1}}{{2}}{{3}}
Non-isomorphic representatives of the a(4) = 33 sets of sets of sets:
{{1234}} {{1}{123}} {{1}{2}{12}} {{1}}{{1}{12}}
{{1}{234}} {{12}{13}} {{1}}{{2}{12}}
{{12}{34}} {{1}}{{123}} {{12}}{{1}{2}}
{{1}}{{234}} {{1}{2}{13}} {{1}}{{2}}{{12}}
{{1}{2}{34}} {{12}}{{13}} {{1}}{{2}}{{1}{2}}
{{12}}{{34}} {{1}}{{1}{23}}
{{1}}{{2}{34}} {{1}}{{2}{13}}
{{1}{2}{3}{4}} {{12}}{{1}{3}}
{{12}}{{3}{4}} {{2}}{{1}{13}}
{{1}}{{2}}{{34}} {{1}}{{1}{2}{3}}
{{1}}{{2}{3}{4}} {{1}}{{2}}{{13}}
{{1}{2}}{{3}{4}} {{1}{2}}{{1}{3}}
{{1}}{{2}}{{3}{4}} {{1}}{{2}}{{1}{3}}
{{1}}{{2}}{{3}}{{4}}
Cf.
A004111,
A007716,
A049311,
A050326,
A050343,
A283877,
A306186,
A316980,
A318564,
A318565,
A318566,
A318812.
A330655
Number of balanced reduced multisystems of weight n whose atoms cover an initial interval of positive integers.
Original entry on oeis.org
1, 1, 2, 12, 138, 2652, 78106, 3256404, 182463296, 13219108288, 1202200963522, 134070195402644, 17989233145940910, 2858771262108762492, 530972857546678902490, 113965195745030648131036, 27991663753030583516229824, 7800669355870672032684666900, 2448021231611414334414904013956
Offset: 0
The a(0) = 1 through a(3) = 12 multisystems:
{} {1} {1,1} {1,1,1}
{1,2} {1,1,2}
{1,2,2}
{1,2,3}
{{1},{1,1}}
{{1},{1,2}}
{{1},{2,2}}
{{1},{2,3}}
{{2},{1,1}}
{{2},{1,2}}
{{2},{1,3}}
{{3},{1,2}}
The strongly normal case is
A330475.
The case where the atoms are all different is
A005121.
The case where the atoms are all equal is
A318813.
Multiset partitions of normal multisets are
A255906.
Series-reduced rooted trees with normal leaves are
A316651.
-
allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1]];
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]]]];
totm[m_]:=Prepend[Join@@Table[totm[p],{p,Select[mps[m],1
-
EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
R(n,k)={my(v=vector(n), u=vector(n)); v[1]=k; for(n=1, #v, u += v*sum(j=n, #v, (-1)^(j-n)*binomial(j-1,n-1)); v=EulerT(v)); u}
seq(n)={concat([1], sum(k=1, n, R(n, k)*sum(r=k, n, binomial(r, k)*(-1)^(r-k))))} \\ Andrew Howroyd, Dec 30 2019
A330467
Number of series-reduced rooted trees whose leaves are multisets whose multiset union is a strongly normal multiset of size n.
Original entry on oeis.org
1, 1, 4, 18, 154, 1614, 23733, 396190, 8066984, 183930948, 4811382339, 138718632336, 4451963556127, 155416836338920, 5920554613563841, 242873491536944706, 10725017764009207613, 505671090907469848248, 25415190929321149684700, 1354279188424092012064226
Offset: 0
The a(3) = 18 trees:
{1,1,1} {1,1,2} {1,2,3}
{{1},{1,1}} {{1},{1,2}} {{1},{2,3}}
{{1},{1},{1}} {{2},{1,1}} {{2},{1,3}}
{{1},{{1},{1}}} {{1},{1},{2}} {{3},{1,2}}
{{1},{{1},{2}}} {{1},{2},{3}}
{{2},{{1},{1}}} {{1},{{2},{3}}}
{{2},{{1},{3}}}
{{3},{{1},{2}}}
The singleton-reduced version is
A316652.
Not requiring weakly decreasing multiplicities gives
A330469.
The case where the leaves are sets is
A330625.
Cf.
A000311,
A000669,
A004114,
A005121,
A005804,
A141268,
A292504,
A292505,
A318812,
A318849,
A319312,
A330471,
A330475.
-
strnorm[n_]:=Flatten[MapIndexed[Table[#2,{#1}]&,#]]&/@IntegerPartitions[n];
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]]]];
multing[t_,n_]:=Array[(t+#-1)/#&,n,1,Times];
amemo[m_]:=amemo[m]=1+Sum[Product[multing[amemo[s[[1]]],Length[s]],{s,Split[c]}],{c,Select[mps[m],Length[#]>1&]}];
Table[Sum[amemo[m],{m,strnorm[n]}],{n,0,5}]
-
\\ See links in A339645 for combinatorial species functions.
cycleIndexSeries(n)={my(v=vector(n), p=sExp(x*sv(1) + O(x*x^n))); v[1]=sv(1); for(n=2, #v, v[n] = polcoef( sExp(x*Ser(v[1..n])), n ) + polcoef(p, n)); 1 + x*Ser(v)}
StronglyNormalLabelingsSeq(cycleIndexSeries(15)) \\ Andrew Howroyd, Dec 28 2020
Showing 1-10 of 30 results.
Comments