組合せ (数学)

数学において、組合せ（くみあわせ、combination）とは、いくつかの要素の集まりからいくつかの要素を選び出す方法、あるいは選び出した要素をその“並べる順番の違いを区別せずに”並べたもののことである。

組合せは組合せ論と呼ばれる数学の分野で研究される。

組合せの総数

重複を持たない組合せ

単純な場合で、異なる n 個のものから異なる m 個のものを選ぶ（このとき必然的に n ≥ m なる非負整数(自然数)でなければいけないが, このほかには何の制限も課されない）組合せというのを考えると、その選び方の総数はよく知られており、Combination の頭文字を取って、しばしば _nC_m または C(n, m) のような記号を使って表される。これは具体的には

<math>{}_n{\rm C}_{m} = {n\times (n-1)\times\cdots\times(n-m+1) \over m\times(m-1)\times\cdots\times 1}</math>

という数値になる。n, m が n ≥ m を満たす0以上の整数であるとき、この右辺の分数が実際に整数になることは、分母および分子の素因数に着目することで算術的にも証明できるが、組合せの数え上げという意味付けによって割り切れることが示されるところに、組合せ論的な意味があると考えられる。

_nC_m は 「ナンバー・オブ・コンビネーションズ・フロム n チューズ m」 またはそのまま 「エヌ シー エム」 などと読むことが多いようである。あるいは、二項展開の係数の意味で二項係数とも呼び、しばしば

<math>{n \choose m} = {n! \over m!(n-m)!} = {n^{\underline{m}} \over m^{\underline{m}}}</math>

と表す。ここで ! は階乗、右辺の記号は下降階乗冪を表す。

二項定理は _nC_m を数列と見なしたときの母関数が二項式の冪になるということを述べており、冪の拡張とともに二項冪の展開

<math>(1+x)^n=\sum_{m=0}^{\infty}{n \choose m}x^m</math>

の係数という意味付けのもと、n や m が非負整数以外の場合にも拡張して用いられる。この展開は n が非負整数ならば m は n まで増えたところでそれ以降の係数が 0 になって止まるが、一般の二項展開では止まらずに m は無限大までとる。

重複組合せ

n 種のものから、重複 (repetition) を許して r 個のものを取り出す（という以外に制限を持たない）組合せというものを考えて、n から r とる重複組合せ（ちょうふくくみあわせ、じゅうふくくみあわせ、repeated combination）と呼び、その総数を _nH_r と表す。これは

<math>{}_n{\rm H}_r = {}_{n+r-1}{\rm C}_{r} = {{n+r-1} \choose {r}} = \frac{(n+r-1)!}{r!(n-1)!}</math>

によって計算することができる。記号 H は斉次積 (Homogeneous product) の頭文字から来たものである。これは重複組合せを斉次積、つまり斉次多項式 (homogeneous polynomial) の冪乗積 (product)

<math>(x_1+x_2+\cdots+x_n)^r</math>

の係数を無視した項として取り出すことができることに由来している。したがって、重複組合せの総数 _nH_r は斉次積の展開によって得られる項の総数に等しい。また、

<math>\left\langle\begin{matrix}n\\r\end{matrix}\right\rangle = {}_n{\rm H}_r = (-1)^r{-n \choose r}</math>

は多重集合係数あるいは負の二項係数とも呼ばれ、

<math>(1-x)^{-n} = \sum_{r=0}^{\infty}\left\langle\begin{matrix}n\\r\end{matrix}\right\rangle x^r</math>

という対応がある。

例

{1, 2, 3, 4, 5} から重複を許さず3つを選び取る組合せは、{(1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 3, 4), (1, 3, 5), (1, 4, 5), (2, 3, 4), (2, 3, 5), (2, 4, 5), (3, 4, 5)} の ₅C₃ = 10 通りである。一方、{1, 2, 3, 4, 5} から重複を許して3つを選ぶ組み合わせは

{(1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 1, 4), (1, 1, 5),

(1, 2, 2), (1, 2, 3), (1, 2, 4), (1, 2, 5),

(1, 3, 3), (1, 3, 4), (1, 3, 5),

(1, 4, 4), (1, 4, 5),

(1, 5, 5),

(2, 2, 2), (2, 2, 3), (2, 2, 4), (2, 2, 5),

(2, 3, 3), (2, 3, 4), (2, 3, 5),

(2, 4, 4), (2, 4, 5),

(2, 5, 5),

(3, 3, 3), (3, 3, 4), (3, 3, 5),

(3, 4, 4), (3, 4, 5),

(3, 5, 5),

(4, 4, 4), (4, 4, 5),

(4, 5, 5),

(5, 5, 5)}

の ₅H₃ = 35 通りである。この中には重複を許さない場合の 10 通りが含まれているのが確認できる。

性質

多くの公式があるが、いくつか挙げると、

m _nC_m = n _n-1C_m-1

_nC_m = _n-1C_m + _n-1C_m-1

_mC_m + _m+1C_m + … + _nC_m = _n+1C_m+1

(_nC₀)² +(_nC₁)² + … + (_nC_n)² = _2nC_n

などがある。更に、_nC_mの偶奇について面白いことが言える。

n = 2^p(1) + 2^p(2) + …、m = 2^q(1) + 2^q(2) + …

というように、n と m を二進展開したとき、 {p(1), p(2), ...} ⊃ {q(1), q(2), ...} であることが、_nC_m が奇数であることの必要十分条件になっている。

関連項目

• 順列
• 二項定理