重複順列と重複組み合わせ
競プロやっていたら必要になった。
自分なりに理解したことをまとめておく。
重複順列
なんてことはない。
1度選んだものをもう一度選べるというもの。
例えば、1から3の整数の選び方の順列といえば、となるが、
重複順列では一度選んだ整数をもう一度選びなおすことができるため、となる。
重複組み合わせ
重複順列と同じで、1度選んだものをもう一度選べる組み合わせ。
重複順列の組み合わせ版と考えればいい。
ただ、計算方法が少し複雑。
A個の要素を重複を許してB個取り出したときの組み合わせを考えるとき、
B個のマスの間に仕切りをA-1個おき、仕切りで作られた区間をそれぞれ左からA1、A2、A3としていく。
この仕切りの置き方の通りがこの重複組み合わせの答えとなる。
仕切りもマスとして数えた、B+A-1個のマスがあるとして、どこに仕切りを設置するか考える。
この時、B+A-1 C A-1となる。
また、別の考え方として、仕切りを設置しない場所を考えることもできる。
この時、B+A-1 C B であるが、結局のところ上の式と同じようになる。
また、重複をゆする順列の考えを使用し、組み合わせの計算を行うことができる。
仕切りも含めたB+A-1個のマスの並べ方は(B+A-1)!通り。
このうち、B個の重複は無視するのでB!で割る。
さらに、仕切りの重複も無視するので(A-1)!で割る。