ｎ個の箱とｎ個の球を全部異なるように入れる総数

ｎ個の箱とｎ個の球がある。ｎ個の箱には、1,2,・・・nと通し番号がついている。ｎ個の球にも1,2,・・・nと通し番号がついている。いま、ｎ個の箱に１つずつ球を入れるとき、箱の番号と球の番号が全部異なっているような入れ方の総数をU_nとする。
(1)U_1、U_2、U_3、U_4を求めよ
(2)U_n+1、U_ｎ、U_n-1の間の関係を表す式を求めよ
(3)U_n+1、U_nとの間の関係を表す式を求めよ。

この問題を考えています。(1)はU_1＝０、U_2＝１、U_3＝６、U_4＝９　数え上げていったのですがあっているでしょうか？
(2)(3)は「漸化式」を求める問題だと思うのですが、
うまく立てられません。予想して帰納法はうまくいきませんでした。ほかにいい方法はないでしょうか？
回答いただければ幸いです。よろしくお願いします

No.1 ベストアンサー 回答者： stomachman 回答日時： 2006/08/10 23:35

U[1]=0, U[2]=1までは良いけれど、ご質問のU[3],U[4]は違ってますね。

漸化式は、まず小さいnについて調べてみることが重要です。でも、調べた僅かな例からカンで式を予想するってのは、確信が持てませんし、あんまり旨く行きません。それよりも、「U[n+1]で表されるもの（この場合、ボールの入れ方）」を「U[n]で表されるもの」と「U[n-1]で表されるもの」から作り出す手順を具体化してみることがポイントです。

「(n+1)個の箱と球について、箱の番号と球の番号が全部異なっているような入れ方」を数えてみましょう。

　まず、「n個の箱と球について、箱の番号と球の番号が全部異なっているような入れ方」をひとつ決めたとしましょう。
　そして、これらの箱の中からひとつ選んで箱jとしましょう。（この選び方はn通りあります。）箱jに入っている球を球kとしましょう。球kを箱jから取り除き、そこに、n+1番の箱と球を持ってきます。
球kを箱(n+1)に入れ、空いた箱jに球(n+1)を入れれば、「(n+1)個の箱と球について、箱の番号と球の番号が全部異なっているような入れ方」がひとつ出来上がります。
　だから、このやりかたでn×U[n]通りが作れます。

　しかしそれだけではありません。
　「n個の箱と球について、箱の番号と球の番号が一箇所を除いて全部異なっているような入れ方」を一つ決めたとしましょう。箱の番号と球の番号が一致しているところがひとつだけあるので、その番号をjとします。で、n+1番の箱と球を持ってきます。そして、球jを箱(n+1)に入れ、空いた箱jに球(n+1)を入れれば、「(n+1)個の箱と球について、箱の番号と球の番号が全部異なっているような入れ方」がひとつ出来上がります。

　ここで「n個の箱と球について、箱の番号と球の番号が一箇所を除いて全部異なっているような入れ方」は何通りあるでしょうか。一致している番号を何にするかの選び方がn通りあります。そして、残りの「(n-1)個の箱と球について、箱の番号と球の番号が全部異なっているような入れ方」をすれば良いのだから、n×U[n-1]通りあります。

　以上から、
U[n+1] = nU[n] + nU[n-1]
と分かります。これは線形漸化式なので、機械的に一般項を出すことも可能です。

この回答への補足

回答ありがとうございます。
(2)まではうまく理解できました。
(3)なのですが、(2)で得られた３項間漸化式を２項間漸化式にすることはできるのでしょうか？

補足日時：2006/08/11 22:48

No.3 回答者： ryn 回答日時： 2006/08/18 18:51

もう解決しているかもしれませんが，

　U[n+1] = nU[n] + nU[n-1]
の3項間漸化式は
　U[n+1] - (n+1)*U[n] = (-1)*{ U[n] - n*U[n-1] }
のように変形することで2項間漸化式に持っていくことが出来ます．

No.2 回答者： ryn 回答日時： 2006/08/11 14:08

同じような質問をしたことがあるので

参考にしてください．

参考URL：http://oshiete1.goo.ne.jp/kotaeru.php3?q=676711