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.
Best Answer
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.