組合せ (数学)

テンプレート:Redirect テンプレート:Expand English 数学において、組合せ（くみあわせ、テンプレート:Lang-en-short）とは、有限個の互いに区別可能な要素の集まりから有限個を選び出す方法であるテンプレート:Sfn。あるいは選び出した要素をその“並べる順番の違いを区別せずに”並べたもののことであるテンプレート:Sfn。組合せは組合せ数学と呼ばれる数学の分野で研究される。身近な例でいえば、デッキ（山札）から決まった数のカード（手札）を引くことや、ロトくじなどがその例である。

日常では組合せとは要素が2個以上の物を示すが、数学においては要素が1個や0個の場合も組合せの内に含めて考える。

定義

位数テンプレート:Mvar の有限集合テンプレート:Mvar と非負整数テンプレート:Mvar に対し、集合テンプレート:Mvar に関する組合せとはこの集合の（有限）部分集合のことを言い、特にテンプレート:Mvar に関するテンプレート:Mvar-組合せ（あるいはもっと具体的に、与えられたテンプレート:Mvar 個の元からテンプレート:Mvar 個選んで得られる組合せ）とはテンプレート:Mvar のテンプレート:Mvar-元部分集合を言う。

テンプレート:Mvar のテンプレート:Mvar-組合せ全体の成す集合をテンプレート:Math と表す^[1]^[2]とき、テンプレート:Math の位数は有限であり、初等組合せ論においてはテンプレート:Lang の頭文字を取って、テンプレート:Mvar またはテンプレート:Math のような記号で表す。テンプレート:仮リンクが1634年の『実用算術』でテンプレート:Mvar の記号を定義した^[3]。ただし、この数は数学のあらゆる分野に頻繁に現れ、大抵の場合 $(\binom{n}{k})$ と書かれる。特に二項定理

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

に係数として現れることは顕著であり、これにより $(\binom{n}{k})$ はふつう二項係数と呼ばれる。二項展開の係数として数 $(\binom{n}{k})$ を定義するものと考えればテンプレート:Math2 またはテンプレート:Math2 のとき $(\binom{n}{k}) = 1$ , テンプレート:Math2 のとき $(\binom{n}{k}) = 0$ と考えるのは自然である。

実用上は個々の係数が具体的に

(\binom{n}{k}) = \frac{n \times (n - 1) \times \dots \times (n - k + 1)}{k \times (k - 1) \times \dots \times 1} (= \frac{P (n, k)}{k!})

で与えられることを利用するのが簡便である。この式の分子はテンプレート:Mvar-順列（テンプレート:Mvar個のものを“並べる順番の違いを区別して”並べたもの）を作る総数を表し、分母はそれらテンプレート:Mvar個の並べ替えの総数がテンプレート:Math であることを表し、並びだけが異なるそれらは同じ組合せを与えるものであるから、割っているのはそれらの違いを無視することに対応している。

組合せの数え上げ

𝒫_{k + 1} (A \cup {a}) = 𝒫_{k + 1} (A) \cup {X \cup {a} ∣ X \in 𝒫_{k} (A)}

と書ける。ただし、テンプレート:Math2 のときテンプレート:Math である。（この等式の位数は、パスカルの三角形を構成するのに用いる漸化式 $(\binom{n + 1}{k + 1}) = (\binom{n}{k + 1}) + (\binom{n}{k})$ に対応する）。

組合せの数の計算

テンプレート:Mvar-元に対するテンプレート:Mvar-組合せの総数を効率的に計算するために以下の等式が利用できる^[4]。テンプレート:Math2 として:

(\binom{n}{k}) = (\binom{n}{n - k}), (\binom{n + 1}{k + 1}) = \frac{n + 1}{k + 1} (\binom{n}{k}), (\binom{n}{0}) = 1 .

最初の式はテンプレート:Math2 なる場合に帰着するのに利用できるし、後の2つは

(\binom{n}{k}) = \frac{n - k + 1}{1} \cdot \frac{n - k + 2}{2} \cdot \dots \cdot \frac{n}{k}

となることを示せる。

注釈

テンプレート:Reflist

参考文献

外部リンク

↑ Louis Comtet, Analyse combinatoire élémentaire, テンプレート:P..
↑ Hervé Gianella, Romain Krust, Frank Taieb et Nicolas Tosel, Problèmes choisis de mathématiques supérieures, テンプレート:P..
↑ テンプレート:Cite
↑ この式は例えば任意の精度の算術ライブラリである GMP が用いている。テンプレート:En Binomial coefficients algorithm を参照。

[1] Louis Comtet, Analyse combinatoire élémentaire, テンプレート:P..

[2] Hervé Gianella, Romain Krust, Frank Taieb et Nicolas Tosel, Problèmes choisis de mathématiques supérieures, テンプレート:P..

[3] テンプレート:Cite

[4] この式は例えば任意の精度の算術ライブラリである GMP が用いている。テンプレート:En Binomial coefficients algorithm を参照。

[1]

[2]

[3]

[4]

組合せ (数学)

目次

定義

組合せの数え上げ

組合せの数の計算

注釈

参考文献

関連項目

外部リンク

ナビゲーションメニュー

組合せ (数学)

定義

組合せの数え上げ

組合せの数の計算

注釈

参考文献

関連項目

外部リンク

ナビゲーション メニュー

検索

ナビゲーションメニュー