A318226
Number of inequivalent leaf-colorings of rooted trees with n nodes.
Original entry on oeis.org
1, 1, 3, 8, 25, 80, 286, 1070, 4280, 17946, 78907, 361248, 1718001, 8456130, 42980034, 225066289, 1212028798, 6701265897, 37986122037, 220477639797, 1308833637621, 7938564964369, 49151551028767, 310388888456536, 1997635594602629, 13093695854320203, 87349973125826943
Offset: 1
Inequivalent representatives of the a(5) = 25 leaf-colorings:
(1111) (11(1)) (1(11)) ((111)) ((1)(1)) (1((1))) ((1(1))) (((11))) ((((1))))
(1112) (11(2)) (1(12)) ((112)) ((1)(2)) (1((2))) ((1(2))) (((12)))
(1122) (12(1)) (1(22)) ((123))
(1123) (12(3)) (1(23))
(1234)
-
undats[m_]:=Union[DeleteCases[Cases[m,_?AtomQ,{0,Infinity},Heads->True],List]];
expnorm[m_]:=If[Length[undats[m]]==0,m,If[undats[m]!=Range[Max@@undats[m]],expnorm[m/.Rule@@@Table[{(undats[m])[[i]],i},{i,Length[undats[m]]}]],First[Sort[expnorm[m,1]]]]];expnorm[m_,aft_]:=If[Length[undats[m]]<=aft,{m},With[{mx=Table[Count[m,i,{0,Infinity},Heads->True],{i,Select[undats[m],#>=aft&]}]},Union@@(expnorm[#,aft+1]&/@Union[Table[MapAt[Sort,m/.{par+aft-1->aft,aft->par+aft-1},Position[m,[__]]],{par,First/@Position[mx,Max[mx]]}]])]];
urt[n_]:=urt[n]=If[n==1,{{}},Join@@Table[Union[Sort/@Tuples[urt/@c]],{c,IntegerPartitions[n-1]}]];
slip[e_,l_,q_]:=ReplacePart[e,Rule@@@Transpose[{Position[e,l],q}]];
allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1]];
Table[Length[Join@@Table[Union[expnorm/@Table[slip[tree,{},seq],{seq,Join@@Permutations/@allnorm[Count[tree,{},{0,Infinity},Heads->True]]}]],{tree,urt[n]}]],{n,7}]
-
\\ See links in A339645 for combinatorial species functions.
cycleIndexSeries(n)={my(Z=x*sv(1), p = Z + O(x^2)); for(n=2, n, p = Z-x + x*sEulerT(p)); p}
InequivalentColoringsSeq(cycleIndexSeries(15)) \\ Andrew Howroyd, Dec 13 2020
A318228
Number of inequivalent leaf-colorings of planted achiral trees with n nodes.
Original entry on oeis.org
1, 1, 3, 6, 13, 20, 43, 58, 115, 171, 323, 379, 1034, 1135, 2321, 4327, 8915, 9212, 33939, 34429, 128414, 234017, 417721, 418976, 2931624, 5096391, 11770830, 20357876, 64853630, 64858195
Offset: 1
Inequivalent representatives of the a(5) = 13 leaf-colorings:
(1111) ((111)) ((1)(1)) (((11))) ((((1))))
(1112) ((112)) ((1)(2)) (((12)))
(1122) ((123))
(1123)
(1234)
-
\\ See links in A339645 for combinatorial species functions.
G(v)={my(t=2, p=sv(1)); for(i=1, #v, my(d=v[i]); if(d>1, p=sApplyCI(symGroupCycleIndex(d), d, p, t)); t=t*d+1); p}
cycleIndex(n)={my(recurse(r,v)=if(r==1, G(v), sumdiv(r-1, d, self()((r-1)/d, concat(d,v))))); recurse(n,[])}
a(n)={StructsByCycleIndex(n, cycleIndex(n), n)} \\ Andrew Howroyd, Dec 13 2020
A318229
Number of inequivalent leaf-colorings of transitive rooted trees with n nodes.
Original entry on oeis.org
1, 1, 2, 5, 13, 34, 92, 255
Offset: 1
Inequivalent representatives of the a(5) = 13 leaf-colorings:
(1111) (1(11)) (11(1))
(1112) (1(12)) (11(2))
(1122) (1(22)) (12(1))
(1123) (1(23)) (12(3))
(1234)
A318234
Number of inequivalent leaf-colorings of totally transitive rooted trees with n nodes.
Original entry on oeis.org
1, 1, 2, 5, 13, 34, 87
Offset: 1
Inequivalent representatives of the a(6) = 34 leaf-colorings:
(11(11)) (11111) (111(1)) (1(111)) (1(1)(1))
(11(12)) (11112) (111(2)) (1(112)) (1(1)(2))
(11(22)) (11122) (112(1)) (1(122)) (1(2)(2))
(11(23)) (11123) (112(2)) (1(123)) (1(2)(3))
(12(11)) (11223) (112(3)) (1(222))
(12(12)) (11234) (123(1)) (1(223))
(12(13)) (12345) (123(4)) (1(234))
(12(33))
(12(34))
A324739
Number of subsets of {2...n} containing no element whose prime indices all belong to the subset.
Original entry on oeis.org
1, 2, 3, 6, 10, 20, 30, 60, 96, 192, 312, 624, 936, 1872, 3744, 7488, 12480, 24960, 37440, 74880, 142848, 285696, 456192, 912384, 1548288, 3096576, 5308416, 10616832, 15925248, 31850496, 51978240, 103956480, 200835072, 401670144, 771489792, 1542979584, 2314469376
Offset: 1
The a(1) = 1 through a(6) = 20 subsets:
{} {} {} {} {} {}
{2} {2} {2} {2} {2}
{3} {3} {3} {3}
{4} {4} {4}
{2,4} {5} {5}
{3,4} {2,4} {6}
{2,5} {2,4}
{3,4} {2,5}
{4,5} {2,6}
{2,4,5} {3,4}
{3,6}
{4,5}
{4,6}
{5,6}
{2,4,5}
{2,4,6}
{2,5,6}
{3,4,6}
{4,5,6}
{2,4,5,6}
The maximal case is
A324762. The case of subsets of {1...n} is
A324738. The strict integer partition version is
A324750. The integer partition version is
A324755. The Heinz number version is
A324760. An infinite version is
A324694.
Cf.
A000720,
A001221,
A001462,
A007097,
A084422,
A085945,
A112798,
A276625,
A279861,
A290689,
A290822,
A304360,
A306844.
-
Table[Length[Select[Subsets[Range[2,n]],!MemberQ[#,k_/;SubsetQ[#,PrimePi/@First/@FactorInteger[k]]]&]],{n,10}]
-
pset(n)={my(b=0,f=factor(n)[,1]); sum(i=1, #f, 1<<(primepi(f[i])))}
a(n)={my(p=vector(n,k,pset(k)), d=0); for(i=1, #p, d=bitor(d, p[i]));
((k,b)->if(k>#p, 1, my(t=self()(k+1,b)); if(bitnegimply(p[k], b), t+=if(bittest(d,k), self()(k+1, b+(1<Andrew Howroyd, Aug 16 2019
A124346
Number of rooted identity trees on n nodes with thinning limbs.
Original entry on oeis.org
1, 1, 1, 2, 2, 4, 6, 11, 17, 32, 56, 102, 184, 340, 624, 1161, 2156, 4036, 7562, 14234, 26828, 50747, 96125, 182545, 347187, 661618, 1262583, 2413275, 4618571, 8850905, 16981142, 32616900, 62713951, 120703497, 232527392, 448344798, 865182999, 1670884073
Offset: 1
The a(7) = 6 trees are ((((((o)))))), (o((((o))))), (o(o((o)))), ((o)(((o)))), ((o)(o(o))), (o(o)((o))). - _Gus Wiseman_, Jan 25 2018
-
idthinQ[t_]:=And@@Cases[t,b_List:>UnsameQ@@b&&Length[b]>=Max@@Length/@b,{0,Infinity}];
itrut[n_]:=itrut[n]=If[n===1,{{}},Select[Join@@Function[c,Union[Sort/@Tuples[itrut/@c]]]/@IntegerPartitions[n-1],idthinQ]];
Table[Length[itrut[n]],{n,25}] (* Gus Wiseman, Jan 25 2018 *)
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
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
A298536
Matula-Goebel numbers of rooted trees such that every branch of the root has a different number of leaves.
Original entry on oeis.org
1, 2, 3, 5, 7, 11, 13, 14, 17, 19, 21, 23, 26, 29, 31, 34, 35, 37, 38, 39, 41, 43, 46, 47, 51, 53, 57, 58, 59, 61, 65, 67, 69, 71, 73, 74, 77, 79, 82, 83, 85, 86, 87, 89, 94, 95, 97, 101, 103, 106, 107, 109, 111, 113, 115, 118, 122, 123, 127, 129, 131, 133
Offset: 1
Sequence of trees begins:
1 o
2 (o)
3 ((o))
5 (((o)))
7 ((oo))
11 ((((o))))
13 ((o(o)))
14 (o(oo))
17 (((oo)))
19 ((ooo))
21 ((o)(oo))
23 (((o)(o)))
26 (o(o(o)))
29 ((o((o))))
31 (((((o)))))
34 (o((oo)))
35 (((o))(oo))
37 ((oo(o)))
38 (o(ooo))
39 ((o)(o(o)))
41 (((o(o))))
43 ((o(oo)))
46 (o((o)(o)))
47 (((o)((o))))
Cf.
A000081,
A007097,
A061775,
A111299,
A214577,
A276625,
A290689,
A290760,
A291442,
A298534,
A298535.
-
nn=2000;
primeMS[n_]:=If[n===1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
leafcount[n_]:=If[n===1,1,With[{m=primeMS[n]},If[Length[m]===1,leafcount[First[m]],Total[leafcount/@m]]]];
Select[Range[nn],UnsameQ@@leafcount/@primeMS[#]&]
A324971
Number of rooted identity trees with n vertices whose non-leaf terminal subtrees are not all different.
Original entry on oeis.org
0, 0, 0, 0, 0, 1, 4, 12, 31, 79, 192, 459, 1082, 2537, 5922, 13816, 32222, 75254, 176034, 412667, 969531, 2283278
Offset: 1
The a(6) = 1 through a(8) = 12 trees:
((o)((o))) ((o)(o(o))) (o(o)(o(o)))
(o(o)((o))) (((o))(o(o)))
(((o)((o)))) (((o)(o(o))))
((o)(((o)))) ((o)((o(o))))
((o)(o((o))))
((o(o)((o))))
(o((o)((o))))
(o(o)(((o))))
((((o)((o)))))
(((o))(((o))))
(((o)(((o)))))
((o)((((o)))))
The Matula-Goebel numbers of these trees are given by
A324970.
Cf.
A000081,
A004111,
A290689,
A317713,
A324850,
A324922,
A324923,
A324924,
A324931,
A324935,
A324936,
A324979.
-
rits[n_]:=Join@@Table[Select[Union[Sort/@Tuples[rits/@ptn]],UnsameQ@@#&],{ptn,IntegerPartitions[n-1]}];
Table[Length[Select[rits[n],!UnsameQ@@Cases[#,{},{0,Infinity}]&]],{n,10}]
A325708
Numbers n whose prime indices cover an initial interval of positive integers and include all prime exponents of n.
Original entry on oeis.org
1, 2, 6, 12, 18, 30, 36, 60, 90, 120, 150, 180, 210, 270, 300, 360, 420, 450, 540, 600, 630, 750, 840, 900, 1050, 1080, 1260, 1350, 1470, 1500, 1680, 1800, 1890, 2100, 2250, 2310, 2520, 2700, 2940, 3000, 3150, 3780, 4200, 4410, 4500, 4620, 5040, 5250, 5400
Offset: 1
The sequence of terms together with their prime indices begins:
1: {}
2: {1}
6: {1,2}
12: {1,1,2}
18: {1,2,2}
30: {1,2,3}
36: {1,1,2,2}
60: {1,1,2,3}
90: {1,2,2,3}
120: {1,1,1,2,3}
150: {1,2,3,3}
180: {1,1,2,2,3}
210: {1,2,3,4}
270: {1,2,2,2,3}
300: {1,1,2,3,3}
360: {1,1,1,2,2,3}
420: {1,1,2,3,4}
450: {1,2,2,3,3}
540: {1,1,2,2,2,3}
600: {1,1,1,2,3,3}
Comments