6
$\begingroup$

How many binary cyclic sequences of length $n$ exist, where ones only appear in blocks of length at least $k$? We do not consider sequences that result from each other by a cyclic shift equivalent.

Example: Let $n=6$ and $k=2$, i.e. we have no isolated one. Then
[0,0,0,0,0,0]
[1,1,0,0,0,0] and 5 cyclic shifts of it
[1,1,1,0,0,0] and 5 cyclic shifts of it
[1,1,1,1,0,0] and 5 cyclic shifts of it
[1,1,0,1,1,0] and 2 cyclic shifts of it
[1,1,1,1,1,0] and 5 cyclic shifts of it
[1,1,1,1,1,1]
are all of the 29 possible sequences.
The case $k=2$ is covered by https://oeis.org/A109377

$\endgroup$
4
  • 1
    $\begingroup$ motivation? what do you got so far? $\endgroup$ Sep 8, 2014 at 21:04
  • 2
    $\begingroup$ The question comes from counting the size of certain ideals in the polynomial ring $R[x]/(x^n+1)$ where $R$ is the boolean semifield. I was hoping someone could point me in the right direction, since this is not a typical necklace problem with equivalence under a group of permutations. $\endgroup$
    – Oliver
    Sep 8, 2014 at 21:08
  • $\begingroup$ This seems the language of a shift of finite type if I understood correctly. So it should have a rational generating function which is ok to compute. $\endgroup$ Sep 9, 2014 at 0:32
  • $\begingroup$ Actually it seems the language of periods for a shift of finite type but this still has a rational generating function. $\endgroup$ Sep 9, 2014 at 1:01

1 Answer 1

6
$\begingroup$

Consider the monoid $M_k$ in the generators $A_k=\lbrace 0, 01^k, 01^{k+1}, 01^{k+2},...\rbrace$, where $1^r$ denotes a string of $r$ ones. This contains all binary sequences with no strings of 1's of length less than $k$, except for the words $1^r$ for $r\geq k$. The monoid $M_k$ is freely generated by $A_k$. Hence if $$ F_k(x) = x+x^{k+1}+x^{k+2}+\cdots = x+\frac{x^{k+1}}{1-x}, $$ then the generating function for the number of words of length $n$ in $M_k$ is $$ G_k(x) = \frac{1}{1-F_k(x)}. $$ It is easy to check that $M_k$ is in fact very pure in the sense of Section 4.7.4 of Enumerative Combinatorics, vol. 1, second ed. Thus by Proposition 4.7.13, the generating function for cyclic words is \begin{eqnarray*} H_k(x) & = &\frac{xF'_k(x)}{1-F_k(x)}\\ & = & \frac{x(1-2x+x^2+(k+1)x^k-kx^{k+1})}{(1-x)(1-2x+x^2-x^{k+1})}. \end{eqnarray*} To account for the words $1^r$, we merely need to add $x^k/(1-x)$ to $H_k(x)$.

$\endgroup$
1
  • 1
    $\begingroup$ You beat me by a millisecond. But I'll make a little routine contribution. To get the asymptotics, find the smallest zero $x=\rho_k$ of the denominator (in (0,1/2) for $k\ge 2$) and also $c_k=\lim_{x\to\rho_k} (1-x/\rho_k) H_k(x)$. Then the $n$th coefficient is asymptotic to $c_k \rho_k^{-n}$ for fixed $k$. $\endgroup$ Sep 9, 2014 at 1:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.