とぽろじい　～大人の数学自由研究～

高校数学から分かる新しい数学、大学で学ぶ数学を少しずつまとめていくブログです。ゆくゆくは本にまとめたいと思っています。

MENU
トップ > ★大学数学 > 【組合せ論】メビウスの反転公式5　「(応用例)古典的なメビウスの反転公式/差分と和分」

【組合せ論】メビウスの反転公式5　「(応用例)古典的なメビウスの反転公式/差分と和分」

★大学数学 *【組合せ論】メビウスの反転公式 ・組合せ論

前回、poset におけるメビウスの反転公式を証明しました。

(前回の記事に関しては下にあるリンクをご利用ください。)

これを用いて、今回からは高校数学でも出会うような「初等的な結果」を導いていこうと思います。

今回はこのシリーズの初回で紹介した古典的なメビウスの反転公式の証明を行います。

また、後半には差分と和分の関係をメビウスの反転公式の結果として与えようと思います。

 

math-topology.hatenablog.com

 

 

 

まずはメビウスの反転公式の確認です。

 

定理(メビウスの反転公式)

P を Poset とする。

任意の P の元 t に対して P の部分集合 I_{t}=\{ s\in P | s\le t \} が有限集合であるとする。(このとき特に P は locally finite poset になります。)

このとき P 上の関数 f,g: P\longrightarrow \mathbb{C} について、以下の条件(1)(2)は同値である。

(1) 任意の x\in P について、 g(x)=\displaystyle\sum_{y\le x}f(y) となる。

(2) 任意の x\in P について、 f(x)=\displaystyle\sum_{y\le x}g(y)\mu (y,x) となる。　

 

ここからは、

① 公式が使える poset かどうかを確認する。

② Möbius function を求める。

③ 公式を適用する。

をという流れに沿ってそれぞれの例を見ていこうと思います。

 

古典的なメビウスの反転公式

(\mathbb{N},|) を 1 以上の自然数と約数・倍数(  a が  b の約数であるときに  a|b と表す )についての poset を考えます。

(\mathbb{N},|) には任意の自然数 n の約数は有限個であることから、①メビウスの反転公式が適用できます。

次に \mu '(m,n)=\mu \left( \dfrac{n}{m} \right) (右辺は古典的な Möbius function) で隣接代数の元を定義すると、

\mu '(m,n)=-\displaystyle\sum_{m\le x \le n} \mu ' (x,n) を満たします。

(証明は具体的に素因数を与えて、二項係数の交代和を二項定理で計算することで簡単にできます。気になる方は以下のサイト様で古典的な Möbius function についての証明が分かりやすく紹介されていますので参考にしてみるとよいかと思います。)

mathtrain.jp

 

したがって \mu ' \in I(\mathbb{N}) について

\mu ' \ast \zeta  =\delta

となります。

ゆえに (\mu ' \ast \zeta)\ast \mu  =\delta\ast\mu となり、

associativity から \mu' \ast (\zeta \ast \mu)=\mu

すなわち \mu' =\mu となります。*1

これにより② (\mathbb{N},|) における Möbius function が古典的なものと一致することが分かります。

したがって③一般の poset に対するメビウスの反転公式を適用すると、古典的なメビウスの反転公式が証明されることとなります。

 

系1(古典的なメビウスの反転公式)

  (\mathbb{N},|) 上の関数 f,g: \mathbb{N}\longrightarrow \mathbb{C} について、以下の条件(1)(2)は同値である。

(1) 任意の n\in \mathbb{N} について、 g(x)=\displaystyle\sum_{d | n}f(d) となる。

(2) 任意の n\in \mathbb{N} について、 f(n)=\displaystyle\sum_{d | n}g(d)\mu \left( \frac{n}{d} \right) となる。　

 

差分と和分

0 以上の整数と通常の大小関係によって定義される poset (\mathbb{Z}_{\ge 0},\le) を考えます。 (\mathbb{Z}_{\ge 0},\le) 上の関数はいわゆる「数列」となります。

 

このとき I_{n}=\{ k\in \mathbb{Z}_{\ge 0} | k\le n \} は n+1 個の整数からなるため①メビウスの反転公式が適用できます。

m\lt n のとき

\mu(m,n)=-\displaystyle\sum_{m\le x \lt n} \mu(m,x) から

②帰納的に Möbius function は以下のようになります。

\mu (m,n)= \left\{ \begin{array}{} 1　　　　(m=n)\\ -1　　　(m+1=n) \\0 　　　　(otherwise) \end{array} \right.

となります。

この \mu について、

n=0 のとき

\displaystyle\sum_{m=0}^{n} g(m)\mu (m,n)

=g(0)\mu(0,0)

=g(0)

 

n\ge1 のとき

\displaystyle\sum_{m=0}^{n} g(m)\mu (m,n)

=-g(n-1)+g(n)

 

つまりメビウスの反転公式(2)の条件の右辺は数列 g の差分を表すことになります。

このことから③ poset に関するメビウスの反転公式を適用すると差分と和分の関係(差分和分学の基本定理)が証明されます。

 

系2(差分と和分の関係)

数列 a,b: \mathbb{Z}_{\ge 0}\longrightarrow \mathbb{C} について、以下の条件(1)(2)は同値である。

(1) 任意のn\in\mathbb{Z}_{\ge 0} について、 b_{n}=\displaystyle\sum_{k=0}^{n}a_{k}

(2) 任意の n\in\mathbb{Z}_{\ge 0} について、 a_{n+1}=b_{n+1}-b_{n} ( =(\Delta b)_{n} ) となり、かつ a_{0}=b_{0} 。　

 

差分と和分(微分差分の離散バージョン)については過去にシリーズとしてまとめてありますので、そちらもぜひご覧ください。

math-topology.hatenablog.com

 

参考文献

[Sta] Richard P. Stanley, Enumerative Combinatorics, Cambridge University Press40 W. 20 St. New York, NYUnited States, 2012.

まとめ

メビウスの反転公式の応用例として今回は古典的なメビウスの反転公式、差分と和分の関係の証明を行いました。

「大道具を使って、諸分野の基本的な公式を証明していく」雰囲気を掴んでいただければ幸いです。

次回は引き続きメビウスの反転公式の応用例として、包除原理とオイラーの多面体定理に触れていこうと思います。

 

最後までお読みいただきありがとうございます。

次回もなにとぞよろしくお願いいたします。

次の記事

 

 

math-topology.hatenablog.com

*1:群論などで単位元の一意性を示すときの考え方です。