Number of binary strings of length n with k adjacent ones

Question

Consider a space $H_n$ of binary strings of $n$ variables. Let $B(n,k)$ be the set of strings with $k$ ones having also an other one on the right, i.e.

$$B(n,k) = \{s \in H_n \, \, \, s.t. \, \, \, \sum^{n-1}_{i=0} s_{i} s_{|i+1|_n} = k \}, $$

where for simplicity I assumed also periodic boundaries with the modulus $n$. For instance, for $k=n$ this number must be $1$, for $k=n-1$ there are $n$ such strings...

Is it possible to know what is the cardinality of $B(n,k)$ exactly, or at least the functional dependence of $B(n,k)$ on $k$, fixed $n$? Or does it rescale to a known function when we divide by the total number of strings $2^n$ ?

P.S. The boundary condition is not essential. Solutions to the same problem, without boundary condition would be also well appreciated.

Answer 1

Let $C(n,k)$ be the number of strings of length $n$ having $k$ ones with another $1$ on the left, ending in $1$ and $D(n,k)$ be the number of strings of length $n$ having $k$ ones with another $1$ on the left, ending in $0$. Then $B(n,k)=C(n,k)+D(n,k)$ and you have recurrences $C(n,k)=C(n-1,k-1)+D(n-1,k), D(n,k)=C(n-1,k)+D(n-1,k), D(1,0)=1, C(1,0)=1$. This avoids any periodic boundary-it uses linear strings. I ran some numbers but didn't see an obvious relation.

Answer 2

By mere counting, the number $B(n,k)$ (without the periodic boundary) is given by

$$B(n,k)=2\, T(n,k,0) + T(n,k,1) + T(n,k,-1)\approx 4 \,T(n,k,0)$$

with

$$T(n,k,e) =\sum_{j}{k +j -1 \choose j-1}{n-k -j -1 \choose j-1 +e}$$

with the appropiate limits for the index of summation.

I've checked this agrees with Ross Millikan's answer. Some values:

$B(8,5)=9\\B(27,11)=5160560\\B(100,20)=67984278293083430807186562176$

I doubt this can be simplified more, even in its approximate form. For large values of $n,k$, we'd be looking for asymptotics for sum of the form

$$\sum_{j=0}^{b/2} {a +j \choose j}{b - j \choose j}$$

which seems an interesting problem in itself, but, again, it does not look straightforward.