A301700 -id:A301700 - cp's OEIS frontend

A303547 Number of non-isomorphic periodic multiset partitions of weight n.

0, 1, 1, 4, 1, 13, 1, 33, 10, 94, 1, 327, 1, 913, 100, 3017, 1, 10233, 1, 34236, 919, 119372, 1, 432234, 91, 1574227, 9945, 5916177, 1, 22734231, 1, 89003059, 119378, 356058543, 1000, 1453509039, 1, 6044132797, 1574233, 25612601420, 1, 110509543144, 1, 485161348076

Offset: 1

Gus Wiseman, Apr 26 2018

nonn

A multiset is periodic if its multiplicities have a common divisor greater than 1. For this sequence neither the parts nor their multiset union are required to be periodic, only the multiset of parts.

			Non-isomorphic representatives of the a(4) = 4 multiset partitions are {{1,1},{1,1}}, {{1,2},{1,2}}, {{1},{1},{1},{1}}, {{1},{1},{2},{2}}.

Cf. A000740, A000837, A001055, A007716, A007916, A049311, A100953, A255906, A269134, A275024, A293993, A301700, A303386, A303431, A303546.

a(n) = 1 if n is prime.

a(n) = A007716(n) - A303546(n).

More terms from Jinyuan Wang, Jun 21 2020

A317718 Number of uniform relatively prime rooted trees with n nodes.

Original entry on oeis.org

1, 1, 2, 4, 7, 13, 27, 55, 125, 278, 650, 1510, 3624, 8655, 21017, 51212, 125857, 310581, 770767, 1920226

Offset: 1

Gus Wiseman, Aug 05 2018

An unlabeled rooted tree is uniform and relatively prime iff either it is a single node or a single node with a single uniform relatively prime branch, or the branches of the root have empty intersection (relatively prime) and equal multiplicities (uniform) and are themselves uniform relatively prime trees.

			The a(6) = 13 uniform relatively prime rooted trees:
  (((((o)))))
  ((((oo))))
  (((o(o))))
  (((ooo)))
  ((o((o))))
  ((o(oo)))
  ((oooo))
  (o(((o))))
  (o((oo)))
  (o(o(o)))
  (o(ooo))
  ((o)((o)))
  (ooooo)

A. David Christopher and M. Davamani Christober, Relatively Prime Uniform Partitions, Gen. Math. Notes, Vol. 13, No. 2, December, 2012, pp. 1-12.

Cf. A000081, A001190, A004111, A072774, A301700, A317588.

Cf. A317705, A317707, A317708, A317709, A317710, A317711, A317712, A317717.

purt[n_]:=purt[n]=If[n==1,{{}},Join@@Table[Select[Union[Sort/@Tuples[purt/@ptn]],Or[Length[#]==1,And[SameQ@@Length/@Split[#],Intersection@@#=={}]]&],{ptn,IntegerPartitions[n-1]}]];
Table[Length[purt[n]],{n,20}]

A321283 Number of non-isomorphic multiset partitions of weight n in which the part sizes are relatively prime.

Original entry on oeis.org

1, 1, 2, 7, 21, 84, 214, 895, 2607, 9591, 31134, 119313, 400950, 1574123, 5706112, 22572991, 86933012, 356058243, 1427784135, 6044132304, 25342935667, 110414556330, 481712291885, 2166488898387, 9784077216457, 45369658599779, 211869746691055, 1011161497851296, 4871413403219085

Offset: 0

Gus Wiseman, Nov 06 2018

nonn

Also the number of nonnegative integer matrices up to row and column permutations with sum of elements equal to n and no zero rows or columns, in which the row sums are relatively prime.
Also the number of non-isomorphic multiset partitions of weight n in which the multiset union of the parts is aperiodic, where a multiset is aperiodic if its multiplicities are relatively prime.
The weight of a multiset partition is the sum of sizes of its parts. Weight is generally not the same as number of vertices.

			Non-isomorphic representatives of the a(1) = 1 through a(4) = 21 multiset partitions with relatively prime part-sizes:
  {{1}}  {{1},{1}}  {{1},{1,1}}    {{1},{1,1,1}}
         {{1},{2}}  {{1},{2,2}}    {{1},{1,2,2}}
                    {{1},{2,3}}    {{1},{2,2,2}}
                    {{2},{1,2}}    {{1},{2,3,3}}
                    {{1},{1},{1}}  {{1},{2,3,4}}
                    {{1},{2},{2}}  {{2},{1,2,2}}
                    {{1},{2},{3}}  {{3},{1,2,3}}
                                   {{1},{1},{1,1}}
                                   {{1},{1},{2,2}}
                                   {{1},{1},{2,3}}
                                   {{1},{2},{1,2}}
                                   {{1},{2},{2,2}}
                                   {{1},{2},{3,3}}
                                   {{1},{2},{3,4}}
                                   {{1},{3},{2,3}}
                                   {{2},{2},{1,2}}
                                   {{1},{1},{1},{1}}
                                   {{1},{1},{2},{2}}
                                   {{1},{2},{2},{2}}
                                   {{1},{2},{3},{3}}
                                   {{1},{2},{3},{4}}
Non-isomorphic representatives of the a(1) = 1 through a(4) = 21 multiset partitions with aperiodic multiset union:
  {{1}}  {{1,2}}    {{1,2,2}}      {{1,2,2,2}}
         {{1},{2}}  {{1,2,3}}      {{1,2,3,3}}
                    {{1},{2,2}}    {{1,2,3,4}}
                    {{1},{2,3}}    {{1},{2,2,2}}
                    {{2},{1,2}}    {{1,2},{2,2}}
                    {{1},{2},{2}}  {{1},{2,3,3}}
                    {{1},{2},{3}}  {{1,2},{3,3}}
                                   {{1},{2,3,4}}
                                   {{1,2},{3,4}}
                                   {{1,3},{2,3}}
                                   {{2},{1,2,2}}
                                   {{3},{1,2,3}}
                                   {{1},{1},{2,3}}
                                   {{1},{2},{2,2}}
                                   {{1},{2},{3,3}}
                                   {{1},{2},{3,4}}
                                   {{1},{3},{2,3}}
                                   {{2},{2},{1,2}}
                                   {{1},{2},{2},{2}}
                                   {{1},{2},{3},{3}}
                                   {{1},{2},{3},{4}}

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

Cf. A000740, A000837, A007716, A007916, A100953, A301700, A303386, A303431, A303546, A303547, A320800-A320810.

\\ See links in A339645 for combinatorial species functions.
seq(n)={my(A=symGroupSeries(n)); NumUnlabeledObjsSeq(sCartProd(sExp(A), 1 + sum(d=1, n, moebius(d) * (-1 + sExp(O(x*x^n) + sum(i=1, n\d, polcoef(A,i*d)*x^(i*d)))) )))} \\ Andrew Howroyd, Jan 17 2023

\\ faster self contained program.
EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
K(q, t, k)={EulerT(Vec(sum(j=1, #q, my(g=gcd(t, q[j])); g*x^(q[j]/g)) + O(x*x^k), -k))}
a(n)={if(n==0, 1, my(s=0); forpart(q=n, my(u=vector(n, t, K(q, t, n\t))); s+=permcount(q)*polcoef(sum(d=1, n, moebius(d)*exp(sum(t=1, n\d, sum(i=1, n\(t*d), u[t][i*d]*x^(i*d*t))/t, O(x*x^n)) )), n)); s/n!)} \\ Andrew Howroyd, Jan 17 2023

a(n) = A007716(n) - A320810(n). - Andrew Howroyd, Jan 17 2023

Terms a(11) and beyond from Andrew Howroyd, Jan 17 2023

A317709 Aperiodic relatively prime tree numbers. Matula-Goebel numbers of aperiodic relatively prime trees.

Original entry on oeis.org

1, 2, 3, 5, 6, 10, 11, 12, 13, 15, 18, 20, 22, 24, 26, 29, 30, 31, 33, 37, 40, 41, 44, 45, 47, 48, 50, 52, 54, 55, 58, 60, 61, 62, 66, 71, 72, 74, 75, 78, 79, 80, 82, 88, 89, 90, 93, 94, 96, 99, 101, 104, 108, 109, 110, 113, 116, 120, 122, 123, 124, 127, 130

Offset: 1

Gus Wiseman, Aug 05 2018

nonn

A positive integer n is in the sequence iff either n = 1 or n is a prime number whose prime index already belongs to the sequence or n is not a perfect power and its prime indices are relatively prime numbers already belonging to the sequence. A prime index of n is a number m such that prime(m) divides n.

			The sequence of aperiodic relatively prime tree numbers together with their Matula-Goebel trees begins:
   1: o
   2: (o)
   3: ((o))
   5: (((o)))
   6: (o(o))
  10: (o((o)))
  11: ((((o))))
  12: (oo(o))
  13: ((o(o)))
  15: ((o)((o)))
  18: (o(o)(o))
  20: (oo((o)))
  22: (o(((o))))
  24: (ooo(o))
  26: (o(o(o)))
  29: ((o((o))))
  30: (o(o)((o)))
  31: (((((o)))))

Cf. A000081, A061775, A111299, A214577, A276625, A277098, A301700, A303431, A316503.

Cf. A317705, A317707, A317708, A317710, A317711, A317712.

rupQ[n_]:=Or[n==1,If[PrimeQ[n],rupQ[PrimePi[n]],And[GCD@@FactorInteger[n][[All,2]]==1,GCD@@PrimePi/@FactorInteger[n][[All,1]]==1,And@@rupQ/@PrimePi/@FactorInteger[n][[All,1]]]]];
Select[Range[100],rupQ]

A320800 Number of non-isomorphic multiset partitions of weight n in which both the multiset union of the parts and the multiset union of the dual parts are aperiodic.

Original entry on oeis.org

1, 1, 1, 5, 14, 78, 157, 881, 2267, 9257, 28397

Offset: 0

Gus Wiseman, Nov 02 2018

The latter condition is equivalent to the parts having relatively prime sizes.
A multiset is aperiodic if its multiplicities are relatively prime.
The dual of a multiset partition has, for each vertex, one part consisting of the indices (or positions) of the parts containing that vertex, counted with multiplicity. For example, the dual of {{1,2},{2,2}} is {{1},{1,2,2}}.
The weight of a multiset partition is the sum of sizes of its parts. Weight is generally not the same as number of vertices.

			Non-isomorphic representatives of the a(1) = 1 through a(4) = 14 multiset partitions:
  {{1}}  {{1},{2}}  {{1},{2,2}}    {{1},{2,2,2}}
                    {{1},{2,3}}    {{1},{2,3,3}}
                    {{2},{1,2}}    {{1},{2,3,4}}
                    {{1},{2},{2}}  {{2},{1,2,2}}
                    {{1},{2},{3}}  {{3},{1,2,3}}
                                   {{1},{1},{2,3}}
                                   {{1},{2},{2,2}}
                                   {{1},{2},{3,3}}
                                   {{1},{2},{3,4}}
                                   {{1},{3},{2,3}}
                                   {{2},{2},{1,2}}
                                   {{1},{2},{2},{2}}
                                   {{1},{2},{3},{3}}
                                   {{1},{2},{3},{4}}

Cf. A000740, A000837, A007716, A007916, A100953, A301700, A303386, A303431, A303546, A303547, A316983, A320801-A320810.

A320804 Number of non-isomorphic multiset partitions of weight n with no singletons in which all parts are aperiodic multisets.

Original entry on oeis.org

1, 0, 1, 2, 6, 13, 41, 104, 326, 958, 3096, 9958, 33869, 116806, 417741, 1526499, 5732931, 22015642, 86543717, 347495480, 1424832602, 5959123908, 25407212843, 110344848622, 487879651220, 2194697288628, 10039367091586, 46675057440634, 220447539120814

Offset: 0

Gus Wiseman, Nov 06 2018

nonn

Also the number of nonnegative integer matrices with (1) sum of elements equal to n, (2) no zero columns, (3) no rows summing to 0 or 1, and (4) no rows whose nonzero entries have a common divisor > 1, up to row and column permutations.
A multiset is aperiodic if its multiplicities are relatively prime.
The weight of a multiset partition is the sum of sizes of its parts. Weight is generally not the same as number of vertices.

			Non-isomorphic representatives of the a(2) = 1 through a(5) = 13 multiset partitions with aperiodic parts and no singletons:
  {{1,2}}  {{1,2,2}}  {{1,2,2,2}}    {{1,1,2,2,2}}
           {{1,2,3}}  {{1,2,3,3}}    {{1,2,2,2,2}}
                      {{1,2,3,4}}    {{1,2,2,3,3}}
                      {{1,2},{1,2}}  {{1,2,3,3,3}}
                      {{1,2},{3,4}}  {{1,2,3,4,4}}
                      {{1,3},{2,3}}  {{1,2,3,4,5}}
                                     {{1,2},{1,2,2}}
                                     {{1,2},{2,3,3}}
                                     {{1,2},{3,4,4}}
                                     {{1,2},{3,4,5}}
                                     {{1,3},{2,3,3}}
                                     {{1,4},{2,3,4}}
                                     {{2,3},{1,2,3}}

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

Cf. A000740, A000837, A007716, A007916, A100953, A301700, A302545, A303386, A303546, A303707, A303708, A320797-A320813.

EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
K(q, t, k)={EulerT(Vec(sum(j=1, #q, gcd(t, q[j])*x^lcm(t, q[j])) + O(x*x^k), -k))}
S(q, t, k)={Vec(sum(j=1, #q, if(t%q[j]==0, q[j]*x^t))  + O(x*x^k), -k)}
a(n)={if(n==0, 1, my(mbt=vector(n, d, moebius(d)), s=0); forpart(q=n, s+=permcount(q)*polcoef(exp(x*Ser(dirmul(mbt, sum(t=1, n, K(q, t, n)/t)) - sum(t=1, n, S(q, t, n)/t) )), n)); s/n!)} \\ Andrew Howroyd, Jan 16 2023

Terms a(11) and beyond from Andrew Howroyd, Jan 16 2023

A303551 Number of aperiodic multisets of compositions of total weight n.

Original entry on oeis.org

1, 2, 6, 15, 41, 95, 243, 567, 1366, 3189, 7532, 17428, 40590, 93465, 215331, 493150, 1127978, 2569049, 5841442, 13240351, 29953601, 67596500, 152258270, 342235866, 767895382, 1719813753, 3845442485, 8584197657, 19133459138, 42583565928, 94641591888

Offset: 1

Gus Wiseman, Apr 26 2018

nonn

A multiset is aperiodic if its multiplicities are relatively prime.

			The a(4) = 15 aperiodic multisets of compositions are:
{4}, {31}, {22}, {211}, {13}, {121}, {112}, {1111},
{1,3}, {1,21}, {1,12}, {1,111}, {2,11},
{1,1,2}, {1,1,11}.
Missing from this list are {1,1,1,1}, {2,2}, and {11,11}.

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

Cf. A000740, A000837, A007716, A007916, A034691, A100953, A255906, A269134, A301700, A303386, A303431, A303546, A303552.

with(numtheory):
b:= proc(n) option remember; `if`(n=0, 1, add(add(
      d*2^(d-1), d=divisors(j))*b(n-j), j=1..n)/n)
    end:
a:= n-> add(mobius(d)*b(n/d), d=divisors(n)):
seq(a(n), n=1..35);  # Alois P. Heinz, Apr 26 2018

nn=20;
ser=Product[1/(1-x^n)^2^(n-1),{n,nn}]
Table[Sum[MoebiusMu[d]*SeriesCoefficient[ser,{x,0,n/d}],{d,Divisors[n]}],{n,1,nn}]

EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
seq(n)={my(u=EulerT(vector(n, n, 2^(n-1)))); vector(n, n, sumdiv(n, d, moebius(d)*u[n/d]))} \\ Andrew Howroyd, Sep 15 2018

a(n) = Sum_{d|n} mu(d) * A034691(n/d).

A317787 Number of locally nonintersecting rooted trees with n nodes.

Original entry on oeis.org

1, 1, 2, 4, 8, 18, 40, 95, 227, 557, 1382, 3485, 8865, 22790, 59022, 153972, 404066, 1066236, 2826885, 7527411, 20121154

Offset: 1

Gus Wiseman, Aug 07 2018

An unlabeled rooted tree is locally nonintersecting if there is no common subbranch to all branches directly under any given node.

			The a(6) = 18 locally nonintersecting rooted trees:
  (((((o)))))
  ((((oo))))
  (((o(o))))
  ((o((o))))
  (o(((o))))
  ((o)((o)))
  (((ooo)))
  ((o(oo)))
  ((oo(o)))
  (o((oo)))
  (o(o(o)))
  (oo((o)))
  (o(o)(o))
  ((oooo))
  (o(ooo))
  (oo(oo))
  (ooo(o))
  (ooooo)
Missing from this list are (((o)(o))) and ((o)(oo)).

Cf. A000081, A276625, A301700, A316473, A316475, A316501, A316502, A317708, A317785, A317789.

rurt[n_]:=If[n==1,{{}},Join@@Table[Select[Union[Sort/@Tuples[rurt/@ptn]],Or[Length[#]==1,Intersection@@#=={}]&],{ptn,IntegerPartitions[n-1]}]];
Table[Length[rurt[n]],{n,10}]

a(16)-a(21) from Robert Price, Sep 16 2018

A320806 Number of non-isomorphic multiset partitions of weight n in which each of the parts and each part of the dual, as well as both the multiset union of the parts and the multiset union of the dual parts, is an aperiodic multiset.

Original entry on oeis.org

1, 1, 1, 4, 10, 39, 81, 343, 903, 3223, 9989

Offset: 0

Gus Wiseman, Nov 07 2018

Also the number of nonnegative integer matrices up to row and column permutations with sum of elements equal to n and no zero rows or columns, in which (1) the positive entries in each row and column are relatively prime and (2) the row sums and column sums are relatively prime.
The last condition (aperiodicity of the multiset union of the dual) is equivalent to the parts having relatively prime sizes.
A multiset is aperiodic if its multiplicities are relatively prime.
The dual of a multiset partition has, for each vertex, one part consisting of the indices (or positions) of the parts containing that vertex, counted with multiplicity. For example, the dual of {{1,2},{2,2}} is {{1},{1,2,2}}.
The weight of a multiset partition is the sum of sizes of its parts. Weight is generally not the same as number of vertices.

			Non-isomorphic representatives of the a(1) = 1 through a(4) = 10 multiset partitions:
  {{1}}  {{1},{2}}  {{1},{2,3}}    {{1},{2,3,4}}
                    {{2},{1,2}}    {{2},{1,2,2}}
                    {{1},{2},{2}}  {{3},{1,2,3}}
                    {{1},{2},{3}}  {{1},{1},{2,3}}
                                   {{1},{2},{3,4}}
                                   {{1},{3},{2,3}}
                                   {{2},{2},{1,2}}
                                   {{1},{2},{2},{2}}
                                   {{1},{2},{3},{3}}
                                   {{1},{2},{3},{4}}

Cf. A000740, A000837, A007716, A007916, A100953, A301700, A303386, A303546, A303707, A303708, A316983, A320800-A320810, A321283.

A320811 Number of non-isomorphic multiset partitions with no singletons of aperiodic multisets of size n.

Original entry on oeis.org

1, 0, 1, 2, 7, 21, 57, 200, 575, 1898, 5893

Offset: 0

Gus Wiseman, Nov 08 2018

Also the number of nonnegative integer matrices up to row and column permutations with sum of elements equal to n and no zero rows or columns, in which (1) the row sums are all > 1 and (2) the column sums are relatively prime.
A multiset is aperiodic if its multiplicities are relatively prime.
The weight of a multiset partition is the sum of sizes of its parts. Weight is generally not the same as number of vertices.

			Non-isomorphic representatives of the a(2) = 1 through a(5) = 21 multiset partitions:
  {{1,2}}  {{1,2,2}}  {{1,2,2,2}}    {{1,1,2,2,2}}
           {{1,2,3}}  {{1,2,3,3}}    {{1,2,2,2,2}}
                      {{1,2,3,4}}    {{1,2,2,3,3}}
                      {{1,2},{2,2}}  {{1,2,3,3,3}}
                      {{1,2},{3,3}}  {{1,2,3,4,4}}
                      {{1,2},{3,4}}  {{1,2,3,4,5}}
                      {{1,3},{2,3}}  {{1,1},{1,2,2}}
                                     {{1,1},{2,2,2}}
                                     {{1,1},{2,3,3}}
                                     {{1,1},{2,3,4}}
                                     {{1,2},{1,2,2}}
                                     {{1,2},{2,2,2}}
                                     {{1,2},{2,3,3}}
                                     {{1,2},{3,3,3}}
                                     {{1,2},{3,4,4}}
                                     {{1,2},{3,4,5}}
                                     {{1,3},{2,3,3}}
                                     {{1,4},{2,3,4}}
                                     {{2,2},{1,2,2}}
                                     {{2,3},{1,2,3}}
                                     {{3,3},{1,2,3}}

Cf. A000740, A000837, A007716, A007916, A100953, A301700, A302545, A303386, A303546, A303707, A303708, A320797-A320813, A321283, A321390.

cp's OEIS Frontend

A303547 Number of non-isomorphic periodic multiset partitions of weight n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

A317718 Number of uniform relatively prime rooted trees with n nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A321283 Number of non-isomorphic multiset partitions of weight n in which the part sizes are relatively prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

PARI

Formula

Extensions

A317709 Aperiodic relatively prime tree numbers. Matula-Goebel numbers of aperiodic relatively prime trees.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A320800 Number of non-isomorphic multiset partitions of weight n in which both the multiset union of the parts and the multiset union of the dual parts are aperiodic.

Views

Author

Keywords

Comments

Examples

Crossrefs

A320804 Number of non-isomorphic multiset partitions of weight n with no singletons in which all parts are aperiodic multisets.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions

A303551 Number of aperiodic multisets of compositions of total weight n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A317787 Number of locally nonintersecting rooted trees with n nodes.

Views

Author

Keywords

Comments

Examples

Crossrefs