◆東京都 四年寝太郎 さんからの解答。
【問題１】
問題３の計算より２n−１通り。
【問題２】
問題３の計算より３n−２n通り。
【問題３】
一人も属さないグループがあっても良いとすると、
「一人目がどのグループに入るかがｍ通り。
・・・
ｎ人目がｍ通り。
トータルでｍn通り。」
これは、問題にある条件(１人も属さないグループがあってはならない)に当てはめれば、
１〜ｎグループでの総数の合計。
よって、これから１〜(ｎ−１)グループでの総数の合計を引けば、条件を満たす総数(何通りか)が求まるので、
(ｍn−(ｍ−１)n)通り。
◆東京都 千葉 英伸 さんからのコメント。
３人の生徒Ａ，Ｂ，Ｃを２グループに分ける場合を考えてみましょう。
分け方は、
（Ａ） （Ｂ，Ｃ）
（Ｂ） （Ａ，Ｃ）
（Ｃ） （Ａ，Ｂ）
の３通りしかありません。
四年寝太郎さんの解答だと、７通りになってしまいます。
【コメント】
河野 進さんから 『ｎ！』 問題との関連が指摘されましたので、そちらもご覧ください。
◆東京都 合屋 さんからの解答。
【問題１】 ２つのグループのとき
２つのグループをＡ、Ｂとする。
Ａに属する人数は１〜ｎ−１人
Ａ＝１の時 組み合せは ｎ通り
Ａ＝２の時 組み合せは nＣ2通り
これをＡ＝ｎ−１まで求め集計する。
ここでＡ＝１とＢ＝ｎ−１はグループ分けでは同じことなので、集計値を２で割る必要がある。
すなわち
| （ |
n-1 Σ k=1 | nＣk）／２通りの分け方ができる。 |
●別の解法
ｎ人がグループＡがＢを勝手に選ぶ組み合せは２n通り
これにはＡまたはＢが０人の場合を含む。
題意を満たすためＡ＝０とＢ＝０の２通りを除く。
また、Ａ＝１とＢ＝ｎ−１はグループ分けでは同じことなので、集計値を２で割る必要があるので
|
２n−２ ――――――― ２ | 通りの分け方ができる。 |
◆東京都 四年寝太郎 さんからの解答。
すいません、間違っていました。(^_^;
改めて考えてみたのですが、良く分かりません。
とりあえず、分かった範囲で書いておきます。
【問題１】
問題３の計算より２n-1−１通り。
【問題２】
問題３の計算より
|
３n ――― ６ | ＋ |
１ ――― ２ | −２n-1 |
【問題３】
ｍグループ、ｎ人の分け方をP(m,n)と表わすことにする。
◎P(m,n)=P(m,n-1)*m+P(m-1,n)
or
| ◎P(m,n)= |
mn-ΣP(i,n)*mPi ――――――――――― m! |
の二つの漸化式が作れます。
上の式は、n人目がどこかのグループに属するか、しないかの合計で、下の式は、前回の考え方の修正版です。
一応、両方の答えをコンピュータで計算してみると一致しているので、あっていると思います。
でも、いつものことながら漸化式から進まない。(^_^;
◆東京都 千葉 英伸 さんからのコメント。
たぶん単純な間違いだと思いますが、四年寝太郎さんの漸化式は
P(m,n)=P(m,n-1)*m+P(m-1,n-1) では？
ｍ＝２、３の場合を問題にしましたが、
がんばってｍ＝４，５くらいまで計算すると、
一般項が推測できると思います。(^。^)
◆東京都 元吉 さんからの解答。
漸化式
| P(m,n)= |
n-1 Σ u=m-1 | P(m-1,u)*mn-u-1 |
より計算すると
| P(4,n)= | - |
1 ― 6 | +2n-2- |
3n-1 ――― 2 | + |
2 ― 3 | *4n-2 |
| P(5,n)= |
1 ―― 24 | - |
2n-2 ――― 3 | + |
3n-1 ――― 4 | - |
2 ― 3 | *4n-2+ |
5n-1 ――― 24 |
| P(6,n)=- |
1 ――― 120 | + |
2n-4 ――― 3 | - |
3n-2 ――― 4 | + |
4n-2 ――― 3 | - |
5n-1 ――― 24 | + |
9 ― 5 | *6n-4 |
となります。
この漸化式を使ってP(m,n)を求めるには、等比数列の和の公式を繰り返し用いればよいのですが、mが大きくなると、だんだん計算が面倒になります。
上の計算結果から、一般のP(m,n)の式の格好はだいたいわかりますが、
mとnを使ってP(m,n)を表すのは、なかなか難しそうです。
◆東京都 元吉 さんからの解答。
P(m,n)をmとnで表わすことができました。
| P(m,n)= |
(-1)m-1 ―――――― (m-1)!*0! | + |
(-1)m-2*2n-1 ――――――― (m-2)!*1! | + |
(-1)m-3*3n-1 ――――――― (m-3)!*2! | +・・・ | + |
(-1)0*mn-1 ――――――― 0!*(m-1)! |
で間違いないと思います。
いままで計算してきたm=2,3,4,5,6の場合を、あらためてこの形に書き直すと、以下のようになります。
P(2,n)=-1+2n-1
| P(3,n)= |
1 ― 2 | - | 2n-1 | + |
3n-1 ――― 2 |
| P(4,n)= | - |
1 ― 6 | + |
2n-1 ――― 2 | - |
3n-1 ――― 2 | + |
4n-1 ――― 6 |
| P(5,n)= |
1 ―― 24 | - |
2n-1 ――― 6 | + |
3n-1 ――― 4 | - |
4n-1 ――― 6 | + |
5n-1 ――― 24 |
| P(6,n)=- |
1 ――― 120 | + |
2n-1 ――― 24 | - |
3n-1 ――― 12 | + |
4n-1 ――― 12 | - |
5n-1 ――― 24 | + |
6n-1 ――― 120 |
◆東京都 千葉 英伸 さんからのコメント。
正解だと思います。
もう少し見やすい形に書き直すと、
となります。
なお、これが正しいことを証明するのは、漸化式
P(m,n)=mP(m,n-1)+P(m-1,n-1)
を満たすことを証明すれば良いわけですが、これはそんなに難しくありません。
また、ｍ＝ｎの場合、つまり、ｎ人をｎグループに分ける場合は１通りしかありません。
一般項（＊）で、Ｐ(ｎ＋１，ｎ＋１)＝１ の場合を整理すると、『ｎ！』問題の式が導けます。
『ｎ！』問題を出題したとき、上記の方向からのアプローチによって、あの等式が正しいということは解っていたのですが、（＊）を使わない直接の証明ができていませんでした。
で、これは面白そうだと思って出題したんですが・・・。
あの問題は、いまだに何やら混乱したままですね。(^^ゞ