login
Number of binary words of length 2^n-1 with at least n "0" between any two "1" digits.
4

%I #22 Oct 04 2024 12:29:53

%S 1,2,4,14,106,3970,2951330,601479320126,4878266198984685082072,

%T 20251346657999168900614712784617499550822,

%U 2947350921470608599960387502833128388134614870362931531590353774089056633192

%N Number of binary words of length 2^n-1 with at least n "0" between any two "1" digits.

%H Alois P. Heinz, <a href="/A376697/b376697.txt">Table of n, a(n) for n = 0..14</a>

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

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

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

%F a(n) = 1 + Sum_{i=0..floor((2^n-2)/(n+1))} binomial(2^n-(n*i)-1,i+1). - _John Tyler Rascoe_, Oct 04 2024

%e a(0) = 1: the empty word.

%e a(1) = 2: 0, 1.

%e a(2) = 4: 000, 100, 010, 001.

%e a(3) = 14: 0000000, 1000000, 0100000, 0010000, 0001000, 0000100, 1000100, 0000010, 1000010, 0100010, 0000001, 1000001, 0100001, 0010001.

%o (Python)

%o from math import comb

%o def A376697(n): return 1 + sum(comb(2**n-(n*i)-1,i+1) for i in range(0,(2**n-2)//(n+1)+1)) # _John Tyler Rascoe_, Oct 04 2024

%Y Cf. A000225, A141539, A376033, A376091.

%K nonn

%O 0,2

%A _Alois P. Heinz_, Oct 02 2024