login
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.
14

%I #15 Mar 23 2024 22:13:05

%S 1,1,2,5,13,34,97,277,825,2486,7643,23772,74989,238933,769488,2500758,

%T 8199828,27106647,90316944,303182461,1025139840,3490606305,

%U 11967066094,41302863014,143493606215,501772078429,1765928732426,6254738346969,22294413256484,79968425399831

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

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

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

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/GraphLoop.html">Graph Loop</a>.

%F a(n) = A070166(n,n) - A070166(n-1,n) for n > 0. - _Andrew Howroyd_, Jan 09 2024

%e The a(0) = 1 through a(4) = 13 set-systems:

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

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

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

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

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

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

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

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

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

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

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

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

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

%t brute[m_]:=First[Sort[Table[Sort[Sort /@ (m/.Rule@@@Table[{(Union@@m)[[i]],p[[i]]}, {i,Length[p]}])], {p,Permutations[Range[Length[Union@@m]]]}]]];

%t Table[Length[Union[brute /@ Select[Subsets[Subsets[Range[n],{1,2}],{n}], Union@@#==Range[n]&]]],{n,0,5}]

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

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

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

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

%Y The labeled version is A368597, covering case of A014068.

%Y This is the covering case of A368598.

%Y A000085 counts set partitions into singletons or pairs.

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

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

%Y A111924 counts set partitions into singletons or pairs by length.

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

%K nonn

%O 0,3

%A _Gus Wiseman_, Jan 06 2024

%E Terms a(7) and beyond from _Andrew Howroyd_, Jan 09 2024