2
$\begingroup$

I am faced with the following problem:

Given $C = \{B,C,D,F\}$ and $V = \{A, E, I, O, U\}$ find the number of 9-letter words with elements from $C$ and $V$ such that no two vowels (elements of V) are adjacent.

Following this answer about a very similar question I get that I should express the problem as a double recurrence:

$a_{n+1} = 5b_n$, $a_0 = 1$

$b_{n+1} = 4(a_n + b_n)$, $a_0 = 1$

where $a_n$ is the number of string starting by a vocal and $b_n$ is the number of string starting by a consonant.

Expressing it as a matrix I get $\begin{pmatrix} a_{n+1} \\ b_{n+1} \end{pmatrix} = \begin{pmatrix} 0 & 5 \\ 4 & 4 \end{pmatrix} \begin{pmatrix} a_n \\ b_n \end{pmatrix}$

And I get that the eigenvalues of this matrix are $\{2+\frac{\sqrt{96}}{2}, 2-\frac{\sqrt{96}}{2}\}$. Is this the correct approach?

I don't really know where to go from here or how to solve the recurrence for any given $k$. Thank you in advance

$\endgroup$
  • $\begingroup$ You made a typo : $\begin{pmatrix} a_{n+1} \\ b_{n+1} \end{pmatrix} = \begin{pmatrix} 0 & 5 \\ 4 & 4 \end{pmatrix} \begin{pmatrix} a_n \\ b_n \end{pmatrix}$ $\endgroup$ – Olivier Roche Sep 11 at 9:21
  • $\begingroup$ @OlivierRoche Yes, fixed, thank you $\endgroup$ – Zanzag Sep 11 at 9:22
1
$\begingroup$

You boil your problem down to a linear recurrence relation, which is nice!

There's a little issue with $a_0$ and $b_0$, though : how can the empty word start by anything? One should start the recurrence at $n=1$, we have $a_1 = 5$ and $b_1 = 4$.

Call $A = \begin{pmatrix} 0 & 5 \\ 4 & 4 \end{pmatrix}$, then $$\begin{pmatrix} a_n \\ b_n \end{pmatrix} = A^{n-1} \begin{pmatrix} 5 \\ 4 \end{pmatrix} $$ The point of computing the eigenvalues is to put $A$ in a nicer form so that $A^n$ is easy to compute. Since you have two distinct eigenvalues, you can diagonalize $A$ which will lead you to a nice expression of $a_n$ and $b_n$.

Diagonalization of $A$ :
Edit : in fact $96 = 4 \cdot 24$ and not $4\cdot 19$ !

One finds two distinct eigenvalues, $\lambda_1 = 2 + \sqrt{24}$ and $\lambda_2 = 2 - \sqrt{24}$.
Let $i=1,2$, an eigenvector $v_i$ corresponding to $\lambda_i$ is a nonzero solution to the equation $$(A - \lambda_i \operatorname{Id}) v_i = 0$$ Write $v_i = \begin{pmatrix} x \\ y \end{pmatrix}$, we get $$\left\{\begin{matrix} -\lambda_i x + & 5 y = & x \\ 4 x + & (4-\lambda_i)y = & y \end{matrix} \right.$$ The first line implies $y = \frac{\lambda_i}{5} x$, after which the second line vanishes. Now chose an arbitrary $x \neq 0$, let's take $x = 5$ for convenience.

Now $v_1 = \begin{pmatrix} 5 \\ 2 + \sqrt{24} \end{pmatrix}$ and $v_2 = \begin{pmatrix} 5 \\ 2 - \sqrt{24} \end{pmatrix}$ form a basis of eigenvectors. Take $$P = \begin{pmatrix} 5 & 5 \\ 2 + \sqrt{24} & 2 - \sqrt{24} \end{pmatrix}$$ One has $$ P^{-1}AP = \begin{pmatrix} 2 + \sqrt{24} & 0 \\ 0 & 2 - \sqrt{24}\end{pmatrix} $$ Hence, $$ A^k = P \begin{pmatrix} (2 + \sqrt{24})^k & 0 \\ 0 & (2 - \sqrt{24})^k\end{pmatrix} P^{-1}$$

$\endgroup$
  • $\begingroup$ Thank you, I understand it now. $\endgroup$ – Zanzag Sep 13 at 20:08

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.