解説

方針・初手

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

$$ 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}

$$

である。