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,2

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}.

Links

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

Formula

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

Example

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.

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);

Crossrefs

Main diagonal of A376033.

Cf. A062383, A376697.

Sequence in context: A319210 A292303 A000936 * A319594 A065449 A130618

Adjacent sequences: A376088 A376089 A376090 * A376092 A376093 A376094

Keyword

nonn,base

Author

Alois P. Heinz, Sep 09 2024

Status

approved