Example 2.4.4 Divide a circle into 10 sectors, and color each sector with one of the four colors: red, yellow, blue, and green. Each sector is to be colored with one color, and adjacent sectors must be colored with different colors. How many ways are there to color the sectors? If all four colors must be used, how many ways are there to color the sectors?
Solution: For the first question, we discuss the $n$ sectors: Number the sectors as $1,2, \cdots, n$. The first sector has 4 coloring methods, the second sector has 3 methods (different from the first), $\cdots \cdots$, the $(n-1)$-th sector also has 3 methods. If we consider the $n$-th sector different from the $(n-1)$-th, there are also 3 methods, but at this point, the $n$-th sector can be the same or different from the first, so we have
$$
\begin{array}{l}
\left\{\begin{array}{l}
f_{n}+f_{n-1}=4 \times 3^{n-1}(n>2), \\
f_{2}=12 .
\end{array}\right. \\
\frac{f_{n}}{3^{n}}+\frac{1}{3} \cdot \frac{f_{n-1}}{3^{n-1}}=\frac{4}{3}, \\
\frac{f_{n}}{3^{n}}-1=-\frac{1}{3}\left(\frac{f_{n-1}}{3^{n-1}}-1\right)=\cdots \\
=(-1)^{n-2} \frac{1}{3^{n-2}}\left(\frac{f_{2}}{3^{2}}-1\right) \\
=\frac{(-1)^{n}}{3^{n-2}}\left(\frac{12}{3^{2}}-1\right) \\
=(-1)^{n} \frac{1}{3^{n-1}} \text {, } \\
f_{n}=(-1)^{n} 3+3^{n} . \\
\end{array}
$$

We can also establish another recurrence relation, considering two cases:
(1) The 1st sector and the $(n-1)$-th sector are the same color, in which case the $n$-th sector can take any of the other 3 colors;
(2) The 1st sector and the $(n-1)$-th sector are different colors, in which case the $n$-th sector can take any of the other 2 colors.

In case (1), removing the $n$-th sector and considering the 1st and $(n-1)$-th sectors as one, there are $f_{n-2}$ ways. In case (2), removing the $n$-th sector, there are $f_{n-1}$ ways. Therefore, we have
$$
\left\{\begin{array}{l}
f_{n}=2 f_{n-1}+3 f_{n-2} \quad(n>3), \\
f_{2}=12, f_{3}=24 .
\end{array}\right.
$$

The linear homogeneous recurrence relation $f_{n}-2 f_{n-1}-3 f_{n-2}=0$ can be solved using the characteristic equation, which is $\lambda^{2}-2 \lambda-3=0$, with characteristic roots $\lambda=3,-1$,
$$
f_{n}=a \cdot 3^{n}+b \cdot(-1)^{n},
$$
$$
\therefore f_{n}=3^{n}+(-1)^{n} \cdot 3 \text {. }
$$

Using $f_{n}(m)$ to denote the number of ways to color $n$ sectors with $m$ colors, similarly we have $f_{n}(m)=(m-1)^{n}$ $+(-1)^{n}(m-1)$.

For the second question: Let $I$ be the set of all 10-sector 4-coloring methods $(|I|=$ $\left.f_{10}(4)=3^{10}+3\right)$, and $A_{i}$ be the set of 10-sector 4-coloring methods where color $i$ is not used $\left(\left|A_{i}\right|=f_{10}(3)=2^{10}+2\right)$. The number of 10-sector 4-coloring methods using all four colors is:
$$
\begin{aligned}
\left|\overline{A_{1}} \overline{A_{2}} \overline{A_{3}} \overline{A_{4}}\right|= & \left|I-\bigcup_{i=1}^{4} A_{i}\right|=|I|-\sum_{i=1}^{4}\left|A_{i}\right|+\sum_{1 \leqslant i<j \leqslant 4}\left|A_{i} A_{j}\right| \\
& -\sum_{1 \leqslant i<j<k \leqslant 4}\left|A_{i} A_{j} A_{k}\right|+\left|\bigcap_{i=1}^{4} A_{i}\right| \\
= & f_{10}(4)-4 f_{10}(3)+C_{4}^{2} f_{10}(2)=3^{10}+3 \\
& -4\left(2^{10}+2\right)+6 \cdot 2=54960 .
\end{aligned}
$$

Alternative solution:
The number of 4-coloring methods using all four colors $=|I|$ - the number of methods using exactly three colors - the number of methods using exactly two colors $=f_{10}(4)-\mathrm{C}_{4}^{3}\left(f_{10}(3)-\mathrm{C}_{3}^{2} f_{10}(2)\right)-\mathrm{C}_{4}^{2} f_{10}(2)=3^{10}+3$ $-4\left(2^{10}+2-3 \cdot 2\right)-6 \cdot 2=54960$.