2
$\begingroup$

Let us fix an alphabet $\Sigma$ of size $c$, then we have the finite language $\Sigma^n$ which is the set of all $n$ length words. For each $N,M$ how many words are there in $\Sigma^n$ such that no sequence of $N$ characters repeats $M$ times in a row?

For instance with N=2 and M=3 101010 would not be counted, but 111010 would be

Here is some data I found on it with a simulation:

c n N M total percent
2,4,2,2,10,0.625
2,5,2,2,16,0.5
2,6,2,2,26,0.40625
2,6,3,2,48,0.75
2,6,2,3,48,0.75
2,7,2,2,42,0.328125
2,7,3,2,88,0.6875
2,7,2,3,88,0.6875
2,8,2,2,68,0.265625
2,8,3,2,162,0.6328125
2,8,4,2,216,0.84375
2,8,2,3,162,0.6328125
2,8,2,4,216,0.84375
2,9,2,2,110,0.21484375
2,9,3,2,298,0.58203125
2,9,4,2,416,0.8125
2,9,2,3,298,0.58203125
2,9,3,3,416,0.8125
2,9,2,4,416,0.8125
2,10,2,2,178,0.173828125
2,10,3,2,548,0.53515625
2,10,4,2,802,0.783203125
2,10,5,2,928,0.90625
2,10,2,3,548,0.53515625
2,10,3,3,802,0.783203125
2,10,2,4,802,0.783203125
2,10,2,5,928,0.90625
3,4,2,2,66,0.8148148148148148
3,5,2,2,180,0.7407407407407407
3,6,2,2,492,0.6748971193415638
3,6,3,2,666,0.9135802469135802
3,6,2,3,666,0.9135802469135802
3,7,2,2,1344,0.6145404663923183
3,7,3,2,1944,0.8888888888888888
3,7,2,3,1944,0.8888888888888888
3,8,2,2,3672,0.5596707818930041
3,8,3,2,5676,0.8651120256058528
3,8,4,2,6318,0.9629629629629629
3,8,2,3,5676,0.8651120256058528
3,8,2,4,6318,0.9629629629629629
3,9,2,2,10032,0.509678402682518
3,9,3,2,16572,0.8419448254839201
3,9,4,2,18792,0.9547325102880658
3,9,2,3,16572,0.8419448254839201
3,9,3,3,18792,0.9547325102880658
3,9,2,4,18792,0.9547325102880658
3,10,2,2,27408,0.4641568866534573
3,10,3,2,48384,0.819387288523091
3,10,4,2,55896,0.9466036681400193
3,10,5,2,58158,0.9849108367626886
3,10,2,3,48384,0.819387288523091
3,10,3,3,55896,0.9466036681400193
3,10,2,4,55896,0.9466036681400193
3,10,2,5,58158,0.9849108367626886
4,4,2,2,228,0.890625
4,5,2,2,864,0.84375
4,6,2,2,3276,0.7998046875
4,6,3,2,3936,0.9609375
4,6,2,3,3936,0.9609375
4,7,2,2,12420,0.758056640625
4,7,3,2,15552,0.94921875
4,7,2,3,15552,0.94921875
4,8,2,2,47088,0.718505859375
4,8,3,2,61452,0.93768310546875
4,8,4,2,64704,0.9873046875
4,8,2,3,61452,0.93768310546875
4,8,2,4,64704,0.9873046875
4,9,2,2,178524,0.6810150146484375
4,9,3,2,242820,0.9262847900390625
4,9,4,2,258048,0.984375
4,9,2,3,242820,0.9262847900390625

The values seem to go to $c^n$ as $N,M$ increase and appear to be a function of $c$, $N+M$. It also seems to decrease as you increase $n$ and increase as you increase $c$. This all makes intuitive sense to me. If I had to guess I would say it is exponential in $n$, polynomial in $c$, and exponential in $N+M$

A secondary question I have is how would you represent the language defined by just the strings counted.

$\endgroup$
  • $\begingroup$ 1. What's your question? I didn't find a question in the body of your post. 2. Why is this a computer science question? It looks like pure math to me. Generally, we expect that questions here need to articulate a clear connection to computer science. If this is primarily a math question, I recommend flagging it for moderator attention to ask them to migrate it to Math.SE or MathOverflow. $\endgroup$ – D.W. May 19 '15 at 23:36
  • $\begingroup$ @D.W. The question is how many strings $n$ long are there without $M$ repetitions of $N$ characters. There is also the question of how would I write the language of these strings. I think it is a computer science question because it is about languages, but if it is deemed off-topic I'm fine with it being flagged for moving. $\endgroup$ – ruler501 May 20 '15 at 0:03
  • 2
    $\begingroup$ The answer will depend on $M,N,n$. So what are you looking for? A formula? Asymptotics? An approximation? An algorithm to compute it? It's not really about languages, in the computer science sense of computability theory; it's just about sequences of length $n$. $\endgroup$ – D.W. May 20 '15 at 5:29
  • 1
    $\begingroup$ What do you mean by "write this language"? Buzzword: square-free. $\endgroup$ – Raphael May 20 '15 at 7:46
  • $\begingroup$ @Raphael I mean something that shows me what form the words that match this criteria take. $\endgroup$ – ruler501 May 20 '15 at 12:00
2
$\begingroup$

For each particular $c,N,M$, this can be solved explicitly by constructing a DFA accepting the language. The general case may also be approached heuristically, though the dependency structure makes heuristic estimates harder to make.

The case $N = 1$ can be solved explicitly. Suppose that the alphabet is $\{0,\ldots,c-1\}$. Represent each word $w_1\ldots w_n$ as the sequence of differences $x_1\ldots x_n$, where $x_1 = w_1$ and $x_i = w_i - w_{i-1} \pmod{c}$ for $i > 1$. Your language then becomes $$ \epsilon + \{0,\ldots,c-1\}((\epsilon + 0 + \cdots + 0^{M-1})\{1,\ldots,c-1\})^*(\epsilon + 0 + \cdots + 0^{M-1}). $$ The corresponding generating function is $$ 1 + cx \cdot \frac{1}{1-\frac{x^M-1}{x-1}\cdot(c-1)x} \cdot \frac{x^M-1}{x-1} = \frac{x^{M+1}-1}{cx-1-(c-1)x^{M+1}}. $$ The asymptotic growth of the number of words is controlled by the smallest (in modulus) root of $(c-1)x^{M+1}-cx+1$. If this modulus is $\alpha$, then the growth rate of the sequence (under reasonable assumptions) is $\Theta((1/\alpha)^n)$.

Plotting a few of the polynomials $(c-1)x^{M+1}-cx+1$ reveals that there are two real roots in $[0,1]$. We are interested in the one near $1/c$. Suppose that $x=(1+\epsilon)/c$ is a root. Then $$ 1 = cx - (c-1)x^{M+1} = 1+\epsilon - \frac{c-1}{c^{M+1}} (1+\epsilon)^{M+1}, $$ and so $$ \epsilon = \frac{c-1}{c^{M+1}} (1+\epsilon)^{M+1}. $$ This shows that $\epsilon$ is exponentially small in terms of $M$, and so we can approximate $(1+\epsilon)^{M+1}$ by $1+(M+1)\epsilon$ to obtain the equation $$ \epsilon \approx \frac{c-1}{c^{M+1}}(1 + (M+1)\epsilon) $$ whose solution is $$ \epsilon \approx \frac{\frac{c-1}{c^{M+1}}}{1-(M+1)\frac{c-1}{c^{M+1}}} = \frac{c-1}{c^{M+1}-(c-1)(M+1)} \approx \frac{c-1}{c^{M+1}}. $$ Since $1/x = c/(1+\epsilon) \approx (1-\epsilon) c$, altogether we obtain that the number of words of length $n$ in which no symbol repeats $M$ times is $\Theta(\alpha^n)$, where $$ \alpha \approx c - \frac{c-1}{c^M}. $$

Carrying this sort of analysis for $N > 1$ seems significantly more difficult.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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