これを解いてみた。
コーディングはしてませんが。
問題概要
500円の商品をa+b個売るのだがおつりを全く用意していない。
客はひとつずつ商品を買っていく。
a人は千円札しか持っていないが、b人は500円玉を持っている。
売る順番を工夫すればうまくやりくりできるが、売る順番は何通りあるか？
ただし、客の区別はつけない。
解法
DPすれば解けそうだが、数学っぽく解くことにする。
千円札しか持っていない人をA、500円玉を持っている人をBと呼ぶ。
つまり、Aはa人、Bはb人いる。
a = 4, b = 6のときの問題を下図に対応させる。
赤線をまたがないように、左下から右or上に辺を辿っていって右上に辿り着く方法の数が答えになる。
上に辿ることがAに商品を売ること、右に辿ることがBに商品を売ること、に対応している。
さて、このままだと数式に出来ないので、少し言い換えをする。
「赤線をまたがないように辿る場合の数」は
「普通に辿る場合の数」ー「赤線をまたいで辿る場合の数」
となる。
「赤線をまたいで辿る場合の数」というのはつまり、
上図の「オレンジの●を通って辿る場合の数」ということ。
それは、
上図のように赤線で折り返すと簡単に求まることが分かる。
まあつまり、計算式としては、
a+b C a - (a-1)+(b+1) C (a-1) = a+b C a - a+b C a-1
となります！(Cはコンビネーションね)
以上〜
