A368597 - OEIS

%I #15 Feb 24 2024 11:03:20

%S 1,1,3,17,150,1803,27364,501015,10736010,263461265,7283725704,

%T 223967628066,7581128184175,280103206674480,11216492736563655,

%U 483875783716549277,22371631078155742764,1103548801569848115255,57849356643299101021960,3211439288584038922502820

%N Number of n-element sets of singletons or pairs of distinct elements of {1..n} with union {1..n}, or loop-graphs covering n vertices with n edges.

%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="/A368597/b368597.txt">Table of n, a(n) for n = 0..200</a>

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

%F a(n) = Sum_{k=0..n} (-1)^(n-k) * binomial(n,k) * binomial(binomial(k+1,2), n). - _Andrew Howroyd_, Jan 06 2024

%e The a(0) = 1 through a(3) = 17 set-systems:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

%o (PARI) a(n) = sum(k=0, n, (-1)^(n-k) * binomial(n,k) * binomial(binomial(k+1,2), n)) \\ _Andrew Howroyd_, Jan 06 2024

%Y This is the covering case of A014068.

%Y Allowing edges of any positive size gives A054780, covering case of A136556.

%Y Allowing any number of edges gives A322661, connected A062740.

%Y The case of just pairs is A367863, covering case of A116508.

%Y The unlabeled version is A368599.

%Y The version contradicting strict AOC is A368730.

%Y The connected case is A368951.

%Y A000085 counts set partitions into singletons or pairs.

%Y A006129 counts covering graphs, connected A001187.

%Y A058891 counts set-systems, unlabeled A000612.

%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. A000272, A000666, A057500, A066383, A333331, A367869, A368596, A368600, A368928, A368951, A369199.

%K nonn

%O 0,3

%A _Gus Wiseman_, Jan 04 2024

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