Skip to main content
5 of 5
edited tags
kodlu
  • 10.4k
  • 2
  • 36
  • 55

counting number of circulant subsequences

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.

Jeff
  • 87
  • 6