证明：
我们令轮状病毒圆心编号为1，圆环上点编号从2~n+1
则可以得出无向图的度数矩阵D和邻接矩阵E
\(D=\begin{bmatrix}n&0&0&0&0&\cdots&0&0&0&0\\0&3&0&0&0&\cdots&0&0&0&0\\0&0&3&0&0&\cdots&0&0&0&0\\0&0&0&3&0&\cdots&0&0&0&0\\0&0&0&0&3&\cdots&0&0&0&0\\\vdots&\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\vdots\\0&0&0&0&0&\cdots&3&0&0&0\\0&0&0&0&0&\cdots&0&3&0&0\\0&0&0&0&0&\cdots&0&0&3&0\\0&0&0&0&0&\cdots&0&0&0&3\\\end{bmatrix}\)
\(E=\begin{bmatrix}0&1&1&1&1&\cdots&1&1&1&1\\1&0&1&0&0&\cdots&0&0&0&1\\1&1&0&1&0&\cdots&0&0&0&0\\1&0&1&0&1&\cdots&0&0&0&0\\1&0&0&1&0&\cdots&0&0&0&0\\\vdots&\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\vdots\\1&0&0&0&0&\cdots&0&1&0&0\\1&0&0&0&0&\cdots&1&0&1&0\\1&0&0&0&0&\cdots&0&1&0&1\\1&1&0&0&0&\cdots&0&0&1&0\\\end{bmatrix}\)
再得到
基尔霍夫Kirchhoff矩阵 \(K=\begin{bmatrix}n&-1&-1&-1&-1&\cdots&-1&-1&-1&-1\\-1&3&-1&0&0&\cdots&0&0&0&-1\\-1&-1&3&-1&0&\cdots&0&0&0&0\\-1&0&-1&3&-1&\cdots&0&0&0&0\\-1&0&0&-1&3&\cdots&0&0&0&0\\\vdots&\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\vdots\\-1&0&0&0&0&\cdots&3&-1&0&0\\-1&0&0&0&0&\cdots&-1&3&-1&0\\-1&0&0&0&0&\cdots&0&-1&3&-1\\-1&-1&0&0&0&\cdots&0&0&-1&3\\\end{bmatrix}\)
然后我们要求K的代数余子式的值，显然是将带有n的那一行，那一列（即第一行，第一列）去掉
接下来就是求n阶行列式\(A=\begin{vmatrix}3&-1&0&0&\cdots&0&0&0&-1\\-1&3&-1&0&\cdots&0&0&0&0\\0&-1&3&-1&\cdots&0&0&0&0\\0&0&-1&3&\cdots&0&0&0&0\\\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\vdots\\0&0&0&0&\cdots&3&-1&0&0\\0&0&0&0&\cdots&-1&3&-1&0\\0&0&0&0&\cdots&0&-1&3&-1\\-1&0&0&0&\cdots&0&0&-1&3\\\end{vmatrix}\)
的值了
对于A，显然不能用\(n^3\)的高斯消元，所以我们要探究A的性质。
将A的第一行变换到最后一行，得到\(B=\begin{vmatrix}-1&3&-1&0&\cdots&0&0&0&0\\0&-1&3&-1&\cdots&0&0&0&0\\0&0&-1&3&\cdots&0&0&0&0\\0&0&0&-1&\cdots&0&0&0&0\\\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\vdots\\0&0&0&0&\cdots&-1&3&-1&0\\0&0&0&0&\cdots&0&-1&3&-1\\-1&0&0&0&\cdots&0&0&-1&3\\3&-1&0&0&\cdots&0&0&0&-1\\\end{vmatrix}\)
先根据行列式的性质得到\(A=(-1)^{n-1}\times B\)
我们发现除了左下角有三个数字外，B已经是一个上三角行列式，接下来是要消去左下角的三个数字
先消第n-1行（倒数第二行）
假设现在在消第i位，设\(F_i\)表示这一行的第i个数，\(G_i\)表示这一行第i+1个数
那么我们可以将B的第i行\(\times F_i\)加到这一来，就可消去第i位。因为第i行-1后面一定是3，所以第i+1位\(+3\times F_i\)同理，第i+2位\(+(-F_i)\)。
即
\(\begin{cases}F_{i+1}=G_i+3\times F_i\\G_{i+1}=-F_i\\\end{cases}\)
由第二个式子推出\(G_i=-F_{i-1}\)带人第一个式子中，得到\(F_{i+1}=3\times F_i-F_{i-1}\)，同时也可得到\(G_{i+1}=3\times G_i-G_{i-1}\)
然后可以快速地将第n-1行消成\(\begin{bmatrix}0&0&0&0&\cdots&0&0&F_{n-1}-1&G_{n-1}+3\end{bmatrix}\) 了
同样的方法，我们可以来消第n行
设第i位为\(H_i\),第i+1位为\(L_i\)
可得方程
\(\begin{cases}H_{i+1}=L_i+3\times H_i\\L_{i+1}=-H_i\\\end{cases}\)
解得\(H_{i+1}=3\times H_i-H_{i-1}\);\(L_{i+1}=3\times L_i-L_{i-1}\)
将第n行消成\(\begin{bmatrix}0&0&0&0&\cdots&0&0&H_{n-1}&L_{n-1}-1\end{bmatrix}\)
设\(F_{n-1}-1=f;G_{n-1}+3=g;H_{n-1}=h;L_{n-1}-1=l;\)
则\(B=\begin{vmatrix}-1&3&-1&0&\cdots&0&0&0&0\\0&-1&3&-1&\cdots&0&0&0&0\\0&0&-1&3&\cdots&0&0&0&0\\0&0&0&-1&\cdots&0&0&0&0\\\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\vdots\\0&0&0&0&\cdots&-1&3&-1&0\\0&0&0&0&\cdots&0&-1&3&-1\\0&0&0&0&\cdots&0&0&f&g\\0&0&0&0&\cdots&0&0&h&l\\\end{vmatrix}\)=\((-1)^{n-2}\times \begin{vmatrix}f&g\\h&l\\\end{vmatrix}\)
所以\(A=(-1)^{n-1}\times B=(-1)^{2n-3}\times \begin{vmatrix}f&g\\h&l\\\end{vmatrix}=-f\times l+g\times h\)
再推一推F,G,H,L,可以看出
\(H_{i-1}=L_{i}=F_{i}=G_{i+1}\)
最后就可以推出\(Ans(n)=3\times Ans(n-1)-Ans(n-2)+2\)了
如果推不出，也可以求出\(F_{i-1},F_{i},F_{i+1}\)再来求答案
原文：https://www.cnblogs.com/xuyixuan/p/11317006.html