分割数の漸化式
分割数の漸化式
分割数\(p\left(n,k\right)\)は以下の漸化式を満たす。
\[ p\left(n,k\right)=p\left(n,k-1\right)+p\left(n-k,k\right) \]
分割数\(p\left(n,k\right)\)は以下の漸化式を満たす。
\[ p\left(n,k\right)=p\left(n,k-1\right)+p\left(n-k,k\right) \]
\(p\left(n,k\right)\)は区別の出来ない\(n\)個の玉を区別の出来ない\(k\)個の箱に空箱ありで分ける方法の数である。
この分け方を空箱があるときとないときとで分けて考える。
空箱があるときは、どれかの空箱を無くすことによって\(k-1\)個の箱に分割することになるので\(P\left(n,k-1\right)\)通りになる。
空箱がないときは、全ての箱から1つずつ玉をとると、\(n-k\)個の玉を\(k\)個の箱に空箱ありで分ける方法の数と同じなので\(p\left(n-k,k\right)\)通りになる。
これより、空箱があるときとないときの両方を足せば求める答えになるので、\(p\left(n,k\right)=p\left(n,k-1\right)+p\left(n-k,k\right)\)となる。
この分け方を空箱があるときとないときとで分けて考える。
空箱があるときは、どれかの空箱を無くすことによって\(k-1\)個の箱に分割することになるので\(P\left(n,k-1\right)\)通りになる。
空箱がないときは、全ての箱から1つずつ玉をとると、\(n-k\)個の玉を\(k\)個の箱に空箱ありで分ける方法の数と同じなので\(p\left(n-k,k\right)\)通りになる。
これより、空箱があるときとないときの両方を足せば求める答えになるので、\(p\left(n,k\right)=p\left(n,k-1\right)+p\left(n-k,k\right)\)となる。
ページ情報
| タイトル | 分割数の漸化式 |
| URL | https://www.nomuramath.com/qow73jjy/ |
| SNSボタン |
分割数の定義と母関数
\[
\sum_{k=0}^{\infty}P\left(k\right)z^{k}=\prod_{k=1}^{\infty}\frac{1}{1-z^{k}}
\]
異分割・奇分割とオイラーの分割恒等式
\[
\sum_{k=0}^{\infty}P_{d}\left(k\right)z^{k}=\prod_{k=1}^{\infty}\left(1+z^{k}\right)
\]
空箱あり・なしの分割数の定義
\[
q\left(n,k\right)=p\left(n-k,k\right)
\]