A140637 -id:A140637 - cp's OEIS frontend

A369200 Number of unlabeled loop-graphs covering n vertices such that it is possible to choose a different vertex from each edge (choosable).

1, 1, 3, 7, 18, 43, 112, 282, 740, 1940, 5182, 13916, 37826, 103391, 284815, 788636, 2195414, 6137025, 17223354, 48495640, 136961527, 387819558, 1100757411, 3130895452, 8922294498, 25470279123, 72823983735, 208515456498, 597824919725, 1716072103910, 4931540188084

Offset: 0

Gus Wiseman, Jan 23 2024

nonn

These are covering loop-graphs with at most one cycle (unicyclic) in each connected component.

			Representatives of the a(1) = 1 through a(4) = 18 loop-graphs (loops shown as singletons):
  {{1}}  {{1,2}}      {{1},{2,3}}          {{1,2},{3,4}}
         {{1},{2}}    {{1,2},{1,3}}        {{1},{2},{3,4}}
         {{1},{1,2}}  {{1},{2},{3}}        {{1},{1,2},{3,4}}
                      {{1},{2},{1,3}}      {{1},{2,3},{2,4}}
                      {{1},{1,2},{1,3}}    {{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},{3},{1,4}}
                                           {{1},{2},{1,3},{1,4}}
                                           {{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..500

Without the choice condition we have A322700, labeled A322661.
Without loops we have A368834, covering case of A134964.
For exactly n edges we have A368984, labeled A333331 (maybe).
The labeled version is A369140, covering case of A368927.
The labeled complement is A369142, covering case of A369141.
This is the covering case of A369145.
The complement is counted by A369147, covering case of A369146.
The complement without loops is A369202, covering case of A140637.
A000085, A100861, A111924 count set partitions into singletons or pairs.
A000666 counts unlabeled loop-graphs, labeled A006125 (shifted left).
A006129 counts covering graphs, unlabeled A002494.
A007716 counts non-isomorphic multiset partitions, connected A007718.
A129271 counts connected choosable simple graphs, unlabeled A005703.
A133686 counts choosable labeled graphs, covering A367869.
Cf. A000088, A000612, A006649, A014068, A055621, A137916, A137917, A368835, A369194, A369199.

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}]], Union@@#==Range[n]&&Length[Select[Tuples[#], UnsameQ@@#&]]!=0&]]],{n,0,4}]

First differences of A369145.

Euler transform of A369289 with A369289(1) = 1. - Andrew Howroyd, Feb 02 2024

a(7) onwards from Andrew Howroyd, Feb 02 2024

A369201 Number of unlabeled simple graphs with n vertices and n edges such that it is not possible to choose a different vertex from each edge (non-choosable).

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 7, 30, 124, 507, 2036, 8216, 33515, 138557, 583040, 2503093, 10985364, 49361893, 227342301, 1073896332, 5204340846, 25874724616, 131937166616, 689653979583, 3693193801069, 20247844510508, 113564665880028, 651138092719098, 3813739129140469

Offset: 0

Gus Wiseman, Jan 22 2024

nonn

These are graphs with n vertices and n edges having at least two cycles in the same component.

			The a(0) = 0 through a(6) = 7 simple graphs:
  .  .  .  .  .  {{12}{13}{14}{23}{24}}  {{12}{13}{14}{15}{23}{24}}
                                         {{12}{13}{14}{15}{23}{45}}
                                         {{12}{13}{14}{23}{24}{34}}
                                         {{12}{13}{14}{23}{24}{35}}
                                         {{12}{13}{14}{23}{24}{56}}
                                         {{12}{13}{14}{23}{25}{45}}
                                         {{12}{13}{14}{25}{35}{45}}

Andrew Howroyd, Table of n, a(n) for n = 0..50
Gus Wiseman, The a(6) = 7 unlabeled non-choosable graphs with 6 vertices and 6 edges.

Without the choice condition we have A001434, covering A006649.
The labeled version without choice is A116508, covering A367863, A367862.
The complement is counted by A137917, labeled A137916.
For any number of edges we have A140637, complement A134964.
For labeled set-systems we have A368600.
The case with loops is A368835, labeled A368596.
The labeled version is A369143, covering A369144.
A006129 counts covering graphs, unlabeled A002494.
A007716 counts unlabeled multiset partitions, connected A007718.
A054548 counts graphs covering n vertices with k edges, with loops A369199.
A129271 counts connected choosable simple graphs, unlabeled A005703.
Cf. A000088, A000612, A014068, A053530, A133686, A140638, A368601, A369141, A369146.

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],{2}],{n}],Select[Tuples[#],UnsameQ@@#&]=={}&]]],{n,0,5}]

a(n) = A001434(n) - A137917(n).

a(25) onwards from Andrew Howroyd, Feb 02 2024

A370644 Number of minimal subsets of {2..n} such that it is not possible to choose a different binary index of each element.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 4, 13, 13, 26, 56, 126, 243, 471, 812, 1438

Offset: 0

Gus Wiseman, Mar 11 2024

A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793.

			The a(0) = 0 through a(7) = 13 subsets:
  .  .  .  .  .  {2,3,4,5}  {2,4,6}    {2,4,6}
                            {2,3,4,5}  {2,3,4,5}
                            {2,3,5,6}  {2,3,4,7}
                            {3,4,5,6}  {2,3,5,6}
                                       {2,3,5,7}
                                       {2,3,6,7}
                                       {2,4,5,7}
                                       {2,5,6,7}
                                       {3,4,5,6}
                                       {3,4,5,7}
                                       {3,4,6,7}
                                       {3,5,6,7}
                                       {4,5,6,7}
The a(0) = 0 through a(7) = 13 set-systems:
  .  .  .  .  .  {2}{12}{3}{13}  {2}{3}{23}       {2}{3}{23}
                                 {2}{12}{3}{13}   {2}{12}{3}{13}
                                 {12}{3}{13}{23}  {12}{3}{13}{23}
                                 {2}{12}{13}{23}  {2}{12}{13}{23}
                                                  {2}{12}{3}{123}
                                                  {2}{3}{13}{123}
                                                  {12}{3}{13}{123}
                                                  {12}{3}{23}{123}
                                                  {2}{12}{13}{123}
                                                  {2}{12}{23}{123}
                                                  {2}{13}{23}{123}
                                                  {3}{13}{23}{123}
                                                  {12}{13}{23}{123}

The version with ones allowed is A370642, minimal case of A370637.
This is the minimal case of A370643.
A048793 lists binary indices, A000120 length, A272020 reverse, A029931 sum.
A070939 gives length of binary expansion.
A096111 gives product of binary indices.
A367902 counts choosable set-systems, ranks A367906, unlabeled A368095.
A367903 counts non-choosable set-systems, ranks A367907, unlabeled A368094.
A370585 counts maximal choosable sets.
Cf. A072639, A140637, A326031, A355529, A367905, A368109, A370589, A370591, A370636, A370639, A370640.

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
fasmin[y_]:=Complement[y,Union@@Table[Union[s,#]& /@ Rest[Subsets[Complement[Union@@y,s]]],{s,y}]];
Table[Length[fasmin[Select[Subsets[Range[2,n]], Select[Tuples[bpe/@#],UnsameQ@@#&]=={}&]]],{n,0,10}]

A369202 Number of unlabeled simple graphs covering n vertices such that it is not possible to choose a different vertex from each edge (non-choosable).

Original entry on oeis.org

0, 0, 0, 0, 2, 13, 95, 826, 11137, 261899, 11729360, 1006989636, 164072166301, 50336940172142, 29003653625802754, 31397431814146891910, 63969589218557753075156, 245871863137828405124380563, 1787331789281458167615190373076, 24636021675399858912682459601585276

Offset: 0

Gus Wiseman, Jan 23 2024

nonn

These are simple graphs covering n vertices such that some connected component has at least two cycles.

			Representatives of the a(4) = 2 and a(5) = 13 simple graphs:
  {12}{13}{14}{23}{24}      {12}{13}{14}{15}{23}{24}
  {12}{13}{14}{23}{24}{34}  {12}{13}{14}{15}{23}{45}
                            {12}{13}{14}{23}{24}{35}
                            {12}{13}{14}{23}{25}{45}
                            {12}{13}{14}{25}{35}{45}
                            {12}{13}{14}{15}{23}{24}{25}
                            {12}{13}{14}{15}{23}{24}{34}
                            {12}{13}{14}{15}{23}{24}{35}
                            {12}{13}{14}{23}{24}{35}{45}
                            {12}{13}{14}{15}{23}{24}{25}{34}
                            {12}{13}{14}{15}{23}{24}{35}{45}
                            {12}{13}{14}{15}{23}{24}{25}{34}{35}
                            {12}{13}{14}{15}{23}{24}{25}{34}{35}{45}

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

Without the choice condition we have A002494, labeled A006129.
The connected case is A140636.
This is the covering case of A140637, complement A134964.
The labeled version is A367868, complement A367869.
The complement is counted by A368834.
The version with loops is A369147, complement A369200.
A005703 counts unlabeled connected choosable simple graphs, labeled A129271.
A007716 counts unlabeled multiset partitions, connected A007718.
A054548 counts graphs covering n vertices with k edges, with loops A369199.
A283877 counts unlabeled set-systems, connected A300913.
Cf. A000088, A000612, A006649, A001434, A055621, A137916, A137917, A140638, A368596, A369141, A369146.

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],{2}]],Union@@#==Range[n] && Length[Select[Tuples[#],UnsameQ@@#&]]==0&]]],{n,0,5}]

First differences of A140637.

a(n) = A002494(n) - A368834(n).

A370643 Number of subsets of {2..n} such that it is not possible to choose a different binary index of each element.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 7, 23, 46, 113, 287, 680, 1546, 3374, 7191, 15008, 30016, 61013, 124354, 252577, 511229, 1031064, 2074281, 4164716, 8350912, 16729473, 33494928, 67034995, 134127390, 268325204, 536737665, 1073581062, 2147162124, 4294458549, 8589210382, 17178890873

Offset: 0

Gus Wiseman, Mar 10 2024

nonn

A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793.

			The a(0) = 0 through a(7) = 23 subsets:
  .  .  .  .  .  {2,3,4,5}  {2,4,6}      {2,4,6}
                            {2,3,4,5}    {2,3,4,5}
                            {2,3,4,6}    {2,3,4,6}
                            {2,3,5,6}    {2,3,4,7}
                            {2,4,5,6}    {2,3,5,6}
                            {3,4,5,6}    {2,3,5,7}
                            {2,3,4,5,6}  {2,3,6,7}
                                         {2,4,5,6}
                                         {2,4,5,7}
                                         {2,4,6,7}
                                         {2,5,6,7}
                                         {3,4,5,6}
                                         {3,4,5,7}
                                         {3,4,6,7}
                                         {3,5,6,7}
                                         {4,5,6,7}
                                         {2,3,4,5,6}
                                         {2,3,4,5,7}
                                         {2,3,4,6,7}
                                         {2,3,5,6,7}
                                         {2,4,5,6,7}
                                         {3,4,5,6,7}
                                         {2,3,4,5,6,7}

The case with ones allowed is A370637, differences A370589.
The minimal case is A370644, with ones A370642.
A048793 lists binary indices, A000120 length, A272020 reverse, A029931 sum.
A058891 counts set-systems, A003465 covering, A323818 connected.
A070939 gives length of binary expansion.
A096111 gives product of binary indices.
Cf. A072639, A326031, A355740, A367905, A368109.
Cf. A133686, A140637, A355529, A367867, A370583, A370636, A370640.

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
Table[Length[Select[Subsets[Range[2,n]], Select[Tuples[bpe/@#],UnsameQ@@#&]=={}&]],{n,0,10}]

More terms from Jinyuan Wang, Mar 28 2025

A368834 Number of unlabeled simple graphs covering n vertices such that it is possible to choose a different vertex from each edge (choosable).

Original entry on oeis.org

1, 0, 1, 2, 5, 10, 27, 62, 165, 423, 1140, 3060, 8427, 23218, 64782, 181370, 511004, 1444285, 4097996, 11656644, 33243265, 94992847, 271953126, 779790166, 2239187466, 6438039076, 18532004323, 53400606823, 154024168401, 444646510812, 1284682242777

Offset: 0

Gus Wiseman, Jan 23 2024

nonn

			Representatives of the a(2) = 1 through a(5) = 10 simple graphs:
  {12}  {12}{13}      {12}{34}          {12}{13}{45}
        {12}{13}{23}  {12}{13}{14}      {12}{13}{14}{15}
                      {12}{13}{24}      {12}{13}{14}{25}
                      {12}{13}{14}{23}  {12}{13}{23}{45}
                      {12}{13}{24}{34}  {12}{13}{24}{35}
                                        {12}{13}{14}{15}{23}
                                        {12}{13}{14}{23}{25}
                                        {12}{13}{14}{23}{45}
                                        {12}{13}{14}{25}{35}
                                        {12}{13}{24}{35}{45}

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

Without the choice condition we have A002494, labeled A006129.
The connected case is A005703, labeled A129271.
This is the covering case of A134964, complement A140637.
The labeled version is A367869, complement A367868.
The version with loops is A369200, complement A369147.
The complement is counted by A369202.
A007716 counts unlabeled multiset partitions, connected A007718.
A054548 counts graphs covering n vertices with k edges, with loops A369199.
A283877 counts unlabeled set-systems, connected A300913.
Cf. A000088, A006649, A001434, A055621, A116508, A133686, A137916, A137917, A368984, A369146.

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],{2}]],Union@@#==Range[n] && Length[Select[Tuples[#],UnsameQ@@#&]]!=0&]]],{n,0,5}]

Euler transform of A005703 with A005703(1) = 0.
First differences of A134964.
a(n) = A002494(n) - A369202(n).

A368532 Minimal numbers whose binary indices of binary indices contradict a strict version of the axiom of choice.

Original entry on oeis.org

7, 25, 30, 42, 45, 51, 53, 54, 60, 75, 77, 78, 83, 85, 86, 90, 92, 99, 101, 102, 105, 108, 113, 114, 116, 120, 385, 390, 408, 428, 434, 436, 458, 460, 466, 468, 482, 484, 488, 496, 642, 645, 668, 680, 689, 692, 713, 716, 721, 724, 728, 737, 740, 752, 771, 773

Offset: 1

Gus Wiseman, Dec 29 2023

nonn

Minimality is relative to the ordering where x < y means the binary indices of x are a subset of those of y (a Boolean algebra).
A binary index of n (row n of A048793) is any position of a 1 in its reversed binary expansion.
The axiom of choice says that, given any set of nonempty sets Y, it is possible to choose a set containing an element from each. The strict version requires this set to have the same cardinality as Y, meaning no element is chosen more than once.

			The terms the corresponding set-systems begin:
   7: {{1},{2},{1,2}}
  25: {{1},{3},{1,3}}
  30: {{2},{1,2},{3},{1,3}}
  42: {{2},{3},{2,3}}
  45: {{1},{1,2},{3},{2,3}}
  51: {{1},{2},{1,3},{2,3}}
  53: {{1},{1,2},{1,3},{2,3}}
  54: {{2},{1,2},{1,3},{2,3}}
  60: {{1,2},{3},{1,3},{2,3}}
  75: {{1},{2},{3},{1,2,3}}
  77: {{1},{1,2},{3},{1,2,3}}
  78: {{2},{1,2},{3},{1,2,3}}
  83: {{1},{2},{1,3},{1,2,3}}
  85: {{1},{1,2},{1,3},{1,2,3}}
  86: {{2},{1,2},{1,3},{1,2,3}}
  90: {{2},{3},{1,3},{1,2,3}}
  92: {{1,2},{3},{1,3},{1,2,3}}
  99: {{1},{2},{2,3},{1,2,3}}

The version for MM-numbers of multiset partitions is A368187.
A000110 counts set partitions.
A003465 counts covering set-systems, unlabeled A055621.
A058891 counts set-systems, unlabeled A000612, connected A323818.
A283877 counts non-isomorphic set-systems, connected A300913.
Cf. A007716, A134964, A355529, A367905, A367907.
Cf. A140637, A367867, A367903, A368094, A368097, A368413.

vmin[y_]:=Select[y,Function[s,Select[DeleteCases[y,s], SubsetQ[bpe[s],bpe[#]]&]=={}]];
Select[Range[100],Select[Tuples[bpe/@bpe[#]] ,UnsameQ@@#&]=={}&]//vmin

cp's OEIS Frontend

A369200 Number of unlabeled loop-graphs covering n vertices such that it is possible to choose a different vertex from each edge (choosable).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A369201 Number of unlabeled simple graphs with n vertices and n edges such that it is not possible to choose a different vertex from each edge (non-choosable).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A370644 Number of minimal subsets of {2..n} such that it is not possible to choose a different binary index of each element.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A369202 Number of unlabeled simple graphs covering n vertices such that it is not possible to choose a different vertex from each edge (non-choosable).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A370643 Number of subsets of {2..n} such that it is not possible to choose a different binary index of each element.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A368834 Number of unlabeled simple graphs covering n vertices such that it is possible to choose a different vertex from each edge (choosable).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A368532 Minimal numbers whose binary indices of binary indices contradict a strict version of the axiom of choice.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica