組合せ (数学)

数学において、組合せ（くみあわせ、）とは、相異なる（あるいは区別可能な）いくつかの要素の集まりからいくつかの要素を（重複無く）選び出す方法である。あるいは選び出した要素をその“並べる順番の違いを区別せずに”並べたもののことである。組合せは組合せ論と呼ばれる数学の分野で研究される。身近な例でいえば、デッキ（山札）から決まった数のカード（手札）を引くことや、ロトくじなどがその例である。
一般的に組合せとは要素が２以上の物を示すが、数学の用語では要素が０個の物や１個の物も組合せと呼ばれる。
定義.
位数 の有限集合 と非負整数 に対し、集合 に関する組合せとはこの集合の（有限）部分集合のことを言い、特に に関する -組合せ（あるいはもっと具体的に、与えられた 個の元から 個選んで得られる組合せ）とは の -元部分集合を言う。
 の -組合せ全体の成す集合を と表すとき、 の位数は有限であり、初等組合せ論においては の頭文字を取って、 または のような記号で表す。が1634年の『実用算術』での記号を定義した。ただし、この数は数学のあらゆる分野に頻繁に現れ、大抵の場合 formula_1 と書かれる。特に二項定理
に係数として現れることは顕著であり、これにより formula_1 はふつう二項係数と呼ばれる。二項展開の係数として数 formula_1 を定義するものと考えれば または のとき formula_5, のとき formula_6 と考えるのは自然である。
実用上は個々の係数が具体的に
で与えられることを利用するのが簡便である。この式の分子は -順列（-個のものを“並べる順番の違いを区別して”並べたもの）を作る総数を表し、分母はそれら -個の並べ替えの総数が であることを表し、並びだけが異なるそれらは同じ組合せを与えるものであるから、割っているのはそれらの違いを無視することに対応している。
組合せの数え上げ.
 は -元集合で、 は に属さない元、 は非負整数とする。このとき、の 個の元からなる部分集合は、 の 個の元からなる部分集合か、さもなくば単元集合 に の -元部分集合を併せたものであるから、
と書ける。ただし、 のとき である。（この等式の位数は、パスカルの三角形を構成するのに用いる漸化式 formula_9 に対応する）。
組合せの数の計算.
-元に対する -組合せの総数を効率的に計算するために以下の等式が利用できる。 として:
最初の式は なる場合に帰着するのに利用できるし、後の二つは
となることを示せる。