数学の命題示しました

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

Σ(-1)^k(nCk)kを求めるkilling involution

自然数  nについて,以下の和を組合せ論的手法で求める.
 \displaystyle \sum_{k=0}^n(-1)^k\binom{n}{k}k= \left\{ \begin{array}{}-1 & n=1\\0& n>1\end{array} \right.




まず,和を \{1,\ldots,n\}の冪集合についての和に書き換える. [n]\triangleq\{1,\ldots,n\}とかくと
 \displaystyle \sum_{k=0}^n(-1)^k\binom{n}{k}k= \sum_{A\subseteq[n]}(-1)^{|A|}|A|

さらに,この和を集合 \mathcal{R}\triangleq\{(A,i)\mid i\in A\subseteq[n]\}についての和に変えることができて,

\displaystyle = \sum_{(A,i)\in\mathcal{R}}(-1)^{|A|}
となる.


 n>1のとき, \mathcal{R}から \mathcal{R}への対合 \varphiで, (B,j)=\varphi(A,i)とすると,
 |B|=|A|\pm 1
が成立するものを構成することができる.対合とは二回当てると元に戻る写像 ( \varphi\circ\varphi={\rm id})のことである.
そのような対合 \varphiが存在するので,集合 \mathcal{R}には |A|が偶数のものと奇数のものが同数存在することが分かり,総和が 0になるのである.
このような論法はkilling involutionと呼ばれる.

以下,対合 \varphiを構成する.


 (A,i)\in\mathcal{R}とする.
自然数 r r\triangleq \min([n]\setminus\{i\})と定める.
 r\in Aならば, \varphi(A,i)\triangleq (A\setminus\{r\},i)とする.
 r\notin Aならば, \varphi(A,i)\triangleq (A\cup\{r\},i)とする.
するとこれは対合であって, |A|は当てる前後で \pm 1変化している.

(証明終わり.)

置換のMajor indexと転倒数の等分布性

major indexとは置換の統計量つまり,対称群から非負整数への写像 {\rm maj}\colon \mathfrak{S}_n\to \mathbb{N}_0である.
major indexは,以前このブログでも紹介した「置換の転倒数」と等分布であることが知られている.
つまり,以下の母関数の式が成立する.(式 (1)とする.)
 \displaystyle\sum_{\sigma\in\mathfrak{S}_n}q^{{\rm maj}(\sigma)}=\prod_{k=1}^n\frac{1-q^k}{1-q}.

(参考:R. P. Stanley, Enumerative combinatorics, vol. 1, second edition, p. 41, 2011)

本記事では式 (1)を証明する.
証明はD. Foataによる,重みを保つ全単射{\rm maj}(\sigma)={\rm inv}(\varphi(\sigma))を構成する方法が有名だが,今回は転倒数との関連は考えず直接証明してみる.
(参考:D. Foata, On the Netto Inversion Number of a Sequence, Proceedings of the American
Mathematical Society 19, pp. 236-240, 1968.)

定義 (減少集合,major index)
置換 \sigma\in\mathfrak{S}_nに対して,その減少集合 D(\sigma)
 D(\sigma)\triangleq \{i\mid \sigma(i)>\sigma(i+1)\}\subseteq\{0,\ldots,n-1\}
と定める.

置換 \sigmamajor indexを,
 \displaystyle{\rm maj}(\sigma)\triangleq\sum_{i\in D(\sigma)}i
と定める.


置換 \sigma\in\mathfrak{S}_n \sigma(1)\cdots\sigma(n)とかく.
 \sigma=47523816\in\mathfrak{S}_8に対して,
 D(\sigma)=\{2,3,6\}であり, {\rm maj}(\sigma)=2+3+6=11である.

major indexと転倒数の等分布性

式 (1)を証明する.
まず,major indexに関する情報を保ちつつ置換を置換に写す全単射を構成する.この全単射は式 (1)の証明の核心となる.

命題
 0\leq k\leq n-1のとき,全単射
 \displaystyle\varphi\colon\{\sigma\in\mathfrak{S}_n\mid \sigma(n)=k\}\to\{\sigma\in\mathfrak{S}_n\mid \sigma(n)=k+1\}
が存在して,
 \displaystyle{\rm maj}\left(\varphi(\sigma)\right)={\rm maj}\left(\sigma\right)+1
を満たす.

証明
置換の行列表記を用いる.
ここでいう置換の行列表記とは, \sigma(i)=jのとき a_{n-j+1,i}=1,そうでないとき a_{n-j+1,i}=0によって n\times n行列 Aを定義し,そのような行列で置換を表すことである.
行列の一番下の行をとり,一番上の行の上に乗せる写像 \varphiと定義する.
つまり,下図のように定義する.
f:id:iwalion:20200913050726p:plain

この写像は明らかに可逆である.
また,この写像を当てたあとは,当てる前よりmajor indexが1増える.
なぜなら, \sigma(r)=1なる r\in\{1,\ldots,n\}が唯一つ存在し, (\varphi(\sigma))(r)=nとなるが,

  •  r\neq 1ならば, r-1\in D(\sigma)であり, D(\varphi(\sigma))=(D(\sigma)\setminus\{r-1\})\cup\{r\}が成立する.
  •  r=1ならば, 1\notin D(\sigma)であり, D(\varphi(\sigma))=D(\sigma)\sqcup\{1\}が成立する.

よって,いずれの場合でもmajor indexが1増えるのである.
(証明終わり.)


命題
母関数の式 (1)が成立する.
式 (1)の再掲:
 \displaystyle\sum_{\sigma\in\mathfrak{S}_n}q^{{\rm maj}(\sigma)}=\prod_{k=1}^n\frac{1-q^k}{1-q}.


証明
置換 \sigma\in\mathfrak{S}_nに対して,置換 \sigma'\in \mathfrak{S}_{n+1}を,行列表記を用いて
f:id:iwalion:20200913051927p:plain
と定める.このとき {\rm maj}(\sigma)={\rm maj}(\sigma')である.
集合 U_{\sigma}\subseteq\mathfrak{S}_{n+1}
 \displaystyle U_{\sigma}\triangleq\left\{\sigma',\varphi(\sigma'),\varphi^2(\sigma'),\ldots,\varphi^{n}(\sigma')\right\}
と定める.
すると集合の等式
 \displaystyle \mathfrak{S}_{n+1}=\bigsqcup_{\sigma\in\mathfrak{S}_n}U_{\sigma}
が成立する.(写像 \varphi全単射なので,右辺の和は非交差である.)

以下,式 (1)を nに関する帰納法で示す.上で示した集合の式から,
 \displaystyle\sum_{\sigma\in\mathfrak{S}_{n+1}}q^{{\rm maj}(\sigma)}=\sum_{\sigma\in\mathfrak{S}_{n}}\left(q^{{\rm maj}(\sigma)}+q^{{\rm maj}(\varphi(\sigma))}+q^{{\rm maj}(\varphi^2(\sigma))}+\cdots+q^{{\rm maj}(\varphi^n(\sigma))}\right)

しかし {\rm maj}(\varphi(\sigma))={\rm maj}(\sigma)+1であったから,
 \displaystyle =\sum_{\sigma\in\mathfrak{S}_{n}}q^{{\rm maj}(\sigma)}q^{0+1+2+\ldots+n}
 \displaystyle =\frac{1-q^{n+1}}{1-q}\sum_{\sigma\in\mathfrak{S}_{n}}q^{{\rm maj}(\sigma)}
帰納法の仮定から
 \displaystyle =\prod_{k=1}^{n+1}\frac{1-q^{k}}{1-q}.
(証明終わり.)

置換の転倒数の母関数

本稿では置換の転倒数の母関数が綺麗という側面から転倒数に触れていくが,転倒数という概念自体は行列式の性質を証明するために有用であったりとか (岩瀬順一,岩瀬順一の「授業をする際のヒント --- 数学編」転倒数を利用し、互換の積への分解を飛ばして行列式を導入する),置換の集合に距離を入れるために使ったりするらしい (萩原学,ポストモダン符号理論としてのネットワーク,置換,形式化3:置換符号,応用数理 26(2), 27-32, 2016).
置換の転倒数の母関数に関する参考文献は,(Stanley,Enumerative Combinatorics volume 1 second edition,p. 36,2011)を参照.

転倒数に関する分かりやすい動画は,龍孫江の「群論:置換の転倒数https://www.youtube.com/watch?v=LXlXGWGmItg&feature=youtu.beを参照せよ.

転倒数の母関数

定義 (転倒数)
 n文字の置換 \sigma\in\mathfrak{S}_nに対して,非負整数 {\rm inv}(\sigma)
 \displaystyle{\rm inv}(\sigma)\triangleq\#\left\{(i,j)\mid i\lt j,  \sigma(i)\gt\sigma(j)\right\}
と定め, \sigma転倒数という.

以下のように,転倒数の母関数は積表示を持つことが知られている.
 \displaystyle \sum_{\sigma\in\mathfrak{S}_n}q^{{\rm inv}(\sigma)}=\prod_{k=1}^n\frac{1-q^k}{1-q}
(式1とする.)
本稿ではこの式 (1)の全単射的証明をしたあと,母関数の精密化を試みる.
式 (1)で表される多項式は「 n q-階乗」と呼ばれ, [n] _q!と書かれることがある.

式 (1)の証明

転倒数に関する情報を保ちつつ n文字の置換を n+1文字の置換にうつす以下の全単射が構成できる.

定理
全単射 \varphi\colon\mathfrak{S}_n\times\{0,\ldots,n\}\to\mathfrak{S}_{n+1}で,任意の(\sigma,i)\in\mathfrak{S}_n\times\{0,\ldots,n\}に対して
 {\rm inv}(\varphi(\sigma,i))={\rm inv}(\sigma)+iなるものが存在する.

証明
 (\sigma,i)\in\mathfrak{S}_n\times\{0,\ldots,n\}とする.
置換 \sigmaを長さ nの列 (\sigma(1),\ldots,\sigma(n))で表す.
文字 n+1を,列 (\sigma(1),\ldots,\sigma(n))の右から i番目に入れて長さ n+1の列
 \displaystyle\left(\sigma(1),\ldots,\sigma(n-i),n+1,\sigma(n-i+1),\ldots,\sigma(n)\right)
を作る.
こうしてできる列は n+1文字の置換を表すから,それを \varphi(\sigma,i)とする.
この対応は可逆である.なぜならば置換 \varphi(\sigma,i)において
文字 n+1がどこに有るかを見てそれを抜けば数 iと置換 \sigmaが分かるからである.
置換 \varphi(\sigma,i)の転倒数は, \sigmaの転倒数に比べて,文字 n+1の右にある i個の数の分増えるので,
 {\rm inv}(\varphi(\sigma,i))={\rm inv}(\sigma)+iが成立する.
(証明終わり.)


定理
転倒数の母関数の式(1)が成立する.

証明
 nに関する帰納法による.上で構成した全単射
 \varphi\colon\mathfrak{S}_{n}\times\{0,\dots,n\}\to\mathfrak{S}_{n+1}により
 \displaystyle\sum_{\sigma\in\mathfrak{S}_{n+1}}q^{{\rm inv}(\sigma)}=\sum_{\sigma\in\mathfrak{S}_{n}}\sum_{i=0}^{n}q^{{\rm inv}(\varphi(\sigma,i))}=\sum_{\sigma\in\mathfrak{S}_{n}}q^{{\rm inv}(\sigma)}\sum_{i=0}^{n}q^{i}

帰納法の仮定から
 \displaystyle=\left(\prod_{k=1}^n\frac{1-q^k}{1-q}\right)\sum_{i=0}^{n}q^{i}=\prod_{k=1}^{n+1}\frac{1-q^k}{1-q}.
(証明終わり.)

母関数を精密化してみる

自然数 kに対して k-転倒数 {\rm inv}_kを以下で定義する.
 \displaystyle{\rm inv}_k(\sigma) \triangleq \#\left\{(i,j)\mid i\lt j,\ \sigma(i)\gt\sigma(j),\ \sigma(i)=k\right\}.
置換 \sigma\in\mathfrak{S}_n k-転倒数 {\rm inv}_kの和は通常の転倒数に一致する.すなわち,
 \displaystyle{\rm inv}_1(\sigma)+\cdots+{\rm inv}_n(\sigma)={\rm inv}(\sigma),\quad \sigma\in\mathfrak{S}_n.

式 (1)を精密化する以下の式が成立する.

定理
 k-転倒数の母関数の式
 \displaystyle\sum_{\sigma\in\mathfrak{S}_n}q_1^{{\rm inv}_1(\sigma)}q_2^{{\rm inv}_2(\sigma)}\cdots q_n^{{\rm inv}_n(\sigma)}=\prod_{k=1}^n\frac{1-q_k^k}{1-q_k}
が成立する.

証明
全単射 \varphi\colon\mathfrak{S}_{n}\times\{0,\dots,n\}\to\mathfrak{S}_{n+1}がもつ以下の性質を用いる.

すなわち任意の (\sigma,i)\in \mathfrak{S}_{n}\times\{0,\dots,n\}に対して
 \displaystyle{\rm inv}_{n+1}(\varphi(\sigma,i))=i,
 \displaystyle{\rm inv}_{k}(\varphi(\sigma,i))={\rm inv}_k(\sigma),\quad (k\leq n)
である.証明は式 (1)の証明とほとんど同じである.
(証明終わり.)

閉路グラフのマッチングを有限オートマトンで記述する

Viennot先生の講義動画で,組合せ論的オブジェクトを有限オートマトン全単射的に変換して,母関数を簡単に求める方法が紹介されていました.
動画では,道グラフのマッチング(その個数はフィボナッチ数)を状態数2の有限オートマトンに変換していました.

youtu.be


この記事では,同じようにして閉路グラフのマッチングを有限オートマトンに変換して母関数を求めてみます.
グラフのマッチング,および閉路グラフやそのマッチング多項式については,以前の記事を参照してください.
iwalion.hatenablog.com

有限オートマトン

この記事では,有限オートマトンとは有向グラフ上の自己交差を許す歩道のことだと思ってかまいません.
この記事ではViennot先生の動画で紹介されている次の定理を使います.証明は動画を見てください.
定理
節点数 nの有向グラフ Gと枝重み w:E(G)\to \mathbb{K}が与えられているとする.
有向グラフ上の歩道 \omegaの重み wを,それが通る枝の重みの積により定める.有向グラフの隣接行列を A=(a)_{i,j}とする.
逆行列 (I-A)^{-1}が存在すると仮定する.
このとき,節点 iから節点 jへ行く全ての歩道の重みの和 (一般には無限和)は, (I-A)^{-1} (i,j)要素で与えられる.

道グラフのマッチング

長さ n道グラフとは,節点集合 V\triangleq\{1,\ldots,n\}と枝集合 E\triangleq\{\{1,2\},\{2,3\},\ldots,\{n-1,n\}\}からなる単純無向グラフです.
長さ nの道グラフのマッチングの個数は,フィボナッチ数 F_{n+1}です.下図に長さ 4の道グラフと,そのマッチングの集合を描きました.
f:id:iwalion:20200712003147p:plain

長さ nの道グラフのマッチングの集合は,下図 (図1)に示す状態数2の有限オートマトン G_1によって受理される長さ nの言語の集合と一対一対応します.

f:id:iwalion:20200712003804p:plain
図1: オートマトン  G_1.有向グラフだと思ってもよい.

図1はただの有向グラフだと思ってもかまいません.その場合,図中の a,b,cは枝重みだと思ってください.グラフ理論の言葉で言うなら,節点 s_1から節点 s_1への長さ nの歩道の集合と全単射であるということです.

どんな全単射かは,下の図を見れば分かる気がします.道グラフの節点 1から節点を順に見ていきマッチングに含まれない節点ならば s_1の自己ループを通り,マッチングに含まれる節点ならば s_1\to s_2\to s_1を通ります.
f:id:iwalion:20200712004738p:plain

フィボナッチ数の母関数

このことを使って,道グラフのマッチングの個数の母関数や,マッチング多項式の母関数を求めることができます.
ここでは,個数の母関数を求めてみます.
個数の母関数とは,無限和 \displaystyle\sum_{n\geq 0} M_nt^nのことです.但し長さ nの道グラフのマッチングの個数を M_nと書きました.
図1の有向グラフにおける枝重み a,b,cをそれぞれ a=b=c=tと定めます.
すると,先に述べた全単射から
 \displaystyle\sum_{n\geq 0} M_nt^n=\sum_{\omega\colon (s_1\to s_1)}w(\omega)
です.和の範囲 \omega\colon (s_1\to s_1)は,グラフ G_1において s_1から s_1に行く全ての歩道について和を取るという意味です.

これは,最初に書いた定理から,グラフ G_1の隣接行列を使って計算できます.グラフ G_1の隣接行列は

 A_1\triangleq
\begin{pmatrix}
w(s_1,s_1)&w(s_1,s_2)\\
w(s_2,s_1)&w(s_2,s_2)
\end{pmatrix}
=
\begin{pmatrix}
t&t\\
t&0
\end{pmatrix}
なので, (I-A)^{-1} (1,1)要素を計算すれば,
 \displaystyle\sum_{n\geq 0} M_nt^n=\frac{1}{1-t-t^2}
が分かります.

閉路グラフのマッチング

次に,同じことを閉路グラフのマッチングでやってみます.閉路グラフとそのマッチングとは,以下のようなものでした.これは n=5の例です.
f:id:iwalion:20200630235153p:plain


閉路グラフの節点を \{1,2,\ldots,n\}とするとき,マッチングに枝 \{n,1\}が含まれているかどうかで,オートマトンの別々の部分に飛ばすようにします.
以下のようなオートマトンが得られました.

定理
 n\geq 3のとき,大きさ nの閉路グラフのマッチングの集合は,以下の有向グラフ G_2において,節点 sから節点 g_1または g_2への長さ nの歩道の集合と一対一対応する.

f:id:iwalion:20200712013847p:plain


書くのがダルくなってきたので,なんでそうなるのかは考えてください.節点 g_1にたどり着くのが枝 \{n,1\}が含まれている場合で,節点 g_2が含まれていない場合です.

閉路グラフのマッチング多項式の母関数

有向グラフ G_2の枝重みを次のように定めます.
f:id:iwalion:20200712014400p:plain

すると, G_2における「節点 sから,節点 g_1または g_2への長さ nの歩道の重みの和」は,閉路グラフのマッチング多項式 C_{\gamma_n}(x)になります.
さらに, G_2の隣接行列 A_2を考え,行列 (I-A_2)^{-1} (s,g_1)成分と (s,g_2)成分の和をとることで,
閉路グラフのマッチング多項式の母関数が
 \displaystyle \frac{1-t^2}{1-tx+t^2}
であることが分かります.

つまり, n\geq 3のとき,形式的冪級数 \displaystyle \frac{1-t^2}{1-tx+t^2} t^nの係数は,マッチング多項式
 C_{\gamma_n}(x)に一致します.

係数の和が素数であるような非負整数係数二次多項式の既約性

定理

定数でなく,また定数項が 0でない非負整数係数の二次多項式  f(x)=ax^2+bx+cは,係数の和  a+b+c素数ならば  \mathbb{Z}上既約である.(整数の範囲で因数分解できない.)

証明

 a\neq 0のとき.

 f(x)が既約でない,つまり ax^2+bx+c=(px+q)(vx+w),\quad (px+q,vx+w\neq 1)と仮定する. p vは非負であるとしても一般性を失わない. a> 0だから p,v\geq 1または p,v\leq -1である.非負性から p,v\geq 1.また, f(x) xの係数 bは非負で定数項 cは正だから q,w\geq 1である.

多項式 (px+q)(vx+w)は係数の和が素数なので, (p+q)(v+w)素数
よって p+q=1または v+w=1
条件 p,v\geq 1かつ q,w\geq 1に反するので矛盾.

 a= 0のとき.

多項式 f(x)=bx+cの係数の和 b+c素数だから, b,cは互いに素.よって bx+cを割り切る定数は 1のみ.よって既約である.

(証明終わり)

関連した予想

三次の場合についても同様の命題「定数でなく,また定数項が 0でない非負整数係数の三次多項式  f(x)=ax^3+bx^2+cx+dは,係数の和  a+b+c+d素数ならば  \mathbb{Z}上既約である.」が成り立つ気がします.
四次以上ではたぶん成り立ちません.

この定理および予想の使いみち

ある集合の母関数を積の形で書きたいとき,集合の要素数素数な場合は,母関数が四次以上の多項式になるようにしないと絶対に因数分解できません.
また,係数が全て正という特殊な条件に限られますが,テストなどで三次多項式が出てきた場合に,係数の和を見て素数だったら,因数分解しようとする無駄な努力をしなくてすみます.

閉路グラフのマッチング多項式〜チェビシェフ多項式の話2

第一種チェビシェフ多項式は, \cos n\theta=T_n(\cos \theta)により定義される多項式 T_n(x)\, n=0,1,2,\ldotsであり,
漸化式
 T_0(x)=1,
 T_1(x)=x,
 T_{n+1}(x)=2xT_n(x)-T_{n-1}(x),\quad(n\geq 1).
により定義することもできます.
第一種チェビシェフ多項式についてはこのブログでも以前話題に上げました.
iwalion.hatenablog.com


第一種チェビシェフ多項式は「閉路グラフのマッチング」と呼ばれる組合せ論的オブジェクトの母関数としても定義することができます.
この記事では,閉路グラフのマッチングを定義し,その母関数が上で定義したチェビシェフ多項式に一致することを述べます.

この話題は,Viennot先生による組合せ論のYoutube講義でも紹介されています.
youtu.be

グラフのマッチング

単純無向グラフ G=(V,E)が与えられているとします.枝集合 Eの部分集合 M\subseteq Eが,「 Mに含まれるどの二つの枝 e_1,e_2\in Mも同じ端点を共有しない」という条件を満たすとき, Mはグラフ Gマッチングであるといいます.
グラフ Gのマッチングの集合を \mathcal{M}(G)と表します.

節点集合 V_n\triangleq\{1,.2,\ldots,n\}と,枝集合 E_n\triangleq\left\{\{1,2\},\{2,3\},\ldots,\{n,1\}\right\}
からなる単純無向グラフ \gamma_n\triangleq(V_n,E_n)を長さ n閉路グラフといいます.

下図の左側は,長さ 5の閉路グラフ \gamma_5で,図の右側はそのマッチングの集合 \mathcal{M}(\gamma_5)です.
f:id:iwalion:20200630235153p:plain



以下の定理により,長さ n+1の閉路グラフのマッチングの集合は,長さ nおよび長さ n-1の閉路グラフのマッチングの集合から作ることができます.

定理
次の全単射 fが存在する.
 f\colon\mathcal{M}(\gamma_{n})\sqcup \mathcal{M}(\gamma_{n-1})\to \mathcal{M}(\gamma_{n+1})

例を使った説明
長さ 3 4の閉路グラフのマッチングから長さ 5の閉路グラフのマッチングを作ってみせます.
基本的な考え方は,

  • 長さ n-1の閉路のマッチングには節点二つとそれを結ぶ枝一つを突っ込み
  • 長さ nの閉路のマッチングには,節点を一つ突っ込む

ことにより,長さ n+1の閉路のマッチングを作ることです.但し,単純に突っ込めない場合に多少局所的な操作を行うことが必要になります.

まずマッチング M\in\mathcal{M}(\gamma_3)に枝を一本突っ込んで \mathcal{M}(\gamma_5)を作ります.
f:id:iwalion:20200701010346p:plain
閉路グラフ \gamma_3の節点 1と節点 3の”左側”に新しい枝とその両端点となる節点二つを置きます.(図の上側)
 \{1,3\}\notin Mの場合,それがそのまま \gamma_5のマッチングになります.
 \{1,3\}\in Mの場合,節点 1,3と新しい二つの節点の間で枝を付け替えることで, \gamma_5のマッチングが得られます.(図の最右列)
この操作は可逆です.


次にマッチング M\in\mathcal{M}(\gamma_4)に節点を一つ入れて \mathcal{M}(\gamma_5)に含まれるマッチングを作ります.
f:id:iwalion:20200701004735p:plain
閉路グラフ \gamma_4の節点 1と節点 4の”左側”に節点を置きます.
 \{1,4\}\notin Mの場合,それがそのまま \gamma_5のマッチングになります.
 \{1,4\}\in Mの場合,枝 \{1,4\}を取り除いて,代わりに 4と新しい節点の間に枝を置くことで \gamma_5のマッチングが得られます.
この操作も可逆です.

以上で,全単射 \mathcal{M}(\gamma_{3})\sqcup \mathcal{M}(\gamma_{4})\to \mathcal{M}(\gamma_{5})が得られたことになります.

証明の概略
上で述べた「局所的な操作」は,いずれも操作する部分以外には影響を与えないので,上で述べた方法で一般に写像
 f\colon\mathcal{M}(\gamma_{n-1})\sqcup \mathcal{M}(\gamma_{n})\to \mathcal{M}(\gamma_{n+1})
が構成できます.
写像 g\colon\mathcal{M}(\gamma_{n+1})\to\mathcal{M}(\gamma_{n-1})\sqcup \mathcal{M}(\gamma_{n})
を作るには, M\in\mathcal{M}(\gamma_{n+1})において

  • 節点 n+1がマッチングに含まれない
  •  \{n,n+1\},\{1,2\}\in M
  •  \{n,n+1\}\in M,\{1,2\}\notin M
  •  \{n+1,1\}\in M

の四通りに場合分けして節点(と枝)を取り除く操作を考えれば,逆写像ができます.

マッチングの母関数(マッチング多項式

上で述べた全単射の存在から,長さ nの閉路グラフのマッチングの個数に関して漸化式
 \#\mathcal{M}(\gamma_{n+1})=\#\mathcal{M}(\gamma_{n})+\#\mathcal{M}(\gamma_{n-1})
が成り立つことが分かります.
この漸化式と \#\mathcal{M}(\gamma_3)=4, \#\mathcal{M}(\gamma_4)=7から定まる数列はリュカ数列と呼ばれる数列の一つです.
A000032 - OEIS


グラフ Gのマッチング Mの重み w\colon\mathcal{M}(G)\to \mathbb{R}[x]を,
 w(M)\triangleq(-1)^{|M|}x^{マッチングに含まれない節点の個数}
と定めます.グラフ Gに対して定まる多項式
 \displaystyle C_{G}(x)\triangleq\sum_{M\in\mathcal{M}(G)}w(M)
を,グラフ Gマッチング多項式といいます.

例えば以下の通り,長さ 4の閉路グラフ \gamma_4のマッチング多項式 x^4-4x^2+2です.
f:id:iwalion:20200701013128p:plain


上で考えた全単射によれば, \mathcal{M}(\gamma_{n+1})のマッチングはすべて, \mathcal{M}(\gamma_{n})のマッチングにマッチしていない節点を一つ足すか, \mathcal{M}(\gamma_{n-1})のマッチングにマッチしている枝を一つ足すことによって得られます.

これは,マッチング多項式でいうと, \gamma_{n+1}のマッチング多項式の各和因子は, \gamma_{n}のマッチング多項式の和因子に xをかけるか, \gamma_{n-1}のマッチング多項式の和因子に -1をかけるかして得ることができるということです.
つまり,次の式が成立します.

定理
閉路グラフ \gamma_nのマッチング多項式は次の漸化式を満たす
 C_{\gamma_{n+1}}(x)=xC_{\gamma_n}(x)-C_{\gamma_{n-1}}(x)


特に,変数 x 2xに変数変換すれば,この漸化式は第一種チェビシェフ多項式 T_n(x)が満たす漸化式と一致します.

マッチング多項式と第一種チェビシェフ多項式の一致

計算してみると n=3,4のときに
 T_3(x)=\displaystyle\frac{1}{2}C_{\gamma_3}(2x),\quad T_4(x)=\frac{1}{2}C_{\gamma_4}(2x)
が成立します.
よって上で示した漸化式から,全ての n\geq 3において,閉路のマッチング多項式 C_{\gamma_n}(x)と第一種チェビシェフ多項式 T_n(x)の間に
 \displaystyle T_n(x)=\frac{1}{2}C_{\gamma_n}(2x)
が成立します.