組合せ (数学)

数学において、組合せ（くみあわせ、英: combination, choose）とは、相異なる（あるいは区別可能な）いくつかの要素の集まりからいくつかの要素を（重複無く）選び出す方法である^[1]。あるいは選び出した要素をその“並べる順番の違いを区別せずに”並べたもののことである^[2]。組合せは組合せ論と呼ばれる数学の分野で研究される。卑近な例でいえば、デッキ（山札）から決まった数のカード（手札）を引くとかロトくじなどがその例である。

定義

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

$E$ の $k$ -組合せ全体の成す集合を $𝒫 k (E)$ と表す^[3]^[4]とき、 $𝒫 k (E)$ の位数は有限であり、初等組合せ論においては Combination の頭文字を取って、 $n C k, C n k, n C k, C n,k$ または $C (n, k)$ のような記号で表す。ただし、この数は数学のあらゆる分野に頻繁に現れ、大抵の場合 $\textstyle {\binom {n}{k}}$ と書かれる。特に二項定理

(1+x)^{n}=\sum _{k=0}^{n}{n \choose k}x^{k}

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

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

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

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

組合せの数え上げ

$A$ は $n$ -元集合で、 $a$ は $A$ に属さない元、 $k$ は非負整数とする。このとき、 $A \cup {a}$ の $k + 1$ 個の元からなる部分集合は、 $A$ の $k + 1$ 個の元からなる部分集合か、さもなくば単元集合 ${a}$ に $A$ の $k$ -元部分集合を併せたものであるから、

{\mathcal {P}}_{k+1}(A\cup \{a\})={\mathcal {P}}_{k+1}(A)\cup \left\{X\cup \{a\}\mid X\in {\mathcal {P}}_{k}(A)\right\}

と書ける。ただし、 $k > n$ のとき $𝒫 k (A) = \emptyset$ である。（この等式の位数は、パスカルの三角形を構成するのに用いる漸化式 ${\tbinom {n+1}{k+1}}={\tbinom {n}{k+1}}+{\tbinom {n}{k}}$ に対応する）。

組合せの数の計算

$n$ -元に対する $k$ -組合せの総数を効率的に計算するために以下の等式が利用できる^[5]。 $0 \leq k \leq n$ として:

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

最初の式は $k \leq n /2$ なる場合に帰着するのに利用できるし、後の二つは

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

となることを示せる。

注釈

^ 岩波数学辞典, 184. 順列・組合せ p. 526.
^ 伏見 1942, p. 5, 第I章　数学的補助手段 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. 120.
^ この式は例えば任意の精度の算術ライブラリである GMP が用いている。 Binomial coefficients algorithm を参照。

参考文献

西岡康夫『数学チュートリアルやさしく語る確率統計』オーム社、2013年。ISBN 9784274214073。
伏見康治『確率論及統計論』河出書房、1942年。ISBN 9784874720127。
日本数学会編編『数学辞典』（第4版）岩波書店、2007年。ISBN 9784000803090。

外部リンク

Weisstein, Eric W. "Combination". mathworld.wolfram.com (英語).
Weisstein, Eric W. "Choose". mathworld.wolfram.com (英語).
Weisstein, Eric W. "k-Subset". mathworld.wolfram.com (英語).

[FOOTNOTE岩波数学辞典184._順列・組合せ_p._526-1] 岩波数学辞典, 184. 順列・組合せ p. 526.

[FOOTNOTE伏見19425第I章_数学的補助手段_1節_組合わせの理論-2] 伏見 1942, p. 5, 第I章　数学的補助手段 1節組合わせの理論.

[3] Louis Comtet, Analyse combinatoire élémentaire, p. 2.

[4] Hervé Gianella, Romain Krust, Frank Taieb et Nicolas Tosel, Problèmes choisis de mathématiques supérieures, p. 120.

[5] この式は例えば任意の精度の算術ライブラリである GMP が用いている。 Binomial coefficients algorithm を参照。

[1]

[2]

[3]

[4]

[5]

定義

組合せの数え上げ

組合せの数の計算

注釈

参考文献

関連項目

外部リンク