撹乱順列

『部屋割り』とは異なるが,『包含と排除の原理』の応用として次の問題を考えてみよう.

攪乱順列

4人の友達A,B,C,Dがクリスマスパーティーでプレゼントを交換する.自分自身の持ってきたプレゼントに誰も当たらないようになるのは何通りの分け方があるか求めよ.

解答1:包含と排除の原理

$U$ :プレゼントの分け方のすべて

$A$ :A君が自分自身のプレゼントをもらう

$B$ :B君が自分自身のプレゼントをもらう

$C$ :C君が自分自身のプレゼントをもらう

$D$ :D君が自分自身のプレゼントをもらう

と集合をおくと

\begin{align} &\ n(U)-n(A\cup B\cup C\cup D)\\ =&\ n(U)-\bigl\{n(A)+n(B)+n(C)+n(D)\\ &\ -n(A\cap B)-n(A\cap C)-n(A\cap D)\\ &\ -n(B\cap C)-n(B\cap D)-n(C\cap D)\\ &\ +n(A\cap B\cap C)+n(A\cap B\cap D)\\ &\ +n(A\cap C\cap D)+n(B\cap C\cap D)\\ &\ -n(A\cap B\cap C\cap D)\bigr\}\\ =&\ 4!-\bigl\{\ _{4}\mathrm{C}_{1}(4-1)!-\ _{4}\mathrm{C}_{2}(4-2)!\\ &\ +\ _{4}\mathrm{C}_{3}(4-3)!-\ _{4}\mathrm{C}_{4}(4-4)!\bigr\}\\ =&\ 4!\left(\dfrac{1}{0!}-\dfrac{1}{1!}+\dfrac{1}{2!}-\dfrac{1}{3!}+\dfrac{1}{4!}\right)\\ =&\ 4!-4\cdot3!+6\cdot2!-4\cdot1!+1\\ =&\ \boldsymbol{9} \end{align}

$\blacktriangleleft$ 4集合での包含と排除の原理

通り

解答2:漸化式を使う

$n$ 人のプレゼント交換において, 自分自身の持ってきたプレゼントに誰も当らない場合の数を $D(n)$ とする.

いま, $D(4)$ は次の3つに場合分けできる.

  1. A君がB君のプレゼントに当る
  2. A君がC君のプレゼントに当る
  3. A君がD君のプレゼントに当る

i. ~iii. は対称的なので,以下i. についてだけ考える(のち4 − 1 = 3倍すればよい).

プレゼントを小文字のアルファベットで表すとして,“A君のプレゼントaをbと考えて”,残りの3人へのプレゼントの配り方を考えると

  1. B君にb(本当はa)を配り,残りC,D君に自分自身のプレゼントが当らないように配る
  2. B,C,D君に自分自身のプレゼントが当らないように配る(見かけの上ではあるが,B君にbが配られない場合を考える)

の2通りに場合分けできる.ここで1. は $D(2)$ ,2. は $D(3)$ に他ならない.つまり $D(4)$ は

\[D(4)=(4-1)\left\{D(3)+D(2)\right\}\]

で計算できる.この関係は $n$ が自然数で一般的に成り立つから

\begin{align} D(4)=&\ (4-1)\left\{D(3)+D(2)\right\}\\ =&\ 3D(3)+3D(2)\\ =&\ 3\left[2\left\{D(2)+D(1)\right\}\right]+3D(2)\\ =&\ 9D(2)+6D(1)\\ =&\ 9D(2)+0\\ =&\ 9\cdot1\\ =&\ \boldsymbol{9} \end{align}
$\blacktriangleleft$ 漸化式ぜんかしきについて詳しくは $FTEXT$ 数学Bで学ぶ

通り