組合せ (数学)

数学において、組合せ（くみあわせ、英: 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)$ のような記号で表す。ピエール・エリゴン（フランス語版）が1634年の『実用算術』で $n C k$ の記号を定義した^[5]。ただし、この数は数学のあらゆる分野に頻繁に現れ、大抵の場合 $\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$ -組合せの総数を効率的に計算するために以下の等式が利用できる^[6]。 $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.
^ 黒木哲徳『なっとくする数学記号』講談社〈ブルーバックス〉、2021年、96,97頁。ISBN 9784065225509。
^ この式は例えば任意の精度の算術ライブラリである 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] 黒木哲徳『なっとくする数学記号』講談社〈ブルーバックス〉、2021年、96,97頁。ISBN 9784065225509。

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

[1]

[2]

[3]

[4]

[5]

[6]