Question: Find the number of five-digit numbers formed by the digits $1, 2, 3, 4, 5, 6$ such that at least three digits are different, and $1, 6$ are not adjacent.
Solution 1: Let $A$ be the set of five-digit numbers formed by $1, 2, 3, 4, 5, 6$ with at least three different digits, $B$ be the set of five-digit numbers formed by $1, 2, 3, 4, 5, 6$ with no $1, 6$ adjacent, and $R$ be the set of five-digit numbers formed by $1, 2, 3, 4, 5, 6$. By the set theory formula, we have
$$
\begin{array}{l}
|A \cap B|=|R|-|\overline{A \cap B}| \\
=|R|-|\bar{A} \cup \bar{B}| \\
=|R|-|\bar{A}|-|\bar{B}|+|\bar{A} \cap \bar{B}| .
\end{array}
$$
$(|E|$ represents the number of elements in set $E$)
And $|R|=6^{5}=7776$.
$|\bar{A}|$ is the number of five-digit numbers formed by one or two digits from $1, 2, 3, 4, 5, 6$. Therefore,
$$
|\bar{A}|=6+\mathrm{C}_{6}^{2}\left(\mathrm{C}_{5}^{1}+\mathrm{C}_{5}^{2}+\mathrm{C}_{5}^{3}+\mathrm{C}_{5}^{4}\right)
$$
$$
=6+15 \times 30=456 \text {. }
$$
$|\bar{A} \cap \bar{B}|$ is the number of five-digit numbers formed by one or two digits from $1, 2, 3, 4, 5, 6$ and with $1, 6$ adjacent. Therefore, it is the number of five-digit numbers formed by $1, 6$, so,
$$
|\bar{A} \cap \bar{B}|=C_{5}^{1}+C_{5}^{2}+C_{5}^{3}+C_{5}^{4}=30 .
$$
$|\bar{B}|$ is the number of five-digit numbers with $1, 6$ adjacent. To find this number, we use a recursive method. Let $b_{n}$ be the number of $n$-digit numbers with $1, 6$ adjacent, and $c_{n}$ be the number of $n$-digit numbers with the first digit being 1 or 6 and $1, 6$ adjacent. Since all are $n$-digit numbers formed by $1, 2, 3, 4, 5, 6$, if the first digit is not $1, 6$, it must be one of $2, 3, 4, 5$. If the first digit is one of $2, 3, 4, 5$, then the remaining $n-1$ digits must contain $1, 6$ adjacent, so,
$$
b_{n}=2 c_{n}+4 b_{n-1} \text {. }
$$

This alone is not enough for recursion, so we need to find a recursive formula for $c_{n}$. $c_{n}$ includes $n$-digit numbers with the first digit being 1 or 6 and $1, 6$ adjacent, which can be in three cases:
(i) The second digit is 6 or 1, in which case the first two digits are already 1, 6 adjacent, and the remaining $n-2$ digits can be any;
(ii) The first digit is still 1 or 6, and from the second digit, the $n-1$ digits must contain 1, 6 adjacent;
(iii) The second digit is one of $2, 3, 4, 5$, then from the third digit, the $n-2$ digits must contain 1, 6 adjacent. So,
$$
\begin{array}{l}
c_{n}=6^{n-2}+c_{n-1}+4 b_{n-2} . \\
\text { Substituting equation (2) into equation (1) gives } \\
b_{n}=2 \times 5^{n-2}+2 c_{n-1}+8 b_{n-2}+4 b_{n-1} \\
=2 \times 6^{n-2}+4 b_{n-2}+5 b_{n-1} .
\end{array}
$$

This is the recursive formula for $b_{n}$. Clearly, $b_{1}=0, b_{2}=2$. Substituting into equation (3) gives
$$
\begin{array}{l} 
b_{3}=2 \times 6+5 \times 2=22, \\
b_{4}=2 \times 6^{2}+4 \times 2+5 \times 22=190, \\
b_{5}=2 \times 6^{3}+4 \times 22+5 \times 190 \\
=1470=|\bar{B}| . \\
\therefore|A \cap B|=7776-456-1470+30 \\
=5880 .
\end{array}
$$

Thus, the number of five-digit numbers is 5880.
Solution 2: Let $x_{n}$ be the number of $n$-digit numbers formed by $1, 2, 3, 4, 5, 6$ with no 1, 6 adjacent and the first digit being 1 or 6, and let $y_{n}$ be the number of $n$-digit numbers formed by $1, 2, 3, 4, 5, 6$ with no 1, 6 adjacent and the first digit being 2, 3, 4, or 5.

Adding a digit in front of an $n$-digit number makes it an $(n+1)$-digit number. To ensure no 1, 6 adjacent, we just need to make sure that if the first digit is 1 or 6, the new digit added cannot be 6 or 1, so,
$$
x_{n+1}=2 y_{n}+x_{n} \text {. }
$$

This indicates that the number of $(n+1)$-digit numbers with no 1, 6 adjacent and the first digit being 1 or 6 can be obtained by adding 1 or 6 in front of the $n$-digit numbers with the first digit being 2, 3, 4, or 5, or by adding 1 or 6 in front of the $n$-digit numbers with the first digit being 1 (or 6).
$$
y_{n+1}=4\left(y_{n}+x_{n}\right) \text {. }
$$

This indicates that the number of $(n+1)$-digit numbers with no 1, 6 adjacent and the first digit not being 1 or 6 can be obtained by adding 2, 3, 4, or 5 in front of the $n$-digit numbers with the first digit being 1, 2, 3, 4, 5, or 6 but not containing 1, 6 adjacent.
$$
\begin{array}{l}
\text { Clearly } x_{1}=2, y_{1}=4 . \text { Substituting into equations (4) and (5) gives } \\
x_{2}=2 \times 4+2=10, \\
y_{2}=4 \times(2+4)=24, \\
x_{3}=2 \times 24+10=58, \\
y_{3}=4 \times(10+24)=136, \\
x_{4}=2 \times 136+58=330,
\end{array}
$$
$$
\begin{array}{l}
y_{4}=4 \times(136+58)=776, \\
x_{5}=2 \times 776+330=1882, \\
y_{5}=4 \times(776+330)=4424 . \\
\therefore x_{5}+y_{5}=6306 .
\end{array}
$$

However, $x_{5}+y_{5}$ includes the five-digit numbers formed by one or two digits, the number of which is
$$
6+\left(\mathrm{C}_{6}^{2}-1\right)\left(\mathrm{C}_{5}^{1}+\mathrm{C}_{5}^{2}+\mathrm{C}_{5}^{3}+\mathrm{C}_{5}^{4}\right)=426 .
$$

Here, $\left(\mathrm{C}_{6}^{2}-1\right)$ subtracts 1 to exclude the five-digit numbers formed by 1, 6, as they are already 1, 6 adjacent and thus not included in $x_{5}+y_{5}$. Therefore, the total number of five-digit numbers is

6306 - 426 = 5880.