組合せ (数学)
出典: フリー百科事典『ウィキペディア（Wikipedia）』
数学において、組合せ（くみあわせ。組み合わせ、または組み合せとも表記される）とは、いくつかの要素の集まりからいくつかの要素を選び出す方法、あるいは選び出した要素をその並べる順番の違いを区別せずに 並べたもののことである。
目次 |
[編集] 組合せの数
単純な場合で、異なる n 個のものから異なる m 個のものを選ぶ組合せというのを考えると、その選び方の総数はよく知られており、しばしば nCm または C(n, m) のような記号を使って表される。これは具体的には
という数値になる。これが実際に整数になることは、分母分子の素因数に着目することで証明できる。
nCm は 「コンビネーション n チューズ m」 またはそのまま 「エヌ シー エム」 などと読むことが多いようである。あるいは、二項展開の係数の意味で二項係数とも呼び、しばしば
と表す。
[編集] 性質
多くの公式があるが、いくつか挙げると、
- m nCm = n n-1Cm-1
- nCm = n-1Cm + n-1Cm-1
- mCm + m+1Cm + … + nCm = n+1Cm+1
- (nC0)2 +(nC1)2 + … + (nCn)2 = 2nCn
などがある。更に、nCmの偶奇について面白いことが言える。
- n = 2p(1) + 2p(2) + …、m = 2q(1) + 2q(2) + …
というように、n と m を二進展開したとき、 {p(1), p(2), ...} ⊃ {q(1), q(2), ...} であることが、nCm が奇数であることの必要十分条件になっている。
[編集] 関連項目
[編集] 外部リンク
- 組合せ数を計算する 高精度計算サイト・計算式ライブラリ
