A330471 -id:A330471 - cp's OEIS frontend

A035310 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.

1, 4, 12, 47, 170, 750, 3255, 16010, 81199, 448156, 2579626, 15913058, 102488024, 698976419, 4976098729, 37195337408, 289517846210, 2352125666883, 19841666995265, 173888579505200, 1577888354510786, 14820132616197925, 143746389756336173, 1438846957477988926

Offset: 1

Alford Arnold

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

			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.
From _Gus Wiseman_, Dec 31 2019: (Start)
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)

Andrew Howroyd, Table of n, a(n) for n = 1..50

Cf. A025487, A000041, A000110, A035098, A080688.
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.
Cf. A035341, A093936, A095705.
Row sums of A317449.
The uniform case is A317584.
The case with empty intersection is A317755.
The strict case is A317775.
The constant case is A047968.
The set-system case is A318402.
The case of strict parts is A330783.
Multiset partitions of integer partitions are A001970.
Unlabeled multiset partitions are A007716.
Cf. A001055, A255906, A269134, A316652, A317654, A318284, A330467, A330471, A330475, A330675.

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, []):
seq(a(n), n=1..10);  # Alois P. Heinz, May 26 2013

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 *)

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

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

More terms from Erich Friedman.
81199 from Alford Arnold, Mar 04 2008
a(10) from Alford Arnold, Mar 31 2008
a(10) corrected by Alford Arnold, Aug 07 2008
a(11)-a(13) from Alois P. Heinz, May 26 2013
a(14) from Alois P. Heinz, Sep 27 2014
a(15) from Alois P. Heinz, Jan 10 2015
Terms a(16) and beyond from Andrew Howroyd, Dec 30 2020

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

Gus Wiseman, Dec 21 2019

nonn

Also inequivalent leaf-colorings of phylogenetic rooted trees with n labels. A phylogenetic rooted tree is a series-reduced rooted tree whose leaves are (usually disjoint) sets.

			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.
Labeled versions are A330467 (strongly normal) and A330469 (normal).
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

Terms a(7) and beyond from Andrew Howroyd, Dec 13 2020

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

Gus Wiseman, Dec 27 2019

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.

			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 maximum-depth case is A330675.
The case where the atoms are {1..n} is A005121.
The case where the atoms are all 1's is A318813.
The tree version is A330471.
Multiset partitions of strongly normal multisets are A035310.
Cf. A000311, A000669, A001678, A316652, A318812, A330467, A330474, A330628, A330663, A330679.

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

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

Gus Wiseman, Dec 22 2019

nonn

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).

			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.
Row sums of A339645.
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

Terms a(7) and beyond from Andrew Howroyd, Dec 11 2020

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

Gus Wiseman, Dec 22 2019

nonn

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.

			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.
The unlabeled version is A330465.
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

Terms a(10) and beyond from Andrew Howroyd, Dec 28 2020

A330625 Number of series-reduced rooted trees whose leaves are sets (not necessarily disjoint) with multiset union a strongly normal multiset of size n.

Original entry on oeis.org

1, 1, 3, 14, 123, 1330, 19694

Offset: 0

Gus Wiseman, Dec 25 2019

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.

			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}}}

The generalization where the leaves are multisets is A330467.
The singleton-reduced case is A330628.
The unlabeled version is A330624.
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.
Cf. A000669, A004111, A141268, A300660, A316652, A330469, A330475, A330626, A330668, A330675.

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}]

A330628 Number of series/singleton-reduced rooted trees on strongly normal multisets of size n whose leaves are sets (not necessarily disjoint).

Original entry on oeis.org

1, 1, 1, 5, 42, 423, 5458, 80926

Offset: 0

Gus Wiseman, Dec 26 2019

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).

A finite multiset is strongly normal if it covers an initial interval of positive integers with weakly decreasing multiplicities.

			The a(4) = 42 trees:
  {{1}{1}{12}}    {{12}{12}}      {{1}{123}}      {1234}
  {{1}{{1}{12}}}  {{1}{2}{12}}    {{12}{13}}      {{1}{234}}
                  {{1}{{2}{12}}}  {{1}{1}{23}}    {{12}{34}}
                  {{2}{{1}{12}}}  {{1}{2}{13}}    {{13}{24}}
                                  {{1}{3}{12}}    {{14}{23}}
                                  {{1}{{1}{23}}}  {{2}{134}}
                                  {{1}{{2}{13}}}  {{3}{124}}
                                  {{1}{{3}{12}}}  {{4}{123}}
                                  {{2}{{1}{13}}}  {{1}{2}{34}}
                                  {{3}{{1}{12}}}  {{1}{3}{24}}
                                                  {{1}{4}{23}}
                                                  {{2}{3}{14}}
                                                  {{2}{4}{13}}
                                                  {{3}{4}{12}}
                                                  {{1}{{2}{34}}}
                                                  {{1}{{3}{24}}}
                                                  {{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}}}

The generalization where leaves are multisets is A330471.
The non-singleton-reduced version is A330625.
The unlabeled version is A330626.
The case with all atoms distinct is A000311.
Strongly normal multiset partitions are A035310.
Cf. A000669, A004111, A004114, A005804, A196545, A281118, A330465, A330467, A330624, A330654, A330668.

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];
ssrtrees[m_]:=Prepend[Join@@Table[Tuples[ssrtrees/@p],{p,Select[mps[m],Length[m]>Length[#1]>1&]}],m];
Table[Sum[Length[Select[ssrtrees[s],FreeQ[#,{_,x_Integer,x_Integer,_}]&]],{s,strnorm[n]}],{n,0,5}]

A330654 Number of series/singleton-reduced rooted trees on normal multisets of size n.

Original entry on oeis.org

1, 1, 2, 12, 112, 1444, 24099, 492434, 11913985

Offset: 0

Gus Wiseman, Dec 26 2019

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).
A finite multiset is normal if it covers an initial interval of positive integers.
First differs from A316651 at a(6) = 24099, A316651(6) = 24086. For example, ((1(12))(2(11))) and ((2(11))(1(12))) are considered identical for A316651 (series-reduced rooted trees), but {{{1},{1,2}},{{2},{1,1}}} and {{{2},{1,1}},{{1},{1,2}}} are different series/singleton-reduced rooted trees.

			The a(0) = 1 through a(3) = 12 trees:
  {}  {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 orderless version is A316651.
The strongly normal case is A330471.
The unlabeled version is A330470.
The balanced version is A330655.
The case with all atoms distinct is A000311.
The case with all atoms equal is A196545.
Normal multiset partitions are A255906.
Cf. A000669, A004114, A005804, A281118, A316651, A330469, A330626, A330676.

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]]]];
allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1]];
ssrtrees[m_]:=Prepend[Join@@Table[Tuples[ssrtrees/@p],{p,Select[mps[m],Length[m]>Length[#1]>1&]}],m];
Table[Sum[Length[ssrtrees[s]],{s,allnorm[n]}],{n,0,5}]

cp's OEIS Frontend

A035310 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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Extensions

A330465 Number of non-isomorphic series-reduced rooted trees whose leaves are multisets with a total of n elements.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Extensions

A330475 Number of balanced reduced multisystems whose atoms constitute a strongly normal multiset of size n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A330470 Number of non-isomorphic series/singleton-reduced rooted trees on a multiset of size n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Extensions

A330467 Number of series-reduced rooted trees whose leaves are multisets whose multiset union is a strongly normal multiset of size n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Extensions

A330625 Number of series-reduced rooted trees whose leaves are sets (not necessarily disjoint) with multiset union a strongly normal multiset of size n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A330628 Number of series/singleton-reduced rooted trees on strongly normal multisets of size n whose leaves are sets (not necessarily disjoint).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A330654 Number of series/singleton-reduced rooted trees on normal multisets of size n.

Views

Author

Keywords

Comments

Examples

Crossrefs