131026 初版 131026 更新
問題
8人から4人選ぶ組合せをすべて求めよ。
場合の数は 70 と分かっているが、全部挙げるにはどうすればよいだろうか。
書くのは面倒だから、コンピュータを使えばいい。
でも、コンピュータにどう書かせればいいか。
一例を挙げる。
有名な公式に次のようなものがある。
8C0 +
8C1 +
8C2 +
8C3 +
8C4 +
8C5 +
8C6 +
8C7 +
8C8 =28
二項定理で証明するのだが、
組合せを集合と見ると、
元が8個の集合の部分集合を、元の個数で分類している。
組合せは、2種類の同じものを含む順列でもあったから、
組合せは、2進数展開で実現できる。
例として 8C4 70 個を書いてみる。
1 から 255 = 28-1 までを2進数に展開する
都合があって、通常と違って左から右に一の位、二の位、四の位, … と展開する。
8桁の数字のうち、1 であるものが 4つ であるものが 求めるものである。
例えば 89 は この展開表記では 10011010 となるが、
これは、U={1,2,3,4,5,6,7,8} から {1,4,5,7} をとったと見る。