組合せ (数学)

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

一般的に組合せとは要素が２以上の物を示すが、数学の用語では要素が０個の物や１個の物も組合せと呼ばれる。

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

 の -組合せ全体の成す集合を  と表すとき、 の位数は有限であり、初等組合せ論においては  の頭文字を取って、 または  のような記号で表す。が1634年の『実用算術』での記号を定義した。ただし、この数は数学のあらゆる分野に頻繁に現れ、大抵の場合  と書かれる。特に二項定理
 
に係数として現れることは顕著であり、これにより  はふつう二項係数と呼ばれる。二項展開の係数として数  を定義するものと考えれば  または  のとき ,  のとき  と考えるのは自然である。

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

組合せの数え上げ 
 は -元集合で、 は  に属さない元、 は非負整数とする。このとき、の  個の元からなる部分集合は、 の  個の元からなる部分集合か、さもなくば単元集合 に  の -元部分集合を併せたものであるから、
 
と書ける。ただし、 のとき  である。（この等式の位数は、パスカルの三角形を構成するのに用いる漸化式  に対応する）。

組合せの数の計算 
-元に対する -組合せの総数を効率的に計算するために以下の等式が利用できる。 として:
 
最初の式は  なる場合に帰着するのに利用できるし、後の二つは
 
となることを示せる。

注釈

参考文献

関連項目 
 重複組合せ
 順列
 重複順列
 置換 (数学)
 重複置換
 写像12相
 組合せ数学（組合せ論）

外部リンク 
 
 
 

数学に関する記事