数学A 場合の数 問題 24 解説

方針・初手

辞書式順序では、左から順に文字を比べる。まず使う文字をアルファベット順に並べると

$$ C,\ E,\ M,\ O,\ P,\ T,\ U $$

である。各桁で、指定された文字より前に置ける未使用文字が何個あるかを数え、その後ろの並べ方の数を足していく。

解法1

(1)

最初の文字列は、7文字をアルファベット順にそのまま並べたものである。したがって

$$ \mathrm{CEMOPTU} $$

である。

また、7文字はすべて異なるので、全部の文字列の個数は

$$ 7! = 5040 $$

である。

(2)

$\mathrm{COMPUTER}$ が何番目かを求める。文字の順序は

$$ C < E < M < O < P < T < U $$

である。

まず、1文字目が $C$ より前のものは存在しない。

2文字目は $O$ である。1文字目 $C$ を使った後、未使用文字は

$$ E,\ M,\ O,\ P,\ T,\ U $$

である。このうち $O$ より前にある文字は $E,M$ の2個なので、2文字目が $E$ または $M$ である文字列は

$$ 2 \cdot 5! = 240 $$

個ある。

3文字目は $M$ である。$C,O$ を使った後、未使用文字は

$$ E,\ M,\ P,\ T,\ U $$

である。このうち $M$ より前にある文字は $E$ の1個なので、

$$ 1 \cdot 4! = 24 $$

個を加える。

4文字目は $P$ である。$C,O,M$ を使った後、未使用文字は

$$ E,\ P,\ T,\ U $$

である。このうち $P$ より前にある文字は $E$ の1個なので、

$$ 1 \cdot 3! = 6 $$

個を加える。

5文字目は $U$ である。$C,O,M,P$ を使った後、未使用文字は

$$ E,\ T,\ U $$

である。このうち $U$ より前にある文字は $E,T$ の2個なので、

$$ 2 \cdot 2! = 4 $$

個を加える。

6文字目は $T$ である。$C,O,M,P,U$ を使った後、未使用文字は

$$ E,\ T $$

である。このうち $T$ より前にある文字は $E$ の1個なので、

$$ 1 \cdot 1! = 1 $$

個を加える。

よって、$\mathrm{COMPUTER}$ より前にある文字列の個数は

$$ 240+24+6+4+1=275 $$

である。したがって、$\mathrm{COMPUTER}$ は

$$ 275+1=276 $$

番目である。

(3)

200番目の文字列を求める。1番目から数える代わりに、先頭を $0$ 番目として考えると、200番目は

$$ 200-1=199 $$

番目である。

まず、先頭の文字ごとに

$$ 6! = 720 $$

個ずつある。$199<720$ なので、1文字目は最初の文字 $C$ である。

残りは

$$ E,\ M,\ O,\ P,\ T,\ U $$

であり、残りの番号は $199$ のままである。

次に、2文字目ごとに

$$ 5! = 120 $$

個ずつある。

$$ 199 = 1\cdot 120 + 79 $$

なので、2文字目は残りの文字のうち2番目、すなわち $M$ である。

残りは

$$ E,\ O,\ P,\ T,\ U $$

であり、残りの番号は $79$ である。

次に、3文字目ごとに

$$ 4! = 24 $$

個ずつある。

$$ 79 = 3\cdot 24 + 7 $$

なので、3文字目は残りの文字のうち4番目、すなわち $T$ である。

残りは

$$ E,\ O,\ P,\ U $$

であり、残りの番号は $7$ である。

次に、4文字目ごとに

$$ 3! = 6 $$

個ずつある。

$$ 7 = 1\cdot 6 + 1 $$

なので、4文字目は残りの文字のうち2番目、すなわち $O$ である。

残りは

$$ E,\ P,\ U $$

であり、残りの番号は $1$ である。

次に、5文字目ごとに

$$ 2! = 2 $$

個ずつある。

$$ 1 = 0\cdot 2 + 1 $$

なので、5文字目は残りの文字のうち1番目、すなわち $E$ である。

残りは

$$ P,\ U $$

であり、残りの番号は $1$ である。

次に、6文字目ごとに

$$ 1! = 1 $$

個ずつある。

$$ 1 = 1\cdot 1 + 0 $$

なので、6文字目は残りの文字のうち2番目、すなわち $U$ である。

最後に残る文字は $P$ である。

したがって、200番目の文字列は

$$ \mathrm{CMTOEUP} $$

である。

解説

辞書式順序の問題では、「左から何文字目まで一致しているか」を基準に数える。

ある位置で文字を固定すると、その後ろの並べ方は階乗で数えられる。たとえば、2文字目を決めた後に5文字残るなら、その後ろは $5!$ 通りである。

$\mathrm{COMPUTER}$ が何番目かを求めるときは、各文字について「その文字より小さい未使用文字を置いた場合」を足し上げる。一方、200番目の文字列を求めるときは、階乗で区切られたブロックを順にたどる。

答え

(1)

最初の文字列は

$$ \mathrm{CEMOPTU} $$

全部で

$$ 5040 $$

通りである。

(2)

$\mathrm{COMPUTER}$ は

$$ 276 $$

番目である。

(3)

200番目の文字列は

$$ \mathrm{CMTOEUP} $$

である。