■制限のある分割から(その24)

x1+x2+x3=n,x1≧x2≧x3≧0の解の個数をa3(n)とおくと、a3(n)=p3(n+3)

また、y3=x3,y2=x2-x3,y1=x2-x1とおくと、a3(n)は

y1+2y2+3y3=n,y1≧0,y2≧0,y3≧0の解の個数と等しくなる。

したがって、

Σa3(n)x^n=(1-x)^-1(1-x^2)^-1(1-x^3)^-1

===================================

ω=exp(2πi/3)とおいて、部分分数分解すると

Σa3(n)x^n=1/6(1-x)^-3+1/4(1-x)^-2+17/72(1-x)^-1+1/8(1+x)^-1+1/9(1-ωx)^-1+1/9(1-ω^2x)^-1

a3(n)=1/12(n+3)^2-7/72+1/8(-1)^n+1/9(ω+ω^2)

|a3(n)-1/12(n+3)^2|≦7/72+1/8+7/72+2/9<1/2

以上より、p3(n)=(n+3)^3/12に最も近い整数となる。

===================================

1からkで番号づけられた箱に、n個の互いに区別のつかない球を入れる分け方の総数を数えてみる。

n個の青球を一列に並べてそれらの間にk-1個の赤玉を挟み込む選び方の総数と等しくなるから、

  (n+k-1,k-1)

===================================

方程式x1+x2+x3+・・・+xk=nの非負整数解の総数は・・・(n+k-1,k-1)

方程式x1+x2+x3+・・・+xk=nの正の整数解の総数は・・・(n-1,k-1)

===================================

集合{1,2,・・・、k}、互いに連続しないr個の要素{x1,x2,・・・,xr}を選ぶ選び方の総数は

x1<x2<・・・<xrとしてよいから、

x1≧1,x2-x1≧2,・・・、xr-xr-1≧2

y1=x1,y2=x2-x1-1,・・・、yr=n-xr+1とおくと、yiは正の整数でΣyi=n-r+2

したがって、(n-r+1,r)

===================================