辞書式配列の問題
小手調べ １２３４５の５文字を並べ替えたもののうち、
２５０００より小さいものは何個あるか。

解答； 一万の位が１のとき、４！＝２４個
一万の位が２のとき、千の位は１，３，４のいずれか。
よって、３×（３！）＝１８個
以上より、４２個があります。

辞書式配列の問題は、この問題のように、○○○○○以下の数字は何個あるか、
という問題に帰着させると解きやすくなります。

例題ＳＵＰＥＲの５文字を並べ替えて単語を作る。
作った全ての単語を辞書式に並べていき、ＳＰＲＵＥのように、
意味を持たない単語も数えるものとする。
(１)ＳＵＰＥＲは何番目にあるか。
(２)５０番目の単語は何か。

もちろん、全部で５！＝１２０通りですが、単語全てを並べるのは時間がかかりますね。
この問題を分かりやすくするポイントは、数字に置き換えることです。
（このアイデアは佐々木信吾さんより頂きました。ありがとうございます。）
とりあえず、１番目は何か考えましょう。ＥＰＲＳＵですね。
これを順に１，２，３，４，５とします。
文字と数字の対応表も作っておけば更に分かりやすくなります。

１２３４５
ＥＰＲＳＵ
両方の問題ともに、○○で始まるものは何個あるかを数えるのがポイントです。

(１)について
この最初の単語を並べ替えながら表を作っていきます。
ＳＵＰＥＲは４５２１３であることに注意します。
「小手調べ」の問題にしたがって、４５２１３以下の数字が何個あるかを調べればよくなります。 次のように表を作れば、さらに分かりやすくなると思います。
先頭の数字（文字）個数
１（Ｅ）４！＝２４個
２（Ｐ）２４個
３（Ｒ）２４個(小計２４×３＝７２個)
４１（ＳＥ）３！＝６個
４２，４３（ＳＰ，ＳＲ）６個ずつ（小計６×３＝１８個）
４５１（ＳＵＥ）２！＝２個
これの次が４５２１３（ＳＵＰＥＲ）ですから、全部で７２＋１８＋２＋１＝９３文字目となります。

(２)について
(１)のように、頭文字が同じ単語はいくつずつあるかを考えれば良いと思います。
（１）との違いは、残りがいくつあるのか気にすることです。
同様に表を作ってみます。
先頭の数字（文字）個数残り個数
１（Ｅ）４！＝２４２６
２（Ｐ）４！＝４８２
３（Ｒ）から始まる単語の２つ目ということになります。
３から始まる数字は小さい順に、３１２４５，３１２５４ですから、
これを文字で置きなおせば、５０番目はＲＥＰＵＳとなります。
慣れるために、もう1つ問題を出しますので、考えてみましょう。

解かずに修行に出る

問題　ＦＲＩＥＮＤの６文字を並べ替えて単語を作る。作った全ての単語を辞書式に並べていくとき、
　(１)ＦＲＩＥＮＤは何番目か。
　(２)２００番目の単語は何か。

解説へ
解答

(１)まず、単語内で辞書式に並べると、最初の文字は、ＤＥＦＩＮＲ。
よって、対応表は次の通り。
１２３４５６
ＤＥＦＩＮＲ
ＦＲＩＥＮＤを数字に対応させると３６４２５１。
１，２で始まるものはそれぞれ５！＝１２０個ずつある。（小計２４０）
３１，３２，３４，３５で始まるものはそれぞれ４！＝２４個ずつある。（小計９６）
３６１，３６２で始まるものは３！＝６個ずつある。（小計１２）
３６４１で始まるものは２！個ある。
次は３６４２１５，その次が３６４２５１（ＦＲＩＥＮＤ）だから、
全部で２４０＋９６＋１２＋２＋２＝３５２番目。
(２)１で始まる数字は５！＝１２０個あるので、
２００番目の単語は２から始まる数字の８０番目。
（並べるのが大変なときは更に絞ります。）
２１，２３，２４で始まる単語はそれぞれ４！＝２４個あるので、
８０＝２４×３＋８より、求める単語は２５から始まる数字の８番目。
さらに２５１から始まる単語は３！＝６個あるので、 求める文字は２５３から始まる単語の２番目。
２５３から始まる単語は順に、２５３１４６，２５３１６４だから、
２００番目の単語は、ＥＮＦＤＲＩ。

修行に出る

目次へ