Example 3.18 Find the SDR of Array II:
$$
\begin{array}{cccccccc}
1 & 2 & 3 & \cdots & n-3 & n-2 & n-1 & n \\
2 & 3 & 4 & \cdots & n-2 & n-1 & n & 1 \\
3 & 4 & 5 & \cdots & n-1 & n & 1 & 2
\end{array}
$$

the number of SDRs $z_{n}$.
Solution: The $z_{n}$ SDRs of Array II can be divided into the following three categories:
(1) SDRs where the representative of the $n$-th column is $n$.
Among them, there is 1 SDR where the representative of the $n-1$-th column is $n-1$, and there are $u_{n-2}$ SDRs where the representative of the $n-1$-th column is 1 (where $u_{n}$ is the number of SDRs of Array I). Therefore, the number of SDRs in this category is $1+u_{n-2}$.
(2) SDRs where the representative of the $n$-th column is 1.
There are $u_{n-1}$ SDRs in this category.
(3) SDRs where the representative of the $n$-th column is 2.
Among them, there is 1 SDR where the representative of the 1st column is 3, and there are $u_{n-2}$ SDRs where the representative of the 1st column is 1. Therefore, there are $1+u_{n-2}$ SDRs in this category.
By the principle of addition, we have
$$
\begin{aligned}
z_{n} & =1+u_{n-2}+u_{n-1}+1+u_{n-2} \\
& =u_{n}+u_{n-2}+2 .
\end{aligned}
$$

Let $\alpha_{1}=\frac{1+\sqrt{5}}{2}, \alpha_{2}=\frac{1-\sqrt{5}}{2}$, since $u_{n}=\frac{1}{\sqrt{5}}\left(\alpha_{1}^{n+1}-\alpha_{2}^{n+1}\right)$, we have
$$
\begin{aligned}
z_{n} & =\frac{1}{\sqrt{5}}\left(\alpha_{1}^{n+1}-\alpha_{2}^{n+1}\right)+\frac{1}{\sqrt{5}}\left(\alpha_{1}^{n-1}-\alpha_{2}^{n-1}\right)+2 \\
& =\frac{1}{\sqrt{5}} \alpha_{1}^{n-1}\left(\alpha_{1}^{2}+1\right)-\frac{1}{\sqrt{5}} \alpha_{2}^{n-1}\left(\alpha_{2}^{2}+1\right)+2 .
\end{aligned}
$$

Since $\alpha_{1}, \alpha_{2}$ are the two roots of the equation $x^{2}-x-1=0$, we have $\alpha_{1}^{2}-\alpha_{1}-1=0, \alpha_{2}^{2}-\alpha_{2}-1=0$, thus
$$
\begin{aligned}
\alpha_{1}^{2}+1 & =\alpha_{1}+2=\frac{1+\sqrt{5}}{2}+2 \\
& =\sqrt{5} \cdot \frac{1+\sqrt{5}}{2}=\sqrt{5} \alpha_{1}, \\
\alpha_{2}^{2}+1 & =\alpha_{2}+2=\frac{1-\sqrt{5}}{2}+2 \\
& =-\sqrt{5} \frac{1-\sqrt{5}}{2}=-\sqrt{5} \alpha_{2},
\end{aligned}
$$

Therefore,
$$
\begin{aligned}
z_{n} & =\frac{1}{\sqrt{5}} \alpha_{1}^{n-1} \cdot \sqrt{5} \alpha_{1}-\frac{1}{\sqrt{5}} \alpha_{2}^{n-1}\left(-\sqrt{5} \alpha_{2}\right)+2 \\
& =\alpha_{1}^{n}+\alpha_{2}^{n}+2 \\
& =\left(\frac{1+\sqrt{5}}{2}\right)^{n}+\left(\frac{1-\sqrt{5}}{2}\right)^{n}+2
\end{aligned}
$$