ペアとかの問題 数学！

質問

全くやりかたがわからないのでおねがいします！！全部数え上げる以外でお願いします！

二人一組のペアが五組いて、ペアごとにA,B,C,D,Eの札を持っている。いま、ペアのうちの一人がA,B,C,D,Eと書かれたくじを引いて、ペア替えを行うとき、すべてのペアがもとと違うパートナーになる場合は何通りあるか。

回答No.4

staratras

No.2&3です。5組の場合に限定せず、少し一般的な考え方を補足します。　　　　　　　　　　　　　
2組の場合には、相互に交換する(互換)の場合1通りだけであることは自明です。
3組の場合には、AはBまたはCと交換することができますが、AがBと交換した場合にはBはCと、CはAと交換せざるを得ませんし、AがCと交換した場合にはCはBとBはAとそれぞれ交換せざるを得ません。したがって2通りです。

4組以上になると問題が複雑化します。それは全体を複数のグループに分けて、そのグループの中だけで交換が完結するように分割することができるようになるからです。具体的には4組の場合には4組全体で交換するほか、2組ずつ2グループに分けることもできます。

ここで4組全体で交換する場合の1人1人の選択肢を考えると、AはB,C,Dのいずれかを選べるので3通り、Aが選んだ相手は、Aと自分自身(Aが選んだ相手でもある)以外の2人から選べるので2通り、Aが選んだ相手が選んだ相手は元に戻ってAを選ぶほかないので1通りです。したがって全体では(4-1)!=6通りです。（これは何組に増えても同様でｎ組全体を使って交換する組み合わせは(n-1)!通りです）

一方、2組ずつ2つに分ける方法は3通りです。なぜならばAが選べるのはB,C,Dの3人のうちの1人なので3通りの選択肢がありますが、Aが誰かを選ぶと残りの2人が自動的に決まるからです。互換は1通りしかないので2組ずつ2つに分けた場合の総数は3通りで4組の場合の合計は6+3＝9(通り)です。

5組の場合はNo.2に書いた通り、場合分けは2組+3組という分割と5組全体を使う交換の2つです。

6組になるとさらに場合分けが増え、「2組+2組+2組」、「2組+4組」、「3組+3組」、「6組全体」の4通りになります。そのそれぞれについて、「分割のやりかたが何通りあるか」×「その分割の中で交換の仕方が何通りあるか」を計算し、すべて加えると答えが出ます。

組の数が多い場合は分割の組み合わせが増えてこのやり方では計算が面倒になりますので、No.1の方のように漸化式を使って考える方が効率的でしょう。以下は漸化式を作る方法の一例です。厳密には数学的帰納法で証明すべきですが、大まかな考え方です。

組(ペア)の数がnのときの題意を満たす組み合わせの総数をF(n)とします。（n≧4）F(n)をF(n-1)以下で表すにはどうすればよいか、まずF(n-1)の組み合わせの特定の一つに対して、この(n-1)個の要素の後なら後、前なら前に1個を追加させる(割り込ませる)ことにします。この総数は(n-1)F(n-1)通りです。これは追加した組が互換の片方でない場合です。

ただ、これでF(n)をすべて網羅しているかといえばそうではありません。F(4)を例にとれば、4組全体を使う交換はF(3)の3個の要素の後に1個を割り込ませる方法で得られますが、F(4) のうち2組が2つある分割（追加した1組が互換の片方である場合）はこのやり方では得られず、2つ前のF(2)に2組を加えてやる必要があります。この組み合わせ方は追加する2組同士で交換する1通りだけでなく、F(2) の2(=n-2)個の要素とそれぞれ交換させる方法もあるので、3（=n-2+1=n-1）通りあります。一般化すれば新たに追加する組が互換の片方である組み合わせの総数は(n-1)F(n-2)通りあるということです。

まとめると求めるF(n)=(n-1)(F(n-1)+F(n-2)) となります。

回答No.3

staratras

No.2です。図が添付されていなかったので追加します。

互換がある例は、A→B,B→A,C→E,D→C,E→Dとなることを示しています。

互換がない例は、A→D,B→A,C→B,D→E,E→Cとなることを示しています。

回答No.2

staratras

AとBがお互いに(A→B,B→A)「いってこい」で交換する部分(「互換（ごかん）」）が含まれているか、いないかで分けて考えると分かりやすいかと思います。

１、互換を含む場合　
2組含むと、残りの1人の行き先がなくなるので含むことができるのは1組(2人)だけです。

5人から2人を選ぶ組み合わせは、5C2=10(通り)あります。残りの3人を仮にC、D、Eと
するとその交換の方法は2通りだけです。(C→D→E→CまたはC→E→D→C）したがって全
体の組み合わせは10×2=20(通り）です。

２、互換を含まない場合　
Aの選択肢は自分(A)以外のBCDEの4通りです。ここでそのほかのものについて考えます。
「Aが選んだ相手」はAと自分自身(Aが選んだ相手でもある）以外の3人の3通りを選べま
す。

「Aが選んだ相手が選んだ相手」は、AとAが選んだ相手と自分自身(「Aが選んだ相手が
選んだ相手」でもある)以外の2人の2通りを選べます。

「Aが選んだ相手が選んだ相手が選んだ相手」の選択肢は残った1人だけです。
したがって全体の組み合わせは4!=24(通り）です。

１と２は重なる部分がなく、また数え落としもないので、合計の組み合わせは20+24=44(通り）です。

なお１と２の区別は下のように「あみだくじ」で考えると視覚的にわかりやすいかもしれません。

回答No.1

f272

求める場合の数をF(5)とします。5は5ペアということです。
Aの人はB，C，D，Eのどれかを引いているはずです。
もしAの人がBを引いていたらBの人が引いたくじを，Aの人がCを引いていたらCの人が引いたくじを，Aの人がDを引いていたらDの人が引いたくじを，Aの人がEを引いていたらEの人が引いたくじを考えて(ここまでで4通りの場合がある)，それがAであるかAでないかで場合分けをします。
もしそれがAであれば，残り3つの場合の数を数える。
もしそれがAでなければ，Aの人以外の4つの場合の数を数える。
結局F(5)=4*(F(3)+F(4))通りになります。

F(3)やF(4)は同様に考えると
F(3)=2*(F(1)+F(2))
F(4)=3*(F(2)+F(3))
です。また明らかに
F(1)=0
F(2)=1
です。これでF(5)を順番に求めることができますね。
F(3)=2*(F(1)+F(2))=2
F(4)=3*(F(2)+F(3))=9
F(5)=4*(F(3)+F(4))=44
です。