login
A321283
Number of non-isomorphic multiset partitions of weight n in which the part sizes are relatively prime.
11
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,3
COMMENTS
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.
LINKS
FORMULA
a(n) = A007716(n) - A320810(n). - Andrew Howroyd, Jan 17 2023
EXAMPLE
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}}
PROG
(PARI) \\ 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
(PARI) \\ 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
KEYWORD
nonn
AUTHOR
Gus Wiseman, Nov 06 2018
EXTENSIONS
Terms a(11) and beyond from Andrew Howroyd, Jan 17 2023
STATUS
approved