Displaying 1-10 of 13 results found.
Let f(n) = number of ways to factor n = A001055(n); a(n) = sum of f(k) over all terms k in A025487 that have n factors.
+10
21
1, 4, 12, 47, 170, 750, 3255, 16010, 81199, 448156, 2579626, 15913058, 102488024, 698976419, 4976098729, 37195337408, 289517846210, 2352125666883, 19841666995265, 173888579505200, 1577888354510786, 14820132616197925, 143746389756336173, 1438846957477988926
COMMENTS
Ways of partitioning an n-multiset with multiplicities some partition of n.
Number of multiset partitions of strongly normal multisets of size n, where a finite multiset is strongly normal if it covers an initial interval of positive integers with weakly decreasing multiplicities. The (weakly) normal version is A255906. - Gus Wiseman, Dec 31 2019
EXAMPLE
a(3) = 12 because there are 3 terms in A025487 with 3 factors, namely 8, 12, 30; and f(8)=3, f(12)=4, f(30)=5 and 3+4+5 = 12. The a(1) = 1 through a(3) = 12 multiset partitions of strongly normal multisets:
{{1}} {{1,1}} {{1,1,1}}
{{1,2}} {{1,1,2}}
{{1},{1}} {{1,2,3}}
{{1},{2}} {{1},{1,1}}
{{1},{1,2}}
{{1},{2,3}}
{{2},{1,1}}
{{2},{1,3}}
{{3},{1,2}}
{{1},{1},{1}}
{{1},{1},{2}}
{{1},{2},{3}}
(End)
MAPLE
with(numtheory):
g:= proc(n, k) option remember;
`if`(n>k, 0, 1) +`if`(isprime(n), 0,
add(`if`(d>k, 0, g(n/d, d)), d=divisors(n) minus {1, n}))
end:
b:= proc(n, i, l)
`if`(n=0, g(mul(ithprime(t)^l[t], t=1..nops(l))$2),
`if`(i<1, 0, add(b(n-i*j, i-1, [l[], i$j]), j=0..n/i)))
end:
a:= n-> b(n$2, []):
MATHEMATICA
g[n_, k_] := g[n, k] = If[n > k, 0, 1] + If[PrimeQ[n], 0, Sum[If[d > k, 0, g[n/d, d]], {d, Divisors[n] ~Complement~ {1, n}}]]; b[n_, i_, l_] := If[n == 0, g[p = Product[Prime[t]^l[[t]], {t, 1, Length[l]}], p], If[i < 1, 0, Sum[b[n - i*j, i-1, Join[l, Array[i&, j]]], {j, 0, n/i}]]]; a[n_] := b[n, n, {}]; Table[Print[an = a[n]]; an, {n, 1, 13}] (* Jean-François Alcover, Dec 12 2013, after Alois P. Heinz *)
PROG
(Python)
from sympy.core.cache import cacheit
from sympy import divisors, isprime, prime
from operator import mul
@cacheit
def g(n, k):
return (0 if n > k else 1) + (0 if isprime(n) else sum(g(n//d, d) for d in divisors(n)[1:-1] if d <= k))
@cacheit
def b(n, i, l):
if n==0:
p = reduce(mul, (prime(t + 1)**l[t] for t in range(len(l))))
return g(p, p)
else:
return 0 if i<1 else sum([b(n - i*j, i - 1, l + [i]*j) for j in range(n//i + 1)])
def a(n):
return b(n, n, [])
for n in range(1, 11): print(a(n)) # Indranil Ghosh, Aug 19 2017, after Maple code (PARI)
EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
D(p, n)={my(v=vector(n)); for(i=1, #p, v[p[i]]++); my(u=EulerT(v)); Vec(1/prod(k=1, n, 1 - u[k]*x^k + O(x*x^n))-1, -n)/prod(i=1, #v, i^v[i]*v[i]!)}
seq(n)={my(s=0); forpart(p=n, s+=D(p, n)); s} \\ Andrew Howroyd, Dec 30 2020
CROSSREFS
Sequence A035341 counts the ordered cases. Tables A093936 and A095705 distribute the values; e.g. 81199 = 30 + 536 + 3036 + 6181 + 10726 + 11913 + 14548 + 13082 + 21147. The case with empty intersection is A317755. The case of strict parts is A330783. Multiset partitions of integer partitions are A001970. Unlabeled multiset partitions are A007716.
Number of non-isomorphic balanced reduced multisystems of weight n.
+10
16
COMMENTS
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.
EXAMPLE
Non-isomorphic representatives of the a(3) = 7 multisystems:
{1,1,1}
{1,1,2}
{1,2,3}
{{1},{1,1}}
{{1},{1,2}}
{{1},{2,3}}
{{2},{1,1}}
Non-isomorphic representatives of the a(4) = 48 multisystems:
{1,1,1,1} {{1},{1,1,1}} {{{1}},{{1},{1,1}}}
{1,1,1,2} {{1,1},{1,1}} {{{1,1}},{{1},{1}}}
{1,1,2,2} {{1},{1,1,2}} {{{1}},{{1},{1,2}}}
{1,1,2,3} {{1,1},{1,2}} {{{1,1}},{{1},{2}}}
{1,2,3,4} {{1},{1,2,2}} {{{1}},{{1},{2,2}}}
{{1,1},{2,2}} {{{1,1}},{{2},{2}}}
{{1},{1,2,3}} {{{1}},{{1},{2,3}}}
{{1,1},{2,3}} {{{1,1}},{{2},{3}}}
{{1,2},{1,2}} {{{1}},{{2},{1,1}}}
{{1,2},{1,3}} {{{1,2}},{{1},{1}}}
{{1},{2,3,4}} {{{1}},{{2},{1,2}}}
{{1,2},{3,4}} {{{1,2}},{{1},{2}}}
{{2},{1,1,1}} {{{1}},{{2},{1,3}}}
{{2},{1,1,3}} {{{1,2}},{{1},{3}}}
{{1},{1},{1,1}} {{{1}},{{2},{3,4}}}
{{1},{1},{1,2}} {{{1,2}},{{3},{4}}}
{{1},{1},{2,2}} {{{2}},{{1},{1,1}}}
{{1},{1},{2,3}} {{{2}},{{1},{1,3}}}
{{1},{2},{1,1}} {{{2}},{{3},{1,1}}}
{{1},{2},{1,2}} {{{2,3}},{{1},{1}}}
{{1},{2},{1,3}}
{{1},{2},{3,4}}
{{2},{3},{1,1}}
CROSSREFS
The case where the atoms are all different is A318813. The case where the atoms are all equal is (also) A318813. The labeled case of set partitions is A005121. The labeled case of integer partitions is A330679. The case of maximal depth is A330663. The version where leaves are sets (as opposed to multisets) is A330668. Cf. A000311, A000669, A001678, A002846, A004114, A007716, A048816, A213427, A306186, A320154, A320160, A330470, A330666.
Number of balanced reduced multisystems whose atoms constitute an integer partition of n.
+10
13
1, 1, 2, 4, 12, 40, 180, 936, 5820, 41288, 331748, 2968688, 29307780, 316273976, 3704154568, 46788812168, 634037127612, 9174782661984, 141197140912208, 2302765704401360, 39671953757409256, 719926077632193848, 13726066030661998220, 274313334040504957368
COMMENTS
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.
EXAMPLE
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}}}
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]]]];
totm[m_]:=Prepend[Join@@Table[totm[p], {p, Select[mps[m], 1<Length[#]<Length[m]&]}], m];
Table[Sum[Length[totm[m]], {m, IntegerPartitions[n]}], {n, 0, 5}]
CROSSREFS
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.
Number of balanced reduced multisystems of weight n whose atoms cover an initial interval of positive integers.
+10
11
1, 1, 2, 12, 138, 2652, 78106, 3256404, 182463296, 13219108288, 1202200963522, 134070195402644, 17989233145940910, 2858771262108762492, 530972857546678902490, 113965195745030648131036, 27991663753030583516229824, 7800669355870672032684666900, 2448021231611414334414904013956
COMMENTS
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.
EXAMPLE
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}}
MATHEMATICA
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<Length[#]<Length[m]&]}], m];
Table[Sum[Length[totm[m]], {m, allnorm[n]}], {n, 0, 5}]
PROG
(PARI)
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
CROSSREFS
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.
Number of series-reduced rooted trees whose leaves are multisets whose multiset union is a strongly normal multiset of size n.
+10
10
1, 1, 4, 18, 154, 1614, 23733, 396190, 8066984, 183930948, 4811382339, 138718632336, 4451963556127, 155416836338920, 5920554613563841, 242873491536944706, 10725017764009207613, 505671090907469848248, 25415190929321149684700, 1354279188424092012064226
COMMENTS
A multiset is strongly normal if it covers an initial interval of positive integers with weakly decreasing multiplicities.
Also the number of different colorings of phylogenetic trees with n labels using strongly normal multisets of colors. A phylogenetic tree is a series-reduced rooted tree whose leaves are (usually disjoint) sets.
EXAMPLE
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}}}
MATHEMATICA
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}]
PROG
(PARI) \\ 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
CROSSREFS
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.
Number of balanced reduced multisystems of maximum depth whose atoms constitute a strongly normal multiset of size n.
+10
10
1, 1, 2, 6, 43, 440, 7158, 151414
COMMENTS
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 finite multiset is strongly normal if it covers an initial interval of positive integers with weakly decreasing multiplicities.
EXAMPLE
The a(2) = 2 and a(3) = 6 multisystems:
{1,1} {{1},{1,1}}
{1,2} {{1},{1,2}}
{{1},{2,3}}
{{2},{1,1}}
{{2},{1,3}}
{{3},{1,2}}
The a(4) = 43 multisystems (commas and outer brackets elided):
{{1}}{{1}{11}} {{1}}{{1}{12}} {{1}}{{1}{22}} {{1}}{{1}{23}} {{1}}{{2}{34}}
{{11}}{{1}{1}} {{11}}{{1}{2}} {{11}}{{2}{2}} {{11}}{{2}{3}} {{12}}{{3}{4}}
{{1}}{{2}{11}} {{1}}{{2}{12}} {{1}}{{2}{13}} {{1}}{{3}{24}}
{{12}}{{1}{1}} {{12}}{{1}{2}} {{12}}{{1}{3}} {{13}}{{2}{4}}
{{2}}{{1}{11}} {{2}}{{1}{12}} {{1}}{{3}{12}} {{1}}{{4}{23}}
{{2}}{{2}{11}} {{13}}{{1}{2}} {{14}}{{2}{3}}
{{22}}{{1}{1}} {{2}}{{1}{13}} {{2}}{{1}{34}}
{{2}}{{3}{11}} {{2}}{{3}{14}}
{{23}}{{1}{1}} {{23}}{{1}{4}}
{{3}}{{1}{12}} {{2}}{{4}{13}}
{{3}}{{2}{11}} {{24}}{{1}{3}}
{{3}}{{1}{24}}
{{3}}{{2}{14}}
{{3}}{{4}{12}}
{{34}}{{1}{2}}
{{4}}{{1}{23}}
{{4}}{{2}{13}}
{{4}}{{3}{12}}
MATHEMATICA
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]]]];
totm[m_]:=Prepend[Join@@Table[totm[p], {p, Select[mps[m], 1<Length[#]<Length[m]&]}], m];
Table[Sum[Length[Select[totm[m], Depth[#]==If[Length[m]<=1, 2, Length[m]]&]], {m, strnorm[n]}], {n, 0, 5}]
CROSSREFS
The case with all atoms equal is A000111. The case with all atoms different is A006472. The version allowing all depths is A330475. The version where the atoms are the prime indices of n is A330665. The (weakly) normal version is A330676. The version where the degrees are the prime indices of n is A330728. Multiset partitions of strongly normal multisets are A035310. Series-reduced rooted trees with strongly normal leaves are A316652. Cf. A000311, A000669, A001055, A001678, A005121, A005804, A316651, A318812, A330467, A330474, A330625, A330628, A330664, A330677, A330679.
Number of balanced reduced multisystems of maximal depth whose atoms are the prime indices of n.
+10
9
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 1, 1, 1, 5, 1, 1, 1, 2, 1, 3, 1, 5, 1, 1, 1, 7, 1, 1, 1, 5, 1, 3, 1, 2, 2, 1, 1, 16, 1, 2, 1, 2, 1, 5, 1, 5, 1, 1, 1, 11, 1, 1, 2, 16, 1, 3, 1, 2, 1, 3, 1, 27, 1, 1, 2, 2, 1, 3, 1, 16, 2, 1, 1, 11, 1
COMMENTS
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.
FORMULA
a(product of n distinct primes) = A006472(n).
EXAMPLE
The a(n) multisystems for n = 2, 6, 12, 24, 48:
{1} {1,2} {{1},{1,2}} {{{1}},{{1},{1,2}}} {{{{1}}},{{{1}},{{1},{1,2}}}}
{{2},{1,1}} {{{1,1}},{{1},{2}}} {{{{1}}},{{{1,1}},{{1},{2}}}}
{{{1}},{{2},{1,1}}} {{{{1},{1}}},{{{1}},{{1,2}}}}
{{{1,2}},{{1},{1}}} {{{{1},{1,1}}},{{{1}},{{2}}}}
{{{2}},{{1},{1,1}}} {{{{1,1}}},{{{1}},{{1},{2}}}}
{{{{1}}},{{{1}},{{2},{1,1}}}}
{{{{1}}},{{{1,2}},{{1},{1}}}}
{{{{1},{1}}},{{{2}},{{1,1}}}}
{{{{1},{1,2}}},{{{1}},{{1}}}}
{{{{1,1}}},{{{2}},{{1},{1}}}}
{{{{1}}},{{{2}},{{1},{1,1}}}}
{{{{1},{2}}},{{{1}},{{1,1}}}}
{{{{1,2}}},{{{1}},{{1},{1}}}}
{{{{2}}},{{{1}},{{1},{1,1}}}}
{{{{2}}},{{{1,1}},{{1},{1}}}}
{{{{2},{1,1}}},{{{1}},{{1}}}}
MATHEMATICA
primeMS[n_]:=If[n==1, {}, Flatten[Cases[FactorInteger[n], {p_, k_}:>Table[PrimePi[p], {k}]]]];
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<Length[#]<Length[m]&]}], m];
Table[Length[Select[totm[primeMS[n]], Length[#]<=1||Depth[#]==PrimeOmega[n]&]], {n, 100}]
CROSSREFS
The last nonzero term in row n of A330667 is a(n). The non-maximal version is A318812. Other labeled versions are A330675 (strongly normal) and A330676 (normal). Cf. A001055, A005121, A005804, A050336, A213427, A292505, A317144, A318849, A320160, A330474, A330475, A330679.
Number of series/singleton-reduced rooted trees on strongly normal multisets of size n.
+10
8
1, 1, 2, 9, 69, 623, 7803, 110476, 1907428
COMMENTS
A multiset is strongly normal if it covers an initial interval of positive integers with weakly decreasing multiplicities.
A series/singleton-reduced rooted tree on a multiset m is either the multiset m itself or a sequence of series/singleton-reduced rooted trees, one on each part of a multiset partition of m that is neither minimal (all singletons) nor maximal (only one part). This is a multiset generalization of singleton-reduced phylogenetic trees ( A000311).
EXAMPLE
The a(0) = 1 through a(3) = 9 trees:
() (1) (11) (111)
(12) (112)
(123)
((1)(11))
((1)(12))
((1)(23))
((2)(11))
((2)(13))
((3)(12))
The a(4) = 69 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)) (13(24))
(1(1(11))) (2(111)) (2(112)) (13(12)) (14(23))
((11)(12)) (22(11)) (2(113)) (2(134))
(1(1(12))) ((11)(22)) (23(11)) (23(14))
(1(2(11))) (1(1(22))) (3(112)) (24(13))
(2(1(11))) ((12)(12)) ((11)(23)) (3(124))
(1(2(12))) (1(1(23))) (34(12))
(2(1(12))) ((12)(13)) (4(123))
(2(2(11))) (1(2(13))) ((12)(34))
(1(3(12))) (1(2(34)))
(2(1(13))) ((13)(24))
(2(3(11))) (1(3(24)))
(3(1(12))) ((14)(23))
(3(2(11))) (1(4(23)))
(2(1(34)))
(2(3(14)))
(2(4(13)))
(3(1(24)))
(3(2(14)))
(3(4(12)))
(4(1(23)))
(4(2(13)))
(4(3(12)))
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]]]];
strnorm[n_]:=Flatten[MapIndexed[Table[#2, {#1}]&, #]]&/@IntegerPartitions[n];
mtot[m_]:=Prepend[Join@@Table[Tuples[mtot/@p], {p, Select[mps[m], Length[#]>1&&Length[#]<Length[m]&]}], m];
Table[Sum[Length[mtot[s]], {s, strnorm[n]}], {n, 0, 5}]
CROSSREFS
The case with all atoms different is A000311. The case with all atoms equal is A196545. The case where the leaves are sets is A330628. The version for just normal (not strongly normal) is A330654. Cf. A000669, A004114, A005121, A005804, A281118, A318812, A318848, A319312, A330465, A330467, A330475.
Number of series-reduced rooted trees whose leaves are sets (not necessarily disjoint) with multiset union a strongly normal multiset of size n.
+10
8
1, 1, 3, 14, 123, 1330, 19694
COMMENTS
A rooted tree is series-reduced if it has no unary branchings, so every non-leaf node covers at least two other nodes.
A finite multiset is strongly normal if it covers an initial interval of positive integers with weakly decreasing multiplicities.
EXAMPLE
The a(1) = 1 through a(3) = 14 trees:
{1} {1,2} {1,2,3}
{{1},{1}} {{1},{1,2}}
{{1},{2}} {{1},{2,3}}
{{2},{1,3}}
{{3},{1,2}}
{{1},{1},{1}}
{{1},{1},{2}}
{{1},{2},{3}}
{{1},{{1},{1}}}
{{1},{{1},{2}}}
{{1},{{2},{3}}}
{{2},{{1},{1}}}
{{2},{{1},{3}}}
{{3},{{1},{2}}}
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]]]];
strnorm[n_]:=Flatten[MapIndexed[Table[#2, {#1}]&, #]]&/@IntegerPartitions[n];
srtrees[m_]:=Prepend[Join@@Table[Tuples[srtrees/@p], {p, Select[mps[m], Length[#1]>1&]}], m];
Table[Sum[Length[Select[srtrees[s], FreeQ[#, {___, x_Integer, x_Integer, ___}]&]], {s, strnorm[n]}], {n, 0, 5}]
CROSSREFS
The generalization where the leaves are multisets is A330467. The singleton-reduced case is A330628. The case with all atoms distinct is A005804. The case with all atoms equal is A196545. The case where all leaves are singletons is A330471.
Number of non-isomorphic balanced reduced multisystems whose degrees (atom multiplicities) are the weakly decreasing prime indices of n.
+10
5
1, 1, 1, 1, 2, 3, 6, 2, 10, 11, 20, 15, 90, 51, 80, 6, 468, 93, 2910, 80, 521, 277, 20644, 80, 334, 1761, 393, 521, 165874, 1374
COMMENTS
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}.
EXAMPLE
Non-isomorphic representatives of the a(2) = 1 through a(9) = 10 multisystems (commas and outer brackets elided):
1 11 12 111 112 1111 123 1122
{1}{11} {1}{12} {1}{111} {1}{23} {1}{122}
{2}{11} {11}{11} {11}{22}
{1}{1}{11} {12}{12}
{{1}}{{1}{11}} {1}{1}{22}
{{11}}{{1}{1}} {1}{2}{12}
{{1}}{{1}{22}}
{{11}}{{2}{2}}
{{1}}{{2}{12}}
{{12}}{{1}{2}}
Non-isomorphic representatives of the a(12) = 15 multisystems:
{1,1,2,3}
{{1},{1,2,3}}
{{1,1},{2,3}}
{{1,2},{1,3}}
{{2},{1,1,3}}
{{1},{1},{2,3}}
{{1},{2},{1,3}}
{{2},{3},{1,1}}
{{{1}},{{1},{2,3}}}
{{{1,1}},{{2},{3}}}
{{{1}},{{2},{1,3}}}
{{{1,2}},{{1},{3}}}
{{{2}},{{1},{1,3}}}
{{{2}},{{3},{1,1}}}
{{{2,3}},{{1},{1}}}
CROSSREFS
The maximum-depth version is A330664. Unlabeled balanced reduced multisystems by weight are A330474. The case of constant or strict atoms is A318813. Cf. A000669, A005121, A007716, A048816, A141268, A306186, A317791, A318812, A318849, A330470, A330475, A330655, A330728.
Search completed in 0.020 seconds
|