A367907 - OEIS

A367907

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

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

(list; graph; refs; listen; history; text; internal format)

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

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

Wikipedia, Axiom of choice.

FORMULA

A367907 U A367908 U A367909 = A000027.

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.

Cf. A000612, A055621, A072639, A083323, A309326, A326702, A326753, A367769, A367901, A367902, 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: A128840 A041935 A041092 * A349233 A335512 A369375

Adjacent sequences: A367904 A367905 A367906 * A367908 A367909 A367910

KEYWORD

nonn,base

AUTHOR

Gus Wiseman, Dec 11 2023

STATUS

approved