重複組合せの畳み込み

$\sum_i \binom{A + i}{i}\binom{B + K - i}{K - i} = \binom{A + B + K + 1}{K}$ この式変形は重複組合せの畳み込みを別の重複組み合わせで表現したものと解釈できる

重複組合せ: n個から重複を許して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}$
• 

from 二項係数の公式

ARC110D

• 二項係数の下が固定で上の数を和が一定の条件で全パターン足し合わせる問題
• $\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}$
    • 計算が合わない
      • $\binom{A + B + K + 1}{A+B+1}$になるはず
    • これは枠の個数自体が変化してるせいでダブルカウントが起きてるせい
    • 境界になるボールを追加すると考えると下がA+B+1になりそうだが、そうすると上も増やす必要があるのでは？という気持ちになる
    • 実際は重複組み合わせであることで境界が境界だけの役割をはたさない(境界と同じ位置にボールを置きうる)からこれでいいわけなのだが、混乱しそう