【標準】辞書式に並べると何番目？

ここでは、辞書式に並べた場合に、特定のものが何番目に表れるか、逆に、〇番目に表れるのは何か、を求める問題を考えていきます。

辞書式に並べる

例えば、 A, H, M, T という4文字を1回ずつ使って、長さが4の文字列を作るとします。書き出していく場合は、モレやダブりがないように、順番に書き出していった方がいいですね。このとき、紙の辞書に出てくる順番のように、次のようにして並べると、モレやダブりが発生しにくくなります。

AHMT
AHTM
AMHT
AMTH
ATHM
ATMH
……（続く）

このように、1文字目を比較して、アルファベット順で先に出てくるものを先に書き出し、1文字目が同じものに対しては、2文字目を比較して、アルファベット順で先に出てくるものを先に書き出し、…という順に書き出していくことを、辞書式に並べると言います。このような順番を、辞書順や辞書式順序(lexicographic order / dictionary order)と言います。

【基本】まとめて数えるでも出てきましたが、モレやダブりがでないように、書き出すときには辞書順にしましょう。また、数字を並べる場合も、小さい順にし（もしくは大きい順）、順番に並べるようにしましょう。

辞書順で並べたときに何番目に来るか

「辞書式に並べる」という言葉が、問題文に出てくることもあります。

樹形図で考え、上から数えてもいいのですが、少し面倒ですね。計算を使って求められないか考えてみましょう。

MATH が出てくるまでのことを考えてみましょう。まずは1文字目がAの文字列が続きます。上の例でも書いた6通りですね。式で書けば\[ 3!=6 \]通りです。続いて、1文字目がHのものが続きます。これも6通りです。そしてようやく1文字目がMの文字列が登場します。つまり、1文字目がMの文字列が始まる前に12個の文字列が並んでいることになります。

13番目は、1文字目がMからはじまる最初の文字列なので、「MAHT」になりますね。この次は「MATH」です。よって、MATH は14番目の文字列だということがわかります。

このように、求めたいものが出てくるまでの間に、何が並んでいるかを数えれば、求めたいものが何番目に出てくるかがわかります。

次に、22番目の文字列が何かを考えます。辞書式に並んでいるので、1文字目から順番に特定していきます。

1文字目がAの文字列は6個あります。1文字目がHのもの、Mのもの、Tのものもそれぞれ6個あります。よって、Tから始まるものは、19番目から24番目であることがわかり、22番目はこの中にあることがわかります。1文字目は、Tです。

続いて、2文字目を考えましょう。2文字目は、Aのもの、Hのもの、Tのものがそれぞれ2個ずつあります。それぞれ、19・20番目、21・22番目、23・24番目です。よって、22番目の文字列は、2文字目がHだとわかります。また、THからはじまるものの2つ目が22番目の文字列なので、「THMA」が22番目の文字だとわかります。

このように、〇番目の文字が何かを求めるには、1文字目が何か、2文字目が何か、と順番に考えていけばいいことがわかります。

おわりに

ここでは、辞書式に並べたときに、特定のものが何番目にくるかを求める問題を見ました。考えているモノの上に、いくつモノが並んでいるかを考えれば出すことができました。樹形図で考えると、いくつかの枝のかたまりをまとめて数えていることになります。すべて書き出すよりも部分的に数えて、部分的に樹形図で考えると間違わずに解けるでしょう。