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