A368597 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.

1, 1, 3, 17, 150, 1803, 27364, 501015, 10736010, 263461265, 7283725704, 223967628066, 7581128184175, 280103206674480, 11216492736563655, 483875783716549277, 22371631078155742764, 1103548801569848115255, 57849356643299101021960, 3211439288584038922502820

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..200

Eric Weisstein's World of Mathematics, Graph Loop.

Formula

a(n) = Sum_{k=0..n} (-1)^(n-k) * binomial(n,k) * binomial(binomial(k+1,2), n). - Andrew Howroyd, Jan 06 2024

Example

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

Mathematica

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

Prog

(PARI) a(n) = sum(k=0, n, (-1)^(n-k) * binomial(n, k) * binomial(binomial(k+1, 2), n)) \\ Andrew Howroyd, Jan 06 2024

Crossrefs

This is the covering case of A014068.

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

Allowing any number of edges gives A322661, connected A062740.

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

The unlabeled version is A368599.

The version contradicting strict AOC is A368730.

The connected case is A368951.

A000085 counts set partitions into singletons or pairs.

A006129 counts covering graphs, connected A001187.

A058891 counts set-systems, unlabeled A000612.

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

A111924 counts set partitions into singletons or pairs by length.

Cf. A000272, A000666, A057500, A066383, A333331, A367869, A368596, A368600, A368928, A368951, A369199.

Sequence in context: A319946 A213507 A305471 * A135750 A286345 A303063

Adjacent sequences: A368594 A368595 A368596 * A368598 A368599 A368600

Keyword

nonn

Author

Gus Wiseman, Jan 04 2024

Extensions

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

Status

approved