二項係数の式変形について

ここであまり得意でないパターンの問題が出てきたのでメモです。DEGwerさんの数え上げPDFなんかにはいろんな種類が載っているので、また出てきたら追加します。数式をごちゃごちゃいじるとできるパターンもそのうち載せたいです。

$_{(r + 1 +c)}C_{c} = \sum_{i = 0}^{c} {}_{(r+i)}C _{i}$

$\displaystyle_{(r + 1 +c)}C_{c}$ について計算をしたい、とします。
これは、一回の移動で $1$ だけ移動できるとしたときの、座標 $(0,0)$ から $(r + 1,c)$ への最短移動経路の経路数です。

$\displaystyle \sum_{i = 0}^{c} {}_{(r+i)}C _{i}$ について計算します。
これは、座標 $(0,0)$ から $(r,i)$ への最短経路の場合の数を、 $0 \leqq i \leqq c$ について足し合わせたものです。

f:id:emtubasa:20200211134420p:plain

上の(~~適当な~~)図の、水色が今求めたい部分です。その上の行にある、黄色く塗られた部分のマスについて注目します。
水色のマスに行くには、まず黄色のマスの少なくとも1つを通らなければ、たどり着くことはできません。そして、赤い矢印のうちいずれか1つを必ず通ります。しかも、2本以上その矢印を通ることはありません。矢印を通った後は、水色のマスにたどり着くまでひたすら右に進む必要があります。
つまり、赤い矢印それぞれについて経路が重複することはないため、それぞれの赤い矢印について、そこを通る経路数を計算し、その総和を求めれば、それが水色のマスへの経路数になります。
そして、赤い矢印を通る経路数は、赤い矢印の始点である黄色いマスの経路数そのものです( $(r,i)$ から $(r+1,i)$ の矢印ならば、 $(r,i)$ の経路数である $_{(r+i)}C_{i}$ )。よって、結果として矢印の経路数の総和である水色のマスの経路数は、

$\displaystyle _{(r + 1 +c)}C_{c} = \sum_{i = 0}^{c} {}_{(r+i)}C _{i}$

となりました。

例題(ABC154 F - Many Many Paths)

F - Many Many Paths

提出コード

$\displaystyle \sum_{i = r_{1}}^{r_{2}} \sum_{j = c_{1}}^{c_{2}} {}_{i + j}C_{i}$ を求める問題です。
式変形をすると、

$\displaystyle \sum_{i = r_{1}}^{r_{2}} ( \sum_{j = 0}^{c_{2}} \ _{i + j}C_{i} - \sum_{j = 0}^{c_{1} - 1} {}_{i + j}C_{i} )$

となり、ここで $\displaystyle _{(r + 1 +c)}C_{c} = \sum_{i = 0}^{c} {}_{(r+i)}C _{i}$ を使うと、

$\displaystyle \sum_{i = r_{1}}^{r_{2}} (_{i + c_{2} + 1}C_{c_{2}} - {}_{i + c_{1}}C_{c_{1}-1} )$

になります。これで計算量が落ち、答えを求めることができます。

$\sum_{j = 0}^{n}(j \times {}_{n}C_{j}) = n \times 2^{n-1}$

$\displaystyle \sum_{j = 0}^{n}(j \times {}_{n}C_{j}) = \sum_{j = 1}^{n}(j \times {}_{n}C_{j})$ ( $j = 0$ のとき $j \times {}_{n}C_{j} = 0$ のため)
$\displaystyle = \sum_{j = 1}^{n}\frac{n!}{(n-j)!(j-1)!}$ (少し展開して $j$ を削除)
$\displaystyle = \sum_{j = 1}^{n}(n\times \frac{(n-1)!}{(n-j)!(j-1)!})$ ( $n$ を外にだす)
$\displaystyle = \sum_{j=1}^{n}(n\times {}_{n-1}C_{j-1})$ (再びまとめる)
$\displaystyle = n \times \sum_{j=0}^{n-1}{}_{n-1}C_{j}$ ( $n$ をΣの外に出し、 $j$ を0-indexedに直す)
$\displaystyle = n \times 2^{n-1}$ (二項定理) となります。

例題(ABC 150 E - Change a Little Bit)

E - Change a Little Bit

提出コード
できるだけコストの小さいものから使用していくのが良いです。ということで、今回は全パターンの総和を求めるため、 $C$ の順番を変えても差し支えないことから、 $C$ を昇順でソートします。今後、 $C$ は0-indexedだとします。
$i$ 番目のビットを変化させるとします。このとき、問題文にも書いてあるように、残っている個数を $D$ とすると、 $D \times C_{i}$ のコストがかかります。
$i$ より小さい番号のビットは $S,T$ ともにそろっているとします。これらは $i$ ビット存在し、元々のビットパターンが $(0,0),(0,1),(1,0),(1,1)$ の4通りなので、この部分は $4^{i} ( = 2^{2i} )$ 通り存在します。
$i$ 番目のビットは、 $(0,1),(1,0)$ の2通り存在します。
さて、 $i$ より後ろの部分は、 $N-i-1$ ビット存在します。
この中で、 $j$ ビットが $S,T$ で異なっているとします。 $N-i-1-j$ ビットは初めからそろっていることになります。
そろっているビットは $(0,0),(1,1)$ の2通り、異なるビットも $(0,1),(1,0)$ の2通りです。ということで、ビットの組み合わせ自体は $2^{N-i-1}$ 通りです。そして、 $N-i-1$ ビットの中から、現在異なっている $j$ ビットを選ぶのは、 ${}_{N-i-1}C_{j}$ 通りとなります。
そして、このときにコストは $(j+1) \times C_{i}$ かかります。
$j$ については、 $0 \leqq j \leqq N-i-1$ の選び方があり、それぞれ総和を求めていかなければなりません。
長々と条件を書きましたが、これらを全てまとめて書くと、

$\displaystyle \sum_{i=0}^{N-1} (4^{i} \times 2 \times \sum_{j=0}^{N-i-1}(2^{N-i-1} \times {}_{(N-i-1)}C_{j} \times (j+1)\times C_{i}))$

2の累乗と $C_{i}$ を外に出してまとめると、

$\displaystyle \sum_{i=0}^{N-1}(2^{N+i} \times C_{i} \times \sum_{j=0}^{N-i-1}((j+1)\times {}_{(N-i-1)}C_{j}) )$

となります。さらに $(j+1)$ の部分を分配法則を用いて変形し、
* $\displaystyle \sum_{i=0}^{N-1}(2^{N+i} \times C_{i} \times (\sum_{j=0}^{N-i-1} j \times {}_{(N-i-1)}C_{j} + \sum_{j=0}^{N-i-1} {}_{(N-i-1)}C_{j}) )$