A367770 -id:A367770 - cp's OEIS frontend

A367904 Number of sets of nonempty subsets of {1..n} with only one possible way to choose a sequence of different vertices of each edge.

1, 2, 6, 38, 666, 32282, 3965886, 1165884638, 792920124786, 1220537093266802, 4187268805038970806, 31649452354183112810198, 522319168680465054600480906, 18683388426164284818805590810122, 1439689660962836496648920949576152046, 237746858936806624825195458794266076911118

Offset: 0

Gus Wiseman, Dec 08 2023

nonn

			The set-system Y = {{1},{1,2},{2,3}} has choices (1,1,2), (1,1,3), (1,2,2), (1,2,3), of which only (1,2,3) has all different elements, so Y is counted under a(3).
The a(0) = 1 through a(2) = 6 set-systems:
  {}  {}     {}
      {{1}}  {{1}}
             {{2}}
             {{1},{2}}
             {{1},{1,2}}
             {{2},{1,2}}

Christian Sievers, Table of n, a(n) for n = 0..77

The maximal case (n subsets) is A003024.
The version for at least one choice is A367902.
The version for no choices is A367903, no singletons A367769, ranks A367907.
These set-systems have ranks A367908, nonzero A367906.
A000372 counts antichains, covering A006126, nonempty A014466.
A003465 counts covering set-systems, unlabeled A055621.
A058891 counts set-systems, unlabeled A000612.
A059201 counts covering T_0 set-systems.
A323818 counts covering connected set-systems, unlabeled A323819.
Cf. A102896, A133686, A283877, A306445, A355741, A367770, A367862, A367869, A367901, A367905.

Table[Length[Select[Subsets[Subsets[Range[n]]], Length[Select[Tuples[#],UnsameQ@@#&]]==1&]],{n,0,3}]

a(n) = A367902(n) - A367772(n). - Christian Sievers, Jul 26 2024

Binomial transform of A003024. - Christian Sievers, Aug 12 2024

a(5)-a(8) from Christian Sievers, Jul 26 2024

More terms from Christian Sievers, Aug 12 2024

A367769 Number of finite sets of nonempty non-singleton subsets of {1..n} contradicting a strict version of the axiom of choice.

Original entry on oeis.org

0, 0, 0, 1, 1490, 67027582, 144115188036455750, 1329227995784915872903806998967001298, 226156424291633194186662080095093570025917938800079226639565284090686126876

Offset: 0

Gus Wiseman, Dec 05 2023

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.

Includes all set-systems with more edges than covered vertices, but this condition is not sufficient.

			The a(3) = 1 set-system is: {{1,2},{1,3},{2,3},{1,2,3}}.

Wikipedia, Axiom of choice.

Set-systems without singletons are counted by A016031, covering A323816.
The complement is A367770, with singletons allowed A367902 (ranks A367906).
The version for simple graphs is A367867, covering A367868.
The version allowing singletons and empty edges is A367901.
The version allowing singletons is A367903, ranks A367907.
A000372 counts antichains, covering A006126, nonempty A014466.
A003465 counts covering set-systems, unlabeled A055621.
A058891 counts set-systems, unlabeled A000612.
A059201 counts covering T_0 set-systems.
A323818 counts covering connected set-systems.
Cf. A007716, A092918, A102896, A283877, A306445, A326031, A355739, A355740, A355741, A367904, A367905.

Table[Length[Select[Subsets[Select[Subsets[Range[n]], Length[#]>1&]], Select[Tuples[#], UnsameQ@@#&]=={}&]], {n,0,3}]

a(n) = 2^(2^n-n-1) - A367770(n) = A016031(n+1) - A367770(n). - Christian Sievers, Jul 28 2024

a(6)-a(8) from Christian Sievers, Jul 28 2024

A368600 Number of ways to choose a set of n nonempty subsets of {1..n} such that it is not possible to choose a different element from each.

Original entry on oeis.org

0, 0, 0, 3, 164, 18625, 5491851, 4649088885, 12219849683346

Offset: 0

Gus Wiseman, Jan 01 2024

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 a(3) = 3 set-systems:
  {{1},{2},{1,2}}
  {{1},{3},{1,3}}
  {{2},{3},{2,3}}

Wikipedia, Axiom of choice.

For a unique choice we have A003024, any length A367904 (ranks A367908).
Sets of n nonempty subsets of {1..n} are counted by A136556.
For any length we have A367903, ranks A367907, no singletons A367769.
The complement is A368601, any length A367902 (see also A367770, A367906).
A000372 counts antichains, covering A006126, nonempty A014466.
A003465 counts covering set-systems, unlabeled A055621.
A058891 counts set-systems, unlabeled A000612.
A059201 counts covering T_0 set-systems.
A323818 counts covering connected set-systems, unlabeled A323819.
Cf. A003025, A088957, A133686, A334282, A355529, A355740, A367862, A367867, A367868, A367901, A368094, A368097.

Table[Length[Select[Subsets[Rest[Subsets[Range[n]]], {n}],Length[Select[Tuples[#], UnsameQ@@#&]]==0&]],{n,0,3}]

from itertools import combinations, product, chain
from scipy.special import comb
def v(c):
    for elements in product(*c):
        if len(set(elements)) == len(elements):
            return True
    return False
def a(n):
    if n == 0:
        return 1
    subsets = list(chain.from_iterable(combinations(range(1, n + 1), r) for r in range(1, n + 1)))
    cs = combinations(subsets, n)
    c = sum(1 for c in cs if v(c))
    return c
[print(int(comb(2**n-1,n) - a(n))) for n in range(7)] # Robert P. P. McKone, Jan 02 2024

a(n) = A136556(n) - A368601(n).

a(6) from Robert P. P. McKone, Jan 02 2024

a(7)-a(8) from Christian Sievers, Jul 25 2024

A368601 Number of ways to choose a set of n nonempty subsets of {1..n} such that it is possible to choose a different element from each.

Original entry on oeis.org

1, 1, 3, 32, 1201, 151286, 62453670, 84707326890, 384641855115279

Offset: 0

Gus Wiseman, Jan 01 2024

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 a(2) = 3 set-systems:
  {{1},{2}}
  {{1},{1,2}}
  {{2},{1,2}}
Non-isomorphic representatives of the a(3) = 32 set-systems:
  {{1},{2},{3}}
  {{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}}

Wikipedia, Axiom of choice.

For a unique choice we have A003024, any length A367904 (ranks A367908).
Sets of n nonempty subsets of {1..n} are counted by A136556.
For any length we have A367902, ranks A367906, no singletons A367770.
The complement is A368600, any length A367903 (see also A367907, A367769).
A000372 counts antichains, covering A006126, nonempty A014466.
A003465 counts covering set-systems, unlabeled A055621.
A058891 counts set-systems, unlabeled A000612.
A059201 counts covering T_0 set-systems.
A323818 counts covering connected set-systems, unlabeled A323819.
Cf. A003025, A088957, A133686, A334282, A355529, A355740, A367862, A367867, A367901, A367905, A368094, A368097.

Table[Length[Select[Subsets[Rest[Subsets[Range[n]]], {n}],Length[Select[Tuples[#], UnsameQ@@#&]]>0&]],{n,0,3}]

from itertools import combinations, product, chain
def v(c):
    for elements in product(*c):
        if len(set(elements)) == len(elements):
            return True
    return False
def a(n):
    if n == 0:
        return 1
    subsets = list(chain.from_iterable(combinations(range(1, n + 1), r) for r in
range(1, n + 1)))
    cs = combinations(subsets, n)
    c = sum(1 for c in cs if v(c))
    return c
[print(a(n)) for n in range(7)] # Robert P. P. McKone, Jan 02 2024

a(n) + A368600(n) = A136556(n).

a(6) from Robert P. P. McKone, Jan 02 2024

a(7)-a(8) from Christian Sievers, Jul 25 2024

A367916 Number of sets of nonempty subsets of {1..n} with the same number of edges as covered vertices.

Original entry on oeis.org

1, 2, 6, 45, 1376, 161587, 64552473, 85987037645, 386933032425826, 6005080379837219319, 328011924848834642962619, 64153024576968812343635391868, 45547297603829979923254392040011994, 118654043008142499115765307533395739785599

Offset: 0

Gus Wiseman, Dec 08 2023

nonn

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

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

The covering case is A054780.
For graphs we have A367862, covering A367863, unlabeled A006649.
These set-systems have ranks A367917.
A000372 counts antichains, covering A006126, nonempty A014466.
A003465 counts set-systems covering {1..n}, unlabeled A055621.
A058891 counts set-systems, unlabeled A000612.
A059201 counts covering T_0 set-systems.
A136556 counts set-systems on {1..n} with n edges.
Cf. A092918, A102896, A133686, A306445, A323818, A355740, A367770, A367869, A367901, A367902, A367905.

Table[Length[Select[Subsets[Rest[Subsets[Range[n]]]], Length[Union@@#]==Length[#]&]],{n,0,3}]

\\ Here b(n) is A054780(n).
b(n) = sum(k=0, n, (-1)^(n-k) * binomial(n,k) * binomial(2^k-1, n))
a(n) = sum(k=0, n, binomial(n,k) * b(k)) \\ Andrew Howroyd, Dec 29 2023

Binomial transform of A054780.

A367772 Number of sets of nonempty subsets of {1..n} satisfying a strict version of the axiom of choice in more than one way.

Original entry on oeis.org

0, 0, 1, 23, 1105, 154941, 66072394, 88945612865, 396990456067403

Offset: 0

Gus Wiseman, Dec 12 2023

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.

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

Wikipedia, Axiom of choice.

For at least one choice we have A367902.
For no choices we have A367903, no singletons A367769, ranks A367907.
For a unique choice we have A367904, ranks A367908.
These set-systems have ranks A367909.
A000372 counts antichains, covering A006126, nonempty A014466.
A003465 counts covering set-systems, unlabeled A055621.
A058891 counts set-systems, unlabeled A000612.
Cf. A059201, A102896, A133686, A283877, A306445, A323818, A355741, A367770, A367862, A367869, A367901, A367905.

Table[Length[Select[Subsets[Subsets[Range[n]]], Length[Select[Tuples[#], UnsameQ@@#&]]>1&]], {n,0,3}]

A367903(n) + A367904(n) + a(n) = A058891(n).

a(5)-a(8) from Christian Sievers, Jul 26 2024

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[#]]&]

A370639 Number of subsets of {1..n} containing n such that it is possible to choose a different binary index of each element.

Original entry on oeis.org

0, 1, 2, 3, 7, 10, 15, 22, 61, 81, 112, 154, 207, 276, 355, 464, 1771, 2166, 2724, 3445, 4246, 5292, 6420, 7922, 9586, 11667, 13768, 16606, 19095, 22825, 26498, 31421, 187223, 213684, 247670, 289181, 331301, 385079, 440411, 510124, 575266, 662625, 747521

Offset: 0

Gus Wiseman, Mar 08 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(6) = 15 subsets:
  .  {1}  {2}    {3}    {4}      {5}      {6}
          {1,2}  {1,3}  {1,4}    {1,5}    {1,6}
                 {2,3}  {2,4}    {2,5}    {2,6}
                        {3,4}    {3,5}    {3,6}
                        {1,2,4}  {4,5}    {4,6}
                        {1,3,4}  {1,2,5}  {5,6}
                        {2,3,4}  {1,3,5}  {1,2,6}
                                 {2,3,5}  {1,3,6}
                                 {2,4,5}  {1,4,6}
                                 {3,4,5}  {1,5,6}
                                          {2,3,6}
                                          {2,5,6}
                                          {3,4,6}
                                          {3,5,6}
                                          {4,5,6}

Wikipedia, Axiom of choice.

Simple graphs of this type are counted by A133686, covering A367869.
Unlabeled graphs of this type are counted by A134964, complement A140637.
Simple graphs not of this type are counted by A367867, covering A367868.
Set systems of this type are counted by A367902, ranks A367906.
Set systems not of this type are counted by A367903, ranks A367907.
Set systems uniquely of this type are counted by A367904, ranks A367908.
Unlabeled multiset partitions of this type are A368098, complement A368097.
A version for MM-numbers of multisets is A368100, complement A355529.
Factorizations of this type are A368414/A370814, complement A368413/A370813.
For prime instead of binary indices we have A370586, differences of A370582.
The complement for prime indices is A370587, differences of A370583.
The complement is counted by A370589, differences of A370637.
Partial sums are A370636.
The complement has partial sums A370637/A370643, minima A370642/A370644.
The case of a unique choice is A370641, differences of A370638.
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.
A326031 gives weight of the set-system with BII-number n.
Cf. A000612, A326702, A355739, A355740, A367770, A367772, A367905, A367909, A367912, A368094, A368095, A368109, A370640.

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

First differences of A370636.

a(19)-a(42) from Alois P. Heinz, Mar 09 2024

cp's OEIS Frontend

A367904 Number of sets of nonempty subsets of {1..n} with only one possible way to choose a sequence of different vertices of each edge.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A367769 Number of finite sets of nonempty non-singleton subsets of {1..n} contradicting a strict version of the axiom of choice.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A368600 Number of ways to choose a set of n nonempty subsets of {1..n} such that it is not possible to choose a different element from each.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A368601 Number of ways to choose a set of n nonempty subsets of {1..n} such that it is possible to choose a different element from each.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A367916 Number of sets of nonempty subsets of {1..n} with the same number of edges as covered vertices.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A367772 Number of sets of nonempty subsets of {1..n} satisfying a strict version of the axiom of choice in more than one way.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Crossrefs