A376091 Number of binary words of length n avoiding distance (i+1) between "1" digits if the i-th bit is set in the binary representation of n.

1, 2, 4, 4, 12, 11, 17, 14, 81, 57, 81, 61, 260, 126, 236, 106, 5000, 1623, 2653, 1181, 6848, 4751, 2838, 1286, 42024, 7526, 14272, 6416, 55012, 10422, 21992, 3970, 12595401, 1148865, 2411809, 268605, 2146689, 656872, 1018489, 186997, 25401600, 5147033, 1567504

Offset: 0

Author

Alois P. Heinz, Sep 09 2024

Keywords

• nonn
• base

Comments

Also the number of subsets of [n] avoiding distance (i+1) between elements if the i-th bit is set in the binary representation of n. a(6) = 17: {}, {1}, {2}, {3}, {4}, {5}, {6}, {1,2}, {1,5}, {1,6}, {2,3}, {2,6}, {3,4}, {4,5}, {5,6}, {1,2,6}, {1,5,6}.

Examples

			a(6) = 17: 000000, 000001, 000010, 000011, 000100, 000110, 001000, 001100, 010000, 010001, 011000, 100000, 100001, 100010, 100011, 110000, 110001 because 6 = 110_2 and no two "1" digits have distance 2 or 3.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1023

Crossrefs

Main diagonal of A376033.

Cf. A062383, A376697.

Programs

Maple

h:= proc(n) option remember; `if`(n=0, 1, 2^(1+ilog2(n))) end:
b:= proc(n, k, t) option remember; `if`(n=0, 1, add(`if`(j=1 and
      Bits[And](t, k)>0, 0, b(n-1, k, irem(2*t+j, h(k)))), j=0..1))
    end:
a:= n-> b(n$2, 0):
seq(a(n), n=0..50);

Formula

a(2^n-1) = A376697(n).