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

1, 1, 2, 2, 5, 6, 15, 21, 49, 82, 184, 341, 766, 1530, 3428, 7249, 16394, 36009, 82492, 186485, 433096, 1001495, 2358182, 5554644, 13255532, 31718030, 76656602, 185982207, 454889643, 1117496012, 2764222322, 6868902152, 17172601190

Offset

0,3

Links

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

Formula

Inverse Euler transform of A339888.

Example

Non-isomorphic representatives of the a(1) = 1 through a(6) = 15 multiset partitions:
  {1}  {12}    {2}{12}    {12}{12}      {2}{12}{12}      {12}{12}{12}
       {1}{1}  {1}{1}{1}  {13}{23}      {2}{13}{23}      {12}{13}{23}
                          {1}{2}{12}    {3}{13}{23}      {13}{23}{23}
                          {2}{2}{12}    {1}{2}{2}{12}    {13}{24}{34}
                          {1}{1}{1}{1}  {2}{2}{2}{12}    {14}{24}{34}
                                        {1}{1}{1}{1}{1}  {1}{2}{12}{12}
                                                         {1}{2}{13}{23}
                                                         {2}{2}{12}{12}
                                                         {2}{2}{13}{23}
                                                         {2}{3}{13}{23}
                                                         {3}{3}{13}{23}
                                                         {1}{1}{2}{2}{12}
                                                         {1}{2}{2}{2}{12}
                                                         {2}{2}{2}{2}{12}
                                                         {1}{1}{1}{1}{1}{1}

Mathematica

sps[{}]:={{}}; sps[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]& /@ sps[Complement[set, s]]] /@ Cases[Subsets[set], {i, ___}];
mpm[n_]:=Join@@Table[Union[Sort[Sort /@ (#/.x_Integer:>s[[x]])]&/@sps[Range[n]]], {s, Flatten[MapIndexed[Table[#2, {#1}]&, #]]& /@ IntegerPartitions[n]}];
csm[s_]:=With[{c=Select[Subsets[Range[Length[s]], {2}], Length[Intersection@@s[[#]]]>0&]}, If[c=={}, s, csm[Sort[Append[Delete[s, List /@ c[[1]]], Union@@s[[c[[1]]]]]]]]];
brute[m_]:=First[Sort[Table[Sort[Sort /@ (m/.Rule@@@Table[{i, p[[i]]}, {i, Length[p]}])], {p, Permutations[Union@@m]}]]];
Table[Length[Union[brute /@ Select[mpm[n], And@@UnsameQ@@@#&&Max@@Length/@#<=2&&Length[csm[#]]<=1&]]], {n, 0, 8}]

Crossrefs

For edges of any size we have A056156, with loops A007718.

This is the connected case of A339888.

Allowing loops {x,x} gives A368726, Euler transform A320663.

A000085, A100861, A111924 count set partitions into singletons or pairs.

A007716 counts non-isomorphic multiset partitions, into pairs A007717.

A062740 counts connected loop-graphs, unlabeled A054921.

A320732 counts factorizations into primes or semiprimes, strict A339839.

A322661 counts covering loop-graphs, unlabeled A322700.

Cf. A001515, A000666, A122848, A283877, A302545, A320462, A321405, A368598, A368599, A368731.

Sequence in context: A028410 A050216 A345470 * A320296 A329908 A295198

Adjacent sequences: A368724 A368725 A368726 * A368728 A368729 A368730

Keyword

nonn

Author

Gus Wiseman, Jan 06 2024

Status

approved