counting number of circulant subsequences

Question

Let $k\ge1$ and $m\ge1$ be given integers. For any $x=(x_1,\ldots,x_k)\in\{\pm 1\}^k$, define $f(x)=\#\{1\le j\le k: x_j=x_{j+1}=\cdots=x_{j+m-1}\}$. Question: given $0\le l\le k$, for how many $x\in\{\pm 1\}^k$ does $f(x)=l$? Here, for notation simplicity, let $x_{k+1}=x_1,x_{k+2}=i_2,\ldots,x_{k+m-1}=x_{m-1}$.

For example, suppose $k=4$ and $m=3$, if $x=(+1,+1,+1,+1)$ or $x=(-1,-1,-1,-1)$, then $f(x)=4$; if $x=(+1,+1,+1,-1)$, then $f(x)=1$. There are two $x$'s such that $f(x)=4$, eight $x$'s such that $f(x)=1$, and six $x$'s such that $f(x)=0$.

It would be great to have a general and explicit formula for the number of $x\in\{\pm 1\}^k$ such that $f(x)=l$, and the formula should depend on $m,k,l$. Or some references that could help? Thank you.

Answer 1

What you can use is Polya's theory of counting, for alphabet size $k=2.$

An $(n, k)−$necklace is an equivalence class of words of length $n$ over an alphabet of size $k$ under rotation. The basic enumeration problem is:

For a given $n$ and $k,$ how many $(n, k)-$necklaces are there? Equivalently, we are asking how many orbits the cyclic group $C_n$ has on the set of all words of length $n$ over an alphabet of size $k.$ Denote this value by $a(n, k).$

Theorem:

$$a(n,k)=\frac{1}{n}\sum_{d|n} \phi(d) k^{n/d}.$$

Have fun!

Edit: In case it is unclear, you want the orbit sizes of each one of these equivalence classes.