攪乱順列の場合の数(ループ図を利用して解くかなりの難問)

質問

個人的には漸化式とかは面白く好きなのにたいし、この手の問題は嫌いなのでなおさら難問に感じてしまい、解説を見てもまったくわからないので教えてください。

n通の手紙とそのn通に対応した宛名が書かれた封筒がn枚ある。手紙を封筒に1枚ずつ入れるとき、すべての手紙が対応する封筒に入らないような場合の数をa_nとする。
a_(n+2)=(n+1){a_(n+1)+a_n}を証明せよ。

ループ図を使います。ループ図とは文字通りの円状の図のことです。解説の方針に(1)「n+2が長さ2のループに属している場合」(2)「n+2が長さ3以上のループに属している場合」に分けると書いてあります。それぞれの場合が(n+1)、{a_(n+1)+a_n}となり多分積の法則で証明完了といった感じだと思います。

長さ2のループ、の意味も解りません。何の長さかも解りません。この問題集に載っているループ図の問題のうちこれだけがどうしても理解できませんので何か変な誤解をしているのかもしれません。

どなたか、馬鹿な僕にもわかるように教えてください。よろしくお願いいたします。

回答No.1

noname#47975 · ベストアンサー

ループ図については全く無知な者ですが、
攪乱順列の考え方として、まず、ｎ＋２番目にｋ（ｋ＝１、２、…ｎ＋１）
を配置すると考え、以下の２つのケースに分けて考える必要があります。

(1)ｋ番目にｎ＋２を配置するとき
(2)ｋ番目にｎ＋２を配置しないとき

(1)については、残りの１、２、…ｋ－１、ｋ＋１、…、ｎ＋１の
ｎ個を攪乱順列を満たすように配置すればよいので、anである事が
分かります。

(2)については、少し工夫が要ります。
今度は配置できない箇所の番号をそれぞれ以下のように割り当てます。

１については１番目に配置できないので、１’と、
２については２番目に配置できないので、２’と、
…
ｎ＋２についてはｋ番目に配置できないものと見なし、ｋ’（★ここが重
要）と、
．．
ｎ＋１についてはｎ＋１番目に配置できないｎ＋１’と定める事
にします。

すると、どうでしょうか。今度は１’、２’、…、ｋ’、…ｎ＋１’のｎ＋１個のデータを攪乱順列を満たすように配置する問題に変わりました。以上により、an+1になる事が分かります。

そして、ｋは１～ｎ＋１のｎ＋１通りの値を取れるので、
以上により、ａｎ＋２＝ｎ＋１（aｎ＋ａｎ＋１）である事
が分かります。

読んでいるだけではイマイチピンとこないかもしません。
そういう時は、図を描きながら、丁寧に洞察して熟読していけば、上記の考え方を理解する事ができます。

また、ｎ＝２、３、４と実際に試行してみてください。

お礼

ありがとうございます。どうにか理解できました。手を動かして考える習慣をつけようと思います。

回答No.2

kkkk2222

最大画面は？

完全順列／攪乱順列

Ａ（Ｎ＋２）＝（Ｎ＋１）【Ａ（Ｎ＋１）＋Ａ（Ｎ）】
説明の都合上、番号を２減じて

Ａ（Ｎ）＝（Ｎー１）【Ａ（Ｎー１）＋Ａ（Ｎ－２）】
とします。
Ａ（１）＝０
Ａ（２）＝１

＃１０
全個数が１０のときで考える。
ＴＡＧＥＴの式は、
Ａ（１０）＝９【Ａ（９）＋Ａ（８）】

最初の並びを、
１,,２,,３,,４,,５,６,,７,,８,,９,１０
並び替え後を、
○○○○○○○○○○
ここで１０番目にくる場合の数の可能性は、
○○○○○○○○○●
１０はダメなため１０－１＝９通り
さらに、１０番目にくる数を５とする。
○○○○○○○○○５
次に５番目に来る数を考える。
○○○○◎○○○○５
　　ここで、技巧を施す。
　　◎が１０の時と、１０でない時に場合分けする。

（１）◎が１０の時

○○○○１０○○○○５
残りの（１０－２）個の、攪乱順列はＡ（８）
総計、９＊Ａ（８）

（２）◎が１０でない時

○○○○○○○○○５
残りの（１０－１）個の、攪乱順列はＡ（９）
総計、９＊Ａ（９）

（１）（２）よりＴＡＲＧＥＴの式
Ａ（１０）＝９＊Ａ（９）＋＊Ａ（８）
Ａ（１０）＝９【Ａ（９）＋Ａ（８）】
を得る。

ここまでＯＫなら、しめたものです。
次に進む前に２４時間、置いた方が良い気がします。

＃Ｎ　　（形は＃１０と全く同じに書きます）。
全個数がＮのときで考える。
ＴＡＧＥＴの式は
Ａ（Ｎ）＝（Ｎー１）【Ａ（Ｎー１）＋Ａ（Ｎ－２）】　（Ｎ≧３）

最初の並びを
１、２、３、４、５、６、７、８、９、・・・・・・Ｎ
並び替え後を
○○○○○○○○・・・・・・・・・○○○
ここでＮ番目にくる場合の数の可能性は
○○○○○○○○・・・・・・・・・○○●
Ｎはダメなため、（Ｎ－１）通り
さらに、Ｎ番目にくる数をＫとする。
○○○○○○○○・・・・・・・・・○○Ｋ
次にＫ番目に来る数を考える。
○○○○○◎○○・・・・・・・・・○○Ｋ
　　ここで、技巧を施す。
　　◎がＮの時と、Ｎでない時に場合分けする。

（１）◎がＮの時

○○○○Ｎ○○○○５
残りの（Ｎ－２）個の、攪乱順列はＡ（Ｎ－２）
総計、（Ｎ－１）＊Ａ（Ｎ－２）

（２）◎がＮでない時
○○○○○○○○・・・・・・・・・○○Ｋ
残りの（Ｎ－１）個の、攪乱順列はＡ（Ｎ－１）
総計、（Ｎ－１）＊Ａ（Ｎ－１）

（１）（２）よりＴＡＲＧＥＴの式
Ａ（Ｎ）＝（Ｎ－１）＊Ａ（Ｎ－１）＋（Ｎ－１）＊Ａ（Ｎ－２）
Ａ（Ｎ）＝（Ｎー１）【Ａ（Ｎー１）＋Ａ（Ｎ－２）】　（Ｎ≧３）
を得る。

お礼

毎回毎回ありがとうございます。感謝しています。考え方が参考になりました。