最大個数制限付きの分割数の漸化式
最大個数制限付きの分割数の漸化式
区別の出来ない\(n\)個の玉を区別の出来ない\(k\)個の箱に空箱ありで分けるが箱には最大で\(m\)個しか入らないとする。
このときの分け方の方法の数を\(p_{1}\left(n,k,m\right)\)で表すと漸化式、
\[ p_{1}\left(n,k,m\right)=p_{1}\left(n,k-1,m\right)+p_{1}\left(n-k,k,m\right)-p_{1}\left(n-k-m,k-1,m\right) \] となる。
区別の出来ない\(n\)個の玉を区別の出来ない\(k\)個の箱に空箱ありで分けるが箱には最大で\(m\)個しか入らないとする。
このときの分け方の方法の数を\(p_{1}\left(n,k,m\right)\)で表すと漸化式、
\[ p_{1}\left(n,k,m\right)=p_{1}\left(n,k-1,m\right)+p_{1}\left(n-k,k,m\right)-p_{1}\left(n-k-m,k-1,m\right) \] となる。
分け方を空箱があるときとないときとで分けて考える。
空箱があるときは、どれかの空箱を無くすことによって\(k-1\)個の箱に分割することになるので\(p_{1}\left(n,k-1,m\right)\)通りになる。
空箱がないときは、全ての箱から1つずつ玉をとると、\(n-k\)個の玉を\(k\)個の箱に空箱ありで箱には最大\(m-1\)個までで分ける方法の数と同じなので\(p\left(n-k,k,m-1\right)\)通りになる。
これは\(n-k\)個の玉を\(k\)個の箱に空箱ありで箱には最大\(m\)個までで分ける方法の数\(p_{1}\left(n-k,k,m\right)\)から箱に\(m\)個入ってる場合の数\(p_{1}\left(n-k-m,k-1,m\right)\)を引いたものに等しい。
箱に\(m\)個入ってる場合の数は、１つの箱には\(m\)個入っていて残りの\(n-k\)個の玉を\(k-1\)個の箱に最大\(m\)個入れる場合の数となるので\(p_{1}\left(n-k-m,k-1,m\right)\)となるのである。
従って空箱がないときは\(p\left(n-k,k,m-1\right)=p\left(n-k,k,m\right)-p_{1}\left(n-k-m,k-1,m\right)\)となる。
これより、空箱があるときとないときの両方を足せば\(p_{1}\left(n,k,m\right)\)になるので、\(p_{1}\left(n,k,m\right)=p_{1}\left(n,k-1,m\right)+p_{1}\left(n-k,k,m\right)-p_{1}\left(n-k-m,k-1,m\right)\)となり与式は成り立つ。
空箱があるときは、どれかの空箱を無くすことによって\(k-1\)個の箱に分割することになるので\(p_{1}\left(n,k-1,m\right)\)通りになる。
空箱がないときは、全ての箱から1つずつ玉をとると、\(n-k\)個の玉を\(k\)個の箱に空箱ありで箱には最大\(m-1\)個までで分ける方法の数と同じなので\(p\left(n-k,k,m-1\right)\)通りになる。
これは\(n-k\)個の玉を\(k\)個の箱に空箱ありで箱には最大\(m\)個までで分ける方法の数\(p_{1}\left(n-k,k,m\right)\)から箱に\(m\)個入ってる場合の数\(p_{1}\left(n-k-m,k-1,m\right)\)を引いたものに等しい。
箱に\(m\)個入ってる場合の数は、１つの箱には\(m\)個入っていて残りの\(n-k\)個の玉を\(k-1\)個の箱に最大\(m\)個入れる場合の数となるので\(p_{1}\left(n-k-m,k-1,m\right)\)となるのである。
従って空箱がないときは\(p\left(n-k,k,m-1\right)=p\left(n-k,k,m\right)-p_{1}\left(n-k-m,k-1,m\right)\)となる。
これより、空箱があるときとないときの両方を足せば\(p_{1}\left(n,k,m\right)\)になるので、\(p_{1}\left(n,k,m\right)=p_{1}\left(n,k-1,m\right)+p_{1}\left(n-k,k,m\right)-p_{1}\left(n-k-m,k-1,m\right)\)となり与式は成り立つ。
ページ情報
| タイトル | 最大個数制限付きの分割数の漸化式 |
| URL | https://www.nomuramath.com/dbi4yrbh/ |
| SNSボタン |
分割数の定義と母関数
\[
\sum_{k=0}^{\infty}P\left(k\right)z^{k}=\prod_{k=1}^{\infty}\frac{1}{1-z^{k}}
\]
分割数の簡単な値
\[
p\left(n,2\right)=1+\left\lfloor \frac{n}{2}\right\rfloor
\]
空箱あり・なしの分割数の定義
\[
q\left(n,k\right)=p\left(n-k,k\right)
\]
分割数の漸化式
\[
p\left(n,k\right)=p\left(n,k-1\right)+p\left(n-k,k\right)
\]