特征多项式简化多变量常系数线性递推

化零多项式，例如特征多项式可以优化单变量的线性递推（详见博客《特征多项式优化线性递推》），我们来考虑多变量线性递推。我们先来看几个问题，从中体会一下怎么利用化零多项式优化线性递推。

好集个数

如果一个集合的全体元素之和为 $3$ 的倍数，我们则称之为好集（空集元素之和为 $0$ ）。
那么，在集合 $\{1,2,3,…,3n\}$ 的所有子集中，有多少个好集？

这道题(个人认为的)最漂亮的做法并不是利用线性递推，我将这个做法补充在文章结尾。

我们暴力一点，假设 $a_n$ 表示和为 $3$ 的倍数的集合个数，$b_n$ 表示和除 $3$ 余 $1$ 的集合个数，$c_n$ 表示和除 $3$ 余 $2$ 的集合个数,于是我们有：

$\begin{bmatrix}4 & 2 & 2\\2 & 4 & 2\\2 & 2 & 4\end{bmatrix}$ $\begin{bmatrix} a_n \\ b_n \\ c_n \end{bmatrix}$ $=\begin{bmatrix} a_{n+1} \\ b_{n+1} \\ c_{n+1} \end{bmatrix}$

我们记：

$A=\begin{bmatrix}4 & 2 & 2\\2 & 4 & 2\\2 & 2 & 4\end{bmatrix}$

考虑 $A$ 的特征多项式 $f(\lambda)=-\lambda^3+12\lambda^2-36\lambda+32$。
根据 Caylay-Camilton 定理我们有 $f(A)=-A^3+12A^2-36A+32I=0$,于是我们得到：

$(-A^3+12A^2-36A+32I)\begin{bmatrix} a_n \\ b_n \\ c_n \end{bmatrix}=0$ $A^3\begin{bmatrix} a_n \\ b_n \\ c_n \end{bmatrix}-12A^2\begin{bmatrix} a_n \\ b_n \\ c_n \end{bmatrix}+36A\begin{bmatrix} a_n \\ b_n \\ c_n \end{bmatrix}-32\begin{bmatrix} a_n \\ b_n \\ c_n \end{bmatrix}=0$ $\begin{bmatrix} a_{n+3} \\ b_{n+3} \\ c_{n+3} \end{bmatrix}-12\begin{bmatrix} a_{n+2} \\ b_{n+2} \\ c_{n+2} \end{bmatrix}+36\begin{bmatrix} a_{n+1} \\ b_{n+1} \\ c_{n+1} \end{bmatrix}-32\begin{bmatrix} a_n \\ b_n \\ c_n \end{bmatrix}=0$ $\begin{bmatrix} a_{n+3}-12a_{n+2}+36a_{n+1}-32a_n \\ b_{n+3}-12b_{n+2}+36b_{n+1}-32b_n \\ c_{n+3}-12c_{n+2}+36c_{n+1}-32c_n \end{bmatrix}=0$

故：$a_{n+3}-12a_{n+2}+36a_{n+1}-32a_n =0 \Leftrightarrow a_{n+3}=12a_{n+2}-36a_{n+1}+32a_n$。

我们就根据转移矩阵得到递推式了，之后我们就可以使用特征方程法或者生成函数法求通项了，这都是后话。
值得注意的是，如果使用特征方程法，其特征方程就是 $f(\lambda)=0$（想想为什么） 。

一般化

我们发现这个方法适用于任何有较多变量的线性递推（其实任何能用转移矩阵转移的都可以），我们只需要求出转移矩阵的特征多项式。那么对于线性递推中的每一个变量，其递推式系数就是特征多项式前的系数。

有趣的是，每一个不同的变量拥有同样的递推式和特征方程。

好集个数问题的一个非递推解法

考虑函数 $f(x)=(x+1)(x^2+1)(x^3+1)…(x^{3n}+1)$ 的展开式。我们记：

$f(x)=a_0x^0+a_1x^1+a_2x^2+...$ 考虑乘法分配律的过程，我们可以知道 $a_t$ 表示元素之和为 $t$ 的子集个数。于是我们设： $p=a_0+a_3+a_6+...$ $q=a_1+a_4+a_7+...$ $r=a_2+a_5+a_8+...$ 于是 $p$ 即为答案。我们记三次单位根为 $\omega=\frac{-1+\sqrt{3}i}{2}$ 。于是有 $\omega^3=1$ 以及 $\omega^2+\omega+1=0$ 我们考虑把 $1,\omega,\omega^2$ 带入 $f(x)$ 可以得到： $f(1)=a_0+a_1+a_2+...=p+q+r=(1+1)(1+1)...(1+1)=2^{3n}$ $f(\omega)=a_0+a_1\omega+a_2\omega^2+a_3+a_4\omega+a_5\omega^2+...=p+\omega q+\omega^2r=((1+1)(\omega+1)(\omega^2+1))^n=2^n$ $f(\omega^2)=a_0+a_1\omega^2+a_2\omega+a_3+a_4\omega^2+a_5\omega+...=p+\omega^2 q+\omega r=((1+1)(\omega^2+1)(\omega+1))^n=2^n$

三式相加可得 $3p=2^{3n}+2^{n+1}$ ,答案即 $p=\frac{2^{3n}+2^{n+1}}{3}$ 。