数学の命題示しました

主に組合せ論について,読んだ本で出てきたことや,考えたことを書きます.

f-型数列の個数のリスト

 f-型数列と呼んでいるオブジェクトは, fに入れるものを変えることにより,既存のいろんな数列を表すことができる.
 fにいろいろ入れてみて,出てきたものをリスト化しておく.
(「 f-型数列」は筆者の造語です.これを表す言葉がもうあるのを知ってる方は教えて頂けると幸いです.)

 f-型数列の定義

自然数の集合 \mathbb{N}\triangleq\{1,2,\ldots\}の部分集合の列
 f=(f(1),f(2),\ldots)に対し,
(つまり f(i)\subseteq\mathbb{N},\ i=1,2,\ldotsが与えられているとし,)
数列 a=(a_1,a_2,\ldots,a_n)であって,条件

  •  a_1=1,
  •  a_{i+1}\in f(a_i),\qquad i=1,\ldots,n-1

を満たすものを,長さ n f-型数列という.

与えられた fに対して,長さ n f-型数列の個数を e[f]_n とかく.
そして,数列 (e[f]_0,e[f]_1,e[f]_2,\ldots)を, f-型数列の個数列という.

例:

 f\triangleq([2],[3],[4],\ldots)のとき.(但し, [n]\triangleq\{1,\ldots,n\}
長さ 0 f-型数列:1通り
長さ 1 f-型数列:1通り
長さ 2 f-型数列: (1,1),(1,2)の2通り
長さ 3 f-型数列: (1,1,1),(1,1,2),(1,2,1),(1,2,2),(1,2,3)の5通り
...
 f-型数列の個数列は (1,1,2,5,14,42,\ldots)であり,それはカタラン数列であることが証明できる.


以下,与えた fに応じて,f-型数列の個数列のリストを作成した.
(中には予想も含まれるので注意.)

リストの見方

リストは三列からなる.

  • 左の列は f
  • 中央の列は,その fによってできるf-型数列の個数列の名前や,オンライン数列大辞典へのリンク.
  • 後ろの列は,筆者がその証明を知っているか,知らないかの区別を記している.「○」は筆者が証明を知っていることを表し,「X」は証明があってもそれを筆者が知らないか,または予想であることを表す.

なお,列 fによっては, fの最初の数項だけが重要で,それ以降の項は f-型数列の個数列に無関係な場合もある.その場合は,初項から必要な項までのみを記す.

リスト(最終更新日: 2023年02月02日)

自然数の部分集合の列 f  f-型数列の個数列 証明
 (\{1\})  (1,1,1,\ldots)
 (\{2\},\{1,2\})  (1,1,1,2,3,5,\ldots), フィボナッチ数列 F_n
 (\{1,2\},\{1,2\})  (1,1,2,4,8,16,\ldots),\ 2^n
 (\{1,2,3\},\{1,2\},\{1,2,3\}) フィボナッチ数列の偶数項 F_{2n} X
 ([4],[2],[3],[4]) 母関数 \frac{(1-x)^3}{(1 - 4x + 3x^2 - x^3)}の数列.A052529 - OEIS X
 ([2],[3],[4],[5],\ldots) カタラン数 C_n
 ([3],[3],[4],[5],\ldots)  \binom{2n}{n}/2
 ([4],[3],[4],[5],[6],\ldots) 母関数 \frac{1}{(1-xC(x)^3)}の数列. C(x)はカタラン数の母関数 X
 ([4],[4],[4],[5],[6],\ldots) 母関数 \frac{(1-2xC(x))}{(1-xC(x))}の数列. X
 ([3],[4],[5],[6],\ldots)  \binom{3n}{n}/(2n+1), A001764 - OEIS X
 ([1+r],[2+r],[3+r],[4+r],\ldots)  \binom{(r+1)n}{n}/(rn+1) X
 ([2],[4],[6],\ldots) ある種の二分木の数, A002449 - OEIS X
 ([3],\{1\},[3],[4],[5],\ldots) ある種の木, A000958 - OEIS X
 ([3],\{2\},[3],[4],[5],\ldots) カタラン数の部分和, A014138 - OEIS X
 (\{1,3\},\{2\},[3],[4],[5],\ldots) カタラン数の隣接項の和-1,  C_{n+1}+C_n-1 X
 (\{1,2\},\{1,2,3\},\{2,3,4\},\{3,4,5\},\ldots) directed animalの個数, A005773 - OEIS X

要素が全部1のヘッセンベルグ行列のn乗の(1,1)成分はカタラン数

対角成分の一つ上まで非零要素が入っていてよいような行列をヘッセンベルグ行列という.
行列 A\triangleq(\chi_{i+1\geq j})_{i,j=1}^{\infty}

 =\begin{pmatrix}
1&1&0&0&0&0&0&\cdots\\
1&1&1&0&0&0&0&\cdots\\
1&1&1&1&0&0&0&\cdots\\
1&1&1&1&1&0&0&\cdots\\
1&1&1&1&1&1&0&\cdots\\
1&1&1&1&1&1&1&\cdots\\
1&1&1&1&1&1&1&\cdots\\
\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\cdots\\
\end{pmatrix}
をここでは「要素が全部1のヘッセンベルグ行列」と呼ぶ.( \chi_Pは命題 Pの特性関数.)

命題
 n自然数とする.
行列 A^n (1,1)成分はカタラン数である.つまり
 \displaystyle\left[A^n\right]_{1,1} =C_n=\frac{1}{n+1}\binom{2n}{n}が成り立つ.
証明
有向グラフ G\triangleq(V,E) V\triangleq\mathbb{N}=\{1,2,\ldots\}
 \displaystyle E\triangleq\bigcup_{i=1}^\infty\bigcup_{j=1}^{i+1}\{(i,j)\}
により定義すると,行列 Aはグラフ Gの隣接行列である.
よって, A^n (1,1)成分は Gの節点 1から節点 1への,長さ nの歩道の数である.
ここで,グラフ Gの全ての節点は節点1への枝を持つので,上記の歩道の数は節点 1を始点とする長さ n-1の歩道の数に等しい.

そのような歩道を,訪れた順に節点を並べることにより
 (a_1,a_2,\ldots,a_n)という節点の列として表記する.
 a_1=1である.また,歩道の長さが n-1なので,この列の長さは nなことに注意.)
するとグラフの作り方から 1\leq a_i\leq a_i+1が成り立つ.

例:長さ 3の歩道は
 (1,1,1),(1,1,2),(1,2,1),(1,2,2),(1,2,3)の5通り.

このような列から「サイズ nのballot sequence」への全単射を構成する.
サイズ nのballot sequenceとは, n個の 1 n個の -1からなる長さ 2nの列で,すべての部分和が非負なものである.
サイズ nのballot sequenceの数はカタラン数 C_nであることが知られている.
(例えば [1]の問77を見よ.)

例:サイズ 3のballot seqenceは
 (1,1,1,-1,-1,-1),(1,1,-1,1,-1,-1),(1,1,-1,-1,1,-1),(1,-1,1,1,-1,-1),(1,-1,1,-1,1,-1)の5通り.


長さ nの歩道からサイズ nのballot sequenceへの全単射は以下のように作る.([1]の問80より.)
 a_{n+1}\triangleq 1, b_i\triangleq a_i-a_{i+1}+1とする.
歩道 (a_1,\ldots,a_n)の各 a_iを, 1,-1^{b_i}に置き換える.
 -1^{b_i}は, b_i個の -1を表す.)

例: (1,2,1)\mapsto(1,1,-1,-1,1,-1)

(証明終わり)

参考文献:
StanleyのCatalan numbers (2015)
www.amazon.com

両側Dyck路と(3,3,4,5,6,...)型数列の全単射

二次元平面において点 (0,0)から出発し,ステップ \nearrow(+1,+1) \searrow(+1,-1)を用いて点 (2n,0)までゆくパスをサイズ nの両側Dyck路という.
サイズ nの両側Dyck路の数は \binom{2n}{n}である.

サイズ nの両側Dyck路のうち,最初のステップが \nearrowであるものの集合を \mathbf{B}_nとする.
 |\mathbf{B}_n|=\frac{1}{2}\binom{2n}{n}
である.

集合 \mathbf{B}_{5}の両側Dyck路の例


次に「 (3,3,4,5,6,\ldots)型数列」を定義する.
写像 f:\mathbb{N}\to \mathbb{N}が与えられているとする.
自然数の列 s=(s_1,s_2,\ldots,s_n)で条件

  •  s_1=1
  •  s_i=rならば, 1\leq s_{i+1}\leq f(r)\ (1\leq i\leq n-1)

を満たすものを, f-型数列,あるいは (f(1),f(2),f(3),\ldots)型数列と呼ぶことにする.

サイズ n(3,3,4,5,6,\ldots)型数列とは,長さ n自然数の列
 s=(s_1,s_2,\ldots,s_n)
であって,以下の条件を満たすものである.

  •  s_1=1
  •  s_i\leq 2のとき, s_{i+1}\in\{1,2,3\} s_{i}\geq 3のとき, s_{i+1}\in \{1,2,\ldots,s_i+1\}

ただし 1\leq i\leq n-1
サイズ n(3,3,4,5,6,\ldots)型数列の集合を \mathbf{S}_nとする.

例えば, (1,3,4,4,2)\in\mathbf{S}_5である.

本稿では以下を証明する.
命題
集合 \mathbf{S}_nと集合 \mathbf{B}_nの間に全単射が作れる.

またここから, |\mathbf{S}_n|=\frac{1}{2}\binom{2n}{n}がわかる.


この命題を証明するために,いくつか準備をする.
以下では集合 \mathbf{B}_nの両側Dyck路を B=(B_1,B_2,\ldots,B_{2n})\in\mathbf{B}_n,\ B_i\in\{\nearrow,\searrow\}とかく.
このとき集合 \mathbf{B}_nの定義から B_1=\nearrowである.
両側Dyck路 B\in\mathbf{B}_nに対し自然数 {\rm add}(B)\in\mathbb{N}を以下のように定義する.

  •  B_2=\nearrowのとき, {\rm add}(B)\triangleq \min\{i\mid i\geq 3,  B_i=\searrow\}
  •  B_2=\searrowのとき, {\rm add}(B)\triangleq \min\{i\mid i\geq 3, B_i=\nearrow\}

集合 \mathcal{B}_n\subset \mathbf{B}_{n}\times\mathbb{N}
 \mathcal{B}_n\triangleq\{(B,i)\mid B\in\mathbf{B}_{n}, 1\leq i\leq {\rm add}(B), i\in\mathbb{N}\}
と定める.

補題
集合 \mathcal{B}_nと集合 \mathbf{B}_{n+1}の間に全単射が作れる.
証明
集合 \mathcal{B}_nと集合 \mathbf{B}_{n+1}の間の全単射 gを作る.
 (B,i)\in\mathcal{B}_nをとる.サイズ n+1の両側Dyck路 B'

  •  i=1または, i>1かつ B_{i-1}=\nearrowのとき

 B'\triangleq(B_1,\ldots,B_{i-1},\nearrow,\searrow,B_{i},\ldots,B_{2n})

  •  i>1かつ B_{i-1}=\searrowのとき

 B'\triangleq(B_1,\ldots,B_{i-1},\searrow,\nearrow,B_{i},\ldots,B_{2n})
と定める.
すると,上記で \nearrow,\searrowまたは \searrow,\nearrowを入れた場所は,
パス B' B'=(\nearrow,\searrow,\searrow,\ldots)という形のときは最初に現れる谷として,また
パス B'がそれ以外の形のときは最初に現れる頂上として同定可能である.
ゆえに B'を見れば (B,i)が復元できるので対応 g\colon(B,i)\mapsto B'全単射である.
(証明終わり)

 B=(\nearrow,\searrow,\searrow,\searrow,\nearrow,\nearrow)\in\mathbf{B_3}としたときの, g(B,i),\ i=1,2,3,4,5を説明する図.

補題
 (B,i)\in\mathcal{B}_nとする.上記で定めた全単射 gについて,
 i\leq 2のとき,  {\rm add}(g(B,i))=3
 i\geq 3のとき,  {\rm add}(g(B,i))=i+1
が成り立つ.
証明
 B_2=\nearrowのときと B_2=\searrowのときの両方について,
 i=1,\ i=2, \geq 3の場合に場合分けして確かめればわかる.


命題の証明
数列 s=(s_1,s_2,s_3,_\ldots,s_n)\in\mathbf{S}_nをとる.
上記補題により,ある i\ (1\leq i\leq n-1)とある B\in\mathbf{B}_{k}に対して (B,s_{i})\in\mathcal{B}_kならば, (g(B,s_i),s_{i+1})\in\mathcal{B}_{k+1}である.よって,
 s\in\mathbf{S}_nに対応する \mathbf{B}_nの元を
 g(\cdots g(g(g(\nearrow\searrow,s_2),s_3),s_4)\cdots),s_n)
と定めることができる.
 gが可逆なのでこの対応は可逆である.
(証明終わり)

 s=(1,3,4,4,2)に対応する両側Dyck路を作る様子.上から順に g(\nearrow\searrow,3) g(g(\nearrow\searrow,3),4) g(g(g(\nearrow\searrow,3),4),4) g(g(g(g(\nearrow\searrow,3),4),4),2)

1円玉,5円玉,10円玉を使ってN円をぴったり支払う方法のq-母関数

非負整数の集合を \mathbb{Z}_0とかく.
1円玉,5円玉,10円玉を使って N円をぴったり支払う方法の数とは,集合
 S(N)\triangleq\{(a,b,c)\mid a+5b+10c=N,\ a,b,c\in\mathbb{Z}_0\}
の要素数である.

以前の記事
(1円玉,5円玉,10円玉を使ってN円をぴったり支払う方法の数 - 数学の命題示しました)
では,非負整数 Nが,非負整数 n r\in\{0,1,2,3,4\}を用いて
 N=10n+rとかけるとき, |S(N)|=(n+1)^2であることを示した.

本記事ではこの集合について単なる要素数より詳しい下式を証明する.

定理
 nは非負整数とし, r\in\{0,1,2,3,4\}とする.集合 S(r,n)
 S(r,n)\triangleq\{(a,b,c)\mid a+5b+10c=10n+r,\ a,b,c\in\mathbb{Z}_0\}
と定める.このとき
 \displaystyle\sum_{(a,b,c)\in S(r,n)}q^{b+c}=(1+q+\cdots+q^{n})^2
が成立する.

補足
右辺は rには依存しない.
 q\to 1とすると,以前証明した式に戻る.

証明
まず,任意の非負整数 nに対して, S(0,n) S(r,n),\ r\in\{1,2,3,4\}の間には
 S(0,n)\ni (a,b,c)\mapsto (a+r,b,c)\in S(r,n)
という全単射がとれる.
だから,証明は S(0,n)に対して行えばよい.

第一象限の点の集合
 A\triangleq \{(b,c)\mid (a,b,c)\in S(0,n)\}
 =\{(b,c)\mid a+5b+10c=10n,\ a,b,c\in\mathbb{Z}_0\}
を考える.これは
 A=\{(b,c)\mid b+2c\leq 2n,\ b,c\in\mathbb{Z}_0\}
とかける.

また,第一象限の点の集合
 B\triangleq \{0,\ldots,n\}\times\{0,\ldots,n\}
も考える.

集合 Aから集合 Bへの全単射
 A\ni(b,c)\mapsto (s,t)\in B
であって,
 b+c=s+t
を満たすものを作れば証明が完了する.
以下,そのような全単射を作る.

 n=6の例で全単射を説明する.
集合 Aと集合 Bを図示すると以下の図 (上)のようになる.

集合 Aから集合 Bへの全単射は図の (下)のように作る.
すなわち,集合 Aにおいて直線 y=d-xの上に乗っている点 (b,c)を、直線と平行に
適当な距離だけ北西へ移動させると,集合 Bに一致させることができる。
この移動によって, b+cの値は変わらない。

(証明終わり)

ケーリー・ハミルトンの定理の組合せ論的証明

1,概要

正方行列 Aの固有多項式 p_A(\lambda)\triangleq\det(A-I\lambda)について, p_A(A)=Oが成り立つ.
これをCayley–Hamiltonの定理という.

Cayley–Hamiltonの定理は線形代数のクラスの後半で習うのが普通であるが,実は線形代数の知識を用いずに証明できる.
具体的には,置換を用いた行列式の定義と行列の n乗の定義から,組合せ論的考察により証明できる.

本記事で紹介する証明は,組合せ論的な視点から線形代数を再構成したBrualdi [1]の本からとったものである.

以下第2節ではまず準備として行列式や固有多項式を,組合せ論的オブジェクトの母関数として解釈する.
次に第3節で,行列の n乗とグラフ上の歩道の対応を復習する.
最後に第4節で,上の二つを組み合わせてCayley–Hamiltonの定理を証明する.

2,行列式のHarary-Coater流の定義

以下で述べるように,行列式はグラフのサイクルの母関数として解釈できる.
この考え方はBrualdi [1]の第4章に詳しく,行列式のHarary-Coater流の定義と呼ばれる.

グラフ理論の用語の定義

有向グラフ G=(V,E)部分グラフとは,節点集合 V'\subseteq Vと枝集合 E'\subseteq Eをもつ有向グラフ (V',E')である.
部分グラフの節点集合がもとのグラフの節点集合に等しいとき,つまり V'=Vのとき,グラフ (V,E')全域部分グラフという.
以下では \mathbb{K}はある体を表す。
有向グラフ G=(V,E)枝重みとは,関数 w\colon E\to\mathbb{K}である.有向グラフと枝重みの組 (G,w)のことを,重み付き有向グラフという.
重み付き有向グラフ (G,w)の重み w(G)を,グラフの枝重みの積 w(G)\triangleq\prod_{e\in E}w(e)と定める.

有向グラフが2-正則であるとは,全ての節点の入次数と出次数が1であることである.
(これは一般的な言葉遣いとは違うかもしれない.)
2-正則であるような全域部分グラフのことを2-正則全域部分グラフという.
下図のように,2-正則全域部分グラフは有向グラフの全ての節点を,いくつかの交わりを持たないサイクルによって覆う方法であると思うこともできる.

2-正則全域部分グラフの説明

 n次正方行列 A=(a_{i,j})対応する有向グラフ G(A)とは,
節点集合 V\triangleq\{1,2,\ldots,n\}と,枝集合 E\triangleq \{(i,j)\mid a_{i,j}\neq 0,\ i,j\in\{1,\ldots,n\}\}をもつ有向グラフ G\triangleq (V,E)である.
有向グラフ G(A)の枝重み w\colon E\to\mathbb{K}を,枝 (i,j)\in Eに対して w( (i,j) )\triangleq a_{i.j}と定める.

 n次正方行列 Aに対し,有向グラフ G(A)の2-正則全域部分グラフの集合を \mathcal{L}(A)とかく.
グラフ \gamma\in\mathcal{L}(A)に含まれるサイクルの数(連結成分の数と言い換えてもよい)を c(\gamma)とかく.
下図はその例.

グラフG(A)と集合L(A)の説明

図中で枝重みを青色で書いている.

行列式のサイクル母関数としての表示

これらの用語を用いると,行列式は次のよう書ける.

定理1 (サイクルを用いた行列式の表示)
 n次正方行列 A行列式 \det Aは,以下の和に等しい.
\displaystyle\det A\triangleq\sum_{\gamma\in\mathcal{L}(A)}(-1)^{n-c(\gamma)}w(\gamma).
証明の概略
行列式を置換を用いて定義し,置換のサイクル分解を考える.
(証明終わり)


これについては,例を見るとより納得できるだろう.
上の図で登場した行列

 A=\begin{pmatrix}
a_{1,1}&a_{1,2}&a_{1,3}&0\\
a_{21}&a_{22}&0&0\\
0&0&a_{33}&a_{34}\\
0&a_{42}&0&a_{44}
\end{pmatrix}
行列式
 \det A=a_{{1,1}}a_{{2,2}}a_{{3,3}}a_{{4,4}}-a_{{1,3}}a_{{2,1}}a_{{3,4}}a_{{4,2}}-a_{{1,2}}a_{{2,1}}a_{{3,3}}a_{{4,
4}}
である.
これは以下の図に示すとおり, \mathcal{L}(A)の各要素 \gammaについて,その重み (-1)^{n-c(\gamma)}w(\gamma)を足し合わせたものにひとしい.

 \gamma\in\mathcal{L}(A)とその重み

固有多項式と,2-正則部分グラフ

 n次正方行列 Aに対し,有向グラフ G(A)の (全域でなくてもよい)2-正則部分グラフの集合を \mathcal{C}(A)とかく.
有向グラフ G(A)の節点のうち,部分グラフ \gamma\in\mathcal{C}(A)に含まれていないものの数を, {\rm ip}(\gamma)とかく (isolated points,孤立点の意).

すると以下が成り立つ.

定理2 (サイクルを用いた固有多項式の表示)
 n次正方行列 Aに対し
\displaystyle\det (A-\lambda I)=\sum_{\gamma\in\mathcal{C}(A)}(-1)^{n-c(\gamma)}w(\gamma)\lambda^{{\rm ip}(\gamma)}
が成り立つ.
証明の概略
まず定理1を用いて行列式 \det(A-\lambda I)を2-正則全域部分グラフの母関数として書く.
グラフ \gamma\in\mathcal{L}(A-\lambda I)に自己ループがあるとき,その自己ループしている枝の重みは a_{i,i}-\lambdaであり,それを枝重み a_{i,i}の自己ループとして残すか,重み \lambdaの孤立点として扱うかを選ぶことができる.
(証明終わり)

例として,以下の行列 Aを考える.

 A=\begin{pmatrix}
a_{1,1}&a_{1,2}\\
a_{2,1}&a_{2,2}
\end{pmatrix}
行列 Aの固有多項式
 \det(A-\lambda I)=\lambda^2-\lambda(a_{1,1}+a_{2,2})+a_{1,1}a_{2,2}-a_{1,2}a_{2,1}
である.
一方,グラフ G(A)の2-正則部分グラフの重み和は下図の通り.

グラフを用いた固有多項式の解釈

3,行列の n乗と,グラフ上の歩道の対応

グラフの隣接行列を n乗した行列の第 (i,j)成分は,グラフの節点 iから節点 jへの長さ nの歩道の母関数である.
これはグラフ理論マルコフ連鎖の理論でよく使う事実であるから,知っている人も多いと思う.
本節ではこの事実を復習する.

枝重み付き有向グラフ (V,E)の節点 sから節点 tへの歩道とは,節点の列
 (s=v_0,v_1,v_2,\ldots,v_{n-1},v_n=t), \quad v_i\in V
であって,隣り合う節点 v_i,から v_{i+1}への枝がある,つまり
 (v_i,v_{i+1})\in E,\quad i\in\{0,1,\ldots, n-1\}
なるものである.
歩道 \mu=(v_0,v_1,\ldots,v_n)の重み w(\mu)を,枝重みの積により
 w(\mu)\triangleq\prod_{i=0}^{n-1}w( (v_i,v_{i+1}) )
と定める.
歩道 \mu長さ |\mu|を,列 \muの要素数 -1と定める.
節点 sから節点 tへの歩道の集合を s\rightsquigarrow tとかく.
すると以下が成り立つ.

定理3 (行列の n乗とグラフの歩道の関係)
 n次正方行列 Aに対し A^kの第 (i,j),\ i,j\in\{1,\ldots,n\}成分 [A^k]_{i,j}
 \displaystyle[A^k]_{i,j}=\sum_{\substack{\mu\colon i\rightsquigarrow j\\|\mu|=k}}w(\mu)
と表せる.但し和は節点 iから節点 jへの長さ kの全ての歩道にわたってとる.



4,Cayley–Hamiltonの定理の組合せ論的証明

Cayley–Hamiltonの定理
 n次正方行列 Aに対し p_A(\lambda)\triangleq\det(A-\lambda I)と定めると,
 p_A(A)=Oが成り立つ.

証明
まず定理2から,
\displaystyle p_A(\lambda)=\sum_{\gamma\in\mathcal{C}(A)}(-1)^{n-c(\gamma)}w(\gamma)\lambda^{{\rm ip}(\gamma)}
である.
次に p_A(\lambda)に行列 Aを代入すると,
\displaystyle p_A(A)=\sum_{\gamma\in\mathcal{C}(A)}(-1)^{n-c(\gamma)}w(\gamma)A^{{\rm ip}(\gamma)}
となる.
定理3から,行列 p_A(A)の第 (i,j),\ i,j\in\{1,\ldots,n\}成分 [p_A(A)]_{i,j}
 \displaystyle[p_A(A)]_{i,j}=\sum_{\gamma\in\mathcal{C}(A)}\sum_{\substack{\mu\colon i\rightsquigarrow j\\|\mu|={\rm ip}(\gamma)}}(-1)^{n-c(\gamma)}w(\gamma)w(\mu)
である.

以下,やることは,対合を作って [p_A(A)]_{i,j}=0を示すことである.

行列 A 1\leq i,j\leq nに対して,ケーリーハミルトン配置の集合 \mathcal{K}(A;i,j)を以下のように定義する.
 \mathcal{K}(A;i,j)\triangleq \{(\gamma,\mu)\mid \gamma\in\mathcal{C}(A),\  \mu\colon i\rightsquigarrow j,\ |\mu|={\rm ip}(\gamma)\}.

以下はケーリーハミルトン配置の例である.

ケーリーハミルトン配置の例

言葉でいうと,ケーリーハミルトン配置とは,グラフ G(A)上のいくつかのサイクル(上図赤色)と,節点 iから jへの歩道(上図青色)の重ね合わせであって,歩道の長さがサイクルに含まれない G(A)の節点の数(上図の例では4個)に等しいものである.

これを用いると,今考えている和はケーリーハミルトン配置にわたる和として
(★)  \displaystyle [p_A(A)]_{i,j}=\sum_{(\gamma,\mu)\in \mathcal{K}(A;i,j)}(-1)^{n-c(\gamma)}w(\gamma)w(\mu)
とかける.

式(★)が0であることを示すには以下のような対合 \psiを構成すればよい.

 \psi\colon  \mathcal{K}(A;i,j)\ni (\gamma,\mu)\mapsto (\gamma',\mu')\ni\mathcal{K}(A;i,j)
であって,
 w(\gamma')w(\mu')=w(\gamma)w(\mu),
 c(\gamma')=c(\gamma)\pm 1
を満たすもの.

以下,そのような対合を構成する.
任意のケーリーハミルトン配置 (\gamma,\mu)について,
歩道 \mu \mu=(v_0,v_1,\ldots,v_\ell)とすると,以下の1, 2のどちらかが成り立つような最小の添字 kが存在する.

  1. 節点 v_kは,グラフ \gammaのあるサイクルに含まれる.
  2. より小さい添字 r\lt kが存在して, v_r=v_kである.つまり,歩道 \muが節点 v_kを訪れるのは二度目である.

また,これらの二つが同時に成り立つことはない.

ここから,対合を次のように構成する.

1. が成り立つとき,節点 v_kを含むサイクルをグラフ \gammaから消し,歩道 \muに加える.
2. が成り立つとき,歩道 \muの中の v_r,v_{r+1},\ldots,v_kという部分を歩道から消し,サイクルとしてグラフ \gammaに追加する.

図で書くと以下のようになる.

対合の説明

この対応は所望の対合である.
(証明終わり)

線分上に右詰めで並べる母関数の行列式表示

 1\times長さ nの場所の上に,以下の二種類のタイル

  •  1\times長さ 1のタイル
  •  1\times長さ 2のタイル

右詰めで 0個以上敷くことを考える.
このような敷き方の集合を \mathcal{T}_nとかく.
(記事下に \mathcal{T}_3の例があるのでそれも参照せよ.)

 f(n)をフィボナッチ数とすると,このような敷き方は
 \displaystyle\sum_{i=0}^nf(n)
通りである.ここではより精密に数える.

タイルを置く場所に 0,\ldots,nの数直線を書き,

  •  [k,k+1 ]の場所に置かれた長さ 1のタイルの重みは -a_{k,k},
  •  [k,k+2 ]の場所に置かれた長さ 2のタイルの重みは -a_{k,k+1}

とする.
タイルの敷き方 \omegaの重み w(\omega)は,含まれるタイルの重みの積によって定める.
タイルの敷き方 \omegaに対して,タイルの長さの和を |\omega|とかく.

以下は, n=9のときのタイルの敷き方 \omega\in\mathcal{T}_nとその重み w(\omega)t^{|\omega|}の例.


この重みに関する母関数
 \displaystyle\sum_{\omega\in \mathcal{T}_n}w(\omega)t^{|\omega|}
は以下のような行列式表示を持つ.
  -\det\left[ \begin {array}{ccccccc} a_{{0,0}}t-1&a_{{0,1}}{t}^{2}-1&-1&-1&-1&-1&-1\\ 1&a_{{1,1}}t&a_{{1,2}}{t}^{2}&0&0&0&0\\0&1&a_{{2,2}}t&a_{{2,3}}{t}^{2}&0&0&0\\ 0&0&1&a_{{3,3}}t&a_{{3,4}}{t}^{2}&0&0\\ 0&0&0&1&a_{{4,4}}t&a_{{4,5}}{t}^{2}&0\\ 0&0&0&0&1&a_{{5,5}}t&a_{{5,6}}{t}^{2}\\ 0&0&0&0&0&1&a_{{6,6}}t\end {array} \right]

(これは, n=7のときの例.)


以下は, n=3のときのこの主張の例.