Consider words on the alphabet $X=\{a,b\}$.
a) I have to show that the Ordinary Generating function (OGF) for words on $\{a,b\}$ whose longest run has length $\leqslant k$ (at most $k$) is:
$$
W_{\leqslant k}(z)= \frac{1-z^{k+1}}{1-2z+z^{k+1}}= \frac{1+z+\dots+z^k}{1-z-\dots-z^k }
$$
I know that I have to use the definition of the set of words:
$$ W(z)= \frac{1}{1-2z}
$$
where $2$ is the cardinality of the alphabet, i.e. the number of letters.
I need to know how to use this information to find the ordinary generating function.
b) How likely is that a word of length $250$ contains a run of length $7$ or more?
Best Answer
The OGF for words on $\{a,b\}$ with $n \ge 1$ runs total, each run of length between $1$ and $k$, is $$ 2(z + z^2 + \dots + z^k)^n $$ where the $2$ corresponds to choosing $a$ or $b$ to start with, and each factor of $(z + z^2 + \dots + z^k)$ corresponds to choosing the length of one of the runs.
Therefore the OGF without a condition on $n$ (including the word of length $0$) is $$ 1 + \sum_{n \ge 1} 2(z + z^2 + \dots + z^k)^n = 1 + \frac{2(z + z^2 + \dots + z^k)}{1 - (z + z^2 + \dots + z^k)} = \frac{1 + z + z^2 + \dots + z^k}{1 - z - z^2 - \dots - z^k}. $$