平成１９年９月２日
[流れ星]
第1９５回数学的な応募問題解答
＜解答募集期間：８月１２日～９月２日
［分配問題］
先日生徒から、次のような分配問題の質問を受けました。一般の場合まで考えて作問をしました。
問題１：1から５までの番号のついた５個のボールを、Ａ，Ｂの２つの箱に、どの箱にも少なくとも１個のボールが入るように入れる入れ方は何通りあるか。
問題２：1から５までの番号のついた５個のボールを、Ａ，Ｂ，Ｃの３つの箱に、どの箱にも少なくとも１個のボールが入るように入れる入れ方は何通りあるか。
問題３：1から５までの番号のついた５個のボールを、Ａ，Ｂ，Ｃ，Ｄの４つの箱に、どの箱にも少なくとも１個のボールが入るように入れる入れ方は何通りあるか。
問題４：一般に、異なるｍ個のボールを、異なるｎ個の箱に、どの箱にも少なくとも１個のボールが入るように入れる入れ方は何通りあるかを、包除の原理を用いて、ｍ、ｎと和の記号シグマを用いて表せ。ただし、ｍ≧ｎとする。
問題５：問題４で得た式を用いて、1から６までの番号のついた６個のボールを、Ａ，Ｂ，Ｃ，Ｄ，Ｅの５つの箱に、どの箱にも少なくとも１個のボールが入るように入れる入れ方は何通りあるか。
＜水の流れ：第１８回の応募問題を「本を棚に入れる問題」を参考にしても構いません。＞
ＮＯ１「uchinyan」08/12 15時37分受信
08/15 13時26分受信 更新9/2
第１９５回数学的な応募問題
［分配問題］残暑お見舞い申し上げます。
これを書いている時点では毎日暑いですが，公表される頃には少しは涼しくなっているでしょうか (^^;
問題1
5 個のボールを空箱があってもいいように 2 個の箱に入れるのは，2^5 = 32 通り。
このうちの空箱がある場合の 2 通りを引いて，求めるのは 32
- 2 = 30 通り。
問題2
5 個のボールを空箱があってもいいように 3 個の箱に入れるのは，3^5 通り。
このうち，
少なくとも 1 個空箱がある場合は 3C1 * 2^5 通り
少なくとも 2 個空箱がある場合は 3C2 * 1^5 通り
少なくとも 3 個空箱がある場合は 0 通り <----- これはありえません！
なので，
全体の 3^5 通りから，少なくとも 1 個空箱がある場合の 3C1 * 2^5 通りを引きますが，
これでは，少なくとも 2 個空箱がある場合を 2 回引いてしまうので，これを足します。
これは，例えば，空箱が A, B の場合，引き算で，
少なくとも 1 個の空箱を A とした場合に，もう一つの空箱が B となる場合
少なくとも 1 個の空箱を B とした場合に，もう一つの空箱が A となる場合
の 2C1 = 2 回を数えて引いているからです。
そこで，結局，
3^5 - 3C1 * 2^5 + 3C2 * 1^5 = 243 - 96 + 3 = 150 通り
この引いたり足したりで余分な場合の数を相殺するのが，包除の原理ですね。
問題3
全く同様に，
5 個のボールを空箱があってもいいように 4 個の箱に入れるのは，4^5 通り
少なくとも 1 個空箱がある場合は 4C1 * 3^5 通り
少なくとも 2 個空箱がある場合は 4C2 * 2^5 通り
少なくとも 3 個空箱がある場合は 4C1 * 1^5 通り
なので，
全体の 4^5 通りから，少なくとも 1 個空箱がある場合の 4C1 * 3^5 通りを引きます。
しかしこれでは，少なくとも 2 個空箱がある場合を 2 回引いてしまうので，これを足します。
これは，例えば，空箱が A, B の場合，引き算で，
少なくとも 1 個の空箱を A とした場合に，後一つの空箱が B となる場合
少なくとも 1 個の空箱を B とした場合に，後一つの空箱が A となる場合
の 2C1 = 2 回を数えて引いているからです。
しかし足した後，今度は，少なくとも 3 個空箱がある場合が復活してしまうので，これを引きます。
これは，例えば，空箱が A, B, C の場合，最初の引き算で，
少なくとも 1 個の空箱を A とした場合に，後二つの空箱が B, C となる場合
少なくとも 1 個の空箱を B とした場合に，後二つの空箱が C, A となる場合
少なくとも 1 個の空箱を C とした場合に，後二つの空箱が A, B となる場合
の 3C1 = 3 回を数えて引いていますが，2 回目の足し算で，今度は，
少なくとも 2 個の空箱を A, B とした場合に，後一つの空箱が C となる場合
少なくとも 2 個の空箱を B, C とした場合に，後一つの空箱が A となる場合
少なくとも 2 個の空箱を C, A とした場合に，後一つの空箱が B となる場合
の 3C2 = 3 回を数えて足しており，相殺して少なくとも
3 個空箱がある場合は残っているからです。
そこで，結局，包除の原理から，
4^5 - 4C1 * 3^5 + 4C2 * 2^5 - 4C3 * 1^5 = 1024 - 972 + 192 - 4 = 240 通り
問題4
全く同様に，
m 個のボールを空箱があってもいいように n 個の箱に入れるのは，n^m 通り
少なくとも 1 個空箱がある場合は nC1 * (n-1)^m
通り
少なくとも 2 個空箱がある場合は nC2 * (n-2)^m
通り
．．．
少なくとも k 個空箱がある場合は nCk * (n-k)^m 通り
．．．
少なくとも (n-2) 個空箱がある場合は nC(n-2) * 2^m 通り
少なくとも (n-1) 個空箱がある場合は nC(n-1) * 1^m 通り
ここで，k 個だけ空箱がある場合の場合の数が，足したり引いたりでどうなるのか調べます。
例えば，A1, A2, ..., Ak の空箱がある場合は，
m 個のボールを空箱があってもいいように n 個の箱に入れる場合には，1 = kC0 回含まれています。
少なくとも 1 個空箱がある場合には，その 1 箱を A1 ～ Ak のどの 1 箱にするかで，kC1 回含まれています。
少なくとも 2 個空箱がある場合には，その 2 箱を A1 ～ Ak のどの 2 箱にするかで，kC2 回含まれています。
．．．
少なくとも p 個空箱がある場合には，その p 箱を A1 ～ Ak のどの p 箱にするかで，kCp 回含まれています。
．．．
少なくとも (k-1) 個空箱がある場合には，その (k-1)
箱を A1 ～ Ak
のどの (k-1) 箱にするかで，kC(k-1) 回含まれています。
少なくとも k 個空箱がある場合には，その k 箱を A1 ～ Ak のどの k 箱にするかで，kCk 回含まれています。
そこで，これらの含まれる回数を，今までのように足す引くを行って計算してみると，
kC0 - kC1 + kC2 - ... + (-1)^p * kCp + ... +
(-1)^(k-1) * kC(k-1) + (-1)^k * kCk
= ∑[p=0,k] (-1)^p * kCp
= (1 + (-1))^k <----- 二項定理を使用
= 0
つまり，足す引くを行えば，k 個空箱がある場合の場合の数が確かに相殺していることが分かります。
k は，1 ～ n-1 の任意でよいので，
足す引くの包除の原理によって，空箱がない場合の場合の数が求められていることが分かります。
そこで，求める場合の数は
n^m - nC1 * (n-1)^m + nC2 * (n-2)^m - ... + (-1)^k * nCk * (n-k)^m + ...
+ (-1)^(n-2) * nC(n-2) * 2^m
+ (-1)^(n-1) * nC(n-1) * 1^5
= ∑[k=0,n-1] (-1)^k * nCk * (n-k)^m 通り
(別解)
包除の原理を，広く，足す引くによって余分な場合の数を相殺すること，ととらえて考えましたが，
より狭い意味で，次のような公式ととらえることも多いようです。
今，集合 P の要素の数を n(P)，P と Q の合併集合を P∪Q，共通部分を P∩Q と書くと，
n(P1∪P2∪...∪Pi)
= Σ[j1=1,i] n(Pj1) - Σ[j1,j2の組合せ] n(Pj1∩Pj2) +
Σ[j1,j2,j3の組合せ] n(Pj1∩Pj2∩Pj3)
+ ... + (-1)^(k-1) * Σ[j1,j2,...,jkの組合せ] n(Pj1∩Pj2∩...∩Pjk) + ...
+ (-1)^(i-1) * n(P1∩P2∩...∩Pi)
= Σ[k=1,i]{(-1)^(k-1) * Σ[j1,j2,...,jkの組合せ] n(Pj1∩Pj2∩...∩Pjk)}
が成立します。これは，次のようにして，数学的帰納法で証明できます。
・i =
1 の場合
これは明らか。
・i =
2 の場合
これも，ベン図などを描いて考えれば，P1∪P2 の要素数は，P1
の要素数と P2 の要素数から
重複している共通部分 P1∩P2 の要素数を引けばいいので，
左辺(2) = n(P1∪P2) = n(P1) + n(P2) - n(P1∩P2) = 右辺(2)
で，成立します。
・i 以下で成立したとして i+1 の場合を考えます。
左辺(i+1)
= n(P1∪P2∪...∪Pi+1)
= n((P1∪P2∪...∪Pi)∪Pi+1)
P1∪P2∪...∪Pi と Pi+1 に i = 2 の場合を適用して
= n(P1∪P2∪...∪Pi) + n(Pi+1) - n((P1∪P2∪...∪Pi)∩Pi+1)
ここで，最後の項に集合演算の分配法則を適用して
= n(P1∪P2∪...∪Pi) + n(Pi+1) - n((P1∩Pi+1)∪(P2∩Pi+1)∪...∪(Pi∩Pi+1))
i 項の場合の帰納法の仮定より，
n(P1∪P2∪...∪Pi)
= Σ[k=1,i]{(-1)^(k-1) * Σ[j1,j2,...,jkの組合せ] n(Pj1∩Pj2∩...∩Pjk)}
ここで，後で使うので，この式の右辺には Pi+1 は含まれていないことに注意しておきます。
= Σ[k=1,i]{(-1)^(k-1) * Σ[Pi+1を含まないj1,j2,...,jkの組合せ] n(Pj1∩Pj2∩...∩Pjk)}
一方，やはり，i 項の場合の帰納法の仮定より，
n((P1∩Pi+1)∪(P2∩Pi+1)∪...∪(Pi∩Pi+1))
= Σ[k=1,i]{(-1)^(k-1) * Σ[j1,j2,...,jkの組合せ] n((Pj1∩Pi+1)∩(Pj2∩Pi+1)∩...∩(Pjk∩Pi+1))}
= Σ[k=1,i]{(-1)^(k-1) * Σ[j1,j2,...,jkの組合せ] n(Pj1∩Pj2∩...∩Pjk∩Pi+1)}
= Σ[k=1,i]{(-1)^(k-1) * Σ[j1,j2,...,jkの組合せでjk=i+1]
n(Pj1∩Pj2∩...∩Pjk∩Pi+1)}
ここで，Pj1∩Pj2∩...∩Pjk∩Pi+1 は，j1,j2,...,jk,jk+1
のうちで jk+1 = i+1 ですが，
j1,j2,...,jk,jk+1 の和は組合せの和なので，jk+1 = i+1 だけで Pi+1 の取込みは十分なこと，
つまり，j1 = i+1 とかは j1 <->
jk+1 と置き換えれば十分でわには寄与しないこと，
に注意すると，
n((P1∩Pi+1)∪(P2∩Pi+1)∪...∪(Pi∩Pi+1))
= Σ[k=1,i]{(-1)^(k-1) * Σ[Pi+1を含むj1,j2,...,jk+1の組合せ] n(Pj1∩Pj2∩...∩Pjk+1)}
と書いて十分です。
そこで，これらを 左辺(i+1) に代入して，
左辺(i+1)
= n(P1∪P2∪...∪Pi) + n(Pi+1) - n((P1∪P2∪...∪Pi)∩Pi+1)
= Σ[k=1,i]{(-1)^(k-1) * Σ[Pi+1を含まないj1,j2,...,jkの組合せ] n(Pj1∩Pj2∩...∩Pjk)}
+ n(Pi+1)
- Σ[k=1,i]{(-1)^(k-1) * Σ[Pi+1を含むj1,j2,...,jk+1の組合せ] n(Pj1∩Pj2∩...∩Pjk+1)}
n(Pi+1) を第3項の k = 0 として吸収し，第3項の k = i を分離すると
= Σ[k=1,i]{(-1)^(k-1) * Σ[Pi+1を含まないj1,j2,...,jkの組合せ] n(Pj1∩Pj2∩...∩Pjk)}
- Σ[k=0,i-1]{(-1)^(k-1) * Σ[Pi+1を含むj1,j2,...,jk+1の組合せ] n(Pj1∩Pj2∩...∩Pjk+1)}
- (-1)^(i-1) * n(P1∩P2∩...∩Pi∩Pi+1)
第2項の k を k-1 に置き換えて
= Σ[k=1,i]{(-1)^(k-1) * Σ[Pi+1を含まないj1,j2,...,jkの組合せ] n(Pj1∩Pj2∩...∩Pjk)}
- Σ[k=1,i]{(-1)^(k-2) * Σ[Pi+1を含むj1,j2,...,jkの組合せ] n(Pj1∩Pj2∩...∩Pjk)}
+ (-1)^i * n(P1∩P2∩...∩Pi∩Pi+1)
= Σ[k=1,i]{(-1)^(k-1) * Σ[Pi+1を含まないj1,j2,...,jkの組合せ] n(Pj1∩Pj2∩...∩Pjk)}
+ Σ[k=1,i]{(-1)^(k-1) * Σ[Pi+1を含むj1,j2,...,jkの組合せ] n(Pj1∩Pj2∩...∩Pjk)}
+ (-1)^i * n(P1∩P2∩...∩Pi∩Pi+1)
このとき，第1項と第2項とを合わせて，初めてすべての項 P1 ～ Pi+1 の組合せになるので，
= Σ[k=1,i]{(-1)^(k-1) * Σ[j1,j2,...,jkの組合せ] n(Pj1∩Pj2∩...∩Pjk)}
+ (-1)^i * n(P1∩P2∩...∩Pi∩Pi+1)
= Σ[k=1,i+1]{(-1)^(k-1) * Σ[j1,j2,...,jkの組合せ] n(Pj1∩Pj2∩...∩Pjk)}
= 右辺(i+1)
これで，i+1 の場合も成立することが証明できました。
さて，この集合に関する包除の原理を使って，問題4を考えてみましょう。
今，集合 Pi を少なくとも箱 Ai が空箱である場合の事象の集合とします。
すると，
P1∪P2∪...∪Pn = 少なくとも空箱が一つ以上ある場合の事象の集合
ただし，すべての箱が空箱になることはありえないので，
n(P1∩P2∩...∩Pn) = 0
です。そこで，求める場合の数である，空箱が一つもない場合の事象の個数は，
求める場合の数 = 全体 - n(P1∪P2∪...∪Pn) = n^m - n(P1∪P2∪...∪Pn)
そこで，n(P1∪P2∪...∪Pn) を求めればいいことになります。
これは，空箱の存在は Pi に関して対称なことに注意すると，k
not= n として，
Σ[i1,i2,...,ikの組合せ]
n(Pi1∩Pi2∩...∩Pik) = nCk *
n(P1∩P2∩...∩Pk) = nCk *
(n-k)^m
そこで，n(P1∩P2∩...∩Pn) = 0 だったので，
n(P1∪P2∪...∪Pn) = Σ[k=1,n-1]{(-1)^(k-1) * nCk * (n-k)^m}
求める場合の数 = n^m - n(P1∪P2∪...∪Pn)
= n^m - Σ[k=1,n-1]{(-1)^(k-1) * nCk
* (n-k)^m}
= ∑[k=0,n-1] (-1)^k * nCk * (n-k)^m 通り
になります。
問題5
問題4の結果を使用して，m = 6，n = 5 とすればいいので，
∑[k=0,4] (-1)^k * 5Ck * (5-k)^6
= 5^6 - 5C1 * 4^6 + 5C2 * 3^6 - 5C3 * 2^6 + 5C4 * 1^6
= 15625 - 20480 + 7290 - 640 + 5
= 1800 通り
(考察)
この問題は，次のように考えることもできます。
今，m 個のボールを，n 個の箱に，どの箱にも少なくとも１個のボールが入るように入れる入れ方を a(m,n) とします。
すると，
m 個のボールを空箱があってもいいように n 個の箱に入れるのは，n^m 通り
1 個だけ空箱がある場合は nC1 * a(m,n-1) 通り
2 個だけ空箱がある場合は nC2 * a(m,n-2) 通り
．．．
k 個だけ空箱がある場合は nCk * a(m,n-k) 通り
．．．
(n-2) 個だけ空箱がある場合は nC(n-2) *
a(m,2) 通り
(n-1) 個だけ空箱がある場合は nC(n-1) *
a(m,1) 通り
ここで注目すべきは，空箱の個数に重複がないことです。
そこで，空箱がない場合は，単に，全体からそれぞれの空箱がある場合を引けばいいので，
a(m,n) = n^m - ∑[k=1,n-1] nCk * a(m,n-k)
また明らかに，
a(m,1) = 1
です。これは，漸化式になっており，これを使っても，随時場合の数が求められます。
しかし，一般解を直接に求めるのは難しそうです。取り敢えず，順次求めてみると
a(m,1) = 1
a(m,2) = 2^m - 2C1 * 1 = 2^m - 2C1 * 1^m
a(m,3) = 3^m - 3C1 * (2^m - 2C1)- 3C2 * 1 = 3^m - 3C1 * 2^m + 3 = 3^m - 3C1 *
2^m + 3C2 * 1^m
a(m,4) = 4^m - 4C1 * (3^m - 3C1 * 2^m + 3C2)- 4C2 * (2^m - 2C1) - 4C3 * 1
= 4^m - 4C1 * 3^m + (4C1 * 3C1 - 4C2) * 2^m - (4C1 * 3C2 - 4C2 * 2C1 - 4C3) *
1^m
= 4^m - 4C1 * 3^m + 6 * 2^m - 4 * 1^m
= 4^m - 4C1 * 3^m + 4C2 * 2^m - 4C3 * 1^m
...
となり，確かに，
a(m,n) = ∑[k=0,n-1] (-1)^k * nCk
* (n-k)^m
となっていそうです。そこで，n に関する数学的帰納法で確かめてみましょう。
・n = 1 の場合
左辺(1) = a(m,1) = 1
右辺(1) = ∑[k=0,0] (-1)^k * 1Ck * (1-k)^m = (-1)^0 * 1C0
* (1-0)^m = 1
で，成立します。
・n 以下で成立したとして，n+1 の場合を考えます。
左辺(n+1)
= a(m,n+1)
a(m,n+1) に漸化式を使って，
= (n+1)^m - ∑[k=1,n] (n+1)Ck * a(m,n+1-k)
a(m,n+1-k) に帰納法の仮定を使うと，
= (n+1)^m - ∑[k=1,n] (n+1)Ck * {∑[p=0,n-k] (-1)^p * (n+1-k)Cp * (n+1-k-p)^m}
= (n+1)^m - ∑[k=1,n] ∑[p=0,n-k] (-1)^p * (n+1)Ck * (n+1-k)Cp * (n+1-k-p)^m
ここで，k+p = q とおき，k と p の和を q と k の和に置き換えます。
= (n+1)^m - ∑[q=1,n] ∑[k=1,q] (-1)^(q-k) * (n+1)Ck * (n+1-k)C(q-k) * (n+1-q)^m
= (n+1)^m - ∑[q=1,n] (-1)^q * (n+1-q)^m * {∑[k=1,q] (-1)^k * (n+1)Ck *
(n+1-k)C(q-k)}
ここで，
(n+1)Ck * (n+1-k)C(q-k)
= (n+1)!/k!(n+1-k)! * (n+1-k)!/(n+1-q)!(q-k)!
= (n+1)!/k! * 1/(n+1-q)!(q-k)!
= (n+1)!/(n+1-q)!q! * q!/k!(q-k)!
= (n+1)Cq * qCk
なので，(n+1)Cq を k の和の外に出して，
左辺(n+1)
= (n+1)^m - ∑[q=1,n] (-1)^q * (n+1-q)^m * (n+1)Cq *
{∑[k=1,q] (-1)^k * qCk}
さらに，
∑[k=1,q] (-1)^k * qCk
= ∑[k=0,q] (-1)^k * qCk - 1
二項定理を使って
= (1 + (-1))^q - 1
= 0 - 1
= -1
なので，
左辺(n+1)
= (n+1)^m - ∑[q=1,n] (-1)^q * (n+1-q)^m * (n+1)Cq *
(-1)
= (n+1)^m + ∑[q=1,n] (-1)^q * (n+1)Cq * (n+1-q)^m
= ∑[q=0,n] (-1)^q * (n+1)Cq * (n+1-q)^m
= 右辺(n+1)
で，成立します。
以上より，確かに，
a(m,n) = ∑[k=0,n-1] (-1)^k * nCk
* (n-k)^m
が成立します。
第１８回の応募問題「本を棚に入れる問題」における解法は，この方向ですね。
(感想)
包除の原理は，確かに便利で，他の問題でもお世話になったと思います。
いい復習になりました。
ＮＯ２「πＰ」 08/13 23時49分受信 更新9/2
問い１：ボールは全て異なっていることを考え一つ目のボールはA Bの２通り・・・二個目はA Bの二通り・・とするとこれらは２の５乗通りになりますが条件より全てA あるいは Bに入ってしまうことはさけなければならないので結局2^5-2＝30通り
問い2：このような入れ方の総数をf(3)とするとf(3)は全ての入れ方から（１）全て箱AあるいはBあるいはCに入ってしまう
（２）ボールが箱AとB BとC CとAに入ってしまう（これは箱の選び方が3C2からわかります） を引けばいいことになります
つまりf(3)=3^5-（3C2・ｆ（2)+3)
つまりは１５０通り ただしf(2)は問題１の数と同じです
問い３：同様にして全ての入れ方から（１）４つのうち一つにしか入らない
（２）４つのうち３つにしか入らない
（３）４つのうち２つにしか入らない
場合を引けばいいことになります
総数は4^5で （１）はいうまでもなく４通り （２）は箱の選び方が4C3で入れ方はf(3)です （３）は箱の選び方が4C2で入れ方はf(2)です
よってf(4)=4^5-(4+4C3・f(3)+4C2・ｆ(2)）つまり２４０通り
問い４：漸化式はつくれそうです
まず箱はn個でボールがm個ですからこれまでの議論で考えて見ます
求める数をf(m)とします するとf(m)は入れ方の総数n^mから（一つめのボールは１～ｎまでのｎ通り 二つ目は１～ｎ・・・）
１：箱一つに全て入る
２：n個の箱の内二つに入る
３：・・・・・
・
・
・
ｎ-1：n個の箱のうちn-1個に入る
場合を引けばよくてそれらをそれぞれf(1) f(2) f(3)・・・ｆ（m-1)とします
箱の選び方も考えておくと
f(m)=n^m-(nCn-1・f(m-1)+nCn-2・f(m-2)+・・・ｎC2f(2)+ｎC1f(1))
という漸化式を得られます これをΣを用いると
f(m)=n^m-Σ（k=1⇒m-1)【nCk・ｆ（ｋ）】 一般項なんとか出そうとしましたが無理でした
ＮＯ３「kashiwagi｣08/16 08時49分受信 更新9/2
お世話になります。今回の問題は当初は自分なりに考えて解いてみたら
以外に易しいなと思い、どんな風に解いているのかとヒントを見てみました。 正にがーんと頭を殴られました。そうです、区別のつかない球の計算をして いたのです。 そこで一念発起、再度取り組みました。但し、問４にはてこずりました。包除
の定理・・・・？うーんーと数日考えた結果、やっと思い当たったというのが本当 のところです。数が多くなる場合の威力に驚嘆致しました。
195回問題
問1.題意より異なる箱A,Bに異なる球を入れる組み合わせは以下の表の様になる。
|
|
A |
B |
|
① |
4 |
1 |
|
② |
3 |
2 |
|
③ |
2 |
3 |
|
④ |
1 |
4 |
①：
②：
③：②と同じ
④：①と同じ 以上より求めるものは30通り
|
|
A |
B |
C |
|
① |
3 |
1 |
1 |
|
② |
1 |
3 |
1 |
|
③ |
1 |
1 |
3 |
|
④ |
2 |
2 |
1 |
|
⑤ |
2 |
1 |
2 |
|
⑥ |
1 |
2 |
2 |
問2.問1と同様にして
①：
、②も③も同じ
④：
、⑤も⑥も同じ
以上より求めるものは150通り
|
|
A |
B |
C |
D |
|
① |
2 |
1 |
1 |
1 |
|
② |
1 |
2 |
1 |
1 |
|
③ |
1 |
1 |
2 |
1 |
|
④ |
1 |
1 |
1 |
2 |
問3.上記と全く同様にして
①：
②～④も同じであるから
求めるものは240通り
問4.一般数の場合はこれまでのやり方が通用しないので、包除の定理の適用を試みる。
即ち、これまでと異なり、空きの箱があっても良いものとする。すると題意より
通りとなる。
これから空き箱の場合を引けば良い。そこで、異なるｍ個の球を異なるｎ個の箱に入れる場合を
とすると、
①空箱がｎ-1個の場合は一つの箱に全ての球が集中するので
②空箱がｎ-2個の場合は2箱に集中するので
即ち、＝-(++・・・・・・・・+
)
＝-
となる。
問5.上記式にｍ＝6、ｎに1～5を順次代入し、段階ごとに計算すると、1800通りとなる。
因みに、これくらいの数では問3.までの表作成でやってみると、
となる。
ＮＯ４「新俳人澄朝」8/23
15時57分受信 更新9/2
ＮＯ５「Toru」 08/18 09時30分受信 更新9/2
問題１
１～５のボールがそれぞれAかBにはいり、全てA あるいは全てBをのぞいて
2^5-2=30 (とおり)
問題２
１～５のボ－ルがA～Cのいずれかとして3^5 =243
問題１よりAB, BC, CAにはいってしまうのがそれぞれ30とおり
全てA or B or Cに入るのはそれぞれ1 とおりで
243- 3x30-3x1=150 （とおり）
問題３ 同様に考えて、
4^5 - 4C3 x 150 - 4C2 x 30 － 4C1 x 1 =240 （とおり）
問題4
箱をA1～Anとする。 ボールの入れ方m^nのうち Akにボールが入らないものの集合
をAkとすると 求める数は cは補集合として
｜c(A1∪A2∪---∪An)｜とあらわせれるが、包除の原理から
｜c(A1∪A2∪---∪An)｜=｜U｜―｜A1∪A2∪---∪An｜=｜U｜―Σ｜Ai｜＋Σ｜Ai
∩Aj｜―Σ｜Ai∩Aj∩Ak｜＋----±｜A1∩A2∩----∩An｜
(ここでUは全体集合 i<j<kなど)
｜U｜=m^n
｜Ai｜はAi以外に入れればよいから(n-1)^m ,Aiの選び方はnC1とおり
｜Ai∩Aj｜はAi,Aj以外に入れればよく(n-2)
^m ,Ai,Ajの選び方はnC2とおり
｜Ai∩Aj∩Ak｜はAi,j,Ak以外に入れればよく(n-3)^mで同様にnC3とおり
以下同様で
（上式）=n^m-nC1 x (n-1)^m+nC2 x (n-2)^m-nC3 x
(n-3)^m+------±nCn x 0
=Σ（k=0～n-1）(-1)^k nCk
(n-k)^m
問題５
問題４でm=6 n=5 として
5^6-5C1x4^6+5C2x3^6-5C3x2^6+5C4x1^6=1800 （とおり）
毎日、とんでもない暑さですが、お元気にお過ごしでしょうか。毎回面白い問題で楽
しませてもらっています。ペンネーム Toru
ＮＯ６「kasama」 09/01 10時43分受信
更新9/2
今回も面白い問題だと思います。いろいろ考えてみたのですが、出題者の意図したやり方でできませんでした。もう少し考えてみます。ただ、このように考えるのも一つの方法かと思い解答を送ります。
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
【問題４】 n個の同じ箱にm個のボールを入れる場合数は第2種スターリングですが、その一般項Snmは、 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
【問題５】 n=5、m=6を上記の式に、代入すると、 |
(-1)
(-1)
