Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
Compute the number of words of length $10$ in alphabet $\{a,b,c\}$ such that letter $a$ is always doubled (for example "$aabcbcbcaa$" is allowed but "$abcbcaabcc$" is forbidden).
I am looking for a quick/efficient way to resolve this problem. I thought of fixing "$aa$" in the beginning then draw a tree of the next possibilities but this tree will end up to be a whole forest. Can you help me ?
Say there are $i$ occurrence of 'aa' that you "tape" together. The you have a total of $10-i$ slots, of which $i$ has to be 'aa' and the other $10-2i$ are either 'b' or 'c'. That gives the total $$ \sum_{i=0}^5\sum_{j=0}^{10-2i}\binom{10-i}i \binom{10-2i}j. $$
Here is a second approach: Let $x_n$ $(n\geq0)$ denote the number of admissible words having $n$ letters. Then $$x_0=1,\quad x_1=2,\qquad x_n=2x_{n-1}+x_{n-2}\quad (n\geq2)\ .$$ The characteristic equation of the recursion is $\lambda^2-2\lambda-1=0$ with roots $\lambda=1\pm\sqrt{2}$. It follows that $$x_n=c(1+\sqrt{2})^n+c'(1-\sqrt{2})^n\qquad(n\geq0)\ ,$$ where the constants $c$, $c'$ have to be determined from the initial conditions. The computation gives $$c={2+\sqrt{2}\over4},\qquad c'={2-\sqrt{2}\over4}\ .$$ Now $\bigl|c'(1-\sqrt{2})^n\bigr|<{1\over2}$ for all $n\geq0$. We therefore can write $$x_n={\tt round}\left({2+\sqrt{2}\over4}(1+\sqrt{2})^n\right)\qquad(n\geq0)\ .$$ This gives $$x_{10}={\tt round}\bigl(5740.9999782267896753\bigr)=5741\ .$$ This coincides with the value obtained by ${\tt user10354138}$.
You can break this up into cases based on how many aa pairs there are, which can range from $0$ to $5$. Consider, for example, the case that you have $3$ aa pairs. Then you have four other letters that are all either b or c, so there are $2^4$ ways to choose the subsequence formed by those letters. Then thinking of each aa pair as a single letter, you have $7$ letters, and you need to choose $3$ of them to be an aa pair. This gives $2^4{7\choose 3}$ words with $3$ aa pairs.
In general, the number of words of this form with $i$ aa pairs is $2^{10-2i}{10-i\choose i}$. Then add up all terms of this form as $i$ goes from $0$ to $5$.
A word of length $n$ is either a word of length $n - 1$ and a $b$ or a $c$, or a word of length $n - 2$ and $aa$. Call the number of words of length $n$ $x_n$, you see $x_0 = 1$, $x_1 = 2$, and:
$\begin{align*} x_{n + 2} &= 2 x_n + x_{n - 2} \end{align*}$
Solving this using generating functions is routine. Define:
$\begin{align*} g(z) &= \sum_{n \ge 0} z_n z^n \end{align*}$
Multiply your recurrence by $z^n$, sum over $n \ge 0$ and recognize the resulting sums:
$\begin{align*} \sum_{n \ge 0} x_{n + 2} z^n &= 2 \sum_{n \ge 0} x_{n + 1} z^n + \sum_{n \ge 0} x_n z^n \\ \frac{g(z) - x_0 - x_1 z}{z^2} &= 2 \frac{g(z) - x_0}{z} + g(z) \end{align*}$
Solve for $g(z)$ using the initial values, express as partial fractions:
$\begin{align*} g(z) &= \frac{1}{1 - 2 z - z^2} \\ &= \frac{1}{(1 - (1 - \sqrt{2}) z) (1 - (1 + \sqrt{z}) z)} \\ &= \frac{\sqrt{2} - 1}{2^{3/2} (1 + (\sqrt{2} - 1) z)} + \frac{\sqrt{2} + 1}{2^{3/2} (1 - (\sqrt{2} + 1) z)} \end{align*}$
We need the coefficient of $z^n$, as this is just geometric series:
$\begin{align*} [z^n] g(z) &= (-1)^n \frac{\sqrt{2} - 1}{2^{3/2}} (\sqrt{2} - 1)^n + \frac{\sqrt{2} + 1}{2^{3/2}} (\sqrt{2} + 1)^n \end{align*}$
Noting that $\rvert \sqrt{2} - 1 \lvert < 1$, and furthermore the respective coefficient is also less than $1$, you have finally that:
$\begin{align*} x_n &= \operatorname{round} \left( \frac{\sqrt{2} + 1}{2^{3/2}} (\sqrt{2} + 1)^n \right) \end{align*}$
(No, this isn't the best way to compute $x_n$ for large $n$, but it shows how the value grows).
