重複組合せの畳み込み

$ \sum_i \binom{A + i}{i}\binom{B + K - i}{K - i} = \binom{A + B + K + 1}{K}

$ H^n_k = \binom{n + k - 1}{k}

左辺はA+1個からi個、B+1個からK-i個選ぶ重複組合せで、これの畳み込みはA+B+2個からK個選ぶ重複組合せになる。

$ \sum_i \binom{A + i}{i}\binom{B + K - i}{K - i} = \sum_i H^{A+1}_i H^{B+1}_{K-i} = H^{A+B+2}_K = \binom{A + B + K + 1}{K}

https://gyazo.com/333dc6580cce8f6b5ef4b8cb6abdf495

二項係数の下が固定で上の数を和が一定の条件で全パターン足し合わせる問題

$ \sum_i \binom{A + i}{i}\binom{B + K - i}{K - i} = \sum_i \binom{A + i}{A}\binom{B + K - i}{B}

下固定のまま直接重複組み合わせにできる？

$ \sum_i \binom{A + i}{A}\binom{B + K - i}{B} = \sum_i H_A^{i+1} H_B^{K-i+1} = H_{A+B}^{K+2} = \binom{A + B + K + 1}{A+B}

計算が合わない

これは枠の個数自体が変化してるせいでダブルカウントが起きてるせい

境界になるボールを追加すると考えると下がA+B+1になりそうだが、そうすると上も増やす必要があるのでは？という気持ちになる

実際は重複組み合わせであることで境界が境界だけの役割をはたさない(境界と同じ位置にボールを置きうる)からこれでいいわけなのだが、混乱しそう