組合せ (数学)

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

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

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

 の -組合せ全体の成す集合を  と表すLouis Comtet, Analyse combinatoire élémentaire, .Hervé Gianella, Romain Krust, Frank Taieb et Nicolas Tosel, Problèmes choisis de mathématiques supérieures, .とき、 の位数は有限であり、初等組合せ論においては  の頭文字を取って、 または  のような記号で表す。が1634年の『実用算術』で  の記号を定義した。ただし、この数は数学のあらゆる分野に頻繁に現れ、大抵の場合  と書かれる。特に二項定理

に係数として現れることは顕著であり、これにより  はふつう二項係数と呼ばれる。二項展開の係数として数  を定義するものと考えれば  または  のとき ,  のとき  と考えるのは自然である。

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

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

 組合せの数え上げ 
 は -元集合で、 は  に属さない元、 は非負整数とする。このとき、の  個の元からなる部分集合は、 の  個の元からなる部分集合か、さもなくば単集合 に  の -元部分集合を併せたものであるから、

と書ける。ただし、 のとき  である。（この等式の位数は、パスカルの三角形を構成するのに用いる漸化式  に対応する）。

 組合せの数の計算 
-元に対する -組合せの総数を効率的に計算するために以下の等式が利用できるこの式は例えば任意の精度の算術ライブラリである GMP が用いている。 Binomial coefficients algorithm を参照。。 として:

最初の式は  なる場合に帰着するのに利用できるし、後の2つは

となることを示せる。

 注釈 

 参考文献 




 関連項目 
 組合せ数学
 重複組合せ
 順列
 重複順列
 完全順列
 場合の数
 数え上げ
 数え上げ数学
 置換 (数学)
 重複置換
 写像12相
 樹形図

 外部リンク 




*
Category:数学に関する記事