組合せ (数学)

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

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

単純な場合で、異なる n 個のものから異なる m 個のものを選ぶ組合せというのを考えると、その選び方の総数はよく知られており、しばしば _nC_m または C(n, m) のような記号を使って表される。これは具体的には

{}_n{\rm C}_{m} = {n(n-1)\cdots(n-m+1) \over m(m-1)\cdots 1} = {n! \over m!(n-m)!}

という数値になる。これが実際に整数になることは、分母分子の素因数に着目することで証明できる。

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

n \choose m

と表す。

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

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 が奇数であることの必要十分条件になっている。

Gourt Home::Gourt :: 組合せ (数学)