組み合わせの計算に関する難題
こんにちは.
かなり難しい問題に苦しめられています.
回答者のみなさんの知恵をお貸しください.
よろしくお願いします.
nを20以上の任意の整数とします.
次の5つの条件(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
この5つの条件を同時に満たすような整数の組(a,b,c,d)の各々に対して,
積a*b*c*dを考え,次にそうしてできた積をすべて足し合わせます.
このようにしてできた和はnの関数なのでこれをF(n)とします.
F(n)をnの式で表すことはできるのでしょうか?
実際の例を挙げて説明しておきます.
n=24のときを考えてみます.
n=24のときには,上記の5つの条件を同時に満たすような整数の組(a,b,c,d)は
次の5組だけです.
(a,b,c,d)=(2,4,6,12),(2,4,7,11),(2,4,8,10),
(2,5,7,10),(3,5,7,9).
これら5組の各々に対して積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)を検索して
みましたが,登録されていませんでした.
[ ]をガウス記号とします.
Σ記号を3つ重ねることによって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)の正確な値を求める必要性に
迫られています.先のΣ記号を3つ使ったF(n)の式の計算量はnの多項式オーダー
なのですが,この式でF(10^18)の値を計算するのは時間がかかりすぎてどうにも
なりません.なにか良い計算法はないものでしょうか.
お礼
早速の解答、有り難う御座いました。他の方にも、解答をいただきましたが、15分程の差であなたが一番早かったので、良回答とさせていただきました。