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

1, 2, 4, 14, 106, 3970, 2951330, 601479320126, 4878266198984685082072, 20251346657999168900614712784617499550822, 2947350921470608599960387502833128388134614870362931531590353774089056633192

Offset: 0

Author

Alois P. Heinz, Oct 02 2024

Keywords

• nonn

Examples

			a(0) = 1: the empty word.
a(1) = 2: 0, 1.
a(2) = 4: 000, 100, 010, 001.
a(3) = 14: 0000000, 1000000, 0100000, 0010000, 0001000, 0000100, 1000100, 0000010, 1000010, 0100010, 0000001, 1000001, 0100001, 0010001.
		

Links

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

Crossrefs

Cf. A000225, A141539, A376033, A376091.

Programs

Python

from math import comb
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

Formula

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

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

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

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