ABCDEFの6人が、それぞれ自分以外の5人のうち誰か一人を選んで手紙を出した所、全ての人が他の5人の誰かから手紙をもらった。このような手紙の出し方は全部で何通りあるか。
まず自分自身への手紙も許して、各人が1通ずつの手紙をもらうような場合の数は6!=720通り 次にこのうちAがA自身に手紙を出すような集合をPAとし、同様にPB〜PFを定める。 いま求めるべきは 集合PAのバーかつPBのバーかつ・・・かつPFのばー の要素の個数であるが、包含排除の原理によりこれは n(U)−Σ(i=A~F)n(Pi)+Σ(i,j=A~F)n(PiかつPj) -・・・+(-1)^6n(PAかつPBかつPCかつPDかつPEかつPF) =6!−6×5!+6C2×4!ー6C3×3!+6C2×2!−6C1×1!+1=265通り・・答え とあるのですが、 6C1×1!が納得できません。 この項は Σ(i,j,k,l,m=A~F)n(PiかつPjかつPkかつPlかつPm) だと思うのですが これって意味的には6人中5人が同じ手紙をもらう場合の数ですよね?でもそんなことってありえないですよね? AがAをもらって BがBをもらって CがCをもらって DがDをもらって EがEをもらって
そしてFがFでないものをもらおうとしてもFは Fをもらうしかないはずです
どなたかどうか教えてください よろしくお願いします!!
|
No.17806 - 2012/06/17(Sun) 23:52:59
| ☆ Re: かく乱順列 / rtz | | | 引きすぎたり足し過ぎたりの調整のための計算であって、 実際の場合の数とはちょっと違います。
A、B、Cの3人で考えてみてください。 並べただけの順列は6通り。 このうち1人が一致する分を足し過ぎたから3*2!通り引く。…(1) そうすると2人が一致する分を引きすぎたから3*1!通り足す。…(2) でも3人一致する分を足し過ぎたから1通り引く。
(1)で引かれたのは AがAで一致し、BがB、CがC…☆ AがAで一致し、BがC、CがB BがBで一致し、AがA、CがC…☆ BがBで一致し、AがC、CがA CがCで一致し、AがA、BがB…☆ CがCで一致し、AがB、BがA です。
(2)は、本来1人のみ一致を引きたかったのに 2人以上一致を引きすぎてしまいました(上の☆3つ)。 これを足し直し、 (3)で全部が一致してるのは引かなきゃならんので1つ引いてます。
理屈は6人だろうが一緒です。 引きすぎた分を足し直してるだけです。
それから、「完全順列」「モンモール数」で検索すれば、 漸化式等で解く方法なども載っていますので、そちらも参考にどうぞ。
|
No.17807 - 2012/06/18(Mon) 04:32:51 |
| ☆ Re: かく乱順列 / ヤドラン | | | う〜ん、回答ありがたいですが質問に全く答えてませんね。 今分かりましたが Σ(i,j,k,l,m=A~F)n(PiかつPjかつPkかつPlかつPm) =n(PAかつPBかつPCかつPDかつPE) +n(PAかつPBかつPCかつPDかつPF) +n(PAかつPBかつPCかつPEかつPF) +n(PAかつPBかつPDかつPEかつPF) +n(PAかつPCかつPDかつPEかつPF) +n(PBかつPCかつPDかつPEかつPF) =1×6=6C1という説明がほしかったです
ありがとうございました
|
No.17810 - 2012/06/18(Mon) 18:36:38 |
| ☆ Re: かく乱順列 / ヨッシー | | | rtz さんの記事をよく吟味すれば、たとえば、 (A,B,C)(A,C,B)(B,A,C)(B,C,A)(C,A,B)(C,B,A) のように羅列して考えれば、ご質問にある疑問は解消されるはずです。
逆に、 >Σ(i,j,k,l,m=A~F)n(PiかつPjかつPkかつPlかつPm) >=n(PAかつPBかつPCかつPDかつPE) >+n(PAかつPBかつPCかつPDかつPF) >+n(PAかつPBかつPCかつPEかつPF) >+n(PAかつPBかつPDかつPEかつPF) >+n(PAかつPCかつPDかつPEかつPF) >+n(PBかつPCかつPDかつPEかつPF) >=1×6=6C1 だけでは、 >そしてFがFでないものをもらおうとしてもFは >Fをもらうしかないはずです が解決したかどうか、いささか心配です。
|
No.17818 - 2012/06/19(Tue) 05:45:37 |
|