A368186 -id:A368186 - cp's OEIS frontend

A368598 Number of non-isomorphic n-element sets of singletons or pairs of elements of {1..n}, or unlabeled loop-graphs with n edges and up to n vertices.

1, 1, 2, 6, 17, 52, 173, 585, 2064, 7520, 28265, 109501, 437394, 1799843, 7629463, 33302834, 149633151, 691702799, 3287804961, 16058229900, 80533510224, 414384339438, 2185878202630, 11811050484851, 65318772618624, 369428031895444, 2135166786135671, 12601624505404858

Offset: 0

Gus Wiseman, Jan 05 2024

nonn

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

			Non-isomorphic representatives of the a(0) = 1 through a(4) = 17 set-systems:
  {}  {{1}}  {{1},{2}}    {{1},{2},{3}}        {{1},{2},{3},{4}}
             {{1},{1,2}}  {{1},{2},{1,2}}      {{1},{2},{3},{1,2}}
                          {{1},{2},{1,3}}      {{1},{2},{3},{1,4}}
                          {{1},{1,2},{1,3}}    {{1},{2},{1,2},{1,3}}
                          {{1},{1,2},{2,3}}    {{1},{2},{1,2},{3,4}}
                          {{1,2},{1,3},{2,3}}  {{1},{2},{1,3},{1,4}}
                                               {{1},{2},{1,3},{2,3}}
                                               {{1},{2},{1,3},{2,4}}
                                               {{1},{3},{1,2},{2,4}}
                                               {{1},{1,2},{1,3},{1,4}}
                                               {{1},{1,2},{1,3},{2,3}}
                                               {{1},{1,2},{1,3},{2,4}}
                                               {{1},{1,2},{2,3},{3,4}}
                                               {{2},{1,2},{1,3},{1,4}}
                                               {{4},{1,2},{1,3},{2,3}}
                                               {{1,2},{1,3},{1,4},{2,3}}
                                               {{1,2},{1,3},{2,4},{3,4}}

Andrew Howroyd, Table of n, a(n) for n = 0..50
Eric Weisstein's World of Mathematics, Graph Loop.

For any number of edges of any size we have A000612, covering A055621.
For any number of edges we have A000666, A054921, A322700.
The labeled version is A014068.
Counting by weight gives A320663, or A339888 with loops {x,x}.
The covering case is A368599.
For edges of any size we have A368731, covering A368186.
Row sums of A368836.
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. A001434, A007716, A007717, A058891, A070166, A122848, A124059, A283877, A302545, A322661, A339741, A339887, A370168.

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 /@ Subsets[Subsets[Range[n],{1,2}],{n}]]],{n,0,5}]

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

a(n) = A070166(n, n). - Andrew Howroyd, Jan 09 2024

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

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.

Original entry on oeis.org

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

Gus Wiseman, Jan 06 2024

nonn

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

			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}}

Andrew Howroyd, Table of n, a(n) for n = 0..50
Eric Weisstein's World of Mathematics, Graph Loop.

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.

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}]

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

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

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

A054780 Number of n-covers of a labeled n-set.

Original entry on oeis.org

1, 1, 3, 32, 1225, 155106, 63602770, 85538516963, 386246934638991, 6001601072676524540, 327951891446717800997416, 64149416776011080449232990868, 45546527789182522411309599498741023, 118653450898277491435912500458608964207578

Offset: 0

Vladeta Jovovic, May 21 2000

Also, number of n X n rational {0,1}-matrices with no zero rows or columns and with all rows distinct, up to permutation of rows.

			From _Gus Wiseman_, Dec 19 2023: (Start)
Number of ways to choose n nonempty sets with union {1..n}. For example, the a(3) = 32 covers are:
  {1}{2}{3}  {1}{2}{13}  {1}{2}{123}  {1}{12}{123}  {12}{13}{123}
             {1}{2}{23}  {1}{3}{123}  {1}{13}{123}  {12}{23}{123}
             {1}{3}{12}  {1}{12}{13}  {1}{23}{123}  {13}{23}{123}
             {1}{3}{23}  {1}{12}{23}  {2}{12}{123}
             {2}{3}{12}  {1}{13}{23}  {2}{13}{123}
             {2}{3}{13}  {2}{3}{123}  {2}{23}{123}
                         {2}{12}{13}  {3}{12}{123}
                         {2}{12}{23}  {3}{13}{123}
                         {2}{13}{23}  {3}{23}{123}
                         {3}{12}{13}  {12}{13}{23}
                         {3}{12}{23}
                         {3}{13}{23}
(End)

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

Main diagonal of A055154.
Cf. A048291, A088310, A181230, A259763.
Covers with any number of edges are counted by A003465, unlabeled A055621.
Connected graphs of this type are counted by A057500, unlabeled A001429.
This is the covering case of A136556.
The case of graphs is A367863, covering case of A116508, unlabeled A006649.
Binomial transform is A367916.
These set-systems have ranks A367917.
The unlabeled version is A368186.
A006129 counts covering graphs, connected A001187, unlabeled A002494.
A046165 counts minimal covers, ranks A309326.
Cf. A006126, A058891, A059201, A133686, A323816, A323817, A323818, A326754, A367862, A367901.

Join[{1}, Table[Sum[StirlingS1[n+1, k+1]*(2^k - 1)^n, {k, 0, n}]/n!, {n, 1, 15}]] (* Vaclav Kotesovec, Jun 04 2022 *)
Table[Length[Select[Subsets[Rest[Subsets[Range[n]]],{n}],Union@@#==Range[n]&]],{n,0,4}] (* Gus Wiseman, Dec 19 2023 *)

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

a(n) = Sum_{k=0..n} (-1)^k*binomial(n, k)*binomial(2^(n-k)-1, n).
a(n) = (1/n!)*Sum_{k=0..n} Stirling1(n+1, k+1)*(2^k-1)^n.
G.f.: Sum_{n>=0} log(1+(2^n-1)*x)^n/((1+(2^n-1)*x)*n!). - Paul D. Hanna and Vladeta Jovovic, Jan 16 2008
a(n) ~ 2^(n^2) / n!. - Vaclav Kotesovec, Jun 04 2022
Inverse binomial transform of A367916. - Gus Wiseman, Dec 19 2023

A367917 BII-numbers of set-systems with the same number of edges as covered vertices.

Original entry on oeis.org

0, 1, 2, 3, 5, 6, 8, 9, 10, 11, 13, 14, 17, 19, 21, 22, 24, 26, 28, 34, 35, 37, 38, 40, 41, 44, 49, 50, 52, 56, 67, 69, 70, 73, 74, 76, 81, 82, 84, 88, 97, 98, 100, 104, 112, 128, 129, 130, 131, 133, 134, 136, 137, 138, 139, 141, 142, 145, 147, 149, 150, 152

Offset: 1

Gus Wiseman, Dec 12 2023

nonn

A binary index of n (row n of A048793) is any position of a 1 in its reversed binary expansion. A set-system is a finite set of finite nonempty sets. We define the set-system with BII-number n to be obtained by taking the binary indices of each binary index of n. Every finite set of finite nonempty sets has a different BII-number. For example, 18 has reversed binary expansion (0,1,0,0,1), and since the binary indices of 2 and 5 are {2} and {1,3} respectively, the BII-number of {{2},{1,3}} is 18.

			The terms together with the corresponding set-systems begin:
   0: {}
   1: {{1}}
   2: {{2}}
   3: {{1},{2}}
   5: {{1},{1,2}}
   6: {{2},{1,2}}
   8: {{3}}
   9: {{1},{3}}
  10: {{2},{3}}
  11: {{1},{2},{3}}
  13: {{1},{1,2},{3}}
  14: {{2},{1,2},{3}}
  17: {{1},{1,3}}
  19: {{1},{2},{1,3}}
  21: {{1},{1,2},{1,3}}
  22: {{2},{1,2},{1,3}}
  24: {{3},{1,3}}
  26: {{2},{3},{1,3}}
  28: {{1,2},{3},{1,3}}
  34: {{2},{2,3}}
  35: {{1},{2},{2,3}}
  37: {{1},{1,2},{2,3}}

These set-systems are counted by A054780 and A367916, A368186.
Graphs of this type are A367862, covering A367863, unlabeled A006649.
A003465 counts set-systems covering {1..n}, unlabeled A055621.
A048793 lists binary indices, length A000120, sum A029931.
A058891 counts set-systems, connected A323818, unlabeled A000612.
A070939 gives length of binary expansion.
A136556 counts set-systems on {1..n} with n edges.
Cf. A057500, A059201, A072639, A096111, A116508, A309326, A326031, A326702, A326753, A326754, A367770, A367902, A367905.

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n, 2]],1];
Select[Range[0,100], Length[bpe[#]]==Length[Union@@bpe/@bpe[#]]&]

A368731 Number of non-isomorphic n-element sets of nonempty subsets of {1..n}.

Original entry on oeis.org

1, 1, 2, 10, 97, 2160, 126862, 21485262, 11105374322, 18109358131513, 95465831661532570, 1660400673336788987026, 96929369602251313489896310, 19268528295096123543660356281600, 13203875101002459910158494602665950757, 31517691852305548841992346407978317698725021

Offset: 0

Gus Wiseman, Jan 07 2024

nonn

			Non-isomorphic representatives of the a(3) = 10 set-systems:
  {{1},{2},{3}}
  {{1},{2},{1,2}}
  {{1},{2},{1,3}}
  {{1},{2},{1,2,3}}
  {{1},{1,2},{1,3}}
  {{1},{1,2},{2,3}}
  {{1},{1,2},{1,2,3}}
  {{1},{2,3},{1,2,3}}
  {{1,2},{1,3},{2,3}}
  {{1,2},{1,3},{1,2,3}}

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

The case of graphs is A001434, labeled A116508.
Labeled version is A136556, covering A054780, binomial transform of A367916.
The case of labeled covering graphs is A367863, binomial transform A367862.
These include the set-systems ranked by A367917.
The covering case is A368186, for graphs A006649, connected A057500.
Requiring all edges to be singletons or pairs gives A368598.
A003465 counts covers with any number of edges, unlabeled A055621.
A046165 counts minimal covers, ranks A309326.
A058891 counts set-systems, unlabeled A000612, without singletons A016031.
A059201 counts covering T_0 set-systems, unlabeled A319637, ranks A326947.
Cf. A000088, A007716, A283877, A367901, A367902, A367903, A368599.

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 /@ Subsets[Subsets[Range[n],{1,n}],{n}]]],{n,0,4}]

a(n) = polcoef(G(n, n), n) \\ G defined in A368186. - Andrew Howroyd, Jan 11 2024

Terms a(6) and beyond from Andrew Howroyd, Jan 11 2024

A055130 Triangle T(n,k) of numbers of k-covers of an unlabeled n-set, k=1..2^n-1.

Original entry on oeis.org

1, 1, 2, 1, 1, 4, 9, 10, 6, 3, 1, 1, 7, 29, 87, 181, 287, 364, 365, 290, 187, 97, 39, 13, 4, 1, 1, 10, 72, 417, 1973, 7745, 25830, 74017, 183420, 395311, 744495, 1229807, 1787135, 2289925, 2591162, 2591163, 2289929, 1787148, 1229846, 744592, 395498

Offset: 1

Vladeta Jovovic, Jun 14 2000

			Triangle begins:
[1] 1;
[2] 1, 2,  1;
[3] 1, 4,  9, 10,   6,   3,   1;
[4] 1, 7, 29, 87, 181, 287, 364, 365, 290, 187, 97, 39, 13, 4, 1;
  ...
There are 9 3-covers of an unlabeled 3-set: {{1,2},{2,3},{1,2,3}}, {{1,2},{2,3},{1,3}}, {{1,2},{3},{1,2,3}}, {{1},{1,2},{1,2,3}}, {{1,2},{2,3},{3}}, {{1,2},{2},{2,3}}, {{1},{2},{1,2,3}}, {{1},{2},{1,3}} and {{1},{2},{3}}.

Andrew Howroyd, Table of n, a(n) for n = 1..2036 (rows 1..10)

Row sums give A055621.
Columns k=1..3 are A000012, A014616(n-1), A055195.
Cf. A052265, A368186.

\\ G(n,m) defined in A368186.
row(n)={my(m=2^n-1); Vec(G(n,m) - G(n-1,m))} \\ Andrew Howroyd, Jan 03 2024

T(n,n) = A368186(n). - Andrew Howroyd, Jan 03 2024

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

Original entry on oeis.org

1, 1, 3, 3, 8, 10, 26, 38, 93, 161, 381, 732, 1721, 3566, 8369, 18316, 43280, 98401, 234959, 549628, 1327726, 3175670, 7763500, 18905703, 46762513, 115613599, 289185492, 724438500, 1831398264, 4641907993, 11853385002, 30365353560

Offset: 0

Gus Wiseman, Jan 06 2024

nonn

			Non-isomorphic representatives of the a(1) = 1 through a(5) = 10 multiset partitions:
  {{1}}  {{1,1}}    {{1},{1,1}}    {{1,1},{1,1}}      {{1},{1,1},{1,1}}
         {{1,2}}    {{2},{1,2}}    {{1,2},{1,2}}      {{1},{1,2},{2,2}}
         {{1},{1}}  {{1},{1},{1}}  {{1,2},{2,2}}      {{2},{1,2},{1,2}}
                                   {{1,3},{2,3}}      {{2},{1,2},{2,2}}
                                   {{1},{1},{1,1}}    {{2},{1,3},{2,3}}
                                   {{1},{2},{1,2}}    {{3},{1,3},{2,3}}
                                   {{2},{2},{1,2}}    {{1},{1},{1},{1,1}}
                                   {{1},{1},{1},{1}}  {{1},{2},{2},{1,2}}
                                                      {{2},{2},{2},{1,2}}
                                                      {{1},{1},{1},{1},{1}}

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

For edges of any size we have A007718.
This is the connected case of A320663.
The case of singletons and strict pairs is A368727, Euler transform A339888.
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, A368186, A368598, A368599, A368731.

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], Max@@Length/@#<=2&&Length[csm[#]]<=1&]]],{n,0,8}]

Inverse Euler transform of A320663.

cp's OEIS Frontend

A368598 Number of non-isomorphic n-element sets of singletons or pairs of elements of {1..n}, or unlabeled loop-graphs with n edges and up to n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A054780 Number of n-covers of a labeled n-set.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A367917 BII-numbers of set-systems with the same number of edges as covered vertices.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A368731 Number of non-isomorphic n-element sets of nonempty subsets of {1..n}.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A055130 Triangle T(n,k) of numbers of k-covers of an unlabeled n-set, k=1..2^n-1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula