読者です 読者をやめる 読者になる 読者になる

あざらしとペンギンの問題

主に漫画、数値計算、幾何計算、TCS、一鰭旅、水族館、鰭脚類のことを書きます。

二項係数がゲシュタルト崩壊する〜

遅ればせながら赤座あかりちゃん誕生日おめでとう。

定義が面倒な計算量の話を先延ばしにして小ネタで穴埋めしようとしたら、そこで使う予定だった二項係数が出なかったので焦りました。幸い別の方法で出せたので良かったです。今回は小ネタの準備ということで、二項係数についてちょっと説明します。出せなかった記号とはこういう奴です。

\left( \begin{matrix} n \\ m \end{matrix} \right)

何とか出せたものの、綺麗とは言い難いです。本物のTeXの場合はAMSパッケージを読み込んで \binom{n}{m} とすればもっと綺麗に出ます。なお、タイトルに深い意味はありません。*1

二項係数と二項定理

今回の話の主役である「二項係数」とは、おそらくは中学校で習うところの「組み合わせの数」と呼ばれるものと同じものです。というわけで簡単におさらいをしつつ二項係数を定義しましょう。

まずは、最も基本的な順列の総数から入りましょう。1,2,\dots,n の数字が書かれたカードが1枚ずつあるとします。その中から m 枚のカードを抜き出して一列に並べる方法(順列)は

_n \mathrm{P}_m = n (n - 1) (n - 2) \dots (n - m + 1)

通りあります。すなわち、1番目のカードが n 通り、2番目のカードが残りの n-1 通りの中から選ばれ、と繰り返していって、m 番目のカードを選ぶ時点では残りが n - m + 1 枚あるので、それは n-m+1 通りの中から選ばれ、あとはそれぞれの方法の数の積をとれば、カードを一列に並べる方法すべての数が得られます。上の式は、階乗を用いて

_n \mathrm{P}_m = \frac{n!}{(n - m)!}

と表すこともできます。ただし、0! = 1 かつ 0 \geq m \geq nとします。意味を考えれば m < 0, n < m のとき _n \mathrm{P}_m = 0 とすべきなのでそうします。また、総積の記号を使えば

_n \mathrm{P}_m = \prod_{k=1}^m (n-k+1)

と表すこともできます。

特別な場合として、n 個のカード全てを取り尽くすときの順列の数

_n \mathrm{P}_n = n!

n 個のカードの並べ方の総数を意味します。

もう一つ重要な数え上げとして、n 個のカードから m 個のカードを抜き出すときに、順番を区別しないで数字の組み合わせだけを数えるという問題がありました。そのときの場合の数は

\left( \begin{matrix} n \\ m \end{matrix} \right) = \frac{_n \mathrm{P}_m}{m!} = \prod_{k = 1}^m \frac{n-k+1}{k}

通りあります。すなわち、

(順列の総数 = _n \mathrm{P}_m) =(組み合わせの総数)×(選ばれたカードの並べ方の総数  = m!

から

(組み合わせの総数)= \frac{_n \mathrm{P}_m}{m!}

というわけですね。ところで、記号 \left( \begin{matrix} n \\ m \end{matrix} \right) を初めて見たという方は、これで n 個のものの中から m 個のものを選ぶ組み合わせの数を表すと覚えてください。あるいは _n \mathrm{C}_m という記号を知っている方は、それと同じものであると覚えてください。

「二項係数」とは、この組み合わせの数 \left( \begin{matrix} n \\ m \end{matrix} \right) と全く同一のものです。これがわざわざ二項係数などと呼ばれる理由を次に説明します。

二項式 x + y のべき乗 (x + y)^n を展開するとき、その係数は実は組み合わせの数になります。この事実は「二項定理」と呼ばれています。パスカルの三角形と合わせて習った方も多いのではないでしょうか。(おそらくは高校の範囲。)これを式で書くと、

(x + y)^n = \sum_{k = 0}^n \left( \begin{matrix} n \\ k \end{matrix} \right) x^k y^{n-k}

となります。係数が組み合わせの数になる理由は単純です。まず、(x + y)^n は二項式 (x + y)n 個書けたものです。説明のため、(x + y) のそれぞれに k = 1, 2, \dots, n と番号を振りって (x+y)_k と表すことにします。あとは、それらを全部を掛け合わせて展開したときの x^k y^{n - k} を含む項を数えるのですが、それはこの項がどのようにして作られるかを考えれば見えてきます。例えば、x^k y^{n - k} という項は、(x+y)_1, \dots, (x+y)_n のそれぞれから1つずつ x または y を取って掛け合わせることによってできますよね。xk 個取れば、y は残り n - k 個の二項式から取られることが確定するので、x だけに注目すればよいです。すると、展開式における一つの x^k y^{n - k} は、x の出処の二項式 k 個の番号の組に対応することが分かります。よって、x^k y^{n-k}n 個の二項式から k 個の組を選ぶ組み合わせの数 \left( \begin{matrix} n \\ k \end{matrix} \right) だけ出現することが分かります。例えば、(x+y)^3 = (x+y)_1(x+y)_2(x+y)_3 の展開式において、x^2 yx を1と2、1と3、2と3の組から取ってきた場合の\left( \begin{matrix} 3 \\ 2 \end{matrix} \right) = 3 つ出現します。後はそれらを加えてやれば、上に示した式が出ます。これより、組み合わせの数は二項式のべき乗の展開式の係数に等しい、故に、二項係数と呼ばれているというわけですね。

一般化二項定理

それでは一般化二項定理について紹介しましょう。何を一般化するかというと、べき乗を整数から任意の実数にするのです。まず、上の式において y := 1 として、

(1 + x)^n = \sum_{k = 0}^{\infty} \left( \begin{matrix} n \\ k \end{matrix} \right) x^k

とします。これは n が非負整数ならば正しい式です。なぜなら、k > n ならば \left( \begin{matrix} n \\ k \end{matrix} \right) = 0 だからです。二項係数の式

\left( \begin{matrix} n \\ m \end{matrix} \right) = \prod_{k = 1}^m \frac{n-k+1}{k}

を思い出すと、これは n が非負整数でなくとも定義できることが分かります。そこで、任意の実数 a に対して、「一般化二項係数」を

\left( \begin{matrix} a \\ m \end{matrix} \right) := \prod_{k = 1}^m \frac{a-k+1}{k}

で定義します。このとき、次の定理が成り立ちます。

定理1(一般化二項定理):任意の実数 a に関して、|x| < 1 ならば

(1 + x)^a = \sum_{k = 0}^{\infty} \left( \begin{matrix} a \\ k \end{matrix} \right) x^k

が成り立つ。

別の言い方をすれば、上は (1+x)^ax = 0 の周りにおけるテイラー展開になっています。テイラー展開の公式を思い出すと、x^k の係数は f(x ; a) = (1+x)^a として f^{(k)}(0 ; a) / k! となります。これを計算すると

f^{(k)}(0 ; a) = a (1+x)^{a-1} = a f^{(k-1)}(0 ; a - 1) = \dots
= f^{(0)}(0;0) \prod_{i=1}^k (a - i + 1) = \prod_{i=1}^k (a - i + 1)

となるので、

\frac{f^{(k)}(0 ; a)}{k!} = \prod_{i=1}^k \frac{a - i + 1}{k} = \left( \begin{matrix} a \\ k \end{matrix} \right)

が得られます。

級数の収束についての議論は微分積分学の教科書の多くに載っているので、ここでは敢えて説明しません。

次回はこれを利用して数を数えようという話をやる予定なのですが、その前にちょっとだけ応用について触れておきます。

関数のある点におけるテイラー展開を適当な次数で打ち切ると、その付近での関数の近似値が得られますよね。一般化二項展開はテイラー展開の一種なので、その目的で用いられることはよくあります。

例えば、\sqrt{100} = 10 を少しずらした \sqrt{104} の近似値を求めたいとします。*2ここで、先の一般化二項展開において、a=1/2 とした \sqrt{1+x} について考えます。これを1次までで打ち切ると、

\left( \begin{matrix} 1/2 \\ 1 \end{matrix} \right) = \frac{1}{2}

より、x=0 の周りで

\sqrt{1+x} = 1 + \frac{x}{2} + O(x^2)

となります。グラフで考えると、曲線 y = \sqrt{1+x} (x \geq -1)x = 0 で直線 y = 1+(1/2)x に接することが分かります。また、位置関係より \sqrt{1+x} \leq 1 + (1/2) x であることも分かります。

f:id:azapen6:20130812114512p:plain

これを利用して近似値を求めると、

\sqrt{100 + 4} = 10 \sqrt{1 + 0.04} \approx 10 * (1 + 0.02) = 10.2

となります。実際の値は \sqrt{104} = 10.198039 \dots なので、これだけ大雑把な近似でも悪くない値が出ることがお解り頂けるでしょう。もう少し欲張るならば、2次まででの打ち切りを考えると良さそうですね。まず、

\left( \begin{matrix} 1/2 \\ 2 \end{matrix} \right) = \frac{(1/2)(-1/2)}{2!} = -\frac{1}{8}

より、x=0 の周りで

\sqrt{1+x} = 1 + \frac{x}{2}  - \frac{x^2}{8} + O(x^3)

となります。よって、上と同様に近似値を求めると、

\sqrt{100 + 4} = 10 \sqrt{1 + 0.04} \approx 10 * (1 + 0.02 - 0.0002) = 10.198

となります。これは先よりもよい近似になっていることが分かります。といったところで具体的な計算は打ち切ります。

さらに、一般化二項定理の a は負の値でもよいので、次のようなものにも用いることもできます。

\frac{1}{1+x} = (1+x)^{-1} = \sum_{k = 1}^{\infty} \left( \begin{matrix} -1 \\ k \end{matrix} \right) x^k

ここで、

\left( \begin{matrix} -1 \\ k \end{matrix} \right) = \prod_{i=1}^k \frac{-i}{i} = (-1)^k

から

\frac{1}{1+x} = \sum_{k = 1}^{\infty} (-x)^k

が出ます。これはよく知られた式ですね。x-x で置き換えれば

\frac{1}{1-x} = (1-x)^{-1} = \sum_{k = 1}^{\infty} x^k

が得られます。同様にして

\frac{1}{(1-x)^2} = (1-x)^{-2} = \sum_{k = 1}^{\infty} \left( \begin{matrix} -2 \\ k \end{matrix} \right) (-x)^k

の係数を計算すると

\left( \begin{matrix} -2 \\ k \end{matrix} \right) = \prod_{i=1}^k \frac{-1-i}{i}
=\frac{(-2)*(-3)* \dots * (-k) * (-(k+1))}{2*3* \dots *k} = (-1)^k (k+1)

なので

\frac{1}{(1-x)^2} = \sum_{k = 0}^{\infty} (k+1) x^k

が出ます。これも高校の数学の問題などでお目にかかる式ですね。いずれにしても、これらは一般化二項定理の特殊な場合になっています。

とここまで一般化二項定理の計算例を見て来ましたが、実際は具体的な関数値を近似するためというよりは、理論計算において関数を扱い易い多項式に置き換えるためによく用いられます。これはテイラー展開一般に言えることです。*3

例えば、特殊相対性理論において、注目している慣性系で静止質量 m の物体が速さ v で運動しているとき、光の速さを c として物体が持つエネルギーは

E = \frac{mc^2}{\sqrt{1 - (v/c)^2}} = mc^2 \left( 1 - (v/c)^2\right)^{-1/2}

となりますが、これを展開して1次までで打ち切ると、

E \approx mc^2 + \frac{1}{2} mv^2 \quad (v \ll c)

が得られます。ここで、第1項は静止エネルギーであり、第2項はニュートン力学における運動エネルギーと同じ式です。つまり、ニュートン力学に現れない静止エネルギーを無視すれば、実質的には両者で同じ運動エネルギーの式を与えていると言えます。ただし、vc に比べて非常に小さい場合の話です。

ここまで

今回は先の話の準備として、二項係数と一般化二項定理について説明しました。上の例を見る限りいかにも解析の話のようでいて、実は一般化二項定理には離散的な数え上げにも応用があるのです。それを次回お話します。では。

*1:私がモテないのはどう考えてもお前らが悪い!

*2:もちろん電卓などを使えば簡単に計算できますが、これは例なのでそこに突っ込まないでください。

*3:関数値の近似については、テイラー展開の打ち切りよりもよい方法が様々開発されています。