cp's OEIS Frontend

A367907 Numbers n such that it is not possible to choose a different binary index of each binary index of n.

%I A367907 #15 Feb 11 2024 02:25:16
%S A367907 7,15,23,25,27,29,30,31,39,42,43,45,46,47,51,53,54,55,57,58,59,60,61,
%T A367907 62,63,71,75,77,78,79,83,85,86,87,89,90,91,92,93,94,95,99,101,102,103,
%U A367907 105,106,107,108,109,110,111,113,114,115,116,117,118,119,120,121
%N A367907 Numbers n such that it is not possible to choose a different binary index of each binary index of n.
%C A367907 Also BII-numbers of set-systems (sets of nonempty sets) contradicting a strict version of the axiom of choice.
%C A367907 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.
%C A367907 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.
%H A367907 John Tyler Rascoe, <a href="/A367907/b367907.txt">Table of n, a(n) for n = 1..10000</a>
%H A367907 Wikipedia, <a href="https://en.wikipedia.org/wiki/Axiom_of_choice">Axiom of choice</a>.
%F A367907 A367907 U A367908 U A367909 = A000027.
%e A367907 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.
%e A367907 The terms together with the corresponding set-systems begin:
%e A367907    7: {{1},{2},{1,2}}
%e A367907   15: {{1},{2},{1,2},{3}}
%e A367907   23: {{1},{2},{1,2},{1,3}}
%e A367907   25: {{1},{3},{1,3}}
%e A367907   27: {{1},{2},{3},{1,3}}
%e A367907   29: {{1},{1,2},{3},{1,3}}
%e A367907   30: {{2},{1,2},{3},{1,3}}
%e A367907   31: {{1},{2},{1,2},{3},{1,3}}
%e A367907   39: {{1},{2},{1,2},{2,3}}
%e A367907   42: {{2},{3},{2,3}}
%e A367907   43: {{1},{2},{3},{2,3}}
%e A367907   45: {{1},{1,2},{3},{2,3}}
%e A367907   46: {{2},{1,2},{3},{2,3}}
%e A367907   47: {{1},{2},{1,2},{3},{2,3}}
%e A367907   51: {{1},{2},{1,3},{2,3}}
%t A367907 bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
%t A367907 Select[Range[100], Select[Tuples[bpe/@bpe[#]], UnsameQ@@#&]=={}&]
%o A367907 (Python)
%o A367907 from itertools import count, islice, product
%o A367907 def bin_i(n): #binary indices
%o A367907     return([(i+1) for i, x in enumerate(bin(n)[2:][::-1]) if x =='1'])
%o A367907 def a_gen(): #generator of terms
%o A367907     for n in count(1):
%o A367907         p = list(product(*[bin_i(k) for k in bin_i(n)]))
%o A367907         x = len(p)
%o A367907         for j in range(x):
%o A367907             if len(set(p[j])) == len(p[j]): break
%o A367907             if j+1 == x: yield(n)
%o A367907 A367907_list = list(islice(a_gen(), 100)) # _John Tyler Rascoe_, Feb 10 2024
%Y A367907 These set-systems are counted by A367903, non-isomorphic A368094.
%Y A367907 Positions of zeros in A367905, firsts A367910, sorted A367911.
%Y A367907 The complement is A367906.
%Y A367907 If there is one unique choice we get A367908, counted by A367904.
%Y A367907 If there are multiple choices we get A367909, counted by A367772.
%Y A367907 A048793 lists binary indices, length A000120, reverse A272020, sum A029931.
%Y A367907 A058891 counts set-systems, covering A003465, connected A323818.
%Y A367907 A070939 gives length of binary expansion.
%Y A367907 A096111 gives product of binary indices.
%Y A367907 A326031 gives weight of the set-system with BII-number n.
%Y A367907 Cf. A000612, A055621, A072639, A083323, A309326, A326702, A326753, A367769, A367901, A367902, A367912.
%Y A367907 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).
%K A367907 nonn,base
%O A367907 1,1
%A A367907 _Gus Wiseman_, Dec 11 2023