Number of binary strings of length n with k adjacent ones 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. 
 A: 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.
A: 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.
A: It can also be expressed like this:
Let CB(n, k) be the number of binary strings of length n with k adjacent ones (n >= k + 1).
For k = 0, it is defined as Fibonacci:
CB(n, 0) = CB(n-1, 0) + CB(n-2, 0)
CB(1, 0) = 2, CB(2, 0) = 3
For k > 0, it is defined like this:
CB(n, k) = CB(n-1, k) + CB(n-2, k) + CB(n-1, k-1) - CB(n-2, k-1)
CB(k+1, k) = 1, CB(k+2, k) = 2
For me it was easier way to write (iterative) algorithm with O((k+1)*(n-k)) time complexity, and O(3*k) memory usage. I have found this question in search for better algorithm. I hear it can be calculated in O(n-k).
If somebody is interested, I could try to write good explanation.
