正直に申し上げて、組合せ問題には弱い。若い人と勝負しても五分五分の勝率でしかないことを考えると、本人の力はそんなものかもしれないだろう。

実用性は別として、ACM問題集に組合せ問題は割と多く出題されている。やはり得意でないひとが世の中に多いからだろう。

今回の話は、もっとも基本的な問題のひとつ。

n 個の物から r 個をとって並べる並べ方の数はいくつか。ただし、n 個の物は必ずしも異なる必要はない。また、組合せ問題なので、並べ方の順番まで考慮してはいけない。

例をもって説明すると判りやすいので、つぎのことを考えよう。

文字 A, A, B, B, C から、2文字を取り出してできる組合せは以下の通り。

  AA
  AB または BA ← 前後の順番は考えないので、AB と BA は同一と見なす。
  AC または CA
  BB
  BC または CB

つまり、5 というのが答。

一方、中学校等で、異なる n 個の物から r 個とる組合せの数について真っ先に学ぶ。つまり、上の例で考えると以下のケースに相当する。

文字 A, B, C, D, E から、2文字を取り出してできる組合せの数。(答は勿論 10 )

ほかに、異なる n 個のものから重複を許して r 個とる組合せの総数、いわゆる、重複組合せというのもある。上の例と相当するのは、

文字 A, A, A, A,…, B, B, B, …, C, C, C,… から 2個とる組合せというケース。答えを見てみると、
 
  AA
  AB または BA
  AC または CA
  BB
  BC または CB
  CC

つまり、答えは6だ。例でも判るように、重複組合せとは、文字の種類はすべて異ならなくもていいものの、文字の数は無限にあるというケース。

しかし、今回の話は、文字の種類がすべて異なっても異ならなくても、文字の数が有限の場合の組合せ問題だ。

自分の探し方が悪かったかもしれないが、Webサイトを探しても、図書を調べても、明快な回答はなかなか得られなかった。最終的に、C.L.リウの名著「組合せ数学入門 I 」に答えをやっと見つけた。

母関数を使う方法で解くという。上の例、文字 A, A, B, B, C に対応して、つぎの母関数を立てる。

  (1+x+x2) (1+x+x2) (1+x)

つまり、

  1項目の (1+x+x2) は文字 A, A に対応させる。
  2項目の (1+x+x2) は文字 B, B に対応させる。
  3項目の (1+x) は 文字 C に対応させる。

母関数を展開して、x2の前につく係数が r=2 の答えとなるという。

では展開してみるね。

  (1+x+x2) (1+x+x2) (1+x)
  = (1+x+x2 + x+x2+x3 + x2+x3+x4) (1+x)
  = (1+2x+3x2+2x3+x4) (1+x)
  = 1+x + 2x+2x2 + 3x2+3x3 + 2x3+2x4 + x4+x5
  = 1+3x+5x2+5x3+3x4+x5

確かに、x2の係数は 5、答えとなる。これだけではない、文字 A, A, B, B, C から、ゼロ文字から5文字まで取る組合せの総数はすべて母関数の展開式で判ってしまう。つまり、それぞれの係数を見れれば判るから。母関数というものは魔法みたいだと実感でき、天才数学者オイラーが母関数に魅せられたのも納得できる。

ちなみに、全て異なるn個のものに対応する母関数は

 (1+x) (1+x) … (1+x)   ← n 個
 = (1+x)n
 
になる。係数は組み合わせの公式そのものだから、その正しさは理解できよう。

また、重複組合せに対応する母関数は

 (1+x+x2+x3+…+xk+…)n = 1/(1-x)n

になる。

母関数の展開は筆算では大変だか、プログラムだとただの足し算で計算できるから、大した計算量にはならない。

最後に、ACM問題を紹介しておく。#10532 Combination! Once Again

Comments are closed.

Post Navigation