I have an exercise that told me to calculate number of ways to form a number with $n$ elements from $3$ numbers: $3$, $7$, $9$. The number must not contain any $2$ adjacent of $7$ or $9$. Like $3379$, $397$ or $7973$ is acceptable, $3799$ or $397993$ is not. Please help me!
I tried to take the permutation of all 3 numbers $3^n$ minus the cases which contain 2 consecutive 7 or 9. But I fell short as I couldn't find all the cases, there seems to be a lot.
I'll provide a quick answer using Markov Chains. If you have any questions I will answer them tomorrow.
It is easier to compute the number of arrays to from $n$ elements with at least adjacent $7$'s or $9$'s. Imagine you are walking through each entry of the array and 'picking' up each number in the list with the goal of finding 2 consecutive $7$'s or $9$'s. If it is $3$, you throw it away. If you pick up a $7$ or $9$, you keep it. Go to the next entry. If you pick up a $3$, this is analogous to your progress being reset and you drop whatever you have. If get 2 matching numbers, congrats, you are done, as you have found 2 consecutive numbers in the array. If the next number does not match your current number, there's still a good chance of it not being a $3$, so your progress is not reset.
We denote $X$ as the random variable representing your 'progress'. More specifically, if you are 2 steps away from getting $2$ consecutive $7$'s or $9$'s, $X=0$. If you are 1 step away from this goal, $X=1$. If you have already found $2$ consecutive $7$'s or $9$'s, $X=2$. Obviously, $X=2$ would imply the array having $2$ consecutive $7$'s or $9$'s.
It is now crucial to understand the transition matrix. A transition matrix is a matrix of probabilities, with the entry in the $i$-th row and $j$-th column representing the probabiliy of transition from state $i$ to $j$. You can check the transition matrix required for this problem is:
$$ T=\begin{pmatrix} \frac{1}{3} &\frac{2}{3}&0\\ \frac{1}{3} &\frac{1}{3}&\frac{1}{3}\\ 0&0&1\end{pmatrix} $$
Where the rows and columns represent states $\{0,1,2\}$ respectively. For example, when $X=1$, you are 1 step from obtaining $2$ consecutive $7$'s or $9$'s. This means that the number you have in your hand is either $7$ or $9$. There's a 1/3 chance that the next number is the same, pushing you to $X=2$ (the entry at the 2nd row, 3rd col), a 1/3 chance that the next time is not the same and not $3$, pushing you to $X=1$ (entry at 2nd row, 2nd col), and a 1/3 chance the next entry is $3$, pushing you to $X=0$ (entry at 2nd row, 1st col). I hope it's quite clear, otherwise, this is a good resource.
The entry corresponding to row of the $i$-th state and column of the $j$-th state of $T^n$ represents the probability of getting from the $i$-th state to the $j$-th state in $n$ steps. In this case, $n$, the length of the list, is also akin to the number of 'chances' you have to $2$ consecutive $7$'s or $9$'s. Again, the link provides more information.
After this it's just computation. You may diagonalise the matrix to arrive at a closed form formula.
$$ T=\begin{pmatrix}-\sqrt{2}&\sqrt{2}&1\\ 1&1&1\\ 0&0&1\end{pmatrix}\begin{pmatrix}-\frac{\sqrt{2}-1}{3}&0&0\\ 0&\frac{\sqrt{2}+1}{3}&0\\ 0&0&1\end{pmatrix}\begin{pmatrix}-\frac{1}{2\sqrt{2}}&\frac{1}{2}&-\frac{\sqrt{2}-1}{2\sqrt{2}}\\ \frac{1}{2\sqrt{2}}&\frac{1}{2}&-\frac{1+\sqrt{2}}{2\sqrt{2}}\\ 0&0&1\end{pmatrix} $$ After $n$ steps, we have: $$ T^n= \begin{pmatrix}-\sqrt{2}&\sqrt{2}&1\\ 1&1&1\\ 0&0&1\end{pmatrix}\begin{pmatrix}\left(-\frac{\sqrt{2}-1}{3}\right)^n&0&0\\ 0&\left(\frac{\sqrt{2}+1}{3}\right)^n&0\\ 0&0&1\end{pmatrix}\begin{pmatrix}-\frac{1}{2\sqrt{2}}&\frac{1}{2}&-\frac{\sqrt{2}-1}{2\sqrt{2}}\\ \frac{1}{2\sqrt{2}}&\frac{1}{2}&-\frac{1+\sqrt{2}}{2\sqrt{2}}\\ 0&0&1\end{pmatrix}=\begin{pmatrix}\frac{\left(\frac{1+\sqrt{2}}{3}\right)^n+\left(-\frac{\sqrt{2}-1}{3}\right)^n}{2}&\frac{\left(\frac{1+\sqrt{2}}{3}\right)^n-\left(-\frac{\sqrt{2}-1}{3}\right)^n}{\sqrt{2}}&\frac{\left(\sqrt{2}-1\right)\cdot \:3^n\left(-\frac{\sqrt{2}-1}{3}\right)^n-\left(1+\sqrt{2}\right)^{n+1}+2\cdot \:3^n}{2\cdot \:3^n}\\ \frac{\left(\frac{1+\sqrt{2}}{3}\right)^n-\left(-\frac{\sqrt{2}-1}{3}\right)^n}{2\sqrt{2}}&\frac{\left(\frac{1+\sqrt{2}}{3}\right)^n+\left(-\frac{\sqrt{2}-1}{3}\right)^n}{2}&\frac{-\left(\sqrt{2}-1\right)\cdot \:3^n\left(-\frac{\sqrt{2}-1}{3}\right)^n-\left(1+\sqrt{2}\right)^{n+1}+2\sqrt{2}\cdot \:3^n}{2\sqrt{2}\cdot \:3^n}\\ 0&0&1\end{pmatrix} $$ We want the entry corresponding to the 1st row ($X=0$) and 3rd column ($X=2$) of $T^n$. This gives us the probability that you achieve $X=2$ starting from $X=0$ (we are 2 steps from our goal). We have:
$$P(2 \ \text{conseq} \ 7 \text{ or } 9, n \ \text{steps})= \frac{3^n\cdot \left(\sqrt{2}-1\right)\cdot \left(-\frac{\sqrt{2}-1}{3}\right)^n-\left(1+\sqrt{2}\right)^{\left(n+1\right)}+2\cdot 3^n}{2 \cdot 3^n}$$
It is simple to see that the number of ways this can happen is: $$\frac{3^n\cdot \left(\sqrt{2}-1\right)\cdot \left(-\frac{\sqrt{2}-1}{3}\right)^n-\left(1+\sqrt{2}\right)^{\left(n+1\right)}+2\cdot 3^n}{2}$$
Dont' forget that we want the complement of all the events, so we get $$ 3^n -\frac{3^n\cdot \left(\sqrt{2}-1\right)\cdot \left(-\frac{\sqrt{2}-1}{3}\right)^n-\left(1+\sqrt{2}\right)^{\left(n+1\right)}+2\cdot 3^n}{2} $$
which simplifies down to : $$ \frac{(1+\sqrt2)^{n+1}+(1-\sqrt2)^{n+1}}2 $$
You can check that these 2 expressions are the same. https://www.desmos.com/calculator/14nqdgcqpl
I will admit it's not the prettiest answer, but at least transition matrices are a pretty cool subject, and they are useful when recurrence relations are difficult to observe.