m,n:2以上の自然数、x_1,x_2,…,x_nを0以上m以下の整数とし、S=x_1+x_2+…+x_nとする。
(1)S=2mとなるような(x_1,x_2,…,x_n)の組数を求めよ。 (2)S=3mとなるような(x_1,x_2,…,x_n)の組数を求めよ。
(1)は、x_1,x_2,…,x_nを0以上m以下の制限をなくした場合の(x_1,x_2,…,x_n)の組数から、 x_k>mとなる場合の組数を引けば良いので、 x_i=y_i(i≠k)、y_k=x_k-m-1とおいて、 y_1+y_2+…+y_n=m-1を満たす0以上m以下の(y_1,y_2,…,y_n)の組数を求めればよい。
C[n,k]=n!/(k!*(n-k)!)と書くことにすると、x_kの選び方はn通りあるので、 C[2m+n-1,n-1]-n*C[m+n-2,n-1]
(2)は、x_1,x_2,…,x_nを0以上m以下の制限をなくした場合の(x_1,x_2,…,x_n)の組数から、 「x_k>2m」…[A]または、「x_p>mかつx_q>m」…[B]となる場合の組数を引けば良いので、
[A]のとき (1)と同じでn*C[m+n-2,n-1]
[B]のとき x_i=y_i(i≠p,i≠q,p≠q)、y_p=x_p-m-1,y_q=x_q-m-1とおいて、 y_1+y_2+…+y_n=m-2を満たす0以上m以下の(y_1,y_2,…,y_n)の組数を求めればよい。 C[n,2]*C[m+n-3,n-1]
全体から[A]と[B]を引いて
C[3m+n-1,n-1]-n*C[m+n-2,n-1]-C[n,2]*C[m+n-3,n-1]
としたのですが、(2)は数値を入れて確認すると合っていそうなのですが、 (3)は値を入れてみると答えが違いそうです。 何か考え方がおかしいのでしょうか?
|
No.80359 - 2022/01/17(Mon) 19:02:17
| ☆ Re: 負でない整数の組数2 / IT | | | No.80361 - 2022/01/17(Mon) 20:24:05 |
| ☆ Re: 負でない整数の組数2 / 大西 | | | (2)⇒(1) (3)⇒(2) の間違いでした。
(1)は数値を入れて確認すると合っていそうなのですが、 (2)は値を入れてみると答えが違いそうです。
|
No.80363 - 2022/01/17(Mon) 21:57:12 |
| ☆ Re: 負でない整数の組数2 / IT | | | > (2)は値を入れてみると答えが違いそうです。
たしかに合いませんね。 簡単な m=2,n=3 の場合で 何が考慮漏れか考えたらどうですか?
3m=6 全体は (6,0,0) 3通り (5,1,0) 6通り (4,2,0) 6通り (4,1,1) 3通り (3,3,0) 3通り (3,2,1) 6通り (2,2,2) 1通り 計28 通り
除外すべきものは、 条件を満たすのは(2,2,2) 1通りなので、それ以外。 [A],[B] では除外しきれてない。
|
No.80365 - 2022/01/17(Mon) 22:55:11 |
| ☆ Re: 負でない整数の組数2 / 大西 | | | > (6,0,0) 3通り > (5,1,0) 6通り > (4,2,0) 6通り > (4,1,1) 3通り > (3,3,0) 3通り > (3,2,1) 6通り > (2,2,2) 1通り 計28 通り > >除外すべきものは?
下の1通り以外はすべて除外しないといけないですね。 [A]は除外できていると思うのですが、[B]が何か足りていない 気がしています。
|
No.80366 - 2022/01/17(Mon) 23:23:54 |
| ☆ Re: 負でない整数の組数2 / IT | | | 除外すべきものとして、1つだけmより大となる場合もあるのでは? 上の例でいえば(3,2,1) など
|
No.80368 - 2022/01/18(Tue) 00:09:02 |
| ☆ Re: 負でない整数の組数2 / 大西 | | | 全体から「x_k>m」を引いて「x_p>mかつx_q>m」を加えれば良いのでしょうか?
全体から[A]をやめて[B]と(1)で出て来たn*C[m+n-2,n-1]をn*C[2m+n-2,n-1]に変えたものを引いたら合っているような気がします。
|
No.80372 - 2022/01/18(Tue) 07:47:28 |
| ☆ Re: 負でない整数の組数2 / IT | | | > 全体から「x_k>m」を引いて「x_p>mかつx_q>m」を加えれば良いのでしょうか?
そうですね、条件を満たさないのは、 ちょうど1つの項がmより大きい場合と、 ちょうど2つの項がmより大きい場合 です。 例えば x_1>mかつx_2>m は、x_1>mとx_2>mでダブって引かれますから戻さないといけませんね。
|
No.80380 - 2022/01/18(Tue) 17:50:19 |
| ☆ Re: 負でない整数の組数2 / 大西 | | | S=4m,5m・・・でも同じ方法で求められますね。 包除原理みたいな感じですね。
ありがとうございました。
|
No.80392 - 2022/01/18(Tue) 21:59:26 |
|