Counting n-digits Numbers with Special Properties

Problem

Suppose we compose numbers using only the digits in the set \( \{1,2,3\}\). Compute the total numbers with the following properties:

• having length \(n\)
• beginning and ending with the digit \(\displaystyle 1\)
• the adjacent digits are always different from each other

We indicate this number with \(Z_{n}\). For example if \(n = 4\) the possible configurations are \(\{1231, 1321\}\), and so \(Z_{4}=2\).

Hint
Analyze the third last digit of the number. Distinguish the cases in which the digit is equal to \(1\) or is equal to \(2,3\).

1st solution with elementary methods

Suppose we have the following digits

\[ x = x_{1} x_{2} \cdots x_{n-2} x_{n-1} x_{n} \\ \]

For the hypotheses of the problem we have \(x_{1}=x_{n}=1\). To prove the theorem we compute the percentage of the number of digits equal to \(1\) starting from the second position, as we build the tree of possible configurations.

As it can be seen, the percentage of the number of digits equal to \(1\), indicated with \(a_{k}\) with \(k > 2\), depending on the position \(k\) of the digit, is given by the following formula:

\[ a_{k} = \frac{1}{3} \cdot \left(\frac {2^{k-2} + (-1)^{k-1}}{2^{k-2}}\right) \]

If we take the position \(k=n-2\), that is the third last digit of the number, then we have:

\[ a_{n-2} = \frac{1}{3} \cdot \left(\frac {2^{n-4} + (-1)^{n-1}}{2^{n-4}}\right) \]

The position with index \(n-2\) has a crucial role; in fact we can distinguish two disjoint cases:
a) \(x_{n-2} = 1\)
b) \(x_{n-2} = 2\) or \(x_{n-2}=3\).
In the first case, since the last digit is \(x_{n} = 1\), we have two possible choices, \(x_{n-1}= 2\) or \( x_{n-1}=3\).
In the second case, instead, for the digit \(x_{n-1}\) there is no choice: it must be 2 if the previous one is 3, or it must be 3 if the previous one is 2.
Also the total number of configurations up to the position \(n-2\) included is equal to \(2^{n-3}\), because in each position we have two distinct choices available.
So, to compute the total number of configurations that satisfy the constraints of the problem, we have to add those that have the digit 1 in the position \(n-2\) with those that have the digits \(2,3\). In the first case they have:

\[ N_{1}= 2 \cdot 2^{n-3} \cdot a_{n-2} \\ \]

In the second case we have:

\[ N_{23} = 2^{n-3} \cdot (1 – a_{n-2}) \\ \]

Adding the two values ​​and simplifying, we finally find that the number searched \(Z_{n}=N_{1}+N_{23}\) is:

\[ Z_{n}=\frac{1}{3} \cdot \left(2^{n-1} + 2 \cdot (-1)^{n-1}\right) \\ \]

2nd solution

This solution consists in writing the linear recurrence equation of the value \(Z_{n}\) and then solve with the standard methods of finite difference equations. For an in-depth study of discrete mathematics and in particular finite difference equations, one can see Lipschutz’s book^[1].
Based on the considerations made above, it is not difficult to obtain the recurrence equation:

\[ Z_{n} = Z_{n-1} + 2\cdot Z_{n-2} \\ \]

This linear second order equation can be solved by standard methods, solving the characteristic equation:

\[ \lambda ^2 – \lambda – 2 = 0 \\ \]

The roots are: \(2, -1\). Since the two roots are distinct, the general solution is:

\[ Z_{n}= h \cdot 2^{n} + k \cdot (-1)^{n} \\ \]

The values ​​of the constants \(h, k\) are determined with the initial conditions of the problem: \(Z_{2}=0 \text { and } Z_{3}=2\).
Then the solution is:

\[ Z_{n}=\frac{1}{3} \cdot \left(2^{n-1} + 2 \cdot (-1)^{n-1}\right) \\ \]

---

Bibliography

^[1]Seymour Lipschutz – Discrete Mathematics (McGraw-Hill)