ケイリーの公式の証明6種類

ケイリーの公式の証明たちの紹介です。

ケイリーの公式とは

ケイリーの公式とは $n$ 頂点のラベル付きの木の総数 $T(n)$ が $T(n) = n^{n-2}$ であるという公式のことです。

ここで、ラベル付きであるとは、それぞれの頂点を区別するということです。

たとえば $n = 3$ のとき、頂点を区別しない場合は長さ $3$ のパスのみの $1$ 通りですが、ラベル付きの木の場合は $1 - 2 - 3$ , $2 - 1 - 3$ , $1 - 3 - 2$ の $3 (= 3^{3-2} = T(3))$ 通りです。

証明 1 (プリューファーコード) [1]

おそらく一番有名な証明です。

$n$ 頂点のラベル付きの木の集合から $\{ 1, 2, \ldots, n \}^{n-2}$ への全単射を以下のように構成します。

最もラベルが小さい葉を木から取り除き、その葉と繋がっていた頂点のラベル $a_{1}$ を数列の最初の値とします。

続けて、最もラベルが小さい葉を木から取り除き、その葉と繋がっていた頂点のラベル $a_{2}$ を数列の $2$ 番目の値とします。

以下同様に頂点が $2$ つになるまで操作を続けます。

こうしてできた数列 $a_{1}, a_{2}, \ldots, a_{n-2}$ が木の値となります。

この数列をプリューファーコードといいます。

例えば、以下の木のプリューファーコードは $3, 2, 6, 6$ となります。

f:id:joisino:20170819151034p:plain

これの逆写像は以下のように与えられます。

まず、辺のない $n$ 頂点を用意します。

次に、 $a_{1}, a_{2}, \ldots, a_{n-2}$ に含まれない値のうち、最も小さいものを $b_{1}$ とし、 $a_{1}$ と $b_{1}$ を繋ぎます。

続けて、 $b_{1}, a_{2}, a_{3} \ldots, a_{n-2}$ に含まれない値のうち、最も小さいものを $b_{2}$ とし、 $a_{2}$ と $b_{2}$ を繋ぎます。

続けて、 $b_{1}, b_{2}, a_{3}, a_{4} \ldots, a_{n-2}$ に含まれない値のうち、最も小さいものを $b_{3}$ とし、 $a_{3}$ と $b_{3}$ を繋ぎます。

以下同様に木を構成していきます。

最後に、 $b_{1}, b_{2}, \ldots, b_{n-2}$ に含まれていない $2$ 頂点を繋いで完成です。

これが逆写像になっていることは以下のようにわかります。

まず、プリューファーコードに登場する頂点は元の木の内点で、かつ元の木の内点を全て尽くしています。

なぜなら

$a_{i}$ は $i$ 番目の操作の時点で葉とつながっている点なので、これが葉であると、操作後に頂点数が $1$ の成分になってしまうので矛盾です。よって全ての $a_{i}$ は内点です。
全ての内点は、操作のどこかの時点で葉になり、 $2$ 頂点以外は取り除かれていきます。少なくともその頂点が葉になった瞬間においてコード中に登場するはずなので、全ての内点を尽くしています。

以上より、逆に $a_{1}, a_{2}, \ldots, a_{n-2}$ に含まれない値は初期状態において葉であって、全ての葉を尽くしています。

そのうち最もラベルの小さい頂点は順写像において最初に取り除かれた頂点で、 $a_{1}$ と繋がっていたはずです。

以下帰納的に順写像の操作に対応する辺が見つかっていきます。

最後は、順写像の操作で取り除かれなかった頂点を結べば完成となります。

全単射が存在するということは要素の数が等しいということです。

$\{ 1, 2, \ldots, n \}^{n-2}$ の要素数はもちろん $n^{n-2}$ なので $T(n) = n^{n-2}$ となります。

証明 2 (もうひとつの全単射) [2]

もうひとつ全単射を使った証明を紹介します。

今度は $\{ 1, 2, \ldots, n \}^{n}$ から、 $n$ 頂点からなるラベル付きの木であって $1$ 頂点に赤い印がついていて $1$ 頂点が星形である木への全単射を構成します。

ここで、赤の頂点と星の頂点は同じ頂点でもかまいません。

ラベル付きの木を固定すると赤の頂点と星の頂点の選び方は $n^{2}$ 通りあるので、値域の要素数は $T(n) n^{2}$ で、定義域の要素数は $n^{n}$ なので、これらが等しければケイリーの公式の証明が完了します。

数列 $(a_{1}, a_{2}, \ldots, a_{n})$ を入力とします。

$1 \le i \le n$ について $i$ から $a_{i}$ へ辺があるような $n$ 頂点 $n$ 辺からなるグラフを考えます。

全ての出次数が $1$ であるグラフは functional graph と呼ばれ、サイクルに木がついた連結成分がいくつかあるような形になります。

例えば $7, 4, 8, 1, 7, 4, 4, 3$ のときグラフは以下のようになります。

f:id:joisino:20170819161216p:plain

ここで、サイクル上の頂点をソートして並べたものを $b_{1}, b_{2}, \ldots, b_{k}$ とします。

上の例の場合 $1, 3, 4, 7, 8$ となります。

出力の木としては、 $a_{b_{1}}, a_{b_{2}}, \ldots, a_{b_{k}}$ をこの順に並べてパスとし、残りは functional graph と同様に繋げます。赤の頂点は $a_{b_{1}}$ を選び、星の頂点は $a_{b_{k}}$ を選びます。

上の例の場合は以下のようになります。

f:id:joisino:20170819162001p:plain

逆写像は以下のように構成します。

まず、木のうち、赤の頂点から星の頂点までの（一通りしかない）パスをとって、 $c_{1}, c_{2}, \ldots, c_{k}$ と順に並べます。

パス上の頂点のラベルをソートした数列を $b_{1}, b_{2}, \ldots, b_{k}$ とします。

$1 \le i \le k$ について、元の数列の $b_{i}$ 番目の値が $c_{i}$ であることが分かります。

パス以外の頂点は、パス上の頂点を根とした根付き木を考え、頂点 $v$ の親が $u$ のとき、元の数列の $v$ 番目の値が $u$ となることが分かります。

これで復元できました。

証明 3 (double counting) [2] [3]

この証明もかなり有名な証明です。

wikipedia にもこの証明が載っています。

頂点にも辺にもラベルが付いた $n$ 頂点からなる根付き木の総数 $U(n)$ を二通りの方法で数えます。

一つは、 $T(n)$ を使う方法です。ラベル付きの木を固定したとき、根の選び方が $n$ 通り、辺へのラベルの付け方が $(n-1)!$ 通りあるので、 $U(n) = T(n) \cdot n \cdot (n-1)!$ となります。

もうひとつは辺を $1$ つずつ追加していって逐次的に木を構成していく方法です。 $i$ 番目に追加した辺のラベルを $i$ とします。

辺のない $n$ 頂点からなるグラフを用意します。

最初の辺は、親の選び方が $n$ 通りあって、子の選び方は自分以外の $n-1$ 通りです。

$2$ つ目の辺は、親の選び方がこれも $n$ 通りあります。子の選び方は、根でない頂点を選ぶとその頂点の親が $2$ つになってしまうのでだめです。自分が属している木の根も、ループができてしまうのでだめです。よって、子の候補は $n-2$ 個となります。

同様に、 $1 \le i \le n-1$ について $i$ 番目の辺は、親の選び方が $n$ 通り、子の選び方が $n-i$ 通りとなります。

よって、 $U(n) = \Pi_{i=1}^{n-1} n (n-i) = n^{n-1} \cdot (n-1)!$ となります。

これが $T(n) \cdot n \cdot (n-1)!$ と等しいので $T(n) = n^{n-2}$ となります。

証明 4 (行列木定理) [2]

行列木定理を使った証明です。

ラベル付きの木の総数と $n$ 頂点完全グラフ $K_{n}$ の全域木の総数は同じです。

$K_{n}$ のラプラシアン行列は

$$ \displaystyle \left[ \begin{array}{rrr} n-1 & -1 & -1 & \ldots & -1 \\ -1 & n-1 & -1 & \ldots & -1 \\ -1 & -1 & n-1 & \ldots & -1 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ -1 & -1 & -1 & \ldots & n-1 \end{array} \right] $$

となります。行列木定理より、 $T(n)$ はこの行列の任意の余因子と一致します。

$(1, 1)$ 余因子をとりましょう。

$(1, 1)$ 余因子はもとの行列から $1$ 行目と $1$ 列目を取り除いた $(n-1) \times (n-1)$ 行列の行列式です。

まず、 $2$ 行目から $n-1$ 行目を $1$ 行目に足します。すると $1$ 行目が全て $1$ になります。

$$ \displaystyle \left| \begin{array}{rrr} 1 & 1 & 1 & \ldots & 1 \\ -1 & n-1 & -1 & \ldots & -1 \\ -1 & -1 & n-1 & \ldots & -1 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ -1 & -1 & -1 & \ldots & n-1 \end{array} \right| $$

次に、 $1$ 行目を $2$ 行目から $n-1$ 行目に足します。

$$ \displaystyle \left| \begin{array}{rrr} 1 & 1 & 1 & \ldots & 1 \\ 0 & n & 0 & \ldots & 0 \\ 0 & 0 & n & \ldots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \ldots & n \end{array} \right| $$

この式の値は $n^{n-2}$ なので、 $T(n) = n^{n-2}$ となります。

証明 5 (漸化式) [2]

より一般的な問題を漸化式と帰納法によって解きます。

ラベルの集合の、要素数 $k$ の部分集合 $A$ を任意にとります。

$A$ に含まれている頂点が互いに異なる連結成分に属するようなラベル付き森の数を $S(n,k)$ とします。

これは $A$ の要素数にしかよらないので well-defined です。

便宜上 $S(0,0) = 1, S(n,0) = 0 ( n > 0 )$ とします。

$S(n,k) = k \cdot n^{n-k-1}$ (*) であることを示します。

$T(n) = S(n,1)$ なので、これが示せればケイリーの公式は示されます。

ラベルの集合を $\{ 1, 2, \ldots, n \}$ とし、 $A = \{ 1, 2, \ldots, k \}$ としたときに $S(n, k)$ で数える森を $1$ つ固定します。

この森で頂点 $1$ と繋がっている頂点を $B = \{ a_{1}, a_{2}, \ldots, a_{l} \}$ とします。

このときこの森から頂点 $1$ を取り除いてできる森は、ラベルの集合を $\{ 2, 3, \ldots, n \}$ とし $A = \{ 2, 3, \ldots, k, a_{1}, a_{2}, \ldots, a_{l} \}$ としたときに $S(n-1,k+l-1)$ で数える要素になります。

逆にラベルの集合を $\{ 2, 3, \ldots, n \}$ とし $A = \{ 2, 3, \ldots, k, a_{1}, a_{2}, \ldots, a_{l} \}$ としたとき、新たに頂点 $1$ を加えて $a_{1}, a_{2}, \ldots, a_{l}$ とつなげると、先ほど考えていた $S(n, k)$ で数えた森に対応します。

つまり、 $S(n,k)$ で数える森は、 $A$ と交わらない頂点集合 $B$ ごとに $S(n-1,k+|B|-1)$ 個の森と対応づいているということです。

以上の考察から

$\displaystyle S(n,k) = \sum_{l=0}^{n-k} \binom{n-k}{l} S(n-1, k+l-1)$

となります。これは $B$ として、 $A$ 以外の要素 $n-k$ 個から $l$ 個選ぶというのを $l = 0, 1, \cdots n-k$ について足しあわせているということです。

この漸化式を使って帰納法により (*) を示しましょう。

$\begin{align*} S(n,k) &= \sum_{l=0}^{n-k} \binom{n-k}{l} S(n-1, k+l-1) & \\ &= \sum_{l=0}^{n-k} \binom{n-k}{l} (k+l-1) (n-1)^{n-k-l-1} & ({\rm 帰納法の仮定より})\\ &= \sum_{l=0}^{n-k} \binom{n-k}{l} (n-1-l) (n-1)^{l-1} & (l = n - k - l {\rm と変換}) \\ &= \sum_{l=0}^{n-k} \binom{n-k}{l} (n-1) \cdot (n-1)^{l-1} - \sum_{l=0}^{n-k} \binom{n-k}{l} l \cdot (n-1)^{l-1} & ({\rm 分配}) \\ &= \sum_{l=0}^{n-k} \binom{n-k}{l} (n-1)^{l} - \sum_{l=0}^{n-k} \binom{n-k}{l} l \cdot (n-1)^{l-1} & \\ &= (n-1+1)^{n-k} - \sum_{l=0}^{n-k} \binom{n-k}{l} l \cdot (n-1)^{l-1} & ({\rm 二項定理})\\ &= n^{n-k} - \sum_{l=0}^{n-k} \binom{n-k}{l} l \cdot (n-1)^{l-1} & \\ &= n^{n-k} - \sum_{l=1}^{n-k} \binom{n-k}{l} l \cdot (n-1)^{l-1} & (l=0 {\rm のとき} 0) \\ &= n^{n-k} - (n-k) \sum_{l=1}^{n-k} \binom{n-k-1}{l-1} \cdot (n-1)^{l-1} & ({\rm 二項係数をほぐす})\\ &= n^{n-k} - (n-k) \sum_{l=0}^{n-k-1} \binom{n-k-1}{l} \cdot (n-1)^{l} & (l=l+1 {\rm と変換})\\ &= n^{n-k} - (n-k) (n-1+1)^{n-k-1} & ({\rm 二項定理})\\ &= n^{n-k} - (n-k) n^{n-k-1} & \\ &= k \cdot n^{n-k-1} & \end{align*}$

証明 6 (母関数とラグランジュの反転公式) [1]

$n$ 頂点からなるラベル付きの根付き木の総数を $R(n)$ とします。便宜上 $R(0) = 0$ とします。

根なし木を固定したとき根の選び方は $n$ 通りなので、 $R(n) = n T(n)$ となります。 $R(n) = n^{n-1}$ を示すのが目標です。

根の選び方は $n$ 通りあります。

根の子の個数を $m$ に固定します。

子に順番があると考え、それぞれの部分木の大きさが左から順に $k_{1}, k_{2}, \ldots, k_{m} (k_{1} + k_{2} + \ldots + k_{m} = n-1)$ であるとします。

根の子の部分木について、どのラベルを割り当てるかが $\frac{(n-1)!}{k_{1}! k_{2}! \ldots k_{m}!}$ 通りあります。

各部分木について根付き木の作り方はそれぞれ $R(k_{1}), R(k_{2}), \ldots, R(k_{m})$ 通りあります。

子の順番を取り除くために、これらの積を $m!$ で割る必要があります。

以上より

$\begin{align*} R(n) &= n \sum_{m=0} \frac{1}{m!} \sum_{k_{1} + k_{2} + \ldots + k_{m} = n-1} \frac{(n-1)!}{k_{1}! k_{2}! \ldots k_{m}!} R(k_{1}) \cdot R(k_{2}) \cdot \ldots \cdot R(k_{m}) \\ &= \sum_{m=0} \frac{1}{m!} \sum_{k_{1} + k_{2} + \ldots + k_{m} = n-1} \frac{n!}{k_{1}! k_{2}! \ldots k_{m}!} R(k_{1}) \cdot R(k_{2}) \cdot \ldots \cdot R(k_{m}) \\ \end{align*}$

という漸化式が成り立つことが分かります。

次に $R(n)$ の指数型母関数

$\displaystyle f(x) = \sum_{n=0}^{\infty} \frac{ R(n) x^n }{ n! }$

を考えます。

$\begin{align*} x e^{f(x)} &= x \sum_{m=0}^{\infty} \frac{ f(x)^m }{ m! } \\ &= x \sum_{m=0}^{\infty} \frac{1}{m!} (\sum_{n=0}^{\infty} \frac{ R(n) x^n }{ n! })^m \\ &= x \sum_{m=0}^{\infty} \frac{1}{m!} \sum_{k_{1}=0}^{\infty} \sum_{k_{2}=0}^{\infty} \cdots \sum_{k_{m}=0}^{\infty} \frac{1}{k_{1}! k_{2}! \ldots k_{m}!} R(k_{1}) \cdot R(k_{2}) \cdot \ldots \cdot R(k_{m}) x^{k_{1} + k_{2} + \ldots + k_{m}} \\ &= \sum_{m=0}^{\infty} \frac{1}{m!} \sum_{k_{1}=0}^{\infty} \sum_{k_{2}=0}^{\infty} \cdots \sum_{k_{m}=0}^{\infty} \frac{1}{k_{1}! k_{2}! \ldots k_{m}!} R(k_{1}) \cdot R(k_{2}) \cdot \ldots \cdot R(k_{m}) x^{k_{1} + k_{2} + \ldots + k_{m}+1} \\ &= \sum_{m=0}^{\infty} \frac{1}{m!} \sum_{k_{1}=0}^{\infty} \sum_{k_{2}=0}^{\infty} \cdots \sum_{k_{m}=0}^{\infty} \frac{(k_{1} + k_{2} + \ldots + k_{m} + 1)!}{k_{1}! k_{2}! \ldots k_{m}!} R(k_{1}) \cdot R(k_{2}) \cdot \ldots \cdot R(k_{m}) \frac{x^{k_{1} + k_{2} + \ldots + k_{m}+1}}{(k_{1} + k_{2} + \ldots + k_{m} + 1)!} \\ &= f(x) \end{align*}$

最後の等式は先ほどの漸化式から従います。

よって、 $R(n)$ の指数型母関数 $f(x)$ は $f(x) = x e^{f(x)}$ という単純な方程式に従うことがわかりました。

次にラグランジュの反転公式を使います。

ラグランジュの反転公式とは、べき級数

$\displaystyle f(x) = a + \frac{a_{1}}{1!} x + \frac{a_{2}}{2!} x^{2} + \ldots$

が

$\displaystyle f(x) = a + x \phi( f(x) )$

という方程式を満たすとき、

$\displaystyle a_{n} = \left| \frac{{\rm d}^{n-1}}{{\rm dt}^{n-1}} (\phi(t)^n) \right|_{t=a}$

を満たすというものです。

これに先ほどの方程式を当てはめます。

（本当は収束性などを調べないといけないはずですが、参考文献では特に言及されていませんでした。実際 $R(n) = n^{n-1}$ なので収束半径は $\frac{1}{e}$ になるはずなのですが、答えを使わずに証明する良い方法が思いつかなかったのでここでは省略します。僕が勘違いしていたり、良い方法があったりしたら教えてください）

ここで、 $\phi(t) = e^{t}, a = 0$ なので、

$\displaystyle \frac{{\rm d}^{n-1}}{{\rm dt}^{n-1}} e^{nt} = n^{n-1} e^{nt}$

よって、 $t = a = 0$ を代入すると $R(n) = n^{n-1}$ となり示されました。

最後に

何か間違いや質問などがあればお願いします。

他の証明もあれば教えていただけると嬉しいです。

最後まで読んでいただきありがとうございました。

参考文献

[1] パラモノヴァ(著). ヴィンベルク(著). コーハシ(著). 武部尚志(訳). (2007). モスクワの数学ひろば 3 代数篇／対称性・数え上げ.

[2] Aigner Martin. Ziegler Günter M. (2013). Proofs from THE BOOK 4th edition. pp.201-206

[3] ケイリーの公式 - Wikipedia

2017-08-13

前処理O(n)クエリO(1)のLCAと静的RMQ

時間計算量 <O(n), O(1)> の LCA(Lowest Common Ancestor) と RMQ(Range Minimum Query) を C++ で実装しました。

アルゴリズムの解説はDさんのスライド [1] LCA and RMQ ~簡潔もあるよ！~ がとても分かりやすいのでそちらを参照してください。

概要だけ説明します。

LCA の概要

LCA は頂点を dfs 順で訪れた順に並べると深さの列の RMQ に帰着されます。このことは [2] 蟻本などに載っています。

この列は隣り合う数の差がちょうど $1$ になっています。

この列を $\frac{\log n}{2}$ 個ずつのブロックに分け、それぞれのブロック内の最小値を求めます。

ブロックの数は $\frac{2n}{\log n}$ 個になるので、ブロックの区間の最小値を求めるクエリは sparse table を使うと前処理 $\frac{2n}{\log n} \log \frac{2n}{\log n} = O(n)$ 、クエリ $O(1)$ で処理できます。

ブロックの中についてですが、各ブロックは 1 つ目の数がわかればあとは +1 されるか -1 されるかの 2 通りです。この遷移の種類は高々 $2^{\frac{\log n}{2} - 1} = O(\sqrt{n})$ 個しかありません。

この全ての種類について、最初の数が $0$ だと思って愚直に前計算すると全て合わせて $O(\log^{2} n \cdot \sqrt{n})$ で計算できます。

あとはクエリが来た時に、完全に含まれるブロックを sparse table で処理して、はみ出た部分を前計算した表を参照して答えればよいです。

RMQ の概要

列を Cartesian Tree という木に変換します。

Cartesian Tree は、列のインデックスをノードの値にもつ二分探索木で、列の値についてヒープ条件を満たしています。ヒープ条件を満たしているとは、列の値について、親の値が子の値以下であるということです。

Treap のような感じです。

すると、RMQ はこの Cartesian Tree 上の LCA クエリに帰着されることがわかると思います。

Cartesian Tree の構成の仕方は [1] には載っていないので少し詳しく説明します。

Cartesian Tree を O(n) で構成する

列を左から右に見ていって、順に Cartesian Tree を構成していきます。

今まで構成した Cartesian Tree の頂点の親を配列で管理し、根から右の子を辿るパスをスタックで管理します。

新しく列の最後に値を追加するとします。

このとき、二分探索木の条件から、新しい頂点はスタックで管理されているパス上の頂点の右の子になるか、根になるかのどちらかです。

どの頂点の子になるかは、スタックの頂点の値よりも新しい頂点の値の方が小さければ、スタックから頂点を取り除くことを繰り返し、最終的にスタックの一番上に残っている頂点が新しい頂点の親になります。スタックが空ならば新しい頂点は根になります。

新しい頂点のせいで親から引き離された頂点は、新しい頂点の左の子にすればよいです。

例えば 4, 2, 5, 1, 3, 8, 7, 9 の後ろに 6 を付け加える場合は以下のようになります。

ノードは (index, val) のように表しています。赤いノードがスタックで管理されているパスです。

f:id:joisino:20170813142841p:plain

f:id:joisino:20170813142849p:plain

実装

C++ で実装しました。

LCA

gist.github.com

RMQ

gist.github.com

LCA は GRL_5_C に投げたところ、 $10^{5}$ 頂点 $10^{5}$ クエリで AOJ 上で 0.06s でした。入出力にもある程度時間がかかっていると思います。

RMQ の方は、DSL_3_D (スライド最小値) に投げたところ、 $10^{5}$ 要素 $10^{5}$ クエリで AOJ 上で 0.34s でした。 RMQ は何段階も帰着させている分線形とはいえ遅いです。

メルセンヌツイスタで生成した乱数に対して RMQ を実行すると、手元の環境だと

$10^{6}$ 要素 $10^{6}$ クエリで 0.425s
$10^{7}$ 要素 $10^{7}$ クエリで 5.206s

でした。

最後に

何か間違いや質問などがあればお願いします。

最後まで読んでいただきありがとうございました。

参考文献

[1] LCA and RMQ ~簡潔もあるよ！~

[2] 秋葉拓哉. 岩田陽一. 北川宜稔. (2012). プログラミングコンテストチャレンジブック [第2版]. pp.294 - 295.

2017-08-06

テヘラン旅行

IOI2017（イラン大会）に副団長として参加してきました。

ioi2017.org

IOIの参加記は選手・役員の感想（まだ公開されていないようなのであとでリンクを張ります）に書いたのでそちらを参照してください。

第29回国際情報オリンピックイラン大会速報も面白いのでまだ見てないひとはぜひ。

この記事では、これからテヘランに行く人の参考のために、大会以外の部分についてメモしておきます。

事前準備

買い物をして事前準備をしました。

地球の歩き方

念の為買っておきましたが、ツアー旅行のようなものなのでほとんど使いませんでした。

イランの一般的な情報と、ペルシャ語（特に数字）については少し役に立ったと思います。

圧縮袋

服を圧縮する袋です。

かなり容量が小さくなるので助かりました。これはテヘラン旅行以外でも役に立つと思います。

盗難防止

これのウエストポーチを買いました。

そんなに大きくはなく、パスポートと現金と鍵とカードなどを入れていました。

テヘランはそこまで治安が悪くなかったので、そこまで厳重に警戒する必要は無かったかもしれません。（スマホなどはポケットに入れていましたが取られませんでした）

バザールに行くなどすると危なかったのかもしれません。

貴重品を一箇所に集められるという点ではかなり重宝しました。

マルチビタミン剤

イランの食事はインディカ米、肉、インディカ米、肉、インディカ米という感じなのでビタミンが不足しがちです。

これのおかげ（？）で風邪を引きませんでした。

サイリウム

帰国したあとすぐに映画を見るために持って行きました。

テヘランで使うつもりは無かったのですが、懐中電灯の代わりに使えて便利でした。

二人部屋で夜中起きたときにトイレの電気ガチャ（外れると部屋全体の電気が付く）をせずに済みました。

現地の気候

7 月末から 8 月頭と夏真っ盛りに行ってきました。

気温は最高気温が 35 度ちょっとの日が多く、最高気温 40 度の日もありましたが、湿度がかなり低いので、そこそこ過ごしやすかったです。個人的には夏の京都よりも過ごしやすいと思いました。

テヘランは砂漠なので木陰があまり無かったですが、建物の影や数少ない木陰に隠れると日中でも割と快適でした。

一方、砂が舞っているのと、自動車の排気ガスと、タバコのせいで空気が悪く、乾燥との二重苦で鼻が痛くなってきます。

これを防ぐ手立てはよくわからないのですが、大気汚染が特に酷そうな場所を歩くときは布で鼻を押さえるなどの対策をした方がよいと思います。

また、乾燥のせいで静電気もすごかったので心構えしておきましょう。

現地の買い物

まず一番気をつけないといけないのが、イランではリアルとトマーンという二種類の通貨が使われていることです。

日常的にはどちらかというとトマーンが多く使われていて、外国人向けの店ではリアルで書いてあるものが多い気がしましたが、どちらのパターンもあって、しかも通貨が書いてない場合が多かったので、よく気をつける必要があります。

僕が行った当時は 300リアル = 30 トマーン $\approx$ 1 円くらいでした。

また、もう一つ気をつけないといけないのが、多くの店では、値札がペルシャ数字で書かれていることです。

イランに行く前にペルシャ数字を覚えるか、少なくともペルシャ数字表を携帯していくことをオススメします。

物価は日本よりかなり安く、1 / 3 から 1 / 2 くらいな印象でした。

500mL ミネラルウォーターが 10000 リアル $\approx$ 30円くらいでした。

ホテル

Azadi Hotel というホテルに泊まりました。

一泊二万円以上するホテルだけあって、かなり綺麗で快適でした。

食事とトイレ以外は他の国の一級ホテルとほとんど変わらないと思います。

食事

前述しましたが、イランの食事はインディカ米、肉、インディカ米、肉、インディカ米という感じでした。

f:id:joisino:20170806163526j:plain

こういう感じです。

ホテルの朝食ではパンが出たので、朝食はパンをよく食べました。

f:id:joisino:20170806163637j:plain

こういう感じです。

風習など

まず、イスラム教の色々な風習がありますが、ここに書くには重いので他の文献に任せます。

一番驚いたのは、イラン人はかなり気さくで、街中を歩いているとよく話しかけてきたことです。

特に IOI 期間中は日本国旗が描かれた名札を下げていたこともあって、"Japon?“ と話しかけてくるケースが多かったです。その後の会話は様々ですが、適当に日本っぽい単語を言ってくることが多かったです。ポテトチップス的なお菓子を勧められたりもしました（怖かったので断りました）

あと気をつけたほうが良いのが、トイレ事情です。

イランのトイレはアナログウォシュレット（シャワーがトイレの横についている）を使って洗って、紙ナプキンのようなトイレットペーパーで拭いてゴミ箱に捨てる形式です。

外国人が多く泊まりそうな一級ホテルの Azadi Hotel でもこの形式だったのでイランのトイレはだいたいどこもこうなんだと思います。

IOI 期間中は外国人が集まっていたこともあり、ウォシュレットのせいで公共トイレの床はどこも大洪水でした。

気になる人はトイレに流せるトイレットペーパーを持って行くとよいと思います。

インターネット

イランはインターネット規制が厳しい国で、twitter などは規制されていてアクセスできません。

なので、規制されているサービスを利用したい場合は VPN を用意する必要があります。

僕は大学の VPN (KUINS-PPTP) を利用しました。

また、irancell という会社の SIM カードが IOI から配られました。

irancell の店はテヘランの至るところにあり、テヘラン旅行の際はこれを使うことになることが多そうです。

SIM カードをセットすると SMS でいろいろ情報が送られてきますが、全てペルシャ語なので USSDコード一覧の Switching Language into English を使うことをオススメします。

回線は容量に応じて課金しました。

RechargeOption の Online Recharge からオンラインで課金できます。

課金したあとは Packages からパッケージを買います。

3GB の通信で 13000 トマーン $\approx$ 400 円と激安です。

回線もそこそこ安定していました。

ホテルの wifi もあったのですが、こちらは通信が絶望的に不安定で使い物になりませんでした。具体的には 8.8.8.8 への ping が半分くらいパケットロスしました。

終わりに

テヘラン旅行はとても楽しく、また、IOI がたくさんお金をかけていたこともあって、想像以上に快適でした。

また行きたいかと言われると返答に困りますが。

もしテヘラン旅行に行くなら、楽しんできてください。

最後まで読んでいただきありがとうございました。

2017-08-03

ミラーラビン素数判定法とロー法

ミラーラビン素数判定法について

ミラーラビン素数判定法はフェルマーテストを拡張した感じです。

フェルマーテストでは $p$ が素数のとき、フェルマーの小定理より $a$ と $p$ が互いに素なとき $a^{p-1} \equiv 1 \pmod p$ となることを利用して、 $n$ と互いに素な整数 $a$ を取って $a^{n-1} \not \equiv 1 \pmod n$ であれば合成数と判断するのでした。

ここから更に拡張します。

$x^{2} \equiv 1 \pmod p$ のとき、 $(x-1)(x+1) \equiv 0 \pmod p$ で、 $p$ が素数より $x \equiv 1$ または $x \equiv -1$ となることを利用します。

$(n-1) = 2^{q} d$ というように $d$ に素因数 $2$ が出ないように分解します。

このとき、（ $q \ge 1$ であれば） $a^{2^{q-1}d} = 1$ または $a^{2^{q-1}d} = -1$ となります。

さらに、 $a^{2^{q-1}d} = 1$ のときは（ $q \ge 2$ であれば） $a^{2^{q-2}d} = 1$ または $a^{2^{q-2}d} = -1$ と続きます。

つまり、 $p$ が素数ならば、 $a^{2^{q-i}d}$ が $i = 0, 1, 2, ... q$ のとき $1, 1, ..., 1, -1, ?, ?, ...$ となるか、全部 $1$ になるます。

これの対偶を使って、 $a^{d} = 1$ となるか、 $a^{2^{q-i}d} (1 \le i \le q-1)$ のどこかで $-1$ となるかのどちらかにならなければ、合成数です。

この $a$ をランダムに決めて、テストしてくいくのがミラーラビン素数判定法です。

ここで、テストする数 $n$ が小さければいくつかの $a$ を使うだけで、確実に素数判定を実行できることが保証できます。

例えば、 $n \le 4759123140 (\ge 2^{32})$ なら、 $a = 2, 7, 61$ についてのみ調べれば良いです。

実装

C++ で実装しました。

gist.github.com

メルセンヌツイスタでランダムに生成した $10^{6}$ 個の $10^{9}$ 以下の整数について素数判定するのに手元の環境だと 1.854s かかりました。

ロー法について

乱択で素因数を発見するアルゴリズムです。

[2] 素因数分解の高速なアルゴリズム（ロー法） | 高校数学の美しい物語がとても分かりやすいので、アルゴリズムの内容はそちらを見てください。

実装

これの素数判定にミラーラビンを使って、C++ で実装しました。

gist.github.com

メルセンヌツイスタでランダムに生成した $10^{5}$ 個の $10^{9}$ 以下の整数について素数判定するのに手元の環境だと 1.670s かかりました。

最後に

何か間違いや質問などがあればお願いします。

最後まで読んでいただきありがとうございました。

参考文献

[1] ミラー–ラビン素数判定法 - Wikipedia

[2] 素因数分解の高速なアルゴリズム（ロー法） | 高校数学の美しい物語

2017-07-30

クリーネの不動点定理（とベルマンフォード法）

言語処理系で講義でクリーネの不動点定理をやった時にベルマンフォードの証明にも使えるなぁと思ったので紹介します。

クリーネの不動点定理

$(D,\le)$ を完備半順序集合とし、 $f$ をその上のスコット連続写像とする。このとき、 $f$ は最小不動点を持つ。

ここで、完備半順序集合とは最小元 $\bot$ を持ち、任意の有向部分集合 $X$ について $X$ の上限 $\sqcup X$ が存在する半順序集合とします。

$X$ が有向集合であるとは任意の $a,b \in X$ についてある元 $c \in X$ が存在して $a \le c \land b \le c$ が成り立つこととします。

$f$ が $D$ 上のスコット連続写像であるとは、 $D$ の任意の有向部分集合 $X$ について $f(\sqcup X) = \sqcup \{ f(x) \mid x \in X \}$ が成り立つこととします。

何言ってんだコイツと思った人もブラウザバックを早まらないでください。

あとで有限半順序の場合を紹介しますが、有限の場合は簡単で、ベルマンフォードの証明に応用するのはそこだけで十分なので、意味がわからないひとは少しスクロールしてみてください。

とりあえず一般の完備半順序集合についてクリーネの不動点定理を証明しましょう。

証明

まず、 $f$ がスコット連続なら $f$ は単調です。

なぜなら $X = \{ a, b \}, a \le b$ とすると、 $X$ は有向集合で、 $\sqcup X = b$ となり、スコット連続性を考えると $f(\sqcup X) = f(b) = \sqcup \{ f(a), f(b) \}$ となるので、 $f(a) \le f(b)$ が導かれるからです。

$A = \{ f^{n}(\bot) \mid n \in \mathbb{N} \}$ とします。( $\mathbb{N}$ は $0$ を含むものとします)

このとき、最小性より $\bot \le f(\bot)$ が成り立ち、単調性より $\bot \le f(\bot) \le f^{2}(\bot) \le ...$ となります。

よって、 $A$ は有向集合で、完備性より上限 $\sqcup A$ が存在します。これが目的の最小不動点となることを示します。

まず不動点性ですが、スコット連続性より

$f(\sqcup A) = \sqcup \{ f(f^{n}(\bot)) \mid n \in \mathbb{N} \} = \sqcup \{ f^{n}(\bot) \mid 1 \le n \in \mathbb{N} \} = \sqcup A$ より不動点です。

また、任意の不動点 $x$ について、 $\bot \le x$ と単調性より任意の $n \in \mathbb{N}$ について $f^{n}(\bot) \le f^{n}(x) = x$ となり、 $\sqcup A \le x$ が成立します。

以上より示せました。

有限半順序の場合

おまたせしました。

有限の場合、クリーネの不動点定理は

$(D,\le)$ を最小元 $\bot$ を持つ有限半順序集合とし、 $f$ をその上の広義単調増加写像とする。このとき、 $f$ は最小不動点を持つ。

となります。

$f$ が広義単調増加写像であるとは、任意の $a, b \in D$ に対して $a \le b \Rightarrow f(a) \le f(b)$ が成り立つことです。

それでは証明しましょう（一般の場合を読んだ人は繰り返しになるので読む必要は無いかもしれません）

有限半順序の場合の証明

$D$ の要素数を $|D|$ と表します。

任意に $x \in D$ を一つ取ります。

$\bot, f(\bot), ..., f^{|D|}(\bot)$ を考えると、最小性より $\bot \le f(\bot)$ が成り立ち、単調性より $\bot \le f(\bot) \le ..\ \le f^{|D|}(\bot)$ が成り立ちます。

そして、鳩の巣原理から $0 \le i$ < $j \le |D|$ で $f^{i}(\bot) = f^{j}(\bot)$ となるものが存在し、 $f^{i}(\bot) \le f^{i+1}(\bot) \le ...\le f^{j}(\bot) = f^{i}(\bot)$ の間が全て等号で成り立つので、 $f^{i}(\bot) = \bot'$ が不動点になります。

次に、任意に不動点 $y$ を取ります。

$\bot$ の最小性より $\bot \le y$ です。

また、単調性より、 $\bot' = f^{i}(\bot) \le f^{i}(y) = y$ となるので、 $\bot'$ が不動点の中で最小になります。

ベルマンフォード法について

負の閉路が無い場合のベルマンフォード法の正当性をクリーネの不動点定理で証明します。

双対（ポテンシャル）を考えます。

$D = \{ 0 \} \times \{ -{\rm INF}, ..., -1, 0, 1, ..\, {\rm INF} \}^{|V|-1}$ とします。

ここで、 ${\rm INF}$ は十分大きい数（例えば辺の重みの絶対値の合計）とします。

順序は $(a_{1}, ..., a_{n}) \le (b_{1}, ..., b_{n}) \Leftrightarrow a_{1} \le b_{1} \land ... \land a_{n} \le b_{n}$ と定めます。

$D$ の元はポテンシャルを表しています。

最初の $0$ は開始頂点のポテンシャルを $0$ に固定しているということです。

$f$ をベルマンフォードの一回のループによるポテンシャルの変化とします。

$f$ を適用するとポテンシャルは広義単調減少します。

よって、クリーネの不動点定理より、最大元 $\top = (0,{\rm INF}, ..., {\rm INF})$ から $f$ を有限回適用すると、最大不動点 $\top'$ に到達します。

不動点に到達すると、変化が起こらなくなるので、ベルマンフォードではループを抜けます。

このとき、ベルマンフォードの更新式から $\top'$ は LP の条件を満たします。

ここで、LP の条件を満たす任意の $D$ の元を $x$ とすると、これはベルマンフォードの処理 $f$ の不動点になっているはずです。

よって、最大性から $\top' \ge x$ となり、 $\top'$ が最適です（最短路問題の双対なので、求めるものは最大値となります）

最後に

なんか回りくどいだけになってしまった気もします。（双対を考えればベルマンフォードの正当性はすぐに分かるので）

クリーネの不動点定理は変化しなくなるまで変化させ続けるような他のアルゴリズムについても停止性や正当性の証明に使えると思うので、雰囲気を感じ取ってもらえれば幸いです。

何か間違いや質問などがあればお願いします。

最後まで読んでいただきありがとうございました。

参考文献

[1] 横内寛文. (1994). プログラム意味論 (情報数学講座).

2017-07-27

HashedNets

HashedNets [1] を chainer で実装しました。

HashedNets の説明

ニューラルネットワークのパラメータ数は非常に多く、パラメータは冗長な表現になっていることが多いです。

そこで、自由なパラメータの数を減らして、正則化と軽量化を達成するための手法の一つとして HashedNets が考案されました。

HashedNets では、ハッシュ関数を使って、同じハッシュ値となる辺どうしを重み共有します。

具体的にはまず層ごとに自由なパラメータの数 $K$ を決めて $K$ 次元のパラメータ $w$ を用意します。

次に、ネットワークの辺から $\{ 1,..\ K \}$ へのハッシュ関数 $h$ と $\{ -1, 1 \}$ へのハッシュ関数 $\xi$ を定めます。

順伝播させるときには、辺 $i$ の重みは $\xi(i) \cdot w_{h(i)}$ として計算します。

重み共有する辺の決定にハッシュ関数を使うことで、ランダムに割り付けができ、対応関係の情報を陽に持つ必要が無いので容量の削減が実現できます。

実装

Python 3.5.3 + chainer 2.0.1 で実装しました。

gist.github.com

簡単のため $\xi$ は実装していません。

$\xi$ があれば同じパラメータ数でももう少し表現力が上がったかもしれません。

逆伝播の計算では numpy.bincound を使うと便利でした。

実験

$K$ の値を変えて MNIST の分類を 3 層の全結合ニューラルネットワーク行いました。

元のニューラルネットワークにおいてはパラメータ数はそれぞれ $78400 \sim 2^{16.26}, 10000 \sim 2^{13.29}, 1000 \sim 2^{9.97}$ です。

f:id:joisino:20170724190837p:plain

このときの $K = 2^{10}$ 程度あれば正解率 0.95 くらいまで出ています。

容量の圧縮率はパラメータの数だけ見る単純計算で $(78400+10000+1000) / (1024 \cdot 3) \sim 29.10$ 倍くらいです。

最後に

何か間違いや質問などがあればお願いします。

最後まで読んでいただきありがとうございました。

参考文献

[1] W. Chen. et al. (2015) Compressing Neural Networks with the Hashing Trick

2017-07-23

本質的に曖昧な文脈自由言語

本質的に曖昧な文脈自由言語が存在するという事実は色んなところで何度も目にしてきたのですが、証明を見たことが無かったのでここで紹介します。

流れは大体 [1] と同じですが、補題の証明はオリジナルも混ざってます（本質的には同じだとは思います）（間違ってたら教えてください）

今回本質的に曖昧だと示すのは $L = \{ a^{i} b^{j} c^{k} \mid i, j, k \ge 1, i = j \lor j = k \}$ です。（これが文脈自由であることは簡単なので省略します）

ちなみに、これは計算理論の基礎 [2] （めっちゃいい本）の第2版の演習問題 2.29 です。（本に答えは載っていません）

めちゃくちゃ難しいと思うのですが自信のある人は考えてみてください（僕は分かりませんでした）

少しずつ補題を証明していく形式なので、少しずつ読んで考えてみるのも面白いかもしれません。（最後のステップだけでも普通に難しいと思います）

基本的な記法と定義

文脈自由文法を非終端記号 $V_{N} = \{ A_{1}, A_{2},... ,A_{n} \}$ 、終端記号 $V_{T}$ 、生成規則 $R$ 、開始記号 $A_{n}$ の組 $G = ( V_{N}, V_{T}, R, A_{n} )$ で定義します。

生成規則を $A_{i} \rightarrow \alpha_{1}... \alpha_{k}$ のように表します。

生成規則を 0 回以上適用して新しい列を生成することを $A_{i} \rightarrow^{*} \alpha_{1}... \alpha_{k}$ のように表します。

生成規則を 1 回以上適用して新しい列を生成することを $A_{i} \rightarrow^{+} \alpha_{1}... \alpha_{k}$ のように表します。

文法 $G$ が生成する言語を $L(G)$ と表します。

$x, y, w$ は終端記号の列を表すメタ変数とします。

文法 $G$ が既約であるとは、任意の非終端記号 $A_{i}$ について導出の過程で $A_{i}$ を使って言語の要素を導出できることとします。（つまり、開始記号からある非終端記号に到達できなかったり、ある非終端記号から無限ループやデッドエンドに陥って語を生成できないといったことがないということです。）

証明

補題0

任意の曖昧でない文脈自由文法 $G = ( V_{N}, V_{T}, R, A_{n} )$ について、 $L(G') = L(G)$ となる既約な曖昧でない文脈自由文法 $G'$ が存在する。

補題0の証明

到達できない記号や無限ループやデッドエンドに陥る非終端記号を取り除くだけでよいです。

具体的には

$V_{N}^{*} = \{ A_i \mid ( \exists x,y\, s.t.\, A_{n} \rightarrow^{*} x A_i y ) \land ( \exists w\, s.t.\, A_i \rightarrow^{*} w ) \}$ とすると、 $G' = ( V_{N}^{*}, V_{T}, R, A_{n} )$ とすればよいです。

補題1

任意の既約な曖昧でない文脈自由文法 $G = ( V_{N}, V_{T}, R, A_{n} )$ について、 $A_i \rightarrow^{+} A_i$ となることはない。

補題1の証明

$A_i \rightarrow^{+} A_i$ となる非終端記号があると、 $A_{n} \rightarrow^{*} x A_i y \rightarrow^{*} w$ と $A_{n} \rightarrow^{*} x A_i y \rightarrow^{+} x A_i y \rightarrow^{*} w$ と木の形が違う二通りの導出ができてしまうので、曖昧な文法になります。

定義 ( $P(G)$ )

文法 $G$ について $P(G) = \{ A_i \mid \exists x,y\, s.t.\, A_i \rightarrow^{*} x A_i y \land xy \neq \varepsilon \}$

ここで、補題1 より $G$ が既約で曖昧でないとき、 $xy = \varepsilon$ となることはないので、 $A_{i} \not \in P(G)$ のとき $A_{i}$ から $A_{i}$ を含む列を生成することはありません。

定義 (almost looping)

文法 $G = ( V_{N}, V_{T}, R, A_{n} )$ が almost looping であるとは、

$G$ は既約
$A_{1},... ,A_{n-1} \in P(G)$
任意の $w \in L(G)$ の導出において $A_{n}$ は一度しか出現しない

3 の条件が元の論文と少し違うので注意してください。

補題2

任意の既約な曖昧でない文脈自由文法 $G = ( V_{N}, V_{T}, R, A_{n} )$ について、 $L(G') = L(G)$ となる almost looping な曖昧でない文脈自由文法 $G'$ が存在する。

補題2の証明

まず、 3 が成り立っていないときは新しい開始記号 $X$ と規則 $X \rightarrow A_{n}$ を用意すれば、既約性と非曖昧性は変わらず 3 が成り立つので、最初から 3 は成り立っているものとします。

$G_{0} = G$ から非終端記号 $A_{1},... , A_{n-1}$ を 1 つずつ帰納的に処理して $G_{1},... , G_{n-1}$ と変形していきます。

処理の仕方は、ループしない非終端記号については単純に木を 1 段増やすだけなので、そのような非終端記号を文法から取り除いて、子を親に直接つなぐように生成規則を変化させるというやり方です。

具体的には以下のようになります。

(1) $A_{i} \in P(G_{i-1})$ のとき

このときは何も変化させません。

$G_{i} = G_{i-1}$ とします。

(2) $A_{i} \not \in P(G_{i-1})$ のとき

$G_{i-1} = ( V_{N,i-1}, V_{T}, R_{i-1}, A_{n} )$ とします。

$R_{i-1}$ のうち、左辺が $A_{i}$ であるものの集合を $S_{i}$ とします。

$P(G_{i-1})$ の定義と $G_{i-1}$ の非曖昧性（と補題1）より $S_{i}$ の右辺に $A_{i}$ はないはずです。

$A_{i}$ が右辺にある $G_{i-1}$ の生成規則について、 $A_{i}$ の出現をそれぞれ $S_{i}$ の右辺で置き換えたものを　 $R_{i}$ とします。

$A_{i}$ が右辺に $x$ 回出現する規則の場合は、 $|S_{i}|^x$ 個の規則に置き換わります。

そして、 $G_{i} = ( V_{N,i-1} - \{ A_{i} \}, V_{T}, R_{i}, A_{n} )$ とします。

既約性と非曖昧性は (1) の場合は文法が変化していないので成立し、 (2) の場合も、木の $A_i$ が出てくるノードについて子を親に直接つなぐようにしただけなので成立します。

また、 $j \le i$ なる非終端記号 $A_{j} \in V_{N,i}$ について $A_{j} \in P(G_{i})$ です。

これは、(i) は場合分けの定義からそのままで、(ii) も $A_i$ が無くなったので帰納法の仮定からそのまま成り立ちます。

また、生成する言語も変化しません。

以上より $G' = G_{n-1}$ とすれば目標達成です。

補題3

$L(G) = L (= \{ a^{i} b^{j} c^{k} \mid i, j, k \ge 1, i = j \lor j = k \})$ となる almost looping な文脈自由文法 $G = ( V_{N}, V_{T}, R, A_{n} )$ の開始記号でない非終端記号 $A_{i}$ は以下の 3 タイプのうちちょうど 1 つにあてはまる

$n_i, m_i \ge 0, n_i + m_i \ge 1$ が存在して $A_{i} \rightarrow^{+} a^{n_i} A_{i} a^{m_i}$ または $A_{i} \rightarrow^{+} c^{n_i} A_{i} c^{m_i}$
$n_i \ge 1$ が存在して $A_{i} \rightarrow^{+} a^{n_i} A_{i} b^{n_i}$
$n_i \ge 1$ が存在して $A_{i} \rightarrow^{+} b^{n_i} A_{i} c^{n_i}$

補題3の証明

まず各非終端記号がどのタイプかに属することを示します。

almost looping の定義から、 $A_{i} \rightarrow^{*} x A_{i} y \rightarrow^{*} w \land xy \neq \varepsilon$ となります。

ここで、 $x$ または $y$ に二種類以上の非終端記号を含むとすると、 $A_{i} \rightarrow^{*} x A_{i} y \rightarrow^{*} xx A_{i} yy$ となり、 $L$ が $a, b, c$ の順に並ばなければいけないことに反します。

よって、 $x$ と $y$ に含まれる非終端記号は高々 1 種類となり、ありえる組み合わせは次の 16 通りです

x	y	タイプ
空	空	ありえない(i)
a	空	1
b	空	ありえない(iii)
c	空	1
空	a	1
a	a	1
b	a	ありえない(ii)
c	a	ありえない(ii)
空	b	ありえない(iii)
a	b	2(v)
b	b	ありえない(iii)
c	b	ありえない(ii)
空	c	1
a	c	ありえない(iv)
b	c	3(v)
c	c	1

(i) について: $xy \neq \varepsilon$ です。

(ii) について: $L$ が $a, b, c$ の順に並ばなければいけないことに反します。

(iii) について:

$x = b^{s}, y = b^{t}$ とします。

$A_{n} \rightarrow^{*} u A_{i} v \rightarrow^{*} a^{i} b^{j} c^{k} \in L$ とします。

この真ん中の段階において、 $A_{i} \rightarrow^{*} x A_{i} y$ を $i+k+1$ 回繰り返すと、 $A_{n} \rightarrow^{*} a^{i} b^{j+(s+t)(i+k+1)} c^{k} \not \in L$ となり矛盾します。

(iv) について:

$x = a^{s}, y = c^{t}$ とします。 $A_{n} \rightarrow^{*} u A_{i} v \rightarrow^{*} a^{i} b^{j} c^{k} \in L$ とします。

この真ん中の段階において、 $A_{i} \rightarrow^{*} x A_{i} y$ を $j+1$ 回繰り返すと、 $A_{n} \rightarrow^{*} a^{i+s(j+1)} b^{j} c^{k+t(j+1)} \not \in L$ となり矛盾します。

(v) について:

$x = a^{s}, y = b^{t}, s \neq t$ とします。

$A_{n} \rightarrow^{*} u A_{i} v \rightarrow^{*} a^{i} b^{j} c^{k} \in L$ とします。この真ん中の段階において、 $A_{i} \rightarrow^{*} x A_{i} y$ を $i+j+k+1$ 回繰り返すと、 $A_{n} \rightarrow^{*} a^{i+s(i+j+k+1)} b^{j+t(i+j+k+1)} c^{k} \not \in L$ となり矛盾します。

よって $s = t = n_{i}$ です。

$x = b^{s}, y = c^{t}$ のときも同様です。

次に、どれか一つのタイプにしか属せないことを示します。

仮に、タイプ 1 とタイプ 2 に属していたとすると、

$A_{i} \rightarrow^{*} a^{s} A_{i} b^{s} \rightarrow^{*} a^{s} a^{t} A_{i} a^{u} b^{s} ( s \ge 1, t+u \ge 1 )$ となります。

$y$ は一種類の終端記号しか生成してはいけないので、 $u = 0$ または $s = 0$ です。

$s = 0$ のとき $s \ge 1$ に反します。

$u = 0$ のとき (v) の議論から $t = 0$ となり $t+u \ge 1$ に反します。

これは矛盾です。

タイプ 1 とタイプ 3 についても同様です。

仮に、タイプ 2 とタイプ 3 に属していたとすると、

$A_{i} \rightarrow^{*} a^{s} A_{i} b^{s} \rightarrow^{*} a^{s} b^{t} A_{i} c^{t} b^{s} ( s, t \ge 1 )$ となります。

$L$ が $a, b, c$ の順に並ばなければいけないことに反します。

以上より示せました。

補題4

$L(G) = L$ となる almost looping な文脈自由文法 $G = ( V_{N}, V_{T}, R, A_{n} )$ について、 $w \in L$ が $A_{n}$ と補題3のタイプ1の非終端記号からのみ生成できるとき、 $w$ に含まれる $b$ の個数は $l_{G}$ 個以下となる（ $l_{G}$ は文法 $G$ により定まる定数）