確率漸化式の問題

質問

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)が解けないので
解き方を教えてくれませんか。よろしくお願いします。

回答No.1

rnakamra · ベストアンサー

ヒントだけ。
(2)
(n+1)番の箱に入っている玉の番号がmとすると、次の二通りの場合が考えられます。
A.m番の箱に入っている玉の番号が(n+1)の場合
B.m番の箱に入っている玉の番号が(n+1)以外の場合

Aの場合の数は、m番と(n+1)番以外の(n-1)個の箱に題意を満たすように玉が入っている場合の数であるからu[n-1]通りある。

Bの場合は、m番の箱と(n+1)番の箱の中身を入れ替えると(n+1)番以外のn個の箱に題意を満たすように玉が入っている場合の数に等しいことがわかる。よって、この場合の数はu[n]通りである。

A,Bどちらの場合でもmのとり方はn通りあるから全部の場合の数は(以下略)。

(3)
(2)で求めた関係式をnの代わりにn+1を入れたものを出す。
その式から元の式を引き算すると4項の関係式となるが、u[n+2]の項とu[n+1]の項を左辺に、残りを右辺に集めてよく見るとある関係に気づくはずです。

回答No.3

rnakamra

#1,2のものです。
>ヒントをせっかく頂いたのですが、
>私の頭が悪く解けないので、もっとヒントをお願いします。

これは、ヒントの内容が理解できないということでしょうか。
それともヒントから先がわからないということでしょうか。

基本的に全てを答えるつもりは無いのでそのところは御了承ください。

お礼

ヒントの先が理解できなかったのですが、
兄弟にヒントを少し貰ったら、解けました。

わざわざありがとうございました。

回答No.2

rnakamra

#1のものです。
説明が間違っていました。
B.m番の箱に入っている玉の番号が(n+1)以外の場合

Bの場合は、m番の箱と(n+1)番の箱の中身を入れ替えると(n+1)番以外のn個の箱に題意を満たすように玉が入っている場合の数に等しいことがわかる。よって、この場合の数はu[n]通りである。

ではなく、

Bの場合は、(n+1)の玉が入っている箱と(n+1)番の箱の中身を入れ替えると(以下同じ)
です。
(n+1)の玉が入っている箱の番号をm'とすると、m'番の箱と(n+1)番の箱の中身を入れ替えると、(n+1)番の箱には(n+1)が、それ以外の箱には1～nまでの玉が入ります。しかもm'番以外の箱は箱と玉の番号が一致していませんし、m'の箱の中にもmの玉が入っているので番号は一致しません。

お礼

回答ありがとうございます。
ヒントをせっかく頂いたのですが、
私の頭が悪く解けないので、もっとヒントをお願いします。