質問する
質問を探す 詳しく検索する

解決済

clip!clip!
Ads By Google
たこたこ

確率の入試問題です。

n個の箱とn個の玉がある。n個の箱には1,2,・・・,nと通し番号がついている。n個の玉にも1,2,・・・,nと通し番号がついている。いま、n個の箱に1つずつ玉を入れるとき、箱の番号と玉の番号が全部異なっているような入れ方の総数をu[n]とする。

(1)u[1]=0,u[2]=1,u[3]=,u[4]=
(2)u[n+1],u[n],u[n-1]の間に成り立つ関係式を求めよ。
(3)u[n+1],u[n]の間に成り立つ関係式を求めよ。

(1)のu[3]=2,u[4]=9だと思うのですが、(2),(3)が解けないので
解き方を教えてくれませんか。よろしくお願いします。

2009-06-29 04:38の質問
この質問と回答を読んで役に立った場合は「役に立つ質問」に投票してください。投票が多い質問は、役に立つ質問一覧に掲載され、より多くの人に見てもらうことができます。

回答(2)

1.

2009-06-30 00:50:18ベスト
fu-i
箱に玉を1つずつ入れる入れ方は(n!)通りありますね
そのうち、箱の番号と玉の番号が全部同じ入れ方は、1通りですね

(1)より、u[1]=0,u[2]=1,u[3]=2,u[4]=9

n=3のとき、1箱同じが3通りですので、
箱 玉⇒
1　3 2　1　1 3 2
2　1 3　2　3 2 1
3　2 1　3　2 1 3
u[3]=3!-(1+3)=6-4=2

n=4のとき、1箱同じだと、残る3箱には、ついている番号とは異なる玉が入っています。それがちょうど、u[3]=2になりますね
1箱同じというのは、箱の数分4通りあります。
箱 玉⇒
1　1 x x x
2　x 2 x x
3　x x 3 x
4　x x x 4
また、n=4であれば、2箱同じというのもありますね
箱 玉⇒
1　1 1 1 x x x
2　2 x x 2 2 x
3　x 3 x 3 x 3
4　x x 4 x 4 4
これは、自然と決まってくるので、これは6(=4C2)通りあることになりますね
箱 玉⇒
1　1 1 1 4 3 2
2　2 4 3 2 2 1
3　4 3 2 3 1 3
4　3 2 4 1 4 4
まとめますと、
u[4]=4!-(1+4・u[3]+4C2)=24-(1+4・2+6)=24-15=9

u[n]=n!-(1+n・u[n-1]+nC2)
u[n+1]=(n+1)!-[1+(n+1)・u[n]+(n+1)C2]
自信度 : 自信なし 回答レベル : アドバイス

非常に詳しい解説ありがとうございました。

2.

2009-06-30 01:33:32
fu-i
n=5のとき、1箱同じだと、残る4箱には、ついている番号とは異なる玉が入っています。それがちょうど、u[4]=9になりますね

n=5であれば、2箱同じ3箱同じというのもありますね
2箱同じ 5C2=10　u[3]=2
3箱同じ これも自然と決まってくるので 5C3=5C2=10　u[2]=1

u[5]=5!-(1+5・u[4]+u[3]・5C2+u[2]・5C3)=120-(1+45+20+10)=44

ちなみに、5C1=5ですから、
u[5]=5!-(1+u[4]・5C1+u[3]・5C2+u[2]・5C3)
としてもかまいませんね
u[n]=n!-[1+u[n-1]・nC1+u[n-2]・nC2+u[n-3]・nC3…u[2]・nC(n-2)]
自信度 : 自信なし 回答レベル : アドバイス
Ads By Google

コメント(6)

コメントする
#1.  fu-i
2009-06-30 01:47:19

問題文を読んだ感じ、もっとスマートな関係式がありそうですね
>>1
>>2
ややこしくしてしまった感が否めません(T~T
わかる方よろしくお願いしますねm(__)m

#2.  fu-i
2009-06-30 16:27:37

ベスト回答にしていただきありがとうございます<(_ _)>
上の回答で、質問者であるたこたこさんのお役に立てればよいのですが・・・

#3.  はるぼうず
2009-07-01 04:38:57

あら、見たのが遅くて回答できませんでした。

「けち」つけると、（２）と（３）は漸化式で答えないといけないところなのに答えになっていないような。


自信はないのですが、ヒントになれば。(2) は、
　 u(n+1) = n u(n) + n u(n-1)
かも知れません。

4(=n+1) 個の箱の場合、A) まず 1-3(1からnまで）の 3 個を、1-3 の箱に、数字が一致しないようにいれる（これはu(n) 通りある。）4 は、そのどれか(3=n通りある）をはじき出してそこにいれ、はじき出されたものを 4 の箱に入れる。このような入れ方が、 n u(n) 通りある。B) まず 1-3 のうちの一つだけが自分と同じ数字の箱であるような入れ方を見つける。これは、n u(n-1) 通りある。4 は、その、一致している玉をはじき出してその箱に入れ、はじき出された玉を 4 の箱に入れる。

#4.  はるぼうず
2009-07-01 04:40:02

大事な問題は、これで重複やダブりがないかということで、これが自信がないところです。u(4)まではこれでいいようですが、u(5) はこの考え方だと 44 になります。回答１，２さんの答えとは違うようです。

(3) については、おそらく (2) の漸化式をもとに、u(n+1) と u(n) の間の漸化式を思いつきで求めて、それを数学的帰納法で証明するのではないかと思います。これはこれで難しいし、(2) があっている自信がないと、考える気がおこりません。ごめん。

いずれにせよこれは、時間制限厳しい入試問題にはキツイ難問と思いますよ。

#5.  BLUEPIXY
2009-07-01 05:05:08

#4>u(5) はこの考え方だと 44 になります。回答１，２さんの答えとは違うようです。
回答２で、
2>u[5]=5!-(1+5・u[4]+u[3]・5C2+u[2]・5C3)=120-(1+45+20+10)=44
とありますけど？？

#6.  はるぼうず
2009-07-03 04:19:25

>> #5
コメントどうもありがとうございます。

回答１で、
　u[n]=n!-(1+n・u[n-1]+nC2)
とあります。これにn=5 を代入すると、（u(4)=9）をつかえば
u(5) = 5! - (1+5*9+5*4/2) 

    = 120 - ( 1+45+10 ) 
    = 120 - 56 = 64
となりますので、#3 の結果とは違うのかなと思ったのです。

() のなかの +20 の有無が違いますね。

＃正直なところ回答１，２の説明がよくわからないので。。。

トラックバック(2)

トラックバック一覧
トラックバックURL: