平成２１年２月８日

[流れ星]

　　　　　第２１９回数学的な応募問題解答

　　　　　　＜解答募集期間：1月18日〜2月8日

［自然数の積の和］

皆さん、新年明けましておめでとうございます。今年もよろしくお願いします。

早速ですが、2009年最初の問題です。

問題１：ｘ＋ｙ＝Ｎ（ｘ，ｙは自然数で、Ｎは２以上の自然数）となる自然数の組（ｘ，ｙ）は

　　　　重複組合せの記号Ｈを用いて_２Ｈ_Ｎ−２通りある。これらの組のそれぞれについて積ｘｙを考え、このようにしてできた_２Ｈ_Ｎ−２個の数をすべて加えるといくつになるか。

　　　　例えばＮ＝５のとき、（ｘ、ｙ）＝（１，４），（２，３），（３，２），（４，１）の_２Ｈ_３＝_４C_３＝_４C_１＝４通りあり、その積は４，６，６，４となり、これらの和は4×２＋６×２＝２０で，これが答えです。

　　　　Ｎ＝２，３，４，５，６，・・・を代入して考えてください。

問題２：ｘ＋ｙ＋ｚ＝Ｎ（ｘ，ｙ，ｚは自然数で、Ｎは３以上の自然数）となる自然数の組
（ｘ，ｙ，ｚ）は_３Ｈ_Ｎ−３通りある。これらの組のそれぞれについて積ｘｙｚを考え、このようにしてできた_３Ｈ_Ｎ−３個の数をすべて加えるといくつになるか。

問題３：ｘ＋ｙ＋ｚ＋ｗ＝Ｎ（ｘ，ｙ，ｚ，ｗは自然数で、Ｎは４以上の自然数）となる自然数の組（ｘ，ｙ，ｚ，ｗ）は_４Ｈ_Ｎ−４通りある。これらの組のそれぞれについて

積ｘｙｚｗを考え、このようにしてできた_４Ｈ_Ｎ−４個の数をすべて加えるといくつになるか。

問題４：一般にｘ_１＋ｘ_２＋・・・＋ｘ_ｎ＝Ｎ（ｘ_１，ｘ_２，・・・，ｘ_ｎは自然数で、Ｎはｎ以上の自然数）となる自然数の組（ｘ_１，ｘ_２，・・・，ｘ_ｎ）は_ｎＨ_Ｎ−ｎ通りある。これらの組のそれぞれについて積ｘ_１ｘ_２・・・・ｘ_ｎを考え、このようにしてできた_ｎＨ_Ｎ−ｎ個の数をすべて加えるといくつになるか。

NO1「uchinyan」 1/18 17時53分受信

「uchinyan」 1/24 11時10分受信 更新2/8

第２１９回数学的な応募問題
［自然数の積の和］

問題１：x + y = N, ここで N, x, y は自然数で N >= 2
要するに，��[x+y=N,x>=1,y>=1]{xy} を求めればいいです。
��[x+y=N,x>=1,y>=1]{xy}
= ��[x=1,N-1]{x * (N - x)}
= ��[x=1,N-1]{N * x - x^2}
= N * N(N - 1)/2 - N(N - 1)(2N - 1)/6
= N(N - 1)/6 * (3N - (2N -1))
= (N - 1)N(N + 1)/6
確かに，N = 5 の場合は，6 * 5 * 4 * 1/6 = 20 で一致しています。

問題２：x + y + z = N, ここで N, x, y, z は自然数で N >= 3
同じく，��[x+y+z=N,x>=1,y>=1,z>=1]{xyz} を求めればいいです。
��[x+y+z=N,x>=1,y>=1,z>=1]{xyz}
= ��[x=1,N-2]��[y=1,N-x-1]{x * y * (N - x - y)}
= ��[x=1,N-2]{x * ��[y=1,N-x-1]{(N - x) * y - y^2}}
= ��[x=1,N-2]{x * ((N - x) * (N - x - 1)(N - x)/2 - (N - x - 1)(N - x)(2N - 2x - 1)/6}
= ��[x=1,N-2]{x * (N - x)(N - x - 1)/6 * ((3N - 3x) - (2N - 2x - 1))}
= ��[x=1,N-2]{x * (N - x)(N - x - 1)(N - x + 1)/6}
= 1/6 * ��[x=1,N-2]{x * (N - x)(N - x - 1)(N - x + 1)}
= 1/6 * ��[x=1,N-2]{x * ((N - x)^3 - (N - x))}
= 1/6 * ��[x=1,N-2]{x * ((N^3 - 3N^2 * x + 3N * x^2 - x^3) - (N - x))}
= 1/6 * ��[x=1,N-2]{x * ((N^3 - N) - (3N^2 - 1) * x + 3N * x^2 - x^3)}
= 1/6 * ��[x=1,N-2]{(N^3 - N) * x - (3N^2 - 1) * x^2 + 3N * x^3 - x^4}
ここで，
��[k=1,n]{k} = n(n+1)/2
��[k=1,n]{k^2} = n(n+1)(2n+1)/2
��[k=1,n]{k^3} = n^2(n+1)^2/4
��[k=1,n]{k^4} = n(n+1)(2n+1)(3n^2 + 3n - 1)/30
を用いて計算すると，
= 1/6 * {(N^3 - N) * (N - 2)(N - 1)/2 - (3N^2 - 1) * (N - 2)(N - 1)(2N - 3)/6
+ 3N * (N - 2)^2 * (N - 1)^2 * 1/4 - (N - 2)(N - 1)(2N - 3)(3(N - 2)^2 + 3(N - 2) - 1)/30}
= 1/360 * (N - 2)(N - 1) *
{30(N^3 - N) - 10(3N^2 - 1)(2N - 3) + 45N(N - 2)(N - 1) - 2(2N - 3)(3N^2 - 9N + 5)}
= 1/360 * (N - 2)(N - 1) *
{30N^3 - 30N + 45N^3 - 135N^2 + 90N - 2(2N - 3)(15N^2 - 5 + 3N^2 - 9N + 5)}
= 1/360 * (N - 2)(N - 1){75N^3 - 135N^2 + 60N - 2(2N - 3)(18N^2 - 9N)}
= 1/360 * (N - 2)(N - 1)(75N^3 - 135N^2 + 60N - 72N^3 + 144N^2 - 54N)
= 1/360 * (N - 2)(N - 1)(3N^3 + 9N^2 + 6N)
= (N - 2)(N - 1)N(N + 1)(N + 2)/120

問題３：x + y + z + w = N, ここで N, x, y, z, w は自然数で N >= 4
問題１：の結果は (N + 1)N(N -1)/6 = (N+1)C3 = (N+1)C(2+1)
問題２：の結果は (N - 2)(N - 1)N(N + 1)(N + 2)/120 = (N+2)C5 = (N+2)C(3+2)
となっています。そこで，一般には，(N+n-1)C(2n-1) になるのでは，と予想されます。
問題３：では，これを意識しながら計算してみます。
つまり，問題３：は，n = 4 なので，(N+4-1)C(2*4-1) = (N+3)C7 ではないかと予想されます。
これを数学的帰納法で証明します。
(1) N = 4 の場合
x + y + z + w = 4
なので，解は (x,y,z,w) = (1,1,1,1) だけです。
そこで，求める積の和は 1 です。
一方で，(4+3)C7 = 7C7 = 1 なので，成立しています。
(2) N で成立したとして N+1 の場合
x + y + z + w = N+1
(x-1) + y + z + w = N
なので，x >= 2 の解は，
x' + y + z + w = N
の解 (x',y,z,w) を使って，(x,y,z,w) = (x'+1,y,z,w) と書け，
xyzw = (x'+1)yzw = x'yzw + yzw
になり，x'yzw には帰納法の仮定が，yzw には N -> N-x' とした問題２：の結果が使えます。
また，x = 1 の解は，
y + z + w = N
xyzw = yzw
なので，やはり，問題２：の結果が使えます。
そこで，N+1 の場合の積の和は
��[x+y+z+w=N+1,x>=1,y>=1,z>=1,w>=1]{xyzw}
= ��[x+y+z+w=N+1,x=1,y>=1,z>=1,w>=1]{xyzw} + ��[x+y+z+w=N+1,x>=2,y>=1,z>=1,w>=1]{xyzw}
= 1 * ��[y+z+w=N,y>=1,z>=1,w>=1]{yzw} + ��[x'+y+z+w=N,x'>=1,y>=1,z>=1,w>=1]{(x'+1)yzw}
= ��[y+z+w=N,y>=1,z>=1,w>=1]{yzw}
+ ��[x'+y+z+w=N,x'>=1,y>=1,z>=1,w>=1]{x'yzw} + ��[x'=1,N-3]{��[y+z+w=N-x',y>=1,z>=1,w>=1]{yzw}}
ここで，先に注意したとおり，
��[y+z+w=N,y>=1,z>=1,w>=1]{yzw} = (N+2)C5　<-----　問題２：の結果
��[x'+y+z+w=N,x'>=1,y>=1,z>=1,w>=1]{x'yzw} = (N+3)C7　<-----　帰納法の仮定
��[x'=1,N-3]{��[y+z+w=N-x',y>=1,z>=1,w>=1]{yzw}}
= ��[x'=1,N-3]{(N-x'+2)C5}　<-----　問題２：の結果
= (N+1)C5 + NC5 + ... + 7C5 + 6C5 + 5C5
5C5 = 1 = 6C6 なので，
= (N+1)C5 + NC5 + ... + 7C5 + 6C5 + 6C6
nCr = (n-1)C(r-1) + (n-1)Cr なので，これを順次使用して，
= (N+1)C5 + NC5 + ... + 7C5 + 7C6
= (N+1)C5 + NC5 + ... + 8C6
= ...
= (N+1)C5 + NC5 + NC6
= (N+1)C5 + (N+1)C6
= (N+2)C6
そこで，
��[x+y+z+w=N+1,x>=1,y>=1,z>=1,w>=1]{xyzw}
= (N+2)C5 + (N+3)C7 + (N+2)C6
= (N+2)C5 + (N+2)C6 + (N+3)C7
= (N+3)C6 + (N+3)C7
= (N+4)C7
= ((N+1)+3)C7
となり，N+1 でも成立します。
以上で証明できました。
したがって，積の和は (N+3)C7 になります。

問題４：x1 + x2 + ... + xn = N, ここで N, x1, x2, ..., xn は自然数で N >= n
今までの問題の結果より，積の和は (N+n-1)C(2n-1) と予想されます。
これを，数学的帰納法で証明します。
(1) n = 2 の場合
問題２：より明らか。
(2) n で成立したとして n+1 の場合
x1 + x2 + ... + xn + x_(n+1) = N, N >= n+1
求める積の和 P は，
P = ��[x1+x2+...+xn+x_(n+1)=N,x1>=1,x2>=1,...,xn>=1,x_(n+1)>=1]{x1 * x2 * ... * xn * x_(n+1)}
です。この値を評価するために，さらに，N に関する数学的帰納法を用います。
(2-1) N = n+1 の場合
(x1,x2,...,xn,x_(n+1)) = (1,1,...,1,1) だけが解になるので，明らかに，A = 1 です。
一方で，予想は，(N+(n+1)-1)C(2(n+1)-1) = (N+n)C(2n+1) ですが，
この式は，N = n+1 で (2n+1)C(2n+1) = 1 になるので，成立します。
(2-2) N で成立したとして N+1 の場合
問題３：と同様の議論が使えます。
x1 + x2 + ... + xn + x_(n+1) = N+1
(x1-1) + x2 + ... + xn + x_(n+1) = N
なので，x1 >= 2 の解は，
x1' + x2 + ... + xn + x_(n+1) = N
の解 (x1',x2,...,xn,x_(n+1)) を使って，(x1,x2,z,w) = (x1'+1,y,...,xn,x_(n+1)) と書け，
x1 * x2 * ... * xn * x_(n+1)
= (x1'+1) * x2 * ... * xn * x_(n+1)
= x1' * x2 * ... * xn * x_(n+1) + x2 * ... * xn * x_(n+1)
になり，最初の項には n+1 で N の場合の帰納法の仮定が，
２番目の項には n の場合で N -> N-x1' とした帰納法の仮定が使えます。
また，x1 = 1 の解は，
x2 + ... + xn + x_(n+1) = N
x1 * x2 * ... * xn * x_(n+1) = x2 * ... * xn * x_(n+1)
なので，やはり，n の場合の帰納法の仮定が使えます。
そこで，n+1，N+1 の場合の積の和 P は
P
= ��[x1+x2+...+xn+x_(n+1)=N+1,x1=1,x2>=1,...,xn>=1,x_(n+1)>=1]{x1 * x2 * ... * xn * x_(n+1)}
+ ��[x1+x2+...+xn+x_(n+1)=N+1,x1>=2,x2>=1,...,xn>=1,x_(n+1)>=1]{x1 * x2 * ... * xn * x_(n+1)}
= 1 * ��[x2+...+xn+x_(n+1)=N,x2>=1,...,xn>=1,x_(n+1)>=1]{x2 * ... * xn * x_(n+1)}
+ ��[x1'+x2+...+xn+x_(n+1)=N,x1'>=1,x2>=1,...,xn>=1,x_(n+1)>=1]{(x1'+1) * x2 * ... * xn * x_(n+1)}
= ��[x2+...+xn+x_(n+1)=N,x2>=1,...,xn>=1,x_(n+1)>=1]{x2 * ... * xn * x_(n+1)}
+ ��[x1'+x2+...+xn+x_(n+1)=N,x1'>=1,x2>=1,...,xn>=1,x_(n+1)>=1]{x1' * x2 * ... * xn * x_(n+1)}
+ ��[x1'=1,N-n]{��[x2+...+xn+x_(n+1)=N-x1',x2>=1,...,xn>=1,x_(n+1)>=1]{x2 * ... * xn * x_(n+1)}}
ここで，先に注意したとおり，
��[x2+...+xn+x_(n+1)=N,x2>=1,...,xn>=1,x_(n+1)>=1]{x2 * ... * xn * x_(n+1)}
= (N+n-1)C(2n-1)　<-----　n の場合の帰納法の仮定
��[x1'+x2+...+xn+x_(n+1)=N,x1'>=1,x2>=1,...,xn>=1,x_(n+1)>=1]{x1' * x2 * ... * xn * x_(n+1)}
= (N+n)C(2n+1)　<-----　n+1 で N の場合の帰納法の仮定
��[x1'=1,N-n]{��[x2+...+xn+x_(n+1)=N-x1',x2>=1,...,xn>=1,x_(n+1)>=1]{x2 * ... * xn * x_(n+1)}}
= ��[x1'=1,N-n]{(N-x1'+n-1)C(2n-1)}　<-----　n の場合の帰納法の仮定
= (N+n-2)C(2n-1) + (N+n-3)C(2n-1) + ... + (2n+1)C(2n-1) + (2n)C(2n-1) + (2n-1)C(2n-1)
(2n-1)C(2n-1) = 1 = (2n)C(2n) なので，
= (N+n-2)C(2n-1) + (N+n-3)C(2n-1) + ... + (2n+1)C(2n-1) + (2n)C(2n-1) + (2n)C(2n)
nCr = (n-1)C(r-1) + (n-1)Cr なので，これを順次使用して，
= (N+n-2)C(2n-1) + (N+n-3)C(2n-1) + ... + (2n+1)C(2n-1) + (2n+1)C(2n)
= (N+n-2)C(2n-1) + (N+n-3)C(2n-1) + ... + (2n+2)C(2n)
= ...
= (N+n-2)C(2n-1) + (N+n-3)C(2n-1) + (N+n-3)C(2n)
= (N+n-2)C(2n-1) + (N+n-2)C(2n)
= (N+n-1)C(2n)
そこで，
P
= (N+n-1)C(2n-1) + (N+n)C(2n+1) + (N+n-1)C(2n)
= (N+n-1)C(2n-1) + (N+n-1)C(2n) + (N+n)C(2n+1)
= (N+n)C(2n) + (N+n)C(2n+1)
= (N+n+1)C(2n+1)
= ((N+1)+(n+1)-1)C(2(n+1)-1)
となり，n+1，N+1 でも成立します。
以上で，少々複雑ですが，
n = 2, 3, 4 は問題１：，問題２：，問題３：から成立。
n = 5 は，
N = n = 5 の場合は，明らかに成立。
N = 6 の場合は，n = 4, (n = 5 & N = 5) を基にして成立。
N = 7 の場合は，n = 4, (n = 5 & N = 6) を基にして成立。
N = 8 の場合は，n = 4, (n = 5 & N = 7) を基にして成立。
...
n = 6 も同様
...
と，順次示され，すべての n, N で成立します。
したがって，積の和は，(N+n-1)C(2n-1) になります。

(別解)
一度解答を提出したのですが，
水の流れさんからのメールによるヒント，結果の式の意味などを考えて，
次のような解法を思いつきました。

まず，積の和の場合の数的な意味を考えます。
x1 + x2 + ... + xn = N の自然数の解の組 (x1,x2,...,xn) は，
ボールを N 個，仕切りを n-1 個用意して，ボールを左から順番に横に一列に隙間をあけて並べ，
N-1 個の隙間から n-1 個を選びそこに n-1 個の仕切りを置いて，
左端と一番左の仕切りの間 A1，仕切りと仕切りの間 A2 〜 A_(n-1)，一番右の仕切りと右端の間 An に，
ボールを少なくとも 1 個以上あるようにした場合の，A1 〜 An にあるボールの個数です。
さて，A1 〜 An からボールを 1 個ずつ取り出すことを考えます。
このとき，Ak にあるボールをどの位置，Ak 内の左から何番目，から
取り出したかを意識すると，その場合の数が xk になります。
そして，積 x1 * x2 * ... * xn は，A1 〜 An からの取り出し方，
その和は，すべての取り出し方，になります。

この場合の数を，少し見方を変えてみます
今は,ボールを取り出すと考えましたが，ボールを選んで残し，選んだ以外のボールは取り除く，
と考えても，場合の数は同じです。
ここで，残されたボールには，Ak 内で左から何番目かが，
したがって，最初のボール及び仕切りの列全体の左から何番目かが，
分かっていることが重要です。仕切りも同様です。
つまり，n 個のボールと n-1 個の仕切りが，置かれた位置を意識して交互に並んでいます。

さて，この場合の数を別の方法で数えてみます。

最初に，ボールも仕切りもなく，それらを置く場所だけを考えます。
これは，横一列に並んだ N+n-1 個のスペースです。
このスペースから，n 個のボールを置くスペースと n-1 個の仕切りを置くスペースを選び，
ボールと仕切りを交互に並べます。
するとこれは，先ほどのものと同じで，１：１に対応しています！
この場合の数は，N+n-1 個のスペースから，ボール n 個，仕切り n-1 個，
合わせて 2n-1 個のスペースを選んでくればいいので，(N+n-1)C(2n-1) です。

そこで，求める解の積の和は (N+n-1)C(2n-1) になります。

(感想)
最初，思ったよりも手こずりました。
ただ結果がきれいなので，「もう少し簡単に導けないのかな．．．」と思っていたのですが，
水の流れさんからヒントも頂き，(別解)のようにできました (^^;
しかし，解の積の和がこんなにきれいな形になるとは以外でした。
楽しい問題をありがとうございます。

NO2「新俳人澄朝」1/22 17時34分受信 更新2/8

<コメント：コンカイノ問題には楽しみながら苦労しました。問い�@から問い�Aへの移行，推定までは楽でしたが、その証明で丸三日間費やしました。組合せＣの記号の性質を
力業（ちからわざ）で利用しましたが、他の皆さんの解答が楽しみです。＞

NO3「kashiwagi」 2/03 08時08分受信 更新2/8

＜コメント：お世話になります。今回の問題は非常に面白いですね。計算は大変でしたが、 やりながら数学のもつ規則性にひきつけられ充分に堪能させて頂きました。但し、 ｋ⁴の値を求めるのには苦労致しました。ヒントのような形でこれこれを使えと出して も良かったのでは・・・。 単純な問題の奥にこの様な美しい規則性が隠れているとは・・・＞

219回解答

問1.

各々の積の和をSとして、Nの値に応じて書き出していくと、

N＝2　S₂＝1×1

N＝3　S₃＝1×2　+　2×1

N＝4　S₄＝1×3　+　2×2　+　3×1

N＝5　S₅＝1×4　+　2×3　+　3×2　+　4×1

N＝6　S₆＝1×5　+　2×4　+　3×3　+　4×2　＋5×1

これらより、Nの時は以下の様に推定できる。

S_N＝1×（N-1）　+　2×（N-2）　+　・・・・・・・・　+　（N-2）×2　＋（N-1）×1　＝

問2

問1と同様に書き出していくと、

N＝3　S₃＝1×1×1

N＝4　S₄＝1×1×2　+　1×2×1　+　2×1×1

N＝5　S₅＝1×1×3　+　1×2×2　+　1×3×1　+　2×1×2　+　2×2×1　+　3×1×1

これらより、Nの時は以下の様に推定できる。

S_N＝1×1×（N-2）　+1×2×（N-3）　+　1×3×（N-4）　+・・・・・・・・・・・・・・　+　

1×（N-4）×3　＋1×（N-3）×2　+　1×（N-2）×1　+

2×1×（N-3）　+　2×2×（N-4）　+・・・・・・・・・・+　2×（N-4）×2　+2×（N-3）×1　+

3×1×（N-4）　+3×2×（N-5）　+・・・・・・・・・・+　3×（N-5）×2　+3×（N-4）×1　+

･･･････････････････････････・・・・・・・・・・・・・・・・・

+（N-4）×1×3　+　（N-4）×2×2　+（N-4）×3×1

+（N-3）×1×2　+　（N-3）×2×1　

+（N-2）×1×1

となり、各々の項の規則性より縦に加えて計算すると新しい規則性がでてくる。

　　S₁＝1×1×（N-2）　+　2×1×（N-3）　+　3×1×（N-4）　+・・・・・・・・・・・・+

　　　　　（N-4）×1×3　+　（N-3）×1×2　+　（N-2）×1×1　＝

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　＝

　　　　

同様の計算を各々縦系列で行うと、

S₂＝　　これより推定で

S_N-2＝　　　

となる。ここで問題はｋ⁴であるが、

よりN(N＋1)(N+2)(N+3)(N+4)

また、　　となる。

以上の事を使い計算すると、

S_N-2＝　　となる。

問3.

問1及び問2より容易に類推される。尚、各々の分子の6と120は3！と5！であるから、

　が求めるものである。

問4.

以上より、

　が求めるものである。

皆さん、答えがわかったら、一部でも構いませんから、解答とペンネームを添えて、
メールで送ってください。待っています。