二項係数
[Wikipedia|▼Menu]
個々の二項係数をより効果的に計算するには ( n k ) = n k _ k ! = n ( n − 1 ) ( n − 2 ) ⋯ ( n − ( k − 1 ) ) k ( k − 1 ) ( k − 2 ) ⋯ 1 = ∏ i = 1 k n − ( k − i ) i = ∏ i = 1 k n + 1 − i i {\displaystyle {\binom {n}{k}}={\frac {n^{\underline {k}}}{k!}}={\frac {n(n-1)(n-2)\cdots (n-(k-1))}{k(k-1)(k-2)\cdots 1}}=\textstyle \prod \limits _{i=1}^{k}{\dfrac {n-(k-i)}{i}}=\prod \limits _{i=1}^{k}{\dfrac {n+1-i}{i}}}

で与えられる式を用いる。一つ目の分数の分子に現れる nk は下降階乗冪である。この公式を理解するには二項係数の組合せ論的解釈に依るのが最も簡明である。分子は n 個の対象からなる集合から選ぶ順番を考慮して相異なる k 個の対象を取り出す方法の総数であり、分母は同じ k-組合せを与える相異なる並びの数を数えるものである。
階乗表示

最後に、計算論的には不利だが、短く書けるのでしばしば証明や導出に用いられるよく知られた階乗函数を用いた式は ( n k ) = n ! k ! ( n − k ) ! {\displaystyle {\binom {n}{k}}={\frac {n!}{k!\,(n-k)!}}}

で与えられる。ここに n! は n の階乗である。この式は上記の乗法表示式に、分子分母に対して (n − k)! を掛けることで得られる(その結果、この式において分母と分子は多くの共通因数を持つことになる)。(特に階乗は非常に速く増加するから)この式を(k が小さく n が大きい場合に)実際の数値計算に用いることは(先に共通因数を約分しない限り)実用的でない。この式は上記の乗法表示よりは二項係数が対称性 ( n k ) = ( n n − k ) {\displaystyle {\binom {n}{k}}={\binom {n}{n-k}}} (1)

を持つことを見るのに適している(二項係数の定義から対称性をもつことは分かる)。この対称性を用いれば乗法的な計算をより効果的にすることもできる。下降階乗冪で書けば ( n k ) = { n k _ / k ! if    k ≤ n 2 n n − k _ / ( n − k ) ! if    k > n 2 {\displaystyle {\binom {n}{k}}={\begin{cases}n^{\underline {k}}/k!&{\text{if }}\ k\leq {\frac {n}{2}}\\n^{\underline {n-k}}/(n-k)!&{\text{if }}\ k>{\frac {n}{2}}\end{cases}}}

と書ける。
一般化および二項級数

乗法表示を用いれば、n を任意の数 α(負の整数、実数、複素数、……)あるいは任意の整数が可逆となるような可換環の元に取り換えて、 ( α k ) = α k _ k ! = α ( α − 1 ) ( α − 2 ) ⋯ ( α − k + 1 ) k ( k − 1 ) ( k − 2 ) ⋯ 1 {\displaystyle {\binom {\alpha }{k}}={\frac {\alpha ^{\underline {k}}}{k!}}={\frac {\alpha (\alpha -1)(\alpha -2)\cdots (\alpha -k+1)}{k(k-1)(k-2)\cdots 1}}}

により二項係数の定義を拡張することができる[注 1]。この定義により、二項定理(の一方の変数を 1 としたもの)も一般化して ( 1 + X ) α = ∑ k = 0 ∞ ( α k ) X k {\displaystyle (1+X)^{\alpha }=\textstyle \sum \limits _{k=0}^{\infty }{\dbinom {\alpha }{k}}X^{k}} (2)

と書くことができる。故にこの場合も (α
k) を二項係数と呼ぶことは正当化される。この等式は任意の複素数 α と |X| < 1 なる X に対して有効である。これはまた X を不定元とする
形式冪級数の等式としても解釈でき、それは実際に定数係数 1 を持つ級数の任意の冪の定義として機能する。この定義を用いるポイントは、冪乗として満足することが期待される全ての恒等式(指数法則)、特に

( 1 + X ) α ( 1 + X ) β = ( 1 + X ) α + β , {\displaystyle (1+X)^{\alpha }(1+X)^{\beta }=(1+X)^{\alpha +\beta },}

( ( 1 + X ) α ) β = ( 1 + X ) α β {\displaystyle ((1+X)^{\alpha })^{\beta }=(1+X)^{\alpha \beta }}

が満足されることである。α が非負整数 n のとき、k > n なる全ての項は零であり、上記の無限級数は有限和となり、したがってもともとの二項定理が再び得られる。しかし α がそれ以外の値ならば、負の整数や有理数の場合も含めて、上記の級数は実際に無限和になる。
パスカルの三角形パスカルの三角形の第1000 行に並ぶ二項係数を縦に並べたもの。各二項係数を十進表示し、その各桁の数字を0-9に応じたグレイスケールの点で表してある。画像の左の境界は二項係数の対数グラフにほぼ対応しており、これらが対数凹列(英語版)であることが見て取れる。詳細は「パスカルの三角形」を参照

パスカルの法則(英語版)は重要な漸化式 ( n k ) + ( n k + 1 ) = ( n + 1 k + 1 ) , {\displaystyle {\binom {n}{k}}+{\binom {n}{k+1}}={\binom {n+1}{k+1}},} (3)

で、これを用いて (n
k) が任意の自然数 n, k に対して自然数となること(別な言い方をすれば、連続する k-個の整数の積を k! が割り切ること)を
帰納的に示すことができる。これは定義 (?) や乗法表示からは直ちに明らかなことではない。

パスカルの法則からパスカルの三角形が生じる:

0:1
1:11
2:121
3:1331
4:14641
5:15101051
6:1615201561
7:172135352171
8:18285670562881

番号 n の行には (n
k) の値が k = 0, …, n に対して並べられている。これを書くには、一番外側の 1 から始めて、常に隣り合う2項を加えた数をその真下に書いていけばよい。この方法によって、分数や乗算を使わずに二項係数を手早く計算することができる。

例えば三角形の5行目を見れば(x + y)5 = 1 x5 + 5 x4y + 10 x3y2 + 10 x2y3 + 5 x y4 + 1 y5

が直ちに読み取れる。

他の対角線上の数との差は、上記漸化式 (3) の帰結として、一つ前の対角線上の数である。
解釈

二項係数はよくある数え上げ問題の簡明な公式を与えるという意味で組合せ論において重要である。

n-元集合から k-元を選ぶ方法の総数は (n
k) である(組合せを参照)。

n-元集合から重複を許して k元を選ぶ方法の総数は(n + k − 1
k) 通りある(多重集合を参照)。

k 個の 1 と n 個の 0 を含む文字列は (n + k
k) 種類存在する。

k 個の 1 と n 個の 0 を含み、かつどの2つの 1 も隣り合わない文字列の総数は (n + 1
k) である[5]


次ページ
記事の検索
おまかせリスト
▼オプションを表示
ブックマーク登録
mixiチェック!
Twitterに投稿
オプション/リンク一覧
話題のニュース
列車運行情報
暇つぶしWikipedia

Size:157 KB
出典: フリー百科事典『ウィキペディア(Wikipedia)
担当:undef