自然数を順序を考慮して分割

問題

ABC132 D - Blue and Red Balls

問題概要

ボール:N
うち青:K
ボールを並べて
青の島(青の連続区間の個数)がi個になる並べ方の個数
※同色ボールは区別できない

解法

\left( K\text{を}i\text{個の自然数に分割する方法 } \right) \times \left( N-K\text{を}i+1\text{個の自然数(両端は}0\text{可)に分割する方法} \right)

nr個の自然数に分割する方法

\displaystyle 0を許可するとき,{}{n+r-1}C{r-1}
これは丸と線で区切る考え方のやつ.
O|OO|O|OO||O|OO|をシャッフルする,みたいな

0を許可しないために事前に1つ入れておく.
0が許されない箇所がk個あったとき,
\displaystyle {}{n-k+r-1}C{r-1}