【数学A】例題1.2.24：完全順列（One More）★★★

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 例題A1.2.24：完全順列（One More）★★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

5人の生徒が異なる本を持ち寄り，それらを1冊ずつ分配する．このとき，すべての生徒が自分の持ち寄った本とは違う本を受け取る場合は何通りあるか．

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 例題A1.2.24の解答（One More）★★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

生徒をA，B，C，D，Eとし，本をそれぞれ$a,b,c,d,e$とする．このとき，求める場合の数は，A，B，C，D，Eの順に，各生徒が受け取る本を並べた順列のうち，生徒が自分の持ち寄った本$k(k=a,b,c,d,e)$を受け取らないものの個数に等しい．

例えば，生徒Aが$b$の本を受け取る場合，条件を満たす順列は次のように，11通り

Aが$c,d,e$の本を受け取る場合も，同様に11通りずつある．

よって，求める場合の数は，$11\times 4=44$通り

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 問題A1.2.24：完全順列（One More）★★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

4人の生徒が異なるおもちゃを持ち寄り，それらを1つずつ分配する．このとき，すべての生徒が自分の持ち寄ったおもちゃとは違うおもちゃを受け取る場合は何通りあるか．

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 問題A1.2.24の解答（One More）★★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

生徒をA，B，C，Dとし，おもちゃをそれぞれ$a,b,c,d$とする．このとき，求める場合の数は，A，B，C，Dの順に，各生徒が受け取るおもちゃを並べた順列のうち，生徒が自分の持ち寄ったおもちゃ$k(k=a,b,c,d)$を受け取らないものの個数に等しい．

条件を満たす順列は次のように，$9$通り

よって，求める場合の数は，$9$通り

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 例題A1.2.24の側注：完全順列（One More）★★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% 側注1
与えられた条件より，生徒Aは$a$の本は受け取らない．

% 側注2
自分の持ち寄った本以外を受け取る．

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 問題A1.2.24の側注：完全順列（One More）★★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% 側注1
与えられた条件より，生徒Aは$a$のおもちゃは受け取らない．

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 例題A1.2.24の考え方・補足など：完全順列（One More）★★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 考え方
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

5人の生徒をA，B，C，D，Eとし，本をそれぞれ$a,b,c,d,e$とすると，生徒が自分の持ち寄った本$k(k=a,b,c,d,e)$を受け取らないものの個数を考えればよい．このとき，例えばAは$a$の本を受け取らないことに注意しながら，樹形図や辞書式配列を用いて，重複や漏れのないように場合の数を求める．

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 余談
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

$n$個の数字$1,2,3,\ldots,n$を1列に並べるとき，どの数字$k(1\leqq k\leqq n)$も$k$番目ではないような並べ方を，完全順列という．

なお一般に，完全順列について，次のような関係式が成り立つことが知られている．ただし，$1,2,\ldots,n$の完全順列の総数を$W(n)$とする．

\[
\{
\begin{array}{l}
W(1)=0,W(2)=1\\
W(n)=(n-1)\{W(n-1)+W(n-2)\}(n\geqq 3)\cdots(\mathrm{i})
\end{array}
\]

このような関係式を漸化式といい，数学Bで学習する．