5
$\begingroup$

A finite q-ary-alphabet is given $$A_q = {0,1,2,...,q-1}.$$ Now I am considering the set of all finite strings over the alphabet $A_q$.

I am interested on the number $$N(m,k)_{A_q}$$ of strings of length $m$ which do not contain $k$ consecutive zeros. Is there a general formulary for this number? Or how can I determine $N(m,k)_{A_q}$?

$\endgroup$
  • $\begingroup$ Thank you for accepting my answer but please consider accepting Markus' answer instead as he correctly found a mistake in my generating function (I missed a +1 term in the numerator). He has provided an alternative answer that I judge to be both correct and clear. $\endgroup$ – N. Shales Apr 2 '17 at 1:05
  • $\begingroup$ Also, you are right with your assumption that there is 1 empty word, I have amended my recurrence to include this case, sorry my answer was so messy, we all have good days and bad days I guess. $\endgroup$ – N. Shales Apr 2 '17 at 1:29
4
$\begingroup$

Omitting the suffix $A_q$.

If $X$ is a letter that belongs to our alphabet that is not $0$ then any such string length $m\ge k$ may begin in $k$ mutually exclusive and exhaustive ways

$$X\: [\text{sequence length $m-1$ with no $k$ consecutive $0$s}]$$ $$0X\: [\text{sequence length $m-2$ with no $k$ consecutive $0$s}]$$ $$00X\: [\text{sequence length $m-3$ with no $k$ consecutive $0$s}]$$ $$\vdots$$ $$\underbrace{000\cdots 0}_{k-1 \text{ times}}X\: [\text{sequence length $m-k$ with no $k$ consecutive $0$s}]$$

Then, since $X$ can take $q-1$ different letters, there are $(q-1)N(m-1,k)$ sequences of the first type, $(q-1)N(m-2,k)$ of the second type and so on we have the recurrence

$$N(m,k)=(q-1)\sum_{i=1}^{k}N(m-i,k)$$

with initial conditions

$$N(m,k)= q^m \qquad\text{for}\quad 0\le m \le k-1$$

It is also possible to derive the generating function $f(x)$ for this in several different ways

$$f(x)=\frac{1+x+x^2+\cdots +x^{k-1}}{1-(q-1)(x+x^2+\cdots +x^{k})}=\frac{1-x^k}{1-qx-(q-1)x^{k+1}}$$

One of the nicest is to see that this function "builds" such a sequence from the irreducible "blocks", where the enumerator $x$ has its index representing word length

$$\{1,\, 2,\ldots ,\, q-1,\, 01,\, 02,\ldots ,\, 0(q-1),\, 001,\, 002,\ldots ,\, 00(q-1),\ldots ,\, \underbrace{00\cdots 0}_{\text{$k-1$ times}}1,\, \underbrace{00\cdots 0}_{\text{$k-1$ times}}2,\ldots ,\, \underbrace{00\cdots 0}_{\text{$k-1$ times}}(q-1)\}$$

There $q-1$ blocks of each length $1$ to $k$, this accounts for the denominator term, but then any such sequence built from these blocks may terminate with $1,2,3\ldots ,k-1$ concurrent $0$s or the empty word $\epsilon$, this accounts for the numerator term.

$\endgroup$
  • 1
    $\begingroup$ @N.Younger: You're right, there is precisely one string of length $0$, the empty string, often denoted with $\varepsilon$. $\endgroup$ – Markus Scheuer Apr 1 '17 at 14:04
  • 1
    $\begingroup$ @N.Shales: The generating function seems to be incorrect. When taking $k=3,q=3,m=4$ we should obtain $76$, but $[x^4]f(x)=24$. $\endgroup$ – Markus Scheuer Apr 1 '17 at 19:07
  • 1
    $\begingroup$ @N.Shales: Markus' comment is right: also for $q=2$ your generating function is not correct, while that proposed by Markus checks vs. first few values of the parameters. $\endgroup$ – G Cab Apr 1 '17 at 21:02
  • 1
    $\begingroup$ @N.Shales: No worries, everything's fine. Your answer is very nice and there's no reason to change the acceptance. (+1) I just wanted to clarify the small inconsistency. Best regards, $\endgroup$ – Markus Scheuer Apr 2 '17 at 4:00
  • 1
    $\begingroup$ @N.Shales: I associate mine to Markus' appreciation: your answer is especially valuable for the recursion formula, which is fully correct as I could check through another approach as described in my answer. So, just amend the o.g.f.. $\endgroup$ – G Cab Apr 3 '17 at 15:31
3
$\begingroup$

Let me present another approach to this interesting problem, which will allow to get a closed expression for $N(m,k,q)$.

Let's consider a word of length $m$ from the binary alphabet $\{0,X\}$, having a total of $s$ zero's.

$$ \begin{array}{*{20}c} X &| & {0,} & {0,} & {0,} &| & X &| & 0 &| & {X,} & X &| & {0,} & 0 &| & X \\ 0 &| & {1,} & {2,} & {3,} &| & 0 &| & 1 &| & {0,} & {0,} &| & {1,} & 2 &| & 0 \\ \end{array} $$

Imagine to sequentially scan the word and count the number of consecutive zeros, resetting the counter when the character is different from $0$, as in the exaple above.
Then we can bi-ject each word with an hystogram which has :
- $j$ bars;
- sum of the bars equal $s$;
- $m-s$ Xs.

m_consec_0

Now, the number of ways to compose $j$ bars, summing to $s$, and with a heigth going from $1$ to max $r$ is given by $$ N_b (s - j,r - 1,j) = \text{No}\text{.}\,\text{of}\,\text{solutions}\,\text{to}\;\left\{ \begin{gathered} \text{0} \leqslant \text{integer}\;x_{\,j} \leqslant r - 1 \hfill \\ x_{\,1} + x_{\,2} + \; \cdots \; + x_{\,j} = s - j \hfill \\ \end{gathered} \right. $$ which is expressed by $$ \bbox[lightyellow] { \begin{gathered} N_b (s - j,r - 1,j)\quad \left| \begin{gathered} \;1 \leqslant \text{integer }r \hfill \\ \;0 \leqslant \text{integer}\;j \leqslant \text{integer }s \hfill \\ \end{gathered} \right.\quad = \hfill \\ = \sum\limits_{\left( {0\, \leqslant } \right)\,\,k\,\,\left( { \leqslant \,\frac{{s - j}} {{r - 1}}\, \leqslant \,j} \right)} {\left( { - 1} \right)^k \left( \begin{gathered} j \hfill \\ k \hfill \\ \end{gathered} \right)\left( \begin{gathered} s - 1 - k\,r \\ s - j - k\,r \\ \end{gathered} \right)} \hfill \\ \end{gathered} \tag{1} }$$ as explained in this post.

Then we can dispose the $m-s$ (undistinguishable) X place-holders and the $j$ (distinguishable) bars by
- reserving $j-1$ X's as separators between consecutive $0$ blocks
- putting the remaining X's in any of the $j+1$ interstices, thus in ${m-s+1} \choose{j}$ ways.

Finally we can compose the Xs in $(q-1)^{m-s}$ ways. We shall pay attention to that $j \leqslant s \leqslant \left\lceil {m/2} \right\rceil $

Thus the Number sought for, understood as the number of words which contains max $k-1$ consecutive zeros (in one or more runs) will be $$ \eqalign{ & N(m,k,q)\quad \left| \matrix{ \;1 \le {\rm integer }k,q \hfill \cr \;0 \le {\rm integer}\;m \hfill \cr} \right.\quad = \cr & = \sum\limits_{0\, \le \,\,s\,\, \le \,m} {\left( {q - 1} \right)^{\,m - s} \sum\limits_{0\, \le \,\,j\,\, \le \,s} {\left( \matrix{ m - s + 1 \cr j \cr} \right)\sum\limits_{\left( {0\, \le } \right)\,\,i\,\,\left( {\, \le \,j} \right)} {\left( { - 1} \right)^i \left( \matrix{ j \cr i \cr} \right)\left( \matrix{ s - 1 - i\,\left( {k - 1} \right) \cr s - j - i\,\left( {k - 1} \right) \cr} \right)} } } = \cr & = \sum\limits_{0\, \le \,\,s\,\, \le \,m} {\left( \matrix{ \left( {q - 1} \right)^{\,m - s} \quad \cdot \hfill \cr \sum\limits_{\left( {0\, \le } \right)\,\,i\,\,\left( {\, \le \,m - s + 1} \right)} {\left( { - 1} \right)^i \left( \matrix{ m - s + 1 \cr i \cr} \right)\sum\limits_{\left( {0\, \le } \right)\,\,j - i\,\,\left( { \le \,s - i} \right)} {\left( \matrix{ m - s + 1 - i \cr j - i \cr} \right)\left( \matrix{ s - 1 - i\,\left( {k - 1} \right) \cr s - i\,k - \left( {j - i} \right) \cr} \right)} } \hfill \cr} \right)} = \cr & = \sum\limits_{0\, \le \,\,s\,\, \le \,m} {\left( {q - 1} \right)^{\,m - s} \sum\limits_{\left( {0\, \le } \right)\,\,i\,\,\left( {\, \le \,m - s + 1} \right)} {\left( { - 1} \right)^i \left( \matrix{ m - s + 1 \cr i \cr} \right)\left( \matrix{ m - i\,k \cr s - i\,k \cr} \right)} } = \cr & = \sum\limits_{0\, \le \,\,s\,\, \le \,m} {\left( {q - 1} \right)^{\,m - s} \sum\limits_{\left( {0\, \le } \right)\,\,i\,\,\, \le \,m/k} {\left( { - 1} \right)^i \left( \matrix{ m - s + 1 \cr i \cr} \right)\left( \matrix{ m - i\,k \cr m - s \cr} \right)} } = \cr & = \sum\limits_{\left( {0\, \le } \right)\,\,i\,\,\, \le \,m/k} {\left( { - 1} \right)^{\,i} \sum\limits_{0\, \le \,\,m - s\,\, \le \,m} {\left( \matrix{ m - i\,k \cr m - s \cr} \right)\left( {\left( \matrix{ m - s \cr i \cr} \right) + \left( \matrix{ m - s \cr i - 1 \cr} \right)} \right)\left( {q - 1} \right)^{\,m - s} } } = \cr & = \sum\limits_{\left( {0\, \le } \right)\,\,i\,\,\, \le \,m/k} {\left( { - 1} \right)^{\,i} \left( {\left( \matrix{ m - i\,k \cr i \cr} \right)q^{\,m - i\,k - i} \left( {q - 1} \right)^{\,i} + \left( \matrix{ m - i\,k \cr i - 1 \cr} \right)q^{\,m - i\,k - i + 1} \left( {q - 1} \right)^{\,i - 1} } \right)} = \cr & = q^{\,m} \sum\limits_{\left( {0\, \le } \right)\,\,i\,\,\, \le \,m/k} {\left( {\left( \matrix{ m - i\,k \cr i \cr} \right)\left( {{{1 - q} \over {q^{\,k + 1} }}} \right)^{\,i} } \right)} - q^{\,m - k} \sum\limits_{\left( {0\, \le } \right)\,\,i\,\,\, \le \,\left( {m - k} \right)/k} {\left( {\left( \matrix{ m - k - i\,k \cr i \cr} \right)\left( {{{1 - q} \over {q^{\,k + 1} }}} \right)^{\,i} } \right)} = \cr & = q^{\,m} \sum\limits_{\left( {0\, \le } \right)\,\,i\,\,\left( {\, \le \,m/k} \right)} {\left( {\left( \matrix{ m - i\,k \cr m - i\,\left( {k + 1} \right) \cr} \right)\left( {{{1 - q} \over {q^{\,r + 1} }}} \right)^{\,i} } \right)} - q^{\,\left( {m - k} \right)} \sum\limits_{\left( {0\, \le } \right)\,\,i\,\,\,\left( { \le \,\left( {m - k} \right)/k} \right)} {\left( {\left( \matrix{ \left( {m - k} \right) - i\,k \cr \left( {m - k} \right) - i\,\left( {k + 1} \right) \cr} \right)\left( {{{1 - q} \over {q^{\,k + 1} }}} \right)^{\,i} } \right)} = \cr & = M(m,\;k,\;q) - M(m - k,\;k,\;q) \cr} $$ where:
- in the first passage we use the trinomial revision $\left( \matrix{ s \cr j \cr} \right)\left( \matrix{ j \cr n \cr} \right) = \left( \matrix{ s \cr n \cr} \right)\left( \matrix{ s - n \cr j - n \cr} \right)$
- in the sum in $s$ we use $\sum\limits_k {\left( \matrix{ n \cr k \cr} \right)\left( \matrix{ k \cr m \cr} \right)y^{\,k} } = \left( \matrix{ n \cr m \cr} \right)\left( {1 + y} \right)^{\,n - m} y^{\,m} $ obtainable from $$ \left( {1 + y + y} \right)^{\,n} = \sum\limits_{\left( {0\, \le } \right)\,\,k\,\,\left( {\, \le \,n} \right)} {\left( \matrix{ n \cr k \cr} \right)\left( {1 + y} \right)^{\,k} y^{\,n - k} } = \sum\limits_{\left( {0\, \le } \right)\,\,k\,\,\left( {\, \le \,n} \right)} {\sum\limits_{\left( {0\, \le } \right)\,\,j\,\,\left( {\, \le \,n} \right)} {\left( \matrix{ n \cr k \cr} \right)\left( \matrix{ k \cr j \cr} \right)y^{\,n - j} } } $$

In conclusion $$ \bbox[lightyellow] { \left\{ \matrix{ M(m,k,q) = q^{\,m} \sum\limits_{\left( {0\, \le } \right)\,\,i\,\,\left( {\, \le \,m/k} \right)} {\left( {\left( \matrix{ m - i\,k \cr m - i\,\left( {k + 1} \right) \cr} \right)\left( {{{1 - q} \over {q^{\,k + 1} }}} \right)^{\,i} } \right)} \hfill \cr N(m,k,q) = M(m,\;k,\;q) - M(m - k,\;k,\;q) \hfill \cr} \right.\quad \left| \matrix{ \;1 \le {\rm integer }k,q \hfill \cr \;0 \le {\rm integer}\;m \hfill \cr} \right. \tag{2} }$$

and it can be verified that the above expression

  1. ${\bbox[#dfd,5px]{\text{satisfies the recursion provided in *N. Shales*'s answer}}}$
  2. ${\bbox[#dfd,5px]{\text{gives the terms of the z-transform provided in *Markus Scheuer*'s answer}}}$ .
$\endgroup$
  • $\begingroup$ @G.Cab: I wouldn't consider a sum to be a closed expression, but your answer is in any case a very nice work. Thanks for the hint. (+1) $\endgroup$ – Markus Scheuer Apr 3 '17 at 16:14
  • $\begingroup$ @MarkusScheuer: well, I meant in the acception given in Wikipedia : "closed-form expression is a mathematical expression that can be evaluated in a finite number of operations" , but looks not to be of standard acceptance. $\endgroup$ – G Cab Apr 3 '17 at 18:04
  • $\begingroup$ Yes, there's no common agreement about it. I tend to be rather puristic, but it's not that important. :-) $\endgroup$ – Markus Scheuer Apr 3 '17 at 19:18
3
$\begingroup$

Here we are given a q-ary alphabet. We are asking for the number of words of length $m$ with character $0$ having runs at most length $k-1$.

Words with no consecutive equal characters at all are called Smirnov or Carlitz words. See example III.24 Smirnov words from Analytic Combinatorics by Philippe Flajolet and Robert Sedgewick for more information.

A generating function for the number of Smirnov words over a q-ary alphabet is given by \begin{align*} \left(1-\frac{qz}{1+z}\right)^{-1} \end{align*}

Replacing occurrences of $0$ in a Smirnov word by one up to $k-1$ zeros generates words having runs of $0$ with length less than $k$. \begin{align*}\ z\longrightarrow z+z^2+\cdots+z^{k-1}=\frac{z\left(1-z^{k-1}\right)}{1-z} \end{align*}

Since there are no restrictions to other characters we can replace each occurrence of these characters by one or more occurrences of it. \begin{align*} z\longrightarrow z+z^2+\cdots=\frac{z}{1-z} \end{align*}

The resulting generating function is \begin{align*} \left(1-\frac{(q-1)\frac{z}{1-z}}{1+\frac{z}{1-z}}-\frac{\frac{z\left(1-z^{k-1}\right)}{1-z}}{1+\frac{z\left(1-z^{k-1}\right)}{1-z}}\right)^{-1} &=\frac{1-z^k}{1-qz+(q-1)z^{k+1}} \end{align*}

Denoting with $[z^m]$ the coefficient of $z^m$ in a series we obtain the number of wanted words of length $m$ as \begin{align*} [z^m]\frac{1-z^k}{1-qz+(q-1)z^{k+1}} \end{align*}

Example: Let's look at an example. We take $A_q=\{0,1,2\}$ and $k=3$. We obtain with $q=3$ \begin{align*} \frac{1-z^3}{1-3z+2z^4}=1+3z+9z^2+26z^3+\color{blue}{76}z^4+222z^5+\cdots \end{align*}

The blue colored coefficient of $z^4$ shows there are $\color{blue}{76}$ words of length $4$ built from characters $\{0,1,2\}$ and runs of $0$ with length less than $k=3$. These words are listed lexicographically sorted below.

\begin{array}{cccccccccc} 0010&0110&0210&1011&1111&1211&2012&2112&2212\\ 0011&0111&0211&1012&1112&1212&2020&2120&2220\\ 0012&0112&0212&1020&1120&1220&2021&2121&2221\\ 0020&0120&0220&1021&1121&1221&2022&2122&2222\\ 0021&0121&0221&1022&1122&1222&2100&2200\\ 0022&0122&0222&1100&1200&2001&2101&2201\\ 0100&0200&1001&1101&1201&2002&2102&2202\\ 0101&0201&1001&1102&1202&2010&2110&2210\\ 0102&0202&1010&1110&1210&2011&2111&2211\\ \end{array}

[2017-10-22] Coefficients: We calculate the coefficients of the generating function in order to check OP's answer. We obtain

\begin{align*} \color{blue}{[z^m]}&\color{blue}{\frac{1-z^k}{1-qz+(q-1)z^{k+1}}}\\ &=[z^m](1-z^k)\sum_{j=0}^\infty\left(qz+(1-q)z^{k+1}\right)^j\tag{1}\\ &=[z^m]\sum_{j=0}^\infty z^j\left(q+(1-q)z^k\right)^j(1-z^k)\\ &=\sum_{j=0}^m [z^{m-j}]\left(q+(1-q)z^k\right)^j(1-z^k)\tag{2}\\ &=\sum_{j=0}^m [z^{j}]\left(q+(1-q)z^k\right)^{m-j}(1-z^k)\tag{3}\\ &=\sum_{j=0}^{\left\lfloor\frac{m}{k}\right\rfloor} [z^{kj}]\left(q+(1-q)z^k\right)^{m-kj}(1-z^k)\tag{4}\\ &=\sum_{j=0}^{\left\lfloor\frac{m}{k}\right\rfloor} [z^{kj}]\left(q+(1-q)z^k\right)^{m-kj} -\sum_{j=1}^{\left\lfloor\frac{m}{k}\right\rfloor} [z^{k(j-1)}]\left(q+(1-q)z^k\right)^{m-kj}\tag{5}\\ &=\sum_{j=0}^{\left\lfloor\frac{m}{k}\right\rfloor} q^{m-kj-j}(1-q)^j\binom{m-kj}{j} -\sum_{j=1}^{\left\lfloor\frac{m}{k}\right\rfloor}q^{m-kj-(j-1)}(1-q)^{j-1}\binom{m-kj}{j-1}\tag{6}\\ &\color{blue}{=q^m+\sum_{j=1}^{\left\lfloor\frac{m}{k}\right\rfloor} q^{m-(k+1)j} (1-q)^j\left[\binom{m-kj}{j}-\frac{q}{1-q}\binom{m-kj}{j-1}\right]}\tag{7} \end{align*} and OPs result follows easily from the representation (6).

Comment:

  • In (1) we use the geometric series expansion.

  • In (2) we apply the coefficient of operator rule $[z^{p-q}]A(z)=[z^p]z^qA(z)$ and restrict the upper limit of the series with $m$ since other summands do not contribute.

  • In (3) we change the order of summation $j\rightarrow m-j$.

  • In (4) we respect that only multiples of $k$ of the exponent of $z$ do contribute.

  • In (5) we factor out and note that the right hand sum starts with index $j=1$.

  • In (6) we select the coefficient of $z^{kj}$ resp. $z^{k(j-1)}$ accordingly.

  • In (7) we extract the summand with $j=0$ from the left-hand sum and collect both sums.

$\endgroup$
  • $\begingroup$ you might be interested to know that the coefficients of the o.g.f. you provided have a closed form expression, as explained in my answer. $\endgroup$ – G Cab Apr 3 '17 at 15:35
  • $\begingroup$ @Markus Scheuer: How do i explicitly compute the coefficients from the given generating function in the example? $\endgroup$ – N. Younger Jun 5 '17 at 14:18
  • $\begingroup$ @N.Younger: The same way as I calculated $A(z,t)$ in the other answer, namely using geometric series expansion. $\endgroup$ – Markus Scheuer Jun 5 '17 at 14:45
  • $\begingroup$ @MarkusScheuer: I am trying to extract the coefficients by using the geometric series expansion. But I always get a infinite formula. Could you show your way to get the formula in your example? Thank you! $\endgroup$ – N. Younger Jun 20 '17 at 8:31
  • 1
    $\begingroup$ @Markus Scheuer: Your hint (at least for q=2) is very good. I simulated the asymptotics in matlab and compared it with the exact numbers. Fortunately, the asymptotics are getting better for increasing $k$. In my case, I need to have an asymptotic behaviour which is smaller than the exact numbers. The asymptotics from the Flajolet-book are always greater than the exact number. :( $\endgroup$ – N. Younger Oct 19 '17 at 7:21
2
$\begingroup$

Based on Markus Scheuer's answer, I tried to derive a general formula for the asked number. The number of $q$-ary strings of length $m$ with no $k$ consecutive zeros is $$ N(m,k)_q = \sum_{j=0}^{\lfloor \frac{m}{k} \rfloor} \binom{m-kj}{j}(1-q)^j q^{m-(k+1)j} - \sum_{j=0}^{\lfloor \frac{m-k}{k} \rfloor} \binom{m-k-kj}{j}(1-q)^j q^{m-k-(k+1)j}, $$ where $1 \le k \le m$ is the constraint.

It would be nice, if some can confirm this formula. Is there a possibility to remove the constraint? So I would like to vary $m$ and $k$, even that the formula is valid for $ m \le k $. Or is it already general and the second sum is a "empty" sum if the upper limit is negative?

$\endgroup$
  • $\begingroup$ Your answer is correct. Nice work (+1). You may write the index range in both sums as $j\geq 0$ since the binomial coefficient $\binom{n}{j}=0$ if $j>n$ assured that $m-k\geq 0$. $\endgroup$ – Markus Scheuer Oct 22 '17 at 8:03

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.