A367906 Numbers k such that it is possible to choose a different binary index of each binary index of k.

1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 14, 16, 17, 18, 19, 20, 21, 22, 24, 26, 28, 32, 33, 34, 35, 36, 37, 38, 40, 41, 44, 48, 49, 50, 52, 56, 64, 65, 66, 67, 68, 69, 70, 72, 73, 74, 76, 80, 81, 82, 84, 88, 96, 97, 98, 100, 104, 112, 128, 129, 130, 131, 132

Offset

1,2

Comments

Also BII-numbers of set-systems (sets of nonempty sets) satisfying a strict version of the axiom of choice.

A binary index of k (row k 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 k to be obtained by taking the binary indices of each binary index of k. Every finite set of finite nonempty sets has a different BII-number. For example, 18 has reversed binary digits (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 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.

Links

John Tyler Rascoe, Table of n, a(n) for n = 1..10000

Wikipedia, Axiom of choice.

Example

The set-system {{2,3},{1,2,3},{1,4}} with BII-number 352 has choices such as (2,1,4) that satisfy the axiom, so 352 is in the sequence.
The terms together with the corresponding set-systems begin:
   1: {{1}}
   2: {{2}}
   3: {{1},{2}}
   4: {{1,2}}
   5: {{1},{1,2}}
   6: {{2},{1,2}}
   8: {{3}}
   9: {{1},{3}}
  10: {{2},{3}}
  11: {{1},{2},{3}}
  12: {{1,2},{3}}
  13: {{1},{1,2},{3}}
  14: {{2},{1,2},{3}}
  16: {{1,3}}
  17: {{1},{1,3}}

Mathematica

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n, 2]], 1];
Select[Range[100], Select[Tuples[bpe/@bpe[#]], UnsameQ@@#&]!={}&]

Prog

(Python)
from itertools import count, islice, product
def bin_i(n): #binary indices
    return([(i+1) for i, x in enumerate(bin(n)[2:][::-1]) if x =='1'])
def a_gen(): #generator of terms
    for n in count(1):
        for j in list(product(*[bin_i(k) for k in bin_i(n)])):
            if len(set(j)) == len(j):
                yield(n); break
A367906_list = list(islice(a_gen(), 100)) # John Tyler Rascoe, Dec 23 2023

Crossrefs

These set-systems are counted by A367902, non-isomorphic A368095.

Positions of positive terms in A367905, firsts A367910, sorted A367911.

The complement is A367907.

If there is one unique choice we get A367908, counted by A367904.

If there are multiple choices we get A367909, counted by A367772.

Unlabeled multiset partitions of this type are A368098, complement A368097.

A version for MM-numbers of multisets is A368100, complement A355529.

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, A055621, A059519, A072639, A083323, A309326, A326702, A326753, A367770, A367912.

BII-numbers: A309314 (hyperforests), A326701 (set partitions), A326703 (chains), A326704 (antichains), A326749 (connected), A326750 (clutters), A326751 (blobs), A326752 (hypertrees), A326754 (covers), A326783 (uniform), A326784 (regular), A326788 (simple), A330217 (achiral).

Sequence in context: A292638 A000378 A335513 * A022551 A172251 A286997

Adjacent sequences: A367903 A367904 A367905 * A367907 A367908 A367909

Keyword

base,nonn

Author

Gus Wiseman, Dec 11 2023

Status

approved