A368599 Number of non-isomorphic n-element sets of singletons or pairs of elements of {1..n} with union {1..n}, or unlabeled loop-graphs with n edges covering n vertices.

1, 1, 2, 5, 13, 34, 97, 277, 825, 2486, 7643, 23772, 74989, 238933, 769488, 2500758, 8199828, 27106647, 90316944, 303182461, 1025139840, 3490606305, 11967066094, 41302863014, 143493606215, 501772078429, 1765928732426, 6254738346969, 22294413256484, 79968425399831

Offset

0,3

Comments

It doesn't matter for this sequence whether we use loops such as {x,x} or half-loops such as {x}.

Links

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

Eric Weisstein's World of Mathematics, Graph Loop.

Formula

a(n) = A070166(n,n) - A070166(n-1,n) for n > 0. - Andrew Howroyd, Jan 09 2024

Example

The a(0) = 1 through a(4) = 13 set-systems:
  {}  {{1}}  {{1},{2}}    {{1},{2},{3}}        {{1},{2},{3},{4}}
             {{1},{1,2}}  {{1},{2},{1,3}}      {{1},{2},{3},{1,4}}
                          {{1},{1,2},{1,3}}    {{1},{2},{1,2},{3,4}}
                          {{1},{1,2},{2,3}}    {{1},{2},{1,3},{1,4}}
                          {{1,2},{1,3},{2,3}}  {{1},{2},{1,3},{2,4}}
                                               {{1},{2},{1,3},{3,4}}
                                               {{1},{1,2},{1,3},{1,4}}
                                               {{1},{1,2},{1,3},{2,4}}
                                               {{1},{1,2},{2,3},{2,4}}
                                               {{1},{1,2},{2,3},{3,4}}
                                               {{1},{2,3},{2,4},{3,4}}
                                               {{1,2},{1,3},{1,4},{2,3}}
                                               {{1,2},{1,3},{2,4},{3,4}}

Mathematica

brute[m_]:=First[Sort[Table[Sort[Sort /@ (m/.Rule@@@Table[{(Union@@m)[[i]], p[[i]]}, {i, Length[p]}])], {p, Permutations[Range[Length[Union@@m]]]}]]];
Table[Length[Union[brute /@ Select[Subsets[Subsets[Range[n], {1, 2}], {n}], Union@@#==Range[n]&]]], {n, 0, 5}]

Prog

(PARI) a(n) = polcoef(G(n, O(x*x^n)) - if(n, G(n-1, O(x*x^n))), n) \\ G defined in A070166. - Andrew Howroyd, Jan 09 2024

Crossrefs

For any number of edges we have A000666, A054921, A322700.

For any number of edges of any size we have A055621, non-covering A000612.

For edges of any size we have A368186, covering case of A368731.

The labeled version is A368597, covering case of A014068.

This is the covering case of A368598.

A000085 counts set partitions into singletons or pairs.

A001515 counts length-n set partitions into singletons or pairs.

A100861 counts set partitions into singletons or pairs by number of pairs.

A111924 counts set partitions into singletons or pairs by length.

Cf. A007716, A007717, A058891, A070166, A122848, A283877, A302545, A320663, A322661, A339741, A339887, A339888.

Sequence in context: A318229 A186236 A064780 * A148289 A148290 A029885

Adjacent sequences: A368596 A368597 A368598 * A368600 A368601 A368602

Keyword

nonn

Author

Gus Wiseman, Jan 06 2024

Extensions

Terms a(7) and beyond from Andrew Howroyd, Jan 09 2024

Status

approved