数え上げの質問 A(n)の一般式は存在するか？

質問

任意の自然数nに対して，次の４つの不等式
a+b+c+d≦n，
a≦b≦2a，
b≦c≦3b，
c≦d≦4c
をすべて満たすような非負整数の組(a，b，c，d)の個数をA(n)とします．
A(n)をnの式で表すにはどのようにすればいいのでしょうか？

たとえばA(7)=8です．
なぜならばn=7のとき，上述の４つの不等式をすべて満たすような
非負整数の組(a，b，c，d)は8組あるからです．
その8組を書いておきます．
(a，b，c，d)=(0，0，0，0)，(1，1，1，1)，(1，1，1，2)，(1，1，1，3)，
(1，1，1，4)，(1，1，2，2)，(1，1，2，3)，(1，2，2，2)．
また，A(8)=12，A(9)=17，A(10)=23，A(11)=31，A(12)=41，
A(13)=52，A(14)=65，A(15)=80 などとなります．

巨大な自然数nに対してのA(n)の値を瞬時に計算できるようなA(n)の式が
あれば理想的です．そのような式が無いのであれば近似式でも構いません．
よろしくお願いします．

回答No.2

20080715

＞A(n)をnの式で表すにはどのようにすればいいのでしょうか？

A(n)をnの式で表すには、母関数を利用すれば良いです。
母関数を利用した方法を述べる前に、A(n)の式を示しておきます。
(以下では、FLOOR(α) はαを超えない最大の整数を表すものとします。)

A(n)=1/11*(3*FLOOR(n/33+32/33)+FLOOR(n/33+31/33)-8*FLOOR(n/33+29/33)
-9*FLOOR(n/33+28/33)-4*FLOOR(n/33+26/33)-3*FLOOR(n/33+25/33)
-4*FLOOR(n/33+23/33)+6*FLOOR(n/33+20/33)+3*FLOOR(n/33+19/33)
+7*FLOOR(n/33+17/33)+9*FLOOR(n/33+16/33)+2*FLOOR(n/33+14/33)
-FLOOR(n/33+13/33)-2*FLOOR(n/33+10/33)-3*FLOOR(n/33+8/33)
-2*FLOOR(n/33+7/33)+3*FLOOR(n/33+5/33)+2*FLOOR(n/33+4/33)
+4*FLOOR(n/33+2/33)+2*FLOOR(n/33+1/33)-2*FLOOR(n/33+10/11)
-7*FLOOR(n/33+9/11)-6*FLOOR(n/33+8/11)+4*FLOOR(n/33+7/11)
+4*FLOOR(n/33+6/11)+8*FLOOR(n/33+5/11)-3*FLOOR(n/33+4/11)
-4*FLOOR(n/33+3/11)-3*FLOOR(n/33+2/11)+3*FLOOR(n/33+1/11)
-6*FLOOR(n/33+1/3)+6*FLOOR(n/33)+14)+1/17*(-12*FLOOR(n/17+16/17)
-7*FLOOR(n/17+15/17)-4*FLOOR(n/17+14/17)+4*FLOOR(n/17+13/17)
+7*FLOOR(n/17+12/17)+12*FLOOR(n/17+11/17)+9*FLOOR(n/17+10/17)
+5*FLOOR(n/17+9/17)+7*FLOOR(n/17+8/17)+5*FLOOR(n/17+7/17)
+6*FLOOR(n/17+6/17)-6*FLOOR(n/17+4/17)-5*FLOOR(n/17+3/17)
-7*FLOOR(n/17+2/17)-5*FLOOR(n/17+1/17)-9*FLOOR(n/17)-7)
+1/13*(-4*FLOOR(n/13+11/13)-5*FLOOR(n/13+10/13)+FLOOR(n/13+8/13)
+FLOOR(n/13+7/13)+3*FLOOR(n/13+6/13)-3*FLOOR(n/13+5/13)-FLOOR(n/13+4/13)
-FLOOR(n/13+3/13)+5*FLOOR(n/13+1/13)+4*FLOOR(n/13)+6)
+1/15*(5*FLOOR(n/15+14/15)+7*FLOOR(n/15+13/15)-5*FLOOR(n/15+8/15)
-3*FLOOR(n/15+7/15)+2*FLOOR(n/15+4/15)-3*FLOOR(n/15+1/15)
+3*FLOOR(n/15+4/5)-7*FLOOR(n/15+3/5)+3*FLOOR(n/15+2/5)-2*FLOOR(n/15+1/5)
-3*FLOOR(n/15+2/3)+3*FLOOR(n/15)-4)+1/7*(-FLOOR(n/7+6/7)+FLOOR(n/7+5/7)
+FLOOR(n/7+4/7)+2*FLOOR(n/7+3/7)-2*FLOOR(n/7+1/7)-FLOOR(n/7)-1)
+1/15*(FLOOR(n/5+4/5)-FLOOR(n/5+3/5)-1/5)+1/4*(-FLOOR(n/8+5/8)
+FLOOR(n/8+1/8)-FLOOR(n/8+3/4)+FLOOR(n/8+1/4)-FLOOR(n/8+1/2)
+FLOOR(n/8)+3/2)+1/495*(-5*FLOOR(n/3+2/3)-11*FLOOR(n/3+1/3)
+16*FLOOR(n/3)+7)+1/32*(-6*FLOOR(n/4+1/2)+6*FLOOR(n/4)+3)
+(483930*n^4+10873580*n^3+71161980*n^2+161166030*n-401754919)/980179200
+1/256*(-2*(2*n+7)*FLOOR(n/2+1/2)+2*(2*n+7)*FLOOR(n/2)+2*n+7).

これを使えばA(n)の正確な値が算出できます。
いくつか計算例を挙げておきます。
A(10000)=4948259152904.

A(1000000)=493726936514427309645.

A(10^100)=493715842980548862901804078274666509960627607686431215842980548
8629018040782746665099606276076864323251891082773435714612185200420494538
1415969651263768910827734357146121852004204945381415969651263841511817430
9350779939015233132880191703721115485821368174309350779939015233132880191
7037211154858215404118757059933530521765815883462942286471698236404118757
059933530521765815883462942286471698236404.

数列{A(n)}の母関数 Σ[k=0～∞]A(n)*x^k は、
(1/(1-x))*(Σ[a=0～∞](x^a*Σ[b=a～2a](x^b*Σ[c=b～3b](x^c*(Σ[d=c～4c]x^d)))))
を計算することによって得られます。その計算結果は、
Σ[k=0～∞]A(n)*x^k
=(x^76+3*x^75+6*x^74+11*x^73+19*x^72+30*x^71+45*x^70+65*x^69+90*x^68+121*x^67
+158*x^66+200*x^65+248*x^64+302*x^63+361*x^62+425*x^61+493*x^60+563*x^59
+636*x^58+711*x^57+786*x^56+859*x^55+929*x^54+996*x^53+1059*x^52+1117*x^51
+1169*x^50+1215*x^49+1256*x^48+1292*x^47+1322*x^46+1346*x^45+1366*x^44
+1381*x^43+1391*x^42+1397*x^41+1399*x^40+1396*x^39+1390*x^38+1381*x^37
+1366*x^36+1347*x^35+1324*x^34+1294*x^33+1259*x^32+1219*x^31+1172*x^30
+1121*x^29+1066*x^28+1003*x^27+937*x^26+870*x^25+798*x^24+724*x^23+651*x^22
+576*x^21+504*x^20+438*x^19+373*x^18+313*x^17+260*x^16+210*x^15+167*x^14
+132*x^13+100*x^12+73*x^11+53*x^10+36*x^9+24*x^8+17*x^7+11*x^6+7*x^5+5*x^4
+3*x^3+2*x^2+2*x+1)/((x+1)^2*(1-x)^5*(x^2+1)*(x^2+x+1)*(x^4+1)*
(x^4+x^3+x^2+x+1)*(x^6+x^5+x^4+x^3+x^2+x+1)*(x^8-x^7+x^5-x^4+x^3-x+1)*
(x^12+x^11+x^10+x^9+x^8+x^7+x^6+x^5+x^4+x^3+x^2+x+1)*
(x^16+x^15+x^14+x^13+x^12+x^11+x^10+x^9+x^8+x^7+x^6+x^5+x^4+x^3+x^2+x+1)*
(x^30+x^27+x^24+x^21+x^18+x^15+x^12+x^9+x^6+x^3+1))
となります。
これはxの有理式です。
この有理式を級数展開したときのx^nの係数がA(n)です。

回答No.1

ramayana

次の B(n) を近似式とするのはいかがでしょうか？

B(n) = 0.00049373214739435 n^4 + 0.0110881598581543 n^3 + 0.0730953868684545 n^2 + 0.154127398471299 n - 0.562839118580806

B(n) は、次のようにして導きました。

　a、b、c、d を非負実数として、ご質問の不等式を満たすa、b、c、d 全体からなる 4 次元領域を Ω(n) とする。Ω(n) の体積を V(n) とする。 すると、

　　lim[n→∞]V(n)/A(n) = 1

である。α= V(1) とすれば、V(n) = αn^4 だから、

　　lim[n→∞] αn^4/A(n) = 1

である。
　このαn^4 を近似式としてもよいが、n が小さいとき精度がよろしくない。その理由は、Ωの境界にある格子点の個数をうまく評価していないためである。「Ωの境界」というのは、ご質問の不等式のうち１つ以上が等式になる部分を指す。これは、3 次元領域であるから、そこにある格子点の個数は、漸近的に n^3 に比例する。この境界にある格子点の個数をさらに高精度で評価するには、境界の境界（ご質問の不等式のうち2つ以上が等式になる部分、 2 次元領域）にある格子点の個数を評価する必要がある。これは、漸近的に n^2 に比例する。等々と考えていけば、A(n) を n の 4 次式で近似するのがよいと予想される。

　そこで、近似式 B(n) を

　B(n) = αn^4 +βn^3 +γn^2 + δn + ε

とおいて、係数α、β、γ、δ、εを最小二乗法で推計したのが、冒頭の式である。推計に用いたのは、n=1 から n=200 までの、200 個のデータである。

いくつかの計算結果を以下に示す。

　　A(7) = 8、B(7) = 9.086、B(7)/A(7) = 1.136
　　A(10) = 23、B(10) =24.31、B(7)/A(7) = 1.057
　　A(50) = 4,663、B(10) =4.662*10^3、B(7)/A(7) = 1.000
　　A(100) = 61,209、B(10) =6.121*10^4、B(7)/A(7) = 1.000
　　A(1,000) = 504,882,076、B(10) =5.049*10^8、B(7)/A(7) = 1.000
　　A(2,000) = 7,988,491,930、B(10) =7.989*10^9、B(7)/A(7) = 1.000