2
$\begingroup$

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 ?

$\endgroup$
2
  • 1
    $\begingroup$ Is $aaa$ allowed, or just even multiples? If the latter, then your alphabet is effectively {aa,b,c} $\endgroup$ – Semiclassical 2 days ago
  • $\begingroup$ aaa is not allowed, just even multiples are possible, for example 'aaaaaa' is allowed (3 x aa ) $\endgroup$ – John 2 days ago
4
$\begingroup$

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. $$

$\endgroup$
3
$\begingroup$

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}$.

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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).

$\endgroup$

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.