■漸化式と母関数(その10)
分割数p(n)はフィボナッチ数よりもっと緩やかに増加する.その漸近挙動の主項は
n→∞のとき,(logp(n)/√n)→π√(2/3)
である.
===================================
f(n)=(n−1)(f(n−1)+f(n−2))
これは,モンモール数f(n)がn−1で割り切れることを意味すると同時に,フィボナッチ数よりも急減に増加することを意味する.
参考までに記しますが,
p(n)≦p(n-1)+p(n-2)
が成り立つことより,分割数p(n)の増大速度はフィボナッチ数で上から抑えられることが示されます.したがって,黄金比φ=(√5+1)/2とおくと上界は
p(n)<φ^n.
すなわち,モンモール数>フィボナッチ数>分割数
===================================
pn=f(n)/n!
より,
pn=pn-1−(pn-1−pn-1)/n
pn−pn-1=−(pn-1−pn-1)/n
また,
n!=Σ(n,r)f(r)
f(n)=Σ(−1)^(n-r)(n,r)r!
は二項変換の逆変換・反転表示の特別な形である.
f(n)=[n!/e+m],1/3≦m≦1/2
pn=1/n![n!/e+m],1/3≦m≦1/2
と表すことができる.
===================================