login
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.
3

%I #17 Oct 02 2024 17:42:23

%S 1,2,4,4,12,11,17,14,81,57,81,61,260,126,236,106,5000,1623,2653,1181,

%T 6848,4751,2838,1286,42024,7526,14272,6416,55012,10422,21992,3970,

%U 12595401,1148865,2411809,268605,2146689,656872,1018489,186997,25401600,5147033,1567504

%N 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.

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

%H Alois P. Heinz, <a href="/A376091/b376091.txt">Table of n, a(n) for n = 0..1023</a>

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

%e 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.

%p h:= proc(n) option remember; `if`(n=0, 1, 2^(1+ilog2(n))) end:

%p b:= proc(n, k, t) option remember; `if`(n=0, 1, add(`if`(j=1 and

%p Bits[And](t, k)>0, 0, b(n-1, k, irem(2*t+j, h(k)))), j=0..1))

%p end:

%p a:= n-> b(n$2, 0):

%p seq(a(n), n=0..50);

%Y Main diagonal of A376033.

%Y Cf. A062383, A376697.

%K nonn,base

%O 0,2

%A _Alois P. Heinz_, Sep 09 2024