login
A367907
Numbers n such that it is not possible to choose a different binary index of each binary index of n.
60
7, 15, 23, 25, 27, 29, 30, 31, 39, 42, 43, 45, 46, 47, 51, 53, 54, 55, 57, 58, 59, 60, 61, 62, 63, 71, 75, 77, 78, 79, 83, 85, 86, 87, 89, 90, 91, 92, 93, 94, 95, 99, 101, 102, 103, 105, 106, 107, 108, 109, 110, 111, 113, 114, 115, 116, 117, 118, 119, 120, 121
OFFSET
1,1
COMMENTS
Also BII-numbers of set-systems (sets of nonempty sets) contradicting a strict version of the axiom of choice.
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 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
Wikipedia, Axiom of choice.
FORMULA
EXAMPLE
The set-system {{1},{2},{1,2},{1,3}} with BII-number 23 has choices (1,2,1,1), (1,2,1,3), (1,2,2,1), (1,2,2,3), but none of these has all different elements, so 23 is in the sequence.
The terms together with the corresponding set-systems begin:
7: {{1},{2},{1,2}}
15: {{1},{2},{1,2},{3}}
23: {{1},{2},{1,2},{1,3}}
25: {{1},{3},{1,3}}
27: {{1},{2},{3},{1,3}}
29: {{1},{1,2},{3},{1,3}}
30: {{2},{1,2},{3},{1,3}}
31: {{1},{2},{1,2},{3},{1,3}}
39: {{1},{2},{1,2},{2,3}}
42: {{2},{3},{2,3}}
43: {{1},{2},{3},{2,3}}
45: {{1},{1,2},{3},{2,3}}
46: {{2},{1,2},{3},{2,3}}
47: {{1},{2},{1,2},{3},{2,3}}
51: {{1},{2},{1,3},{2,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):
p = list(product(*[bin_i(k) for k in bin_i(n)]))
x = len(p)
for j in range(x):
if len(set(p[j])) == len(p[j]): break
if j+1 == x: yield(n)
A367907_list = list(islice(a_gen(), 100)) # John Tyler Rascoe, Feb 10 2024
CROSSREFS
These set-systems are counted by A367903, non-isomorphic A368094.
Positions of zeros in A367905, firsts A367910, sorted A367911.
The complement is A367906.
If there is one unique choice we get A367908, counted by A367904.
If there are multiple choices we get A367909, counted by A367772.
A048793 lists binary indices, length A000120, reverse A272020, sum A029931.
A058891 counts set-systems, covering A003465, connected A323818.
A070939 gives length of binary expansion.
A096111 gives product of binary indices.
A326031 gives weight of the set-system with BII-number n.
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: A128840 A041935 A041092 * A349233 A335512 A369375
KEYWORD
nonn,base
AUTHOR
Gus Wiseman, Dec 11 2023
STATUS
approved