組合せ (数学)

出典: フリー百科事典『ウィキペディア（Wikipedia）』

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

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

[編集] 組合せの数

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

[編集] 発展

[編集] 重複組合せ

n種のものから、重複を許してr個のものを取り出す組み合わせの数を $n H r$ (Homogeneous) と書き、以下の計算で表される。

$_nH_r = _{n+r-1}C_{r} = \frac{(n+r-1)!}{r!(n-1)!}$

これは、

${{n+r-1} \choose {r}}$

と書くことも出来る。

{1,2,3,4,5}から3つを選び取る組み合わせは、

${_5C_3} = {\frac{5!}{3!2!}} = 10$

と計算でき、列挙してみれば、

{123,124,125,134,135,145,234,235,245,345} (※) が、その10個とわかる。

{1,2,3,4,5}から重複を許して3つを選ぶ組み合わせは

${_5H_3} = {\frac{7!}{3!4!}} = 35$

と計算でき、上記(※)のほかに以下の25個となる。

{111,112,113,114,115,122,133,144,155,222,223,224,225,233,244,255,333,334,335,344,355,444,445,455,555}

また、 $n C m$ では、n≧m≧0という制約があるが、 $n H r$ では、r≧0であれば良い。

[編集] 関連項目

[編集] 外部リンク

組合せ数を計算する高精度計算サイト・計算式ライブラリ

"http://ja.wikipedia.org../../../%E7%B5%84/%E5%90%88/%E3%81%9B/%E7%B5%84%E5%90%88%E3%81%9B_%28%E6%95%B0%E5%AD%A6%29.html" より作成

カテゴリ: 組合せ論 | 数学に関する記事