Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

重複あり組み合わせの計算方法 (ABC110 D)

D - Factorization

は、方針としては「素因数分解をしてその要素を振り分ける場合の数を計算する」で明らかですが、そこから方針が立たず、エディトリアルを見てもわからず、解説動画を見てなんとなくわかったようなわからないような感じになっていたのですが、ようやく理解したので共有します。

エディトリアルの、

直感的には、bj 個のボールを N − 1 個の仕切りでグループ分けするイメージで、ボールか仕切りか定まっていない bj + N − 1 個の連続したオブジェクトから bj 個の仕切りを選ぶ場合の数です

は自分にはどうしてそういう考え方になるのかわからないのですが、直感に頼らずとも、以下のように考えれば同じ式にたどり着けます。

まず、bをN個のグループに空グループありで分ける方法は、端も含めたb+1の中からN-1個を重複ありで選ぶことに等しいです。これは、数学の記号ではb+1 H N-1で表されます。

重複組合せの公式と例題(玉,整数解の個数) | 高校数学の美しい物語

n H r = n+r-1 C rなので、これは、b+1+N-1-1 C N-1 = b+N-1 C N-1となります。

a+b C a = a+b C bですから、これはb+N-1 C bとなります。

ふつうの組み合わせは日常的にも時々計算するので比較的馴染み深いですが、重複組み合わせは大学入試以来考え方こともなかったので、そんなものが存在していたことすら忘れていました。