質問: 数え上げの質問 a(n)の一般式は存在するか? 任意の自然数nに対して,次の4つの不等式 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のとき,上述の4つの不等式をすべて満たすような 非負整数の組(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)の式が あれば理想的です.そのような式が無いのであれば近似式でも構いません. よろしくお願いします.
回答: >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~∞)))) を計算することによって得られます。その計算結果は、 σ[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)です。