辞書の順に並べると何番目か、逆に何番目は何か

1、2、3、4、5 の 5 枚で作った 5 桁の整数を小さい順に並べます。$34125$ は何番目か。そして 70 番目は何か。

$5!=120$ 個を書き出せば分かりますが、それでは 6 枚 7 枚に増えたときに動けません。上の位から区切っていく数え方に切り替えます。

上の位で束をつくる

小さい順に並べると、まず万の位で 5 つの束に分かれます。1 で始まる束、2 で始まる束、と続く。

どの束にも、残り 4 枚の並べ方の $4!=24$ 個が入ります。束の大きさがそろっている。

束の中では、さらに千の位で 5 つ… ではなく 4 つの小束に分かれ、各小束は $3!=6$ 個。以下同じように細かくなります。

例：34125 は何番目か

自分より小さい数がいくつあるかを、上の位から数えます。

万の位が 1 か 2 のものは全部小さい。$2\times 4!=48$ 個。

万の位が 3 で千の位が 1 か 2 のものも小さい。$2\times 3!=12$ 個。

万の位が 3、千の位が 4 で、百の位が 1 のもの。ここで $34125$ 自身の束に入りました。残るカードは 2 と 5 で、$34125$ と $34152$ の 2 個。

$34125$ はその 1 番目です。自分より小さいものが $48+12=60$ 個なので、$34125$ は 61 番目になります。

例：70 番目を求める

逆向きに、順位から数を組み立てます。

万の位が 1 の束が 1 番目から 24 番目、2 の束が 25 から 48、3 の束が 49 から 72。70 番目は 3 の束の中です。

3 の束の中では $70-48=22$ 番目。残るカードは 1、2、4、5 で、千の位ごとに 6 個ずつ入ります。

$22$ 番目は、$6\times 3=18<22\le 24=6\times 4$ なので 4 番目の小束。千の位は 4 番目に小さい 5 です。

さらに $22-18=4$ 番目。残るカードは 1、2、4 で、百の位ごとに 2 個ずつ。$4=2\times 2$ なので 2 番目の小束で、百の位は 2。

残り 1 番目と 2 番目のうち 2 番目。残るカードは 1 と 4 なので、$41$ の並び。答えは $35241$ です。

割り算で機械的に出す

同じ手順は、割り算の繰り返しでも書けます。順位から 1 を引いて 0 から数え、階乗で割っていく^[1]。

$70-1=69$。$69÷24=2$ 余り 21 なので、残りカードの 3 番目である 3 が万の位。

$21÷6=3$ 余り 3 なので、残り 1、2、4、5 の 4 番目である 5 が千の位。

$3÷2=1$ 余り 1 なので、残り 1、2、4 の 2 番目である 2 が百の位。$1÷1=1$ 余り 0 で、残り 1、4 の 2 番目である 4。最後に 1 が残ります。

$35241$ になりました。商が「残りの何番目か」を、0 から数えた形で表しています。

例：辞書式の文字列

数字でなく文字でも同じです。A、B、C、D、E を並べた 120 個の文字列で、CADEB は何番目か。

A、B で始まるものが $2\times 24=48$ 個。C で始まるうち、2 文字目が A の束に入ります。

2 文字目が A の束では、3 文字目ごとに $2!=2$ 個ずつ並びます。3 文字目が B の束が 2 個あり、CADEB はその次の D の束の中。

D の束は CADBE と CADEB の 2 個で、CADEB は 2 番目です。$48+2+2=52$ 番目になります。

例：ある数以上はいくつあるか

同じ 120 個のうち、$40000$ 以上のものを数えます。

万の位が 4 か 5 なら条件を満たします。$2\times 4!=48$ 個。

$35000$ 以上なら、万の位が 4 か 5 の 48 個に、3 で始まって千の位が 5 のもの $3!=6$ 個を足して 54 個です。

「以上」と「より大きい」の違いにも気をつけます。境目の数自身を含めるかどうかで 1 個ずれる。

例：0 を含む場合

0、1、2、3 の 4 枚で 4 桁の整数を作り、小さい順に並べます。総数は $3\times 3!=18$ 個。

千の位は 1、2、3 のいずれかで、それぞれ $3!=6$ 個ずつ。束の大きさは変わりません。

$2301$ が何番目かを数えます。千の位が 1 のものが 6 個。千の位が 2 で百の位が 0 か 1 のものが $2\times 2=4$ 個。

$2301$ は千の位 2、百の位 3 の束の中で、残るカードが 0 と 1 なので $2301$ と $2310$ の 1 番目。$6+4+1=11$ 番目です。

0 が使えない位は先頭だけなので、2 桁目より下では 0 も普通に順序に入る。ここを飛ばさない。

例：同じものを含む場合

1、1、2、3 の 4 枚を並べてできる 4 桁の整数を小さい順に並べます。総数は $\frac{4!}{2!}=12$ 個。

束の大きさがそろわなくなります。千の位が 1 の束は残り 1、2、3 の $3!=6$ 個。千の位が 2 の束は残り 1、1、3 の $\frac{3!}{2!}=3$ 個。3 の束も 3 個。

$2311$ が何番目かを数えます。千の位が 1 の 6 個が先。千の位が 2 で百の位が 1 のものが、残り 1、3 の 2 個。

$2311$ は千の位 2、百の位 3 の束にあり、残り 1、1 なので 1 個だけ。$6+2+1=9$ 番目です。

同じものがあると束の大きさが位ごとに変わる。毎回、残りのカードから数え直します。

よくある誤り

上の位から束に分け、自分がどの束の何番目にいるかを追う。順位から数を作るときは、その逆をたどるだけです。

参考文献

^[1] が順位と並べ方を対応させる仕組み、^[2] が辞書式の順序、^[3] が順列の公式、^[4] と ^[5] が各国語での整理です。