6
$\begingroup$

I'm interested in estimating the number of binary strings $(a_1, a_2, \dots, a_n)$ that avoid a specific type of structure. A specific example is the following: for any $k$, $(a_{k-3}, a_{k-2}, a_k, a_{k+2})\ne (0,0,1,0)$. One can visualize these objects as "combs", and when shifting a comb along the sequence we are not allowed to hit $(0,0,1,0)$.

If one were to remove the $a_{k-3}$ the problem has a simple solution with recursion, and asymptotics are not hard to obtain. I suspect that this can be bounded by probabilistic arguments. My guess is the answer should be $\Theta(c^n)$ for some constant $c$, and for the specific comb mentioned above I suspect $c\approx 15/8$. I'm more interested in a lower bound than an upper bound, for what it's worth.

I would appreciate if anyone could direct me to a solution to this and/or any literature on this type of problem.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Just write a recursion for $2^6 = 64$ variables determining the last $6$ numbers of the length $k$, then you will be basically raising a $64\times 64$ sized matrix and the $c$ will be its biggest eigenvalue. This is all very standard. $\endgroup$
    – Aleksei Kulikov
    Commented May 27 at 0:17
  • 1
    $\begingroup$ @AlekseiKulikov Good point, I oversimplified. I'm trying to avoid patterns of the form $(a_{k-t}, a_{k-s}, a_k, a_{k+s})$ for general $s,t$. When $s$ and $t$ are small fixed values this is easy, as you say. But I want to know more about what bounds we can get for general $s$ and $t$. $\endgroup$
    – TheBestMagician
    Commented May 27 at 0:38
  • 5
    $\begingroup$ There is a method called the Goulden-Jackson cluster method specifically for this purpose (enumerating languages avoiding specific subwords). $\endgroup$
    – Carl-Fredrik Nyberg Brodda
    Commented May 27 at 0:58
  • 2
    $\begingroup$ In particular, the GJ method shows for your example that $c$ is the reciprocal of the largest root of $x^4 - x^3 + 2x - 1$, or about $1.86676 \approx 15/8 = 1.875$, so your guess was close. This is a good exercise to do. The fact that $c$ is always algebraic follows immediately from formal language theory (it is easy to build a finite state automaton for your language). $\endgroup$
    – Carl-Fredrik Nyberg Brodda
    Commented May 27 at 1:11
  • $\begingroup$ To my credit, constructing a finite state automaton is essentially exactly what I suggested @Carl-FredrikNybergBrodda ... But it seems that the Goulden--Jackson method allows for a much smaller number of states. $\endgroup$
    – Aleksei Kulikov
    Commented May 27 at 1:35

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .