 | 2006/05/17(Wed) 06:18:51 編集(投稿者)
失礼ですが、何故分からないのかが分からないので説明できません。
丁寧に解説されていて、付け足すところなど何もないので、具体例を混ぜて書きます。
はじめのらすかるさんの投稿（無断転載ごめんなさいm(__)m）では
A,B,C,D,Eの順に封筒があるとします。このとき、
a,b,c,d,eの順に招待状が入っていれば完全に合っている場合です。
a,b,c,e,dだと3つは合っていて、2つが間違っている場合です。
この問題では全部間違っている場合
b,c,d,e,a
などのようになる場合の数を求める問題です。
全部間違っている場合は
> ある封筒→それに入っている招待状→その招待状に対する正しい封筒
> →それに入っている招待状→その招待状に対する正しい封筒→…
＜上の例b,c,d,e,aでは＞
ある封筒A→それに入っている招待状b→その招待状に対する正しい封筒B
→それに入っている招待状c→その招待状に対する正しい封筒C→…
> のようにたどった時、
> A→b, B→c, C→d, D→e, E→a
> のように5つでまわるパターンと
> A→b, B→c, C→a, D→e, E→d
> のように3つと2つでまわるバターンのいずれかに限られます。
> 前者は円順列なので(5-1)!=24通り
> 後者は3つと2つに分けて円順列の積なので5C3×(3-1)!×(2-1)!=20通り
> 従って全部で24+20=44通りとなります。
ということです。 （ いや〜面白い解法ですね。らすかるさんの斬新な解法にはいつも驚かされます。
次の投稿で、
zuzuさんは漸化式を使って解かれています。（無断転載ごめんなさいm(__)m）
4人の場合は9通りだという予備知識のもと解かれたものが以下です
> 4人の封筒と招待状が完全に間違った組になっていて、
例)b,c,d,a
>5人目の招待状をその4人の招待状のどれかと入れ替えると完全に間違った組が出来る。
例)b,c,d,a,e→b,e,d,a,c
> 完全に間違った組の4人の場合は9通りだから、9×4=36通り
> 4人のうち1人だけ封筒と招待状が一致していて、
例)a,c,d,b
>5人目の招待状をその一致している人の招待状と入れ替えると完全に間違った組が出来る。
例)a,c,d,b,e→e,c,d,b,a
> 3人が間違った組になっている場合は2通りだから、2×4=8通り
>
> 以上より求める場合の数は、36+8=44通り
以下が漸化式
> 参考
> 求める場合の数をW[5]とします。
> W[1]=0,W[2]=1,W[3]=2,
> W[4]=3(W[3]+W[2])=9,
> W[5]=4(W[4]+W[3])=44
> 一般に、W[n+2]=(n+1)(W[n+1]+W[n])
|
