login
Number of non-isomorphic multiset partitions of weight n into singletons or strict pairs.
15

%I #11 Apr 17 2021 03:43:04

%S 1,1,3,5,13,23,55,104,236,470,1039,2140,4712,9962,21961,47484,105464,

%T 232324,521338,1167825,2651453,6031136,13863054,31987058,74448415,

%U 174109134,410265423,971839195,2317827540,5558092098,13412360692,32542049038,79424450486

%N Number of non-isomorphic multiset partitions of weight n into singletons or strict pairs.

%H Andrew Howroyd, <a href="/A339888/b339888.txt">Table of n, a(n) for n = 0..50</a>

%e Non-isomorphic representatives of the a(1) = 1 through a(4) = 13 multiset partitions:

%e {{1}} {{1,2}} {{1},{2,3}} {{1,2},{1,2}}

%e {{1},{1}} {{2},{1,2}} {{1,2},{3,4}}

%e {{1},{2}} {{1},{1},{1}} {{1,3},{2,3}}

%e {{1},{2},{2}} {{1},{1},{2,3}}

%e {{1},{2},{3}} {{1},{2},{1,2}}

%e {{1},{2},{3,4}}

%e {{1},{3},{2,3}}

%e {{2},{2},{1,2}}

%e {{1},{1},{1},{1}}

%e {{1},{1},{2},{2}}

%e {{1},{2},{2},{2}}

%e {{1},{2},{3},{3}}

%e {{1},{2},{3},{4}}

%o (PARI)

%o EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}

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

%o gs(v) = {sum(i=2, #v, sum(j=1, i-1, my(g=gcd(v[i], v[j])); g*x^(2*v[i]*v[j]/g))) + sum(i=1, #v, my(r=v[i]); (1 + (1+r)%2)*x^r + ((r-1)\2)*x^(2*r))}

%o a(n)={if(n==0, 1, my(s=0); forpart(p=n, s+=permcount(p)*EulerT(Vec(gs(p) + O(x*x^n), -n))[n]); s/n!)} \\ _Andrew Howroyd_, Apr 16 2021

%Y The version for set partitions is A000085, with ordered version A080599.

%Y The case of integer partitions is 1 + A004526(n), ranked by A003586.

%Y Non-isomorphic multiset partitions are counted by A007716.

%Y The case without singletons is A007717.

%Y The version allowing non-strict pairs (x,x) is A320663.

%Y A001190 counts rooted trees with out-degrees <= 2, ranked by A292050.

%Y A339742 counts factorizations into distinct primes or squarefree semiprimes.

%Y A339887 counts factorizations into primes or squarefree semiprimes.

%Y Cf. A001055, A007718, A316983, A319616, A320656, A321729, A339740, A339741.

%K nonn

%O 0,3

%A _Gus Wiseman_, Jan 09 2021

%E Terms a(11) and beyond from _Andrew Howroyd_, Apr 16 2021