Number of q-ary strings of length m which do not contain k consecutive zeros 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}$?
 A: 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.
A: 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.  
 
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


*

*${\bbox[#dfd,5px]{\text{satisfies the recursion provided in *N. Shales*'s answer}}}$

*${\bbox[#dfd,5px]{\text{gives the terms of the z-transform provided in *Markus Scheuer*'s answer}}}$ .

A: 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?
