2019-05-30

ファウルハーバーの公式

冪乗和

$S_m(n)=1^m+2^m+...+(n-1)^m$

に関する一般的な公式について見ていきます。和はn-1までとなっていることに注意してください。

ベルヌーイ数 ${B_k}$ を

$\frac{x}{e^x-1}=\sum_{k=0}^\infty \frac{B_k}{k!}x^k$

で定義する。

少し並べてみると

${B_0=1}$

${B_1=-\frac{1}{2}}$

${B_2=\frac{1}{6}}$

${B_3=0}$

${B_4=-\frac{1}{30}}$

${B_5=0}$

実はこの後も奇数番号では0となります。

#1 kが3以上の奇数のとき

$B_k=0$

$\frac{x}{e^x-1}-B_1x= \frac{x}{2} \frac{e^{\frac{x}{2}}+e^{-\frac{x}{2}} }{e^{\frac{x}{2}}-e^{-\frac{x}{2}} }$

と変形するとこれは偶関数であることが分かる。□

ベルヌーイ多項式 ${B_k(x)}$ を

$B_k(x)=\sum_{i=0}^k \binom{k}{i} B_{k-i}x^i$

で定義する。

少し並べてみると

${B_0(x)=1}$

${B_1(x)=x-\frac{1}{2}}$

${B_2(x)=x^2-x+\frac{1}{6}}$

${B_3(x)=x^3-\frac{3}{2}x^2+\frac{1}{2}x}$

${B_4(x)=x^4-2x^3+x^2-\frac{1}{30}}$

${B_5(x)=x^5-\frac{5}{2}x^4+\frac{5}{3}x^3-\frac{1}{6}x}$

もし二項定理との見た目の類似から

$(B+x)^n =\sum_{i=0}^n \binom{n}{i} B_{n-i}x^i$

と表記してしまうと

$B_k(x)=(B+x)^k$

と書けます。

次に、 ${B_k(0)=B_k}$ は当然だが ${B_k(1)}$ についても

#2 ${k \geq 2 }$ において

$B_k(1)=B_k$

$\frac{e^x-1}{x}\sum_{k=0}^\infty \frac{B_k}{k!}x^k=1$

${k \ge 1}$ において係数比較すると

$\sum_{k=i+j} \frac{B_j}{(i+1)! j!}=0$

$\sum_{j=0}^k \binom{k+1}{j}B_j=0$

$\sum_{j=0}^{k+1} \binom{k+1}{j}B_j=B_{k+1}$

左辺はまさしく ${B_{k+1}(1)}$ となっている。□

#3 ${k \geq 1 }$ において

$B'_k(x)=kB_{k-1}(x)$

$B'_k(x)=\sum_{i=1}^k \binom{k}{i}B_{k-i}x^{i-1}i$

$=k \sum_{i=1}^k \binom{k-1}{i-1}B_{k-i}x^{i-1}$

$=k \sum_{i=0}^{k-1} \binom{k-1}{i}B_{k-i-1}x^{i}$

$=kB_{k-1}(x)$ □

ちなみにこの性質はベルヌーイ数の性質から出てきたのではなく、どんな数列からでも同じような手法で多項式列を構成すればこの性質を持つことになります。

#4 ${k \geq 1 }$ において

$\int_{0}^{1} B_k(x)dx =0$

$\int_{0}^{1} B_k(x)dx$

$=\frac{1}{k+1}\int_{0}^{1} B'_{k+1}(x)dx$

$=\frac{1}{k+1}( B_{k+1}(1)-B_{k+1}(0) )$

#2より

$=0$ □

次が導出のためのメインの公式となります。

#5 ${f}$ を滑らかな関数とする。このとき ${m \ge 1 }$ で

$f(0)=\int_{0}^{1}f(x)dx + \sum_{k=1}^{m} \frac{B_k}{k!}f^{(k-1)}(x)|_{0}^{1}$

$+(-1)^{m+1} \int_{0}^{1}\frac{B_m(x)}{m!}f^{(m)}(x)dx$

が成り立つ。

帰納法で示す。 ${m=1}$ の場合を書き下すと

$f(0)=\int_{0}^{1}f(x)dx -\frac{1}{2}(f(1)-f(0))+ \int_{0}^{1}(x-\frac{1}{2})f'(x)dx$

これは部分積分から簡単に確認できる。

mで成立していると仮定する。#3と部分積分から

${\displaystyle \int_{0}^{1}\frac{B_m(x)}{m!}f^{(m)}(x)dx }$

${\displaystyle =\int_{0}^{1}\frac{B'_{m+1}(x)}{(m+1)!}f^{(m)}(x)dx }$

${\displaystyle = \frac{B_{m+1}(x)}{(m+1)!}f^{(m)}(x)|_0^1 -\int_0^1 \frac{B_{m+1}(x)}{(m+1)!}f^{(m+1)}(x)dx }$

であるから

${\displaystyle (-1)^{m+1}\frac{B_{m+1}(x)}{(m+1)!}f^{(m)}(x)|_0^1 =\frac{B_{m+1}}{(m+1)!}f^{(m)}(x)|_0^1 }$

を確認すればよい。#1, #2によりmが奇数ならそのまま一致し、偶数なら両辺とも０であることが分かる。□

大雑把な捉え方としては、仮に最後の剰余項といえる項が ${m \rightarrow \infty}$ で0に収束するとすると、

$g(x)=\sum_{k=0}^{\infty} \frac{B_k}{k!}f^{(k)}(x)$

とすれば

$f(0)=\int_{0}^{1}g(x)dx$

となって、これは ${ \sum a(n)}$ を計算するために ${a(n)=b(n+1)-b(n)}$ となる ${b(n)}$ を求めることに対応します。

#6 整数 ${a,b(a \lt b)}$ として

$\sum_{k=a}^{b-1}f(k)=\int_{a}^{b}f(x)dx + \sum_{k=1}^{m} \frac{B_k}{k!}f^{(k-1)}(x)|_{a}^{b}$

$+(-1)^{m+1} \int_{a}^{b}\frac{B^{*}_m(x)}{m!}f^{(m)}(x)dx$

但し ${B^*_m(x)=B_m(x-[x]) }$ つまり ${B_m(x)}$ の定義域を ${[0,1)}$ に制限してから周期１の関数となるように繰り返した関数とする。

${f(x+k), k=a,a+1,...,b-1}$

に対して#5を適用し、総和をとることで得られる。□

ファウルハーバーの公式

${m \geq 1, n \geq 2 }$ のとき

$\sum_{k=1}^{n-1}k^m=\frac{1}{m+1}( B_{m+1}(n)-B_{m+1} )$

#6 を ${a=0, b=n, f(x)=x^m}$ として適用すると

$\sum_{k=0}^{n-1}k^m$

$=\int_{0}^{n}x^m dx + \sum_{k=1}^{m} \frac{B_k}{k!}\frac{m!}{(m-k+1)!}x^{m-k+1}|_{0}^{n} +(-1)^{m+1} \int_{0}^{n}B^{*}_m(x)dx$

#4より最後の項(剰余項)は消えて

$=\frac{n^{m+1}}{m+1} + \sum_{k=1}^{m} \frac{B_k}{k!}\frac{m!}{(m-k+1)!}n^{m-k+1}$

$=\frac{n^{m+1}}{m+1} +\frac{1}{m+1}\sum_{k=1}^{m} \binom{m+1}{k} B_k n^{m-k+1}$

$=\frac{1}{m+1}\sum_{k=0}^{m} \binom{m+1}{k} B_k n^{m-k+1}$

$=\frac{1}{m+1}( B_{m+1}(n)-B_{m+1} )$ □

もし ${k=n}$ まで足してかつ公式の形はそのままにしたいなら ${B_1=1/2}$ と ${B_1}$ だけ変更する必要があります。

2018-05-27

位相空間の公理が自然に感じられるためのストーリー(試作)

集合位相

個人的に、こういう順序で辿って行けば位相空間の公理が受け入れやすくなるのでは、というストーリー(？)を描いていきます。

位相構造は集合のつながり具合を記述するらしいものでした。例として位相構造よりはずっと具体的に思える距離空間について考えてみます。ある集合に入れられた距離を試しにすべて２倍してみます。するとこれは異なる距離空間になりますが、空間のつながり具合としては同じに思えます。実際、距離空間の間の連続写像が ${ \epsilon-\delta }$ 論法によって定義されますが、ある写像が連続なら、定義域の方であれ値域の方であれ、距離を上記のように２倍してみたところで連続性はそのまま保たれることが容易に分かります。

また ${ \mathbb{R}^2 }$ にはユークリッド距離の他にたとえばマンハッタン距離

${\displaystyle d ( (x_1,y_1),(x_2,y_2))=|x_1-x_2|+|y_1-y_2| }$

がありますが、距離をユークリッド距離からマンハッタン距離に替えたところで、連続関数であったものがそうでなくなったり、逆に連続でなかった関数が連続になったりすることはありません。こうした例を見ると、集合のつながり具合を定めるような構造というのは、距離を定めることよりもずっと緩いのではないかと思えます。それはどんな構造でしょうか。

・・・

点列の収束というのは空間のつながり方によって定まるであろうことの中で比較的直観的なものです。ここでは試しに、位相空間の公理を忘れた上で、点列の収束の如何こそ集合のつながり方のすべてだ、と言ってみます。

定義　集合 ${ X }$ とその部分集合族 ${ O }$ で、 ${X,\emptyset \in O }$ を満たすものの組 ${ (X,O) }$ を近傍付き空間と呼ぶ。

部分集合族はほぼ何でもいいので部分集合付き空間と言ったほうがいいかもしれませんが雰囲気のための命名です。全体集合や空集合が入っているのは便宜上で本質的なことではありません。

定義　近傍付き空間 ${ (X,O) }$ と ${ X }$ 上の点列 ${ (a_n) }$ および ${ \alpha \in X }$ について、 ${ a_n }$ が ${ \alpha }$ に収束するとは、任意の ${\alpha \in U \in O }$ に対して自然数 ${ N }$ が存在して、 ${ n ＞N }$ ならば ${ a_n \in U }$ であることとし、 ${ a_n \rightarrow \alpha }$ と書く。

${ O }$ の元(近傍)がたくさんあるほど点列は収束しづらくなり、バラバラなイメージとなります。

こうして位相空間の公理を無視して、ひとまずある集合上につながり方の構造っぽいものを定義しました。この定義の拙いところはどこでしょうか。それは、このままでは ${ X }$ を台とする異なる二つの近傍の入れ方が全く同じ点列の収束を導き得るということです。

定義　集合 ${ X }$ を台とする二つの近傍付き空間 ${ (X,O) }$ , ${ (X,O') }$ が点列同型であるとは、任意の ${ X }$ 上の点列 ${ (a_n) }$ , ${ \alpha \in X }$ に対して ${ a_n \rightarrow \alpha }$ であるかどうかが一致していることとする。

点列の収束如何こそつながり方のすべてだと言った以上成り立ってほしいけれど実際は成り立たないことは

「 ${ (X,O) }$ と ${ (X,O') }$ が点列同型であるならば ${ O=O' }$ 」

です。

たとえば

${\displaystyle O=\{A,B,X,\emptyset \} }$

$O'=\{A,B,A \cup B,A \cap B,X, \emptyset \}$

とすると二つは点列同型であることが容易に分かります。

よって目標は、近傍付き空間に何かしら制限(公理)を加えることによって「 ${ (X,O) }$ と ${ (X,O') }$ が点列同型ならば ${ O=O' }$ 」を成り立たせる、もしくは二つが点列同型かどうかを判定する方法を見つける、ということになります。

命題　近傍付き空間 ${ (X,O) }$ に対して

${ s(O):=\{ A \in P(O); 任意のa \in Aに対して}$

${ B_1,...,B_n \in Oが存在してa \in B_1 \cap ...\cap B_n \subset A \} }$

とすると ${ (X,O) }$ と ${ (X,s(O)) }$ は点列同型である。

容易に分かるように

${ (X,O) }$ 　 ${ A_\lambda \in O (\lambda \in \Lambda) }$ 　 ${ B,C \in O }$ に対して

$O'=O \cup \{ \cup_{\lambda \in \Lambda } A_\lambda \}$

$O''=O \cup \{B \cap C \}$

とすれば ${ (X,O),(X,O'),(X,O'') }$ はすべて点列同型となります。

このように各点列の収束如何をそのまま保持する近傍を付け加えられるだけ付け加えたものが ${ (X,s(O)) }$ と言えます。その結果 ${ (X,s(O)) }$ は位相空間の公理を満たしていて、 ${ s(s(O))=s(O) }$ 　となります。

では「近傍付き空間 ${ (X,O) }$ と ${ (X,O') }$ が点列同型ならば ${ s(O)=s(O') }$ 」というのは成り立つでしょうか。言い換えれば、「位相空間の公理を満たす近傍付き空間 ${ (X,O)}$ と ${(X,O') }$ が点列同型ならば ${ O=O' }$ 」は成り立つでしょうか。もし成り立つなら、点列の収束如何から出発する位相の公理への導きは成功と言えそうです。

が、残念ながらこれは必ずしも成り立ちません。可算的には辿り着けないような深部において点列は無力です。

例　 ${ X }$ を、 ${ \mathbb{R} }$ の有限部分集合全体 ${ F }$ に一点 ${ \mathbb{R} }$ を付け加えたものとし、

${ U_\lambda=\{ x \in X; \lambda \subset x \} }$

${ O=\{U_\lambda ; \lambda \in F \}\cup \{ \emptyset \} }$

とし、近傍付き空間 ${ (X,O) }$ を考える。更に ${ O'=O \cup \{\{ \mathbb{R} \}\} }$ とすると ${ (X,O) }$ と ${ (X,O') }$ は点列同型だが ${ s(O) \neq s(O') }$ となる。

なぜなら任意の点列 ${ (a_n) }$ に対して ${ A=\cup_n a_n }$ は高々可算集合であるから ${ r \notin A }$ である ${ r \in \mathbb{R} }$ が存在する。 ${ \mathbb{R} }$ の近傍 ${ U_{\{ r \}}}$ の存在によって、 ${ a_n \rightarrow \mathbb{R} }$ となるのはどちらの近傍付き空間にせよ有限個の ${ n }$ を除いて ${ a_n=\mathbb{R} }$ となる場合に限る。しかし明らかに ${ \{\mathbb{R}\} \notin s(O) }$ 。

しかし可算的な条件を加えれば成り立ちます。

命題　近傍付き空間 ${ (X,O),(X,O') }$ が点列同型で位相の公理を満たし、さらに位相空間における第一可算公理を満たすとする。このとき ${ O=O' }$ となる。

証明　対偶を示す。 ${ O\neq O' }$ と仮定すると対称性から ${ U \in O }$ だが ${ U \notin O' }$ となるものが存在するとしてよい。すると ${ \alpha \in U }$ が存在して、任意の ${\alpha \in V \in O' }$ に対して ${ V \cap U^c \neq \emptyset }$ 。特に、 ${ \alpha }$ の ${ (X,O') }$ における可算な基本近傍系を ${ (V_n)_{n=1,2,..} }$ とすると各 ${ V_n \cap U^c }$ から点を適当にとり点列 ${ (a_n) }$ を作ると ${ (X,O') }$ としては ${ a_n \rightarrow \alpha }$ であるが ${ (X,O) }$ としてはそうではない。□

提言「点列の収束の如何こそ集合のつながり方のすべてだ」を固持するなら近傍付き空間や位相空間の公理に第一可算公理のようなものを入れたほうが良さそうです。しかしむしろ、ある点への近づき方を可算性や直線的な構造に縛られた点列に限ったことの方を反省すべきではないでしょうか。連続濃度の整列集合で果てへ向かったり、無数の支流が絶えず合流しながら大海を目指すような近づき方もあります。

そうして点列を含む概念である有向点族に行き着きます。有向点族の定義は(有向点族 - Wikipedia)を参照してもらうとして、

定義　近傍付き空間 ${ (X,O) }$ と ${ X }$ 上の有向点族 ${ (a_\lambda)_{\lambda \in \Lambda} }$ および ${ \alpha \in X }$ について、 ${ a_\lambda }$ が ${ \alpha }$ に収束するとは、任意の ${\alpha \in U \in O }$ に対して ${ \nu \in \Lambda }$ が存在して、 ${ \lambda ＞\nu }$ ならば ${ a_\lambda \in U }$ であることとし、 ${ a_\lambda \rightarrow \alpha }$ と書く。

定義　集合 ${ X }$ を台とする二つの近傍付き空間 ${ (X,O) }$ , ${ (X,O') }$ が有向点族同型であるとは、任意の ${ X }$ 上の有向点族 ${ (a_\lambda)_{\lambda \in \Lambda} }$ , ${ \alpha \in X }$ に対して ${ a_\lambda \rightarrow \alpha }$ であるかどうかが一致していることとする。

とすると

命題　近傍付き空間 ${ (X,O) }$ に対して ${ (X,O) }$ と ${ (X,s(O)) }$ は有向点族同型である。

命題　近傍付き空間 ${ (X,O),(X,O') }$ が位相の公理を満たし、かつ有向点族同型ならば ${ O=O' }$

証明　対偶を示す。 ${ O\neq O' }$ と仮定すると対称性から ${ U \in O }$ だが ${ U \notin O' }$ となるものが存在するとしてよい。すると ${ \alpha \in U }$ が存在して、任意の ${\alpha \in V \in O' }$ に対して ${ V \cap U^c \neq \emptyset }$ 。

ところで ${\Lambda=\{V \in O';\alpha \in V \} }$ は包含関係 ${ A \subset B }$ を ${ B \le A }$ と定義することによって自然に有向点族とみなせる。各 ${ V \in \Lambda }$ に対して ${ V \cap U^c }$ の点 ${ a_V }$ を適当にとっていくと、 ${ (a_V)_{V \in \Lambda} }$ も自然に有向点族とみなせて、 ${ (X,O') }$ としては ${ a_V \rightarrow \alpha }$ であるが ${ (X,O) }$ としてはそうではない。□

このように点列の代わりに有向点族を考えることによって位相空間の公理をこれ以上増やさずに済みました。もやもやすることは尽きないですが、強引にめでたしめでたしとしておきます。

2018-05-05

バーンサイドの補題

代数

バーンサイドの補題

有限群 ${ G }$ が有限集合 ${ X }$ に作用しているとき ${ G }$ による軌道の数 ${ |X/G| }$ は以下で与えられる。

$|X/G|=\frac{1}{|G|}\sum_{g \in G} |X^g|$

但し ${ X^g=\{x \in X; gx=x\}}$

まず ${ G }$ が推移的な作用である場合に示します。すなわち

補題の補題

${ G }$ が推移的に作用しているとき(軌道がたった一つのとき)

$|G|=\sum_{g \in G} |X^g|$

群 ${ G }$ は軌道ごとに別々に作用していると考えても問題ないので、この場合がバーンサイドの補題の本質的な部分です。

証明

${\displaystyle \sum_{g \in G} |X^g| }$

$=\sum_{g \in G} \sum_{x \in X} \chi_{\{gx=x\}}(g,x)$

$=\sum_{x \in X}\sum_{g \in G} \chi_{\{gx=x\}}(g,x)$

${ G_x }$ を ${ x }$ の固定部分群として

${\displaystyle =\sum_{x \in X} G_x }$

${\displaystyle =\sum_{x \in X} \frac{|G|}{|X|} }$

${\displaystyle =|G| }$ 　□

なんだかよく分からないのでコトバでもう一度追っていきましょう。

各 ${ g \in G }$ に対して ${ g }$ の作用で不変な ${ X }$ の元の数を集計する。しかし ${ g }$ ごとに集計するとその数はバラバラで数えるのが大変。なので ${ x \in X }$ の元ごとに集計することにしてみる(二重和の交換)。すると、同じ軌道上では固定部分群の位数はどれも等しく ${ \frac{|G|}{|X|} }$ であることから。 ${ x \in X }$ 全体で和をとれば ${ \frac{|G|}{|X|}\times |X|=|G| }$ となる。

バーンサイドの補題の証明

${ G }$ の作用を各軌道に制限すれば各々では推移的に作用していることに注意する。

$|X/G||G|$

$=\sum_{Y \in X/G} |G|$

補題の補題より

$=\sum_{Y \in X/G} \sum_{g \in G} |Y^g|$

$=\sum_{g \in G} \sum_{Y \in X/G} |Y^g|$

$=\sum_{g \in G} |X^g|$ □

これもコトバでもう一度(終わりの式から逆走します)。

各 ${ g \in G }$ に対して ${ g }$ の作用で不変な ${ X }$ の元の数を集計する。 ${ X }$ の各軌道ごとに集計してから全軌道で足し合わせることにする。すると補題の補題から、各軌道についてはどれも ${ |G| }$ となる。だからもちろん、全軌道での和は ${ |G|\times|G/X| }$ である。

結局、証明はほとんど部分集計の手順を変えることしかしていませんね。ですがこの補題は回転させたり順序を変えたりして一致するものを同一視する場合の数え上げにおいて非常に便利な式であり、憶えておいて損はないでしょう。

2018-05-03

ベルンシュタインの定理のイメージ優先証明

集合位相

ベルンシュタインの定理

集合 ${ A }$ から集合 ${ B }$ への単射および ${ B }$ から ${ A }$ への単射が存在するならば ${ A }$ から ${ B }$ への全単射が存在する。

この定理の証明はイメージ的にはかなり素朴だと思うので、そちらを優先して冗長に説明してみます。

まず一般論から。

集合 ${ C }$ と単射 ${ f:C \rightarrow C }$ があるとき ${ C }$ 上に、以下のような同値関係が入る。

$a \sim b$

${ \Leftrightarrow }$ 非負整数 ${ n }$ が存在して ${ f^n(a)=b }$ または ${ f^n(b)=a }$

この同値類の一つを ${ E_i }$ とする。 ${ f }$ の定義域、値域を ${ E_i }$ 上に制限したものを ${ f_i }$ とする。

このとき、きっちり証明を書こうとすると面倒くさいけれどイメージ的には明らかなことは

各 ${ f_i:E_i \rightarrow E_i }$ は以下のいずれかと写像として同型

${p:\mathbb{Z} \rightarrow \mathbb{Z} }$ 　 ${ p(x)=x+1}$

$q:\mathbb{N} \rightarrow \mathbb{N}$ 　 ${ q(x)=x+1 }$

${ m }$ を正整数として

$r: \mathbb{Z}/ m \mathbb{Z} \rightarrow \mathbb{Z}/ m \mathbb{Z}$ 　 ${ r([x])=[ x+1 ] }$

但し ${ m=1 }$ のときは一点集合上の自明な写像とみなす。

上の３つの型はそれぞれ、直線型、半直線型、円周型と呼べます。

定理のステートメントの集合 ${ A,B }$ に対して ${ C=A \cup B }$ とすれば二つの単射は ${ C }$ 上の単射を自然に誘導するのでそれを ${ f }$ とする。 ${ f }$ は ${ A }$ の元を ${ B }$ の元に、 ${ B }$ の元を ${ A }$ の元にうつす。

この ${ (C,f) }$ に対して上述の同値関係を考えて、写像をそれぞれの同値類に制限したものに分割する。するとそれぞれの同値類上で ${ A }$ の元と ${ B }$ が一対一対応していることを示せば定理は証明されるが、これはどの型においても ${ A }$ と ${ B }$ が交互に現れることから明らかである（円周型の ${ m }$ は必ず偶数であることに注意）。

2018-04-10

二項係数に関する交代和

計算

${ f(x) }$ を有理式とするときの

$\sum_{k=0}^n (-1)^k {}_nC_k f(k)$

について考えてみる。まず多項式の場合から。

$f(x)=\sum_{i=0}^m a_i x^i$ のとき、

$\sum_{k=0}^n (-1)^k {}_nC_k f(k)=(-1)^n n! \sum_{i=n}^m a_iS(i,n)$

特に ${ m \lt n }$ ならば ${ 0 }$ 。

但し ${ S(i,n) }$ は第二種スターリング数(定義は証明参照)。

例.

$\sum_{k=0}^n (-1)^k {}_nC_k k^n=(-1)^n n!$

$\sum_{k=0}^n (-1)^k {}_nC_k k^{n+1}=(-1)^n n! {}_{n+1}C_2$

${ f_0(x)=1, f_1(x)=x }$

${f_i(x)=x(x-1)...(x-(i-1)) (i \ge 2) }$

とする。

第二種スターリング数 ${ S(i,n) }$ とは ${ x^i }$ を基底 ${ (f_0,f_1,f_2,...)}$ の線形和で表したときの ${ f_n }$ の係数のことである。

二項展開

$(1+x)^n=\sum_{k=0}^n {}_nC_k x^k$

に直接もしくは ${ m }$ 回(但し ${ n }$ 未満)微分してから ${ x=-1 }$ を代入することで、 ${ m \lt n }$ ならば

${\displaystyle \sum_{k=0}^n (-1)^k {}_nC_k f_m(k)=0 }$

また ${ m \gt n }$ においても ${ f_m(0)=...=f_m(n)=0 }$ なのでやはり

${\displaystyle \sum_{k=0}^n (-1)^k {}_nC_k f_m(k)=0 }$

${ m=n }$ では

${\displaystyle \sum_{k=0}^n (-1)^k {}_nC_k f_n(k)=(-1)^n f_n(n)=(-1)^n n! }$

以上から

$\sum_{k=0}^n (-1)^k {}_nC_k k^m$

$=\sum_{k=0}^n (-1)^k {}_nC_k \sum_{i=0}^m S(m,i)f_i(k)$

$=\sum_{i=0}^m S(m,i) \sum_{k=0}^n (-1)^k {}_nC_k f_i(k)$ 　

$=S(m,n) (-1)^n n!$

なので

$f(x)=\sum_{i=0}^m a_i x^i$ のとき、

$\sum_{k=0}^n (-1)^k {}_nC_k f(k)$

$=\sum_{i=0}^m a_i \sum_{k=0}^n (-1)^k {}_nC_k k^i$

$= (-1)^n n! \sum_{i=n}^m a_i S(i,n)$ 　□

有理式の部分分数分解を考えれば、後は ${ f(x)=1/(x+\alpha)^m }$ について計算すればよい。以下 ${ \alpha }$ は ${ 0,-1,...,-n }$ でない複素数とする。

まず ${ m=1 }$ の場合

${\displaystyle \sum_{k=0}^n \frac{(-1)^k {}_nC_k }{k+\alpha} =\frac{n!}{\alpha(\alpha+1)...(\alpha+n)} }$

${ \alpha }$ が正の実数の時

${\displaystyle \sum_{k=0}^n \frac{(-1)^k {}_nC_k }{k+\alpha} }$

$=\sum_{k=0}^n \int_0^1 (-1)^k {}_nC_k x^{k+\alpha-1}dx$

$=\int_0^1 \sum_{k=0}^n (-x)^k {}_nC_k x^{\alpha-1}dx$

$=\int_0^1 (1-x)^n x^{\alpha-1}dx$

$=B(n+1,\alpha)$

$=\frac{n! \Gamma(\alpha)}{\Gamma(n+\alpha+1)}$

${\displaystyle =\frac{n!}{\alpha(\alpha+1)...(\alpha+n)} }$

問題の式の両辺を ${ \alpha }$ に関する複素関数とみると、どちらも ${ 0,-1,...,-n }$ を除く全平面で定義された正則関数。よって一致の定理から従う。(結果的には ${ \alpha }$ に関する有理式とみたときの部分分数分解に過ぎない。)　□

次に ${ m=2 }$ の場合

${\displaystyle \sum_{k=0}^n \frac{(-1)^k {}_nC_k }{(k+\alpha)^2} =\frac{n!}{\alpha(\alpha+1)...(\alpha+n)} \sum_{k=0}^n \frac{1}{k+\alpha} }$

${\displaystyle \sum_{k=0}^n \frac{(-1)^k {}_nC_k }{k+\alpha} =\frac{n!}{\alpha(\alpha+1)...(\alpha+n)} }$

の両辺を ${ \alpha }$ の関数とみて微分すればよい。□

さらに大きな次数についても繰り返し微分していけば原理的には求まる。結果だけ書いておけば

${\displaystyle \sum_{k=0}^n \frac{(-1)^k {}_nC_k }{(k+\alpha)^m} }$

$=n! \sum_{p_0+...+p_n=m-1} \frac{1}{\alpha^{p_0+1}(\alpha+1)^{p_1+1}...(\alpha+n)^{p_n+1}}$

但し ${ p_0,p_1,...,p_n }$ は非負整数を動く。

さらにこれより

${\displaystyle \sum_{k=1}^n \frac{(-1)^{k-1} {}_nC_k }{k^m}= \sum_{p_1+...+p_n=m} \frac{1}{1^{p_1}2^{p_2}...n^{p_n}} }$

但し ${ p_1,p_2,...,p_n }$ は非負整数を動く。

${\displaystyle \sum_{k=1}^n \frac{(-1)^{k-1} {}_nC_k }{k^m}　}$

$=n\sum_{k=1}^n \frac{(-1)^{k-1} {}_{n-1}C_{k-1} }{k^{m+1}}$

${\displaystyle =n\sum_{k=0}^{n-1} \frac{(-1)^k {}_{n-1}C_k }{(k+1)^{m+1}}　}$

${\displaystyle =n!\sum_{p_1+...p_n=m} \frac{1}{1^{p_1+1}...n^{p_n+1}} }$

${\displaystyle =\sum_{p_1+...p_n=m} \frac{1}{1^{p_1}...n^{p_n}} }$ 　□

ちなみに ${ m=1 }$ の場合は

${\displaystyle \sum_{k=1}^n \frac{(-1)^k {}_nC_k }{k+\alpha} =\frac{n!}{\alpha(\alpha+1)...(\alpha+n)}-\frac{1}{\alpha} }$

として ${ \alpha \rightarrow 0 }$ と極限をとれば、右辺はロピタルの定理などを用いれば計算できて

${\displaystyle \sum_{k=1}^n \frac{(-1)^{k-1} {}_nC_k }{k} =\sum_{k=1}^n \frac{1}{k} }$

が分かる。

2018-04-09

サイコロをあるパターンが出るまで投げ続ける

確率統計

サイコロ振り続けるとき、目が ${c_1,c_2,...,c_m}$ の順に連続して出るまでにサイコロを何回振るか、その回数の期待値 ${E}$ を一般的に求めよう。もっと直接的にも計算できるけれど、ここではマルチンゲールを利用してみる。

命題　 ${K=\{ k ; c_k=c_1 \}}$ として

$E=\sum_{k \in K} 6^{m-k+1}$

たとえば１が６回連続して出るまでに振る回数の期待値は ${m=6, K=\{ 1,2,..,6 \} }$ なので ${E=6^6+6^5+..+6=(6^7-6)/5}$ であり、123456と連続して出るまでの期待値は ${m=6, K=\{1\}}$ なので ${E=6^6}$ となる。

先に用語、記号の説明とあとで証明する補題を列挙し、それらを使って証明する。

${E_q}$ を、条件の出目順が出るまでに ${q}$ がでる回数の期待値とする。

補題１　 ${K=\{ k ; c_k=c_1 \}}$ として

$E_{c_1}=\sum_{k \in K} 6^{m-k}$

${ E_{c_1} }$ は他の ${ E_i }$ より計算しやすいというのがポイント

確率変数 ${X_n}$ をn回目の目とし、フィルトレーション ${F_n}$ を

${F_n=\sigma (X_1,X_2,..,X_n)}$

と定義する。

確率変数 ${A_n^i}$ をn回目までに目iが出た回数とする。

補題２　異なる ${i,j}$ について

${M_n=A_n^i-A_n^j}$ は ${F_n}$ に関してマルチンゲール。

${T}$ を、条件を満たした時の回数を表す確率変数とする。明らかにこれは ${F_n}$ に関する停止時刻。

補題３　 ${E[T] \lt \infty}$

補題4　 $E_1=E_2=...=E_6$

これはちょっと不思議な感じがする。

命題の証明　補題１、補題4より

$E=E_1+E_2+...+E_6=6E_{c_1}= \sum_{k \in K} 6^{m-k+1}$ □

以下、各補題を証明する。

補題１　 ${K=\{ k ; c_k=c_1 \}}$ として

$E_1=\sum_{k \in K} 6^{m-k}$

証明　確率変数 ${ L_1 }$ を、サイコロを振り始めて最初に ${ c_1 }$ が出てからその「チャンス」が継続している間に出た ${c_1}$ の目の総数とする。但し「成功」した場合は ${ L_1=\#\{i; c_i=c_1 \} }$ とする。

例　 ${ m=4 }$ , ${ (c_1,..,c_4)=(1211) }$ のとき

出目順が53124134...なら 53[12]4134 と括弧で括った中にある１の数を数えて ${ L_1=1 }$

21121111なら2[1]121111で ${ L_1=1 }$

12111213なら[1211]1213で ${ L_1=3 }$

次に確率変数 ${ L_2 }$ を、 ${ L_1 }$ のカウントを終えたのち、そこから改めてサイコロを振り始めたと考えるときの ${ L_1 }$ に相当するものとする。 ${L_3,L_4,... }$ も同様。すると ${ (L_1,L_2,...) }$ は独立同分布であり、

$E[ L_1 ]=\sum_{k \in K} 6^{1-k}$

$E_1$

${\displaystyle =\sum_{i=1}^\infty E[ L_i ]P(i回目より前のチャンスはすべて失敗) }$

$=E[L_1] \sum_{i=1}^\infty (1-6^{-(m-1)})^{i-1}$

$=\sum_{k \in K}6^{1-k} 6^{m-1}=\sum_{k \in K}6^{m-k}$ □

補題２　異なる ${i,j}$ について

${M_n=A_n^i-A_n^j}$ は ${F_n}$ に関してマルチンゲール。

証明　 ${M_n}$ の ${F_n}$ 適合性、可積分性は明らか。残りの条件は

${E[M_{n+1}-M_n|F_n] }$

${ =E[A_{n+1}^i-A_n^i|F_n]-E[A_{n+1}^j-A_n^j|F_n] }$

${=1/6-1/6=0}$

によって分かる。□

補題３　 ${E[T] \lt \infty}$

証明　 ${ k=1,2,... }$ に対して

$P( T \gt km )$

$\lt P(km回までをm回ごとに区切ったどの区間も条件の出目順でない)$

$=(1-6^m)^k$

であるから

$E[ T ] =\sum_{t=0}^{\infty} P(T \gt t)$

$\lt \sum_{k=0}^{\infty} m P(T \gt km)$

$\lt m \sum_{k=0}^{\infty} (1-6^{-m})^k$

$=m6^m \lt \infty$ 　□

補題4　 $E_1=E_2=...=E_6$

証明

補題２の ${ M_n }$ について、 ${ | M_{n+1}-M_n | \le 1 }$ と補題３から任意抽出定理を適用できる。したがって

$E[ M_T ]=E [ M_0 ]=0$

よって

${\displaystyle E_i=E[A_T^i ]=E[A_T^j ]=E_j }$ □

2018-04-08

対称群の正規部分群

代数

対称群 ${S_n}$ の非自明な正規部分群が交代群と ${S_4}$ でのクラインの四元群のみであることを乏しい知識で示してみます。

用いる知識は

群 ${G}$ の部分群 ${H}$ が正規部分群であることは ${H}$ が ${G}$ のいくつかの共役類の和集合として表されることと同値である。

対称群について ${g,h}$ が同じ共役類に入ることは、両者が同じサイクル構造を持つことと同値である。

などです。

以下では正規部分群とは非自明なもののみを指すとします。

先に4次以下について簡単にみていきます。類等式の部分和で ${S_n}$ の位数の約数となるものが正規部分群の候補になります。

1,2次の対称群はそもそも非自明な部分群が存在しない。

3次の対称群の類等式は ${6=1+2+3}$ 。1を含む部分和で6の非自明な約数になるのは ${1+2}$ のみ。これは交代群 ${A_3}$ が対応する。

4次の対称群の類等式は

${24=1+6(互換)+8(長さ3の巡回置換)}$

${+6(長さ4の巡回置換)+３(互いに素な互換の積)}$

1を含む部分和で24の非自明な約数になるのは ${1+3,1+3+8}$ のみ。これはクラインの四元群 ${V}$ と交代群 ${A_4}$ が対応する。

メインに進みます。

命題　 ${n≧5}$ のとき ${n}$ 次対称群 ${S_n}$ の正規部分群は交代群 ${A_n}$ のみ。

先に用語・記号の説明をします。

共役類 ${C,C'}$ に対して ${C \rightarrow C'}$ とは、

${C}$ を含む任意の正規部分群は ${C’}$ も含むこと

と定義する。

ある ${ g,h \in C }$ が存在して ${ gh \in C' }$ ならば ${C \rightarrow C’}$ 。

${C \rightarrow C’}$ かつ ${C’ \rightarrow C’’}$ ならば ${C \rightarrow C’’}$ 。

に注意してください。

${ S_n }$ の共役類が完全であるとは、その共役類の元を ${\{ 1,2,..,n \}}$ 上の全単射とみるときに不動点を持たないことと定義する。(完全順列に倣った用語です)

${\{e}\}$ 以外の共役類を非自明な共役類と呼ぶ。

5次以上対称群 ${ S_n }$ について以下の補題１～４が成り立ちます。

補題１　長さ３の巡回置換からなる共役類 ${C_3}$ は交代群 ${A_n}$ を生成する。

補題２　完全でない非自明な共役類 ${C}$ について、 ${C \rightarrow C_3}$

補題３　各元が、互いに素な互換の積では表されない非自明な共役類 ${C}$ について、 ${C \rightarrow C_3}$

補題４　非自明な共役類 ${C}$ について、 ${C \rightarrow C_3}$

命題の証明　正規部分群はある非自明な共役類を含む。補題１と補題４により、非自明な共役類を含む正規部分群は交代群 ${A_n}$ を含む。 ${A_n}$ を含む真部分群は存在しないので正規部分群は ${A_n}$ のみ。□

各補題を証明します。

補題１　長さ３の巡回置換からなる共役類 ${C_3}$ は交代群 ${A_n}$ を生成する。

証明　 ${C_3}$ から生成される ${S_n}$ の部分群を ${G}$ とする。 ${C_3 \subset A_n}$ より ${G \subset A_n}$ 。逆の包含関係は、 ${A_n}$ の元は偶数個の互換の積で表されるので任意の二つの互換の積が ${G}$ の元であることを示せばよい。実際、相異なる ${i,j,k,l}$ について