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

1, 1, 3, 5, 13, 23, 55, 104, 236, 470, 1039, 2140, 4712, 9962, 21961, 47484, 105464, 232324, 521338, 1167825, 2651453, 6031136, 13863054, 31987058, 74448415, 174109134, 410265423, 971839195, 2317827540, 5558092098, 13412360692, 32542049038, 79424450486

Offset

0,3

Links

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

Example

Non-isomorphic representatives of the a(1) = 1 through a(4) = 13 multiset partitions:
  {{1}}  {{1,2}}    {{1},{2,3}}    {{1,2},{1,2}}
         {{1},{1}}  {{2},{1,2}}    {{1,2},{3,4}}
         {{1},{2}}  {{1},{1},{1}}  {{1,3},{2,3}}
                    {{1},{2},{2}}  {{1},{1},{2,3}}
                    {{1},{2},{3}}  {{1},{2},{1,2}}
                                   {{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}}

Prog

(PARI)
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}
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))}
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

Crossrefs

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

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

Non-isomorphic multiset partitions are counted by A007716.

The case without singletons is A007717.

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

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

A339742 counts factorizations into distinct primes or squarefree semiprimes.

A339887 counts factorizations into primes or squarefree semiprimes.

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

Sequence in context: A240070 A045414 A089067 * A026733 A005824 A336103

Adjacent sequences: A339885 A339886 A339887 * A339889 A339890 A339891

Keyword

nonn

Author

Gus Wiseman, Jan 09 2021

Extensions

Terms a(11) and beyond from Andrew Howroyd, Apr 16 2021

Status

approved