組み合わせの計算に関する難題

質問

こんにちは．
かなり難しい問題に苦しめられています．
回答者のみなさんの知恵をお貸しください．
よろしくお願いします．

nを20以上の任意の整数とします．
次の５つの条件(1)～(5)を同時に満たすような整数a，b，c，dについて考えます．
(1)a+b+c+d=n
(2)a>1
(3)b-a>1
(4)c-b>1
(5)d-c>1
この５つの条件を同時に満たすような整数の組(a，b，c，d)の各々に対して，
積a*b*c*dを考え，次にそうしてできた積をすべて足し合わせます．
このようにしてできた和はnの関数なのでこれをF(n)とします．
F(n)をnの式で表すことはできるのでしょうか？

実際の例を挙げて説明しておきます．
n=24のときを考えてみます．
n=24のときには，上記の５つの条件を同時に満たすような整数の組(a，b，c，d)は
次の５組だけです．
(a，b，c，d)=(2，4，6，12)，(2，4，7，11)，(2，4，8，10)，
(2，5，7，10)，(3，5，7，9)．
これら５組の各々に対して積a*b*c*dを考え，それらの積を
すべて足し合わせます．そうすると，
(2*4*6*12)+(2*4*7*11)+(2*4*8*10)+(2*5*7*10)+(3*5*7*9)
=3477
となります．
したがって，F(24)=3477ということになります．

n=20～25に対するF(n)の値は，
F(20)=384，F(21)=432，F(22)=984，F(23)=1718，F(24)=3477，F(25)=4620．
となります．
オンライン整数列大辞典でこの数列(384,432,984,1718,3477,4620)を検索して
みましたが，登録されていませんでした．

[　]をガウス記号とします．
Σ記号を３つ重ねることによってF(n)は，
F(n)=Σ{a=2 to [(n-12)/4]}Σ{b=a+2 to [(n-6-a)/3]}Σ{c=b+2 to [(n-2-a-b)/2]}(a*b*c(n-a-b-c))
とかくことができます．
この式を簡略化できないものかと考え，maxima(Maxima-5.25.1)に計算させてみました．
XMaximaを起動させて，
load("simplify_sum")$
sum(sum(sum(a*b*c*(n-a-b-c),c,b+2,fix((n-2-a-b)/2)),b,a+2,fix((n-6-a)/3)),a,2,fix((n-12)/4));
simplify_sum(%);
と打ち込んで様子をみると，nだけでなく変数a，bが混じった式が表示されます．
nだけの式で表すことには失敗しているようです．

現在私は10^18(10の18乗)程度のnに対してのF(n)の正確な値を求める必要性に
迫られています．先のΣ記号を３つ使ったF(n)の式の計算量はnの多項式オーダー
なのですが，この式でF(10^18)の値を計算するのは時間がかかりすぎてどうにも
なりません．なにか良い計算法はないものでしょうか．

回答No.3

20080715

＞F(n)をnの式で表すことはできるのでしょうか？

できます。F(n)を変数nだけの式であらわすことが可能です。
様々な表し方があります。一例を書いておきます。
(以下ではガウス記号[ ]を FLOOR( ) と書くことにします。)

F(n)=
-n*FLOOR(3/4-n/4)/16+n*FLOOR(1/4-n/4)/16
-(n^4-80*n^2+672)*FLOOR(1/2-n/4)/2048+(n^4-80*n^2+672)*FLOOR(-n/4)/2048
+n*FLOOR(n/4+3/4)/16-n*FLOOR(n/4+1/4)/16-(n^4-80*n^2+672)*FLOOR(n/4+1/2)/2048
+(n^4-80*n^2+672)*FLOOR(n/4)/2048+2*(2*n^3-6*n^2-33*n+18)*FLOOR(2/3-n/3)/729
-(5*n^3-21*n^2-69*n+141)*FLOOR(1/3-n/3)/729+(n^3-9*n^2-3*n+105)*FLOOR(-n/3)/729
-(5*n^3-21*n^2-69*n+141)*FLOOR(n/3+2/3)/729+2*(2*n^3-6*n^2-33*n+18)*FLOOR(n/3+1/3)/729
+(n^3-9*n^2-3*n+105)*FLOOR(n/3)/729-(4*n^5-45*n^4-160*n^3-3000*n^2+33456*n-50040)*FLOOR(1/2-n/2)/61440
+(4*n^5-45*n^4-160*n^3-3000*n^2+33456*n-50040)*FLOOR(-n/2)/61440
-(4*n^5-45*n^4-160*n^3-3000*n^2+33456*n-50040)*FLOOR(n/2+1/2)/61440
+(4*n^5-45*n^4-160*n^3-3000*n^2+33456*n-50040)*FLOOR(n/2)/61440
+(864*n^7-27216*n^6+119028*n^5+1873935*n^4+10210816*n^3-241109064*n^2-675074928*n+6933396120)*FLOOR(-n)/104509440
+(864*n^7-27216*n^6+119028*n^5+1873935*n^4+10210816*n^3-241109064*n^2-675074928*n+6933396120)*FLOOR(n)/104509440
+(72*n^7-2268*n^6+10486*n^5+154035*n^4+840168*n^3-20965392*n^2-51549696*n+574801920)/8709120.

このF(n)の計算式を使ってF(10^18)を計算すると、
F(10^18)=
8267195767195766935350529100529101733125734861845990643716012639623838974316578
483242783772413286302169370781893004115292.

F(n)は以下の様にして導きました。
(a*x^a)*(Σ{b=a+2 to ∞}((b*x^b)*(Σ{c=b+2 to ∞}((c*x^c)*Σ{d=c+2 to ∞}(d*x^d)))))
という式を簡単にして３つのΣを全て消した後の式に、a=2を代入します。
すると変数 x の有理式
x^20*(24*x^22+66*x^21+108*x^20+56*x^19-200*x^18-566*x^17-823*x^16-484*x^15+565*x^14
+1890*x^13+2625*x^12+1776*x^11-438*x^10-3036*x^9-4343*x^8-3406*x^7-823*x^6+2146*x^5
+3793*x^4+3782*x^3+2616*x^2+1200*x+384)/((x+1)^3*(x-1)^8*(x^2+1)^2*(x^2+x+1)^4*(x^3+x^2+x+1)^3)
が得られます。
これをマクローリン展開したときのx^nの係数がF(n)になります。
この有理式を部分分数分解します。
ただしその際、各項が g(x)/(1-x^m)^k (m,kは0以上の整数,g(x)はxの多項式)
という形にかけるように、部分分数分解します。
するとx^nの係数が得られます。

回答No.2

nag0720

F(n)=Σ{a=2 to [(n-12)/4]}Σ{b=a+2 to [(n-6-a)/3]}Σ{c=b+2 to [(n-2-a-b)/2]}(a*b*c(n-a-b-c))

この式が計算できないのは、ガウス記号があるからです。
だったら、場合分けをしてガウス記号をはずしてしまえばいいでしょう。

H(n,a,b)=Σ{c=b+2 to [(n-2-a-b)/2]}(a*b*c(n-a-b-c))
G(n,a)=Σ{b=a+2 to [(n-6-a)/3]}H(n,a,b)
F(n)=Σ{a=2 to [(n-12)/4]}G(n,a)
とすれば、
H(n,a,b)は、(n-2-a-b)が偶数のときと奇数のときに分ければガウス記号がはずれます。
G(n,a)は、a=6k+p (0≦p≦5) の６通りに分ければガウス記号がはずれます。
F(n)は、n=24m+q (0≦q≦23)の２４通りに分ければガウス記号がはずれます。

例えば、n=24mのとき、
F(24m)=Σ{a=2 to [(24m-12)/4]}G(24m,a)
=Σ{a=2 to 6m-3}G(24m,a)
=Σ{i=0 to 6m-5}G(24m,2+i)
=Σ{k=0 to m-1}G(24m,2+6k) + Σ{k=0 to m-1}G(24m,2+6k+1)
　+ Σ{k=0 to m-2}G(24m,2+6k+2) + Σ{k=0 to m-2}G(24m,2+6k+3)
　+ Σ{k=0 to m-2}G(24m,2+6k+4) + Σ{k=0 to m-2}G(24m,2+6k+5)

G(24m,2+6k)=Σ{b=2+6k+2 to [(24m-6-2-6k)/3]}H(24m,2+6k,b)
=Σ{b=4+6k to 8m-2-2k}H(24m,2+6k,b)
=Σ{i=0 to 8m-6-8k}H(24m,2+6k,4+6k+j)
=Σ{j=0 to 4m-3-4k}H(24m,2+6k,4+6k+2j) + Σ{j=0 to 4m-4-4k}H(24m,2+6k,4+6k+2j+1)

H(24m,2+6k,4+6k+2j)、H(24m,2+6k,4+6k+2j+1)は(n-2-a-b)の偶奇が確定しているので計算できます。

G(24m,2+6k+1),G(24m,2+6k+2),・・・なども同じですから、かなり面倒ですが丁寧に計算していけばF(n)が求まります。

お礼

回答ありがとうございます．
確かに場合分けをすればガウス記号をはずして
式を簡単にすることができますね．
手間はかかりますが，確実な方法です．
丁寧に説明していただき，ありがとうございました．

回答No.1

B-juggler

代数学屋さんです　ども　ｍ（＿　＿）ｍ

正直多分１０＾１８はちょっと無理ですよ＾＾；

σ(・・*)ｎ＝２０でもう危ない＞＜

多分、プログラミングで出されたほうがいいのかな？

カテゴリちょっと見てみると、「技術者向けコンピュータ」の中に「プログラミング」は

ありますね。言語は知らない言語だけど、その他　ってありますから、

そちらのほうが早い気がします。

(=^. .^=)　ｍ（＿　＿）ｍ　(=^. .^=)

お礼

回答ありがとうございます．
「代数学屋」ということは，数学者さんなのですね．
この問題に対しての数学的なアプローチが欲しかったので，
このカテゴリにて質問をしました．
maximaはフリーのソフトで，かなり便利なソフトです．
数学カテゴリの中にもユーザーがかなりいるんじゃないかと
私は考えています．