131024 初版 131024 更新
ある集合の部分集合を組合せという。
例えば、A = {a, b, c, d, e, f} とすると、
{a, b, d} は 元の個数 3 の組合せである。
{a, b, d} と {a, d, b}, {b, a, d}, {b, d, a}, {d, a, b}, {d, b, a} は 集合としては同一である。
組合せは、順序の違うものを同一視している。
2種類の同じものを含む順列と組合せとは同型である。
例えば、
a, a, a, b, b の2種類5文字の同じものを含む順列と
5つ から 3つ とる組合せ、あるいは 5つ から 2つ とる組合せは同型である。
例えば、
aaabb ↔ 123,
aabab ↔ 124,
aabba ↔ 125,
abaab ↔ 134,
ababa ↔ 135,
abbaa ↔ 145,
baaab ↔ 234,
baaba ↔ 235,
babaa ↔ 245,
bbaaa ↔ 345
このように同型なものへの対応の考えは数学らしい考えである。
n個 から r個 とる組合せの総数を nCr とかく。
\({}_n{\rm C}_r=\dfrac{n!}{r!(n-r)!}\)
\({}_n{\rm C}_0={}_n{\rm C}_n=1\)
\({}_n{\rm C}_1={}_n{\rm C}_{n-1}=n\)
\({}_n{\rm C}_r={}_n{\rm C}_{n-r}\)
正確には上のようになる。
単純な組合せは1つずつとっている。
重複組合せとは、例えば
２つの箱A, Bがあって、それぞれの箱にあるものは区別できない。
箱には十分な個数が入っている。箱の違うものは区別できる。
AからとBからのものとあわせて 10 個とる場合の数。
のような考えである。
a + b = 10 にするのだから、
一方の箱から全く取らないというのを含めると 11 とおりある。
重複組合せ