0
$\begingroup$

Let $S(a,b,c): = \#\{a$-nary sequences of length $b$ without $c$ consecutive occurrences of a digit$\}$.

For example, $S(2,n,3)$ would be the number of binary sequences of length $n$ without $3$ consecutive occurences of a $0$ or $1$. In particular, $S(2,n,3) = 2f_{n+1}$, twice the $(n+1)$st Fibonacci number.

A bit more about this example can be found below, but my question is:

How many $a$-nary sequences of length $b$ never have $c$ consecutive occurrences of a digit?

Re-phrased,

What is a concise formula for $S(a,b,c)$?

Although there are related questions that have been asked on MSE, I have not seen this particular one asked in full generality.


For $S(2,n,3)$, let $f_n$ denote the $n$th Fibonacci number and observe the following:

$n = 1$: $\{0, 1\}$. Total: $2$, i.e., $2f_{2} = 2\cdot1$.

$n = 2$: $\{00, 01, 10, 11\}.$ Total: $4$, i.e., $2f_{3} = 2\cdot2$.

$n = 3$: $\{001, 010, 011, 100, 101, 110\}.$ Total: $6$, i.e., $2f_{4} = 2\cdot3$.

$n = 4$: $\{0010, 0011, 0100, 0101, 0110, 1001, 1010, 1011, 1100, 1101\}.$ Total: $10$, i.e., $2f_{5} = 2\cdot5$.

I've written out a slightly wordy proof that the above pattern continues, but omit it here for the sake of brevity. (If it would be helpful, then I could include it in the post; but an answer to my main question would, of course, subsume this particular result.)

$\endgroup$
1
$\begingroup$

For problems like this the Goulden-Jackson Cluster Method is a convenient method to derive a generating function. The coefficients of this function are the wanted numbers.

We consider the set of words in $ \mathcal{V}^{\star}$ of length $b\geq 0$ built from an alphabet $$\mathcal{V}=\{x_1,\ldots,x_a\}$$ and the set $B=\{x_1^c,\ldots,x_a^c\}$ of bad words, which are not allowed to be part of the words we are looking for. We derive a function $f(s)$ with the coefficient of $s^b$ being the number of words of length $b$ from an $a$-ary alphabet with runs of length $<c$.

According to the paper (p.7) the generating function $f(s)$ is \begin{align*} f(s)=\frac{1}{1-ds-\text{weight}(\mathcal{C})}\tag{1} \end{align*} with $d=|\mathcal{V}|=a$, the size of the alphabet and with the weight-numerator $\mathcal{C}$ with \begin{align*} \text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[x_1^c])+\cdots+\text{weight}(\mathcal{C}[x_a^c]) \end{align*}

We calculate according to the paper \begin{align*} \text{weight}(\mathcal{C}[x_1^c])&=-s^c-\text{weight}(\mathcal{C}[x_1^c])s-\cdots-\text{weight}(\mathcal{C}[x_1^c])s^{c-1}\\ &=-\frac{s^c}{1+s+\cdots+s^{c-1}}=-\frac{s^c(1-s)}{1-s^c}\\ &\cdots\\ \text{weight}(\mathcal{C}[x_a^c])&=-s^c-\text{weight}(\mathcal{C}[x_a^c])s-\cdots-\text{weight}(\mathcal{C}[x_a^c])s^{c-1}\\ &=-\frac{s^c}{1+s+\cdots+s^{c-1}}=-\frac{s^c(1-s)}{1-s^c}\\ \end{align*} and get \begin{align*} \text{weight}(\mathcal{C}[x_1^c])=\cdots=\text{weight}(\mathcal{C}[x_a^c])=-\frac{s^c(1-s)}{1-s^c} \end{align*}

It follows \begin{align*} f(s)&=\frac{1}{1-ds-\text{weight}(\mathcal{C})}\\ &=\frac{1}{1-as+a\frac{s^c(1-s)}{1-s^c}}\\ &=\frac{1-s^c}{1-as+(a-1)s^{c}} \end{align*} and we conclude \begin{align*} S(a,b,c)=[s^b]\frac{1-s^c}{1-as+(a-1)s^{c}} \end{align*}

Example: $a=2,c=3$

In the special case with a binary alphabet $a=2$ and runs of maximum length $<c=3$ we obtain the generating function $f(s)$

\begin{align*} f(s)&=\frac{1-s^3}{1-2s+s^3}\\ &=\frac{1+s+s^2}{1-s-s^2}\\ &=1+2s+4s^2+6s^3+10s^4+16s^5+\mathcal{O}(s^6) \end{align*}

$\endgroup$
  • 1
    $\begingroup$ @BenjaminDickman: Here is an answer based upon the cluster method. It indicates, that the answer of vonbrand is slightly wrong. It coincides with the comment of Marko Riedels besides the constant $1$, since $\frac{1+s^2}{1-s-s^2}-1=\frac{2s(1+s)}{1-s-s^2}$, which means that my approach counts also the empty word $\varepsilon$. In both cases the coefficients of the series result in twice the Fibonacci-number. Regards, $\endgroup$ – Markus Scheuer Apr 3 '16 at 15:55
  • $\begingroup$ Awesome. Is there a straightforward way to extract the coefficients? $\endgroup$ – Benjamin Dickman Apr 3 '16 at 17:13
  • $\begingroup$ You're welcome! Partial fraction expansion or expansion as geometric series $\frac{p(s)}{1-s-s^2}=p(s)\sum_{n\geq 0}(s+s^2)^n$ is the usual way to extract coefficients. Here I've simply invoked Wolfram Alpha and checked the coefficients with some lines of code for plausibility with respect to maximum run lengths. $\endgroup$ – Markus Scheuer Apr 3 '16 at 17:22
2
$\begingroup$

For $a=2$, you get the c-bonacci numbers.

More generally, you just set up the recurrence relation and solve it for $F_b$.

$$F_n = (a-1)[F_{n-1}+ \ldots +F_{n-c}]$$

With a starting condition of $F_1 = a, F_0 = 1, F_{-i} =0$

From the theory of linear recurrences, we know that $F_n = F_n = \sum A_i \alpha_i^n$, where $\alpha_i$ are the roots of the characteristic equation. However, since it doesn't have immediately obvious roots, I would be surprised if there is a compact general answer.

$\endgroup$
  • 1
    $\begingroup$ @benjamin I would be surprised if there was a concise formula for the general case. Even the generalized Fibonacci numbers are not nice $\endgroup$ – Calvin Lin Apr 30 '14 at 16:40
  • $\begingroup$ @BenjaminDickman Do you know the theory of linear recurrences? Because the characteristic equation doesn't have nice / reasonable roots, there is unlikely to be a simple description. $\endgroup$ – Calvin Lin Apr 30 '14 at 20:24
  • $\begingroup$ Thanks for your answer, CL. $\endgroup$ – Benjamin Dickman Aug 17 '14 at 16:47
  • 1
    $\begingroup$ @CalvinLin: I've added a formula for the general case which might be interesting. Regards, $\endgroup$ – Markus Scheuer Apr 3 '16 at 17:28
2
+50
$\begingroup$

In Odlyzko "Enumeration of strings" (in "Combinatorial Algorithms on Words", Apostolico and Galil (eds), Springer, 1985) one of the problems treated is a generalization of this one. The result is that the generating function for the numbers you are looking for is: $$ \sum_{b \ge 0} S(a, b, c) z^b = \frac{1 - z^c}{1 - a z + a z^{c + 1}} $$ What could be done from here is to expand the denominator as a geometric series in $a z - a z^{c + 1}$, but that won't give any kind of closed form.

The Fibonacci numbers $F_0 = 0, F_1 = 1, F_{n + 2} = F_{n+1} + F_n$ have generating function $F(z) = \frac{z}{1 - z - z^2}$. So you have: $$ \sum_{n \ge 0} n F_n z^n = z \frac{\mathrm{d} F}{\mathrm{d} z} = \frac{z (1 + z^2)}{(1 - z - z^2)^2} $$ Your values above are just a coincidence.

Added later: The terms of the sequence can be recovered from the partial fraction expansion of the generating function, each single zero of that gives a term of the form $a \rho^n$ if $1/\rho$ is a zero of the denominator, and multiple zeros give polynomials in $n$ multiplied by the $\rho^n$. Some terms might not be present for particular initial values (which get encoded in the denominator).

Note that this is the closed form of the sequence, there can't be no other (in essence, the coefficients of the Maclaurin series are unique). For particular values of $a$ and $c$ there are known expressions for the zeroes (up to $c = 3$, via the formula for the cuartic). I'm sure the relevant polynomial $1 - a z + a z^{c + 1}$ has no expression for the zeros in roots (at least for $c = 4$ the resulting quintic hasn't). So at least for that particular case (and very probably for all higher $c$ too) there is no "nice formula" (and a monster with $c + 1$ terms isn't very "nice" anyway).

$\endgroup$
  • 1
    $\begingroup$ Are you sure you have the right generating function? I get $$a(z^c-z)/(z-1)\sum_{k\ge 0} (a-1)^k ((z^c-z)/(z-1))^k = {\frac { \left( {z}^{c}-z \right) a}{ \left( -a+1 \right) {z}^{c}+az-1}}$$ This gives for $a=2$ and $c=3$ the gf $$\frac{2z(z+1)}{1-z-z^2}$$ with coefficient $2F_n+2F_{n-1}=2F_{n+1}.$ Also for $a=c=4$ it gives $$4\,{\frac {{z}^{4}-z}{-3\,{z}^{4}+4\,z-1}}$$ with coefficients $$4, 16, 64, 252, 996, 3936, 15552, 61452, 242820, 959472, 3791232,\ldots$$ which is OEIS so it seems to be correct. $\endgroup$ – Marko Riedel Aug 5 '14 at 22:09
  • $\begingroup$ @MarkoRiedel Thank you for the careful checking; as a result, I've (temporarily...) "unchecked" the answer above... $\endgroup$ – Benjamin Dickman Aug 17 '14 at 16:46
  • 1
    $\begingroup$ Something seems to be slightly wrong with the generating function for $S(a,b,c)$. Please note that in the special case $a=2, c=3$ the generating function $\frac{1-z^3}{1-2z+2z^4}=1+2z+4z^2+7z^3+\cdots$ which is not correct, since the coefficient of $z^3$ should be equal to $6$. We have $8$ binary words of length $3$ and two of them $000$ and $111$ have to be excluded. Regards, $\endgroup$ – Markus Scheuer Apr 3 '16 at 16:17

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.