場合の数の問題を線型代数で解く

こんにちは．今回は以下の問題を線型代数を使って解いてみます．

${}$

方針

好きな数字3つの選び方$\binom{9}{3}$通りに対応する頂点$\{V_{i,j,k}\}_{1\leq i< j< k\leq9}$を用意し，添え字が重複しないような頂点同士を辺で結んだグラフを考えると，このグラフの長さ10の閉経路の数を数える問題に帰着できます．

さらにこのグラフの隣接行列，つまり頂点$i$と$j$が辺で結ばれているなら$1$を，そうでないなら$0$を$i,j$成分にもつような行列を$A$とすれば，一般に$A^ne_i$の$e_j$成分が頂点$i$から$j$への長さ$n$の経路の個数になりますから，今回の問題の答えは$\tr A^{10}$になります．これは$A$の固有値が分かれば計算ができます．

${}$

解答

一般化した次の問題を解く．

上述の通り隣接行列を考える．添字集合を$I=\{S\subset \{1,\ldots,N\}\mid |S|=k\}$として$\{e_{S}\}_{S\in I} $を基底とする$\binom{N}{k}$次元$\C$-線型空間$V$を考え，行列$A=(a_{S,T})_{S,T\in I}\in\mathrm{End}\,V$を
$$ a_{S,T}=\begin{cases}1 & (S\cap T=\varnothing)\\ 0 & (S\cap T \neq \varnothing)\end{cases}$$
で定めるとき，$\tr A^n$の値を求めればよい．このために$A$の固有値を求めたい．

${}$

ただ，いろいろな$k$をまとめて考えたいので，以下のようにしてみる．

$R=\C[X_1,\ldots,X_N]/(X_1^2,\ldots,X_N^2)$とし，$S\subset \{1,\ldots,N\}$に対して$X_S:=\prod_{i\in S}X_i$と書くことにする．$R$は$X_S$たちを$\C$-基底とする$2^N$次元$\C$代数である．$R$のdegree$k$-part $R_k$が上述の$V$に対応する．

$\Phi\in\mathrm{End}_{vec.sp}\,R$を
$$ \Phi(X_S)=\sum_{\begin{array}{cc}|T|=|S|\\T\cap S=\varnothing\end{array}}X_T$$
で定めると，$\Phi|_{R_k}$が先の$A$に等しい．$\Phi$を調べることにする．

${}$

さて，一般に行列$A$の固有値を求めるには三角化すればよく，そのためには$A$安定な部分空間$V_i$によるフィルトレーションであって$V_i/V_{i+1}$上$A$が定数倍で作用するものを見つければよい．

また今回の$R$は変数の置換により$\mathfrak{S}_N$の作用が入っており，$\Phi$は定義から$\mathfrak{S}_N$-homなので，$R$のフィルトレーションであって変数の置換で不変なものを考えたい．

そこで，$s=X_1+\ldots+X_N$として，イデアル$(s)^m$による$R$のフィルトレーション
$R\supset(s)\supset\cdots\supset(s)^N\supset(s)^{N+1}=0$
を考える．

${}$

$X_1,\ldots,X_N$の$m$次基本対称式を$e_m$として，$s^m=m!\,e_m$， $s^{N+1}=0$であることに注意する．

$(s)^m/(s)^{m+1}$での$\Phi$の振る舞いを調べると，

$$ \begin{align} \Phi(s^mX_S) &= m!\Phi(e_m X_S)\\[5pt] &=m!\sum_{\begin{array}{cc}|U|=m\\U\cap S=\varnothing\end{array}}\Phi(X_{S\cup U})\\[5pt] &=m!\sum_{\begin{array}{cc}|U|=m,|T|=|S|+m\\ S,T,Uは互いに素\end{array}}X_T\\[5pt] &= m!\binom{N-|S|-m}{m}\sum_{\begin{array}{cc}|T|=|S|+m\\T\cap S=\varnothing\end{array}}X_T\qquad \text{（$U$の選び方の数を数える）}\\[5pt] &=m!\binom{N-|S|-m}{m}\frac{1}{(|S|+m)!}\Big(s-\sum_{i\in S}X_i\Big)^{|S|+m}\\[5pt] &\equiv \binom{N-|S|-m}{m}\frac{m!}{(|S|+m)!}\binom{|S|+m}{m}s^m\Big(-\sum_{i\in S}X_i\Big)^{|S|}\mod(s)^{m+1}\\[5pt] &=(-1)^{|S|}\binom{N-|S|-m}{m}s^mX_S \end{align} $$

となり，$(s)^m/(s)^{m+1}$のdegree$k$-partでは（$|S|=k-m$として）$\Phi|_{R_k}$は$\lambda_m=(-1)^{k-m}\binom{N-2k+m}{m}$倍で作用しているとわかる．

${}$

最後に，固有値の重複度を計算する．
$\dim_\C (s)^m\cap R_k=\big|\{S\mid |S|=k-m\}\big|=\binom{N}{k-m}$より，固有値$\lambda_m$の重複度は$d_m=\binom{N}{k-m}-\binom{N}{k-m-1}$である．

以上より，答えは$\displaystyle \tr A^n=\sum_{m=0}^kd_m\lambda_m^n=$$\displaystyle\sum_{i=0}^k\left(\textstyle\binom{N}{i}-\binom{N}{i-1}\right)\left((-1)^i\textstyle\binom{N-k-i}{k-i}\right)^n$である．

${}$

最初の問題の答えは，$N=9,k=3,n=10$を代入して，

$1\times20^{10}+8\times(-10)^{10}+27\times4^{10}+48\times(-1)^{10}=(2^{10}+8)\cdot 10^{10}+27\cdot2^{20}+48$$=10320028311600$通りである．

${}$

問題のアイディア出しおよび計算の確認をChatGPTに手伝ってもらいました．

${}$

${}$