メインコンテンツまでスキップ

コンビネーションをsetとして表現する

概要​

nCk{}_nC_k や(n,k)(n,k)のかわりに、{{k1,k2}}\{\{k_1,k_2\}\}と表現したらいいのではないか。

nCk{}_nC_k表記のいまいちなところ​

n個の箱の中にk個のボールを入れる組み合わせ数は

nCk=n!k!(n−k)!{}_nC_k = \frac{n!}{k!(n-k)!}

と計算されます。

n個の箱の中から、n-k個のボールを入れない箱を選ぶ組み合わせ数も同じように

nCn−k=n!(n−k)!k!{}_nC_{n-k} = \frac{n!}{(n-k)!k!}

と計算され、当然これらは同じ結果になります。

同じ計算をnCk{}_nC_kとnCn−k{}_nC_{n-k}の2つの方法で表せてしまうのが私としては少し気持ち悪いです。

解決方法​

選ぶものも選ばれないものも数学的には同じ立場であるはずなので、

  • 選ぶもの: k1k_1個
  • 選ばないもの: k2k_2個（従来表現ではn−kn-k個）

として、組み合わせ数の計算に必要な情報を

{k1,k2}\{k_1, k_2\}

という集合で表現することができます。

k1=k2k_1=k_2のこともありうるので、多重集合であることを明示的に示すために、

{{k1,k2}}\{\{ k_1,k_2 \}\}

などと表現したほうがよいかもしれません。

組み合わせ数の計算は次のとおりです。

{{k1,k2}}=(k1+k2)!k1!k2!\{\{k_1, k_2\}\} = \frac{(k_1 + k_2)!}{k_1!k_2!}

私としてはこちらの式のほうが対称性があってすっきりします。

追加うれしさ​

3種以上の並び替えへ拡張しやすい​

この表現方法であれば、3種類以上のものを並び替えるケースにも対応可能です。

たとえば、赤いボールがr個、緑のボールがg個、青のボールがb個あり、これらを並び替える組み合わせ数は{{r,g,b}}\{\{ r,g,b \}\} と表現でき、計算式も次のようにすっきりします。

{{r,g,b}}=(r+g+b)!r!g!b!\{\{ r,g,b \}\} = \frac{(r + g + b)!}{r!g!b!}

n≥kn \ge kが自然に満たされる​

n<k n \lt kのとき、nCk{}_nC_kは0となりますが、{{k1,k2}}\{\{ k_1,k_2 \}\}ではk1k_1とk2k_2が自然数である限り、自動的に n≥max⁡(k1,k2)n \ge \max(k_1,k_2) が満たされます。

動的計画法での計算式がすっきりする​

組み合わせ数は「ボールの数を保ったまま、箱の数を1つ増やす」操作を考えることで、再帰的にも計算できます。

  • 増やす箱にボールが入っていない場合、すなわち元のn-1個の箱にボールがk個入っている場合
  • 増やす箱にボールが入っている場合、すなわち元のn-1個の箱にボールがk-1個入っている場合

を足し合わせることで、

nCk=n−1Ck+n−1Ck−1{}_nC_k= {}_{n-1}C_k + {}_{n-1}C_{k-1}

と計算できます。 ベースは

1C1=1,1C0=1{}_1C_1= 1, {}_1C_0= 1

です。

集合的表記を使えば、このロジックもストレートに表すことができます。

{{k1,k2}}={{k1−1,k2}}+{{k1,k2−1}} (k1≥1∧k2≥1)\{\{ k_1,k_2 \}\} = \{\{ k_1-1,k_2 \}\}+ \{\{ k_1,k_2-1 \}\} \space (k_1 \ge 1 \land k_2 \ge 1) {{k1,k2}}=1 (k1=0∨k2=0)\{\{ k_1,k_2 \}\} = 1 \space (k_1 =0 \lor k_2 =0)