多重集合
多重集合係数に対して漸化式
( ( n k ) ) = ( ( n k − 1 ) ) + ( ( n − 1 k ) ) ( n , k > 0 ) {\displaystyle \left(\!\!{n \choose k}\!\!\right)=\left(\!\!{n \choose k-1}\!\!\right)+\left(\!\!{n-1 \choose k}\!\!\right)\quad (n,k>0)}
を初期条件 ((n0)) = 1 (n ∈ N) および ((0k)) = 0 (k > 0) の下で与えることができる。この漸化式は以下のように組合せ論的に解釈することができる。
以下 [n] = {1, ..., n} と書く。位数 0 の(空)多重集合は常にただ一つであり、また n = 0 のときそれより位数の大きな多重集合は存在しないから、初期条件はこの解釈に適合する。さて n,k > 0 のとき、集合 [n] の元からなる位数 k の多重集合が末尾の元 n を含むか含まないかに分けて考える。含むならば、n の一つはさておいて残りのk − 1 個の元を [n] から選んで多重集合を作りそこに n を加えればよいから、そのようなものは ((nk−1)) 通りある。他方、含まないときは、末尾を除いた集合 [n − 1] から k-元多重集合をつくることになるから、そのようなものは ((n−1k)) 通りである。従って ((nk)) = ((nk−1)) + ((n−1k)) が得られた。