10-digit numbers with constraints
How many 10-digit numbers can be made by using the digits {5,6,7} (all of them) and with the additional constraints that no two consecutive digits must be the same and also that the first and last digits of the number must be the same?
I am trying to find a solution by using combinatorics. I start from the 1st leftmost digit, which can have any value from {5,6,7} (3 possibilities). Then we move to the 2nd digit, which can have 2 values (since it can't be the same with the 1st) and so on, and for the last digit we only have 1 option. But this is not correct, because for the 9th digit we have the restriction that it must be different from the 8th and also different from the 10th, which, in turn, is equal to the 1st. I don't know how to express this.
I therefore tried to find a recursive relation. I found that the general relation is $a(n) = 2*a(n-1)$ if n odd and $2*a(n-1) + 6$ if n is even.
For n=4, we have 6 such numbers (4-digit numbers, but with the given restrictions). Then if we add one more digit to the right, we remove the rightmost (4th) digit, which had to be the same with the first, and now for the 3rd digit we have 2 options instead of 1 (we can also add the options that were rejected because they were neighboring with the 4th digit). So in total we now have $2 x 6 = 12$ options. Therefore, $a(4)=6$ and $a(5)=12$. I don't understand, however, where this $+6$ (in the recursive relation) comes from!
By the way, the correct answer is 510.
Many thanks in anticipation.
I don't understand the recursion in the OP, but here is another recursive solution.
For simplicity, let's suppose the number starts with 5; we will need to remember to multiply our result by 3 in the end, to account for 6 and 7. Let's say a number is "acceptable" if it starts with 5 and has no two consecutive digits the same, ignoring for now the restriction that it must end in 5. Define $a_i(n)$ to be the number of n-digit acceptable strings ending in $i$, for $i=5,6,7$. Then we have $a_5(1) = 1$, $a_6(1)=a_7(1)=0$, and $$a_5(n+1) = a_6(n) + a_7(n) \\ a_6(n+1) = a_5(n) + a_7(n) \\ a_7(n+1) = a_5(n) + a_6(n) $$ because of the requirement that no two consecutive digits are the same. These recursive relations allow us to calculate $a_5(n), a_6(n)$ and $a_7(n)$ for $n$ as large as we like.
The answer to the original question is $3 a_5(10)$.
We have a cycle of nine digits $x_i\in{\mathbb Z}_3$ $(1\leq i\leq 9)$, and can forget about the tenth digit $x_{10}=x_1$. If no two consecutive digits may be the same we automatically use all three of the digits $-1, \>0, \>1 \in{\mathbb Z}_3$. Put $x_i-x_{i-1}=:y_i$ cyclically. It is then required that $y_i\in\{{-1},1\}$. Otherwise the $y_i\in{\mathbb Z}_3$ are arbitrary, except for the condition $$s:=\sum_{i=1}^9y_i=0\quad{\rm mod}\ 3\ .$$ This $s$ will automatically be odd. We can have $s=9$ or $s=-9$ in $1$ way each. The value $s=3$ is realized by six $y_i=1$ and three $y_i=-1$. This can be done in ${9\choose3}=84$ ways. The same holds for $s=-3$. It follows that there are $2(1+84)=170$ admissible choices for the $y_i$. We still are free to choose $x_1$, so that we obtain $510$ admissible three digit numbers in all.
Equivalently, we want to $3$-color the labeled cycle with $9$ vertices. If we know (e.g. see the wiki for chromatic polynomials) that the chromatic polynomial of $C_n,$ the labeled cycle with $n \geq 3$ vertices, is $$\chi(C_n,t) = (t-1)^n + (-1)^n(t-1)$$ then the answer is easy: $$\chi(C_9,3) = (3-1)^9 + (-1)^9(3-1) = 510$$
I have another solution. We call a number satisfying the condition of the problem "accepted". Let $a(n)$ denote the number of accepted numbers with $n$ digits. Imagine an accepted number with $n-2$ digits and put two empty places at the left side of the number with $n-2$ digits. You can easily make two different accepted numbers with $n$ digits. To make this claim clear, assume $1,3,...,1$ is an accepted number with $n-2$ digits, we can build two $n$-digit numbers as below: $$1,2,1,3,...,1$$ $$1,3,1,3,...,1$$
Now, assume we have an accepted number with $n-1$ digits. We can make an accepted number with $n$ digits from this number. For example, assume $1,3,...,1$ is such number. we can write:$$1,2,3,...,1$$ Just notice that we added $1$ to the left side and the first $1$ in$1,3,...,1$ changed into $2$.
Now, assume $n$ is even. An accepted number can be made from $1,2,1,2,1,2,...,1,2$ with $n-2$ digit, as below:$$2,3,1,2,...,1,2$$ It is easy to understand that $1,2,1,2,1,2,...,1,2$ doesn't belong to the set of accepted numbers with $n-2$ digits.
If $n$ is odd, the same goes for it, consider $1,2,1,2,...,1,2$ with $n-1$ digits. It's possible to make an accepted number with $n$ digits from this as below:$$2,3,2, 1,2,1,2,...,1,2$$ In each situation there are 6 accepted numbers (why?) with $n$ digits which can't be made from accepted numbers with $n-1$ or $n-2$ digits. So, we will get $a(n)=a(n-1)+2a(n-2)+6$. To be done, one should check two statements below:
- A $n$-digit accepted number made from $n-2$-digit accepted numbers doesn't coincide with any $n$-digit accepted numbers made from $n-1$-digit accepted numbers and vice versa.
- Each $n$-digit accepted number can be obtained through either $n-2$-digit accepted numbers, $n-1$-digit accepted numbers or those six numbers.
Note: What I wrote implies the formula you mentioned.