SHIKENの6文字を並び替えてできる順列を辞書式順序で並べる。EHIKNSを1番目とするとき、140番目の文字列を求める。

1. 問題の内容

SHIKENの6文字を並び替えてできる順列を辞書式順序で並べる。EHIKNSを1番目とするとき、140番目の文字列を求める。

2. 解き方の手順

SHIKENの6文字をアルファベット順に並べるとEHIKNSとなる。140番目の文字列を求めるために、各文字を先頭に固定した場合の順列の数を考える。

6文字の順列の総数は$6! = 720$通りである。

* 先頭の文字を固定した場合の順列の数は、$5! = 120$通りである。

* 140番目の文字列を求めるので、先頭がEのものは120個あるため、先頭はEではない。

* 次にHを先頭に固定すると、E,Hから始まる順列の数は $120 \times 2= 240$となり、140を超えるので、先頭はHではない。

* 次にIを先頭に固定すると、E,H,Iから始まる順列の数は$120 \times 3= 360$となり、140を超えるので、先頭はIではない。

* 次にKを先頭に固定すると、E,H,I,Kから始まる順列の数は$120 \times 4= 480$となり、140を超えるので、先頭はKではない。

* 次にNを先頭に固定すると、E,H,I,K,Nから始まる順列の数は$120 \times 5= 600$となり、140を超えるので、先頭はNではない。

* 次にSを先頭に固定すると、E,H,I,K,N,Sから始まる順列の数は$120 \times 6= 720$となり、140を超えるので、先頭はSではない。

先頭がEの場合を考える。1番目はEHIKNS, 120番目はESNKHIである。

140番目の文字列は、Eから始まる文字列ではない。

次にHを先頭に固定した場合を考える。EHIKNSを1番目と考えると、Hから始まる文字列は、Eから始まる文字列の次にくる。140番目の文字列はHから始まる文字列ではない。

先頭の文字から順に決めていく。

* Eで始まる文字列は$5! = 120$通り。

* Hで始まる文字列は$5! = 120$通り。

* Iで始まる文字列は$5! = 120$通り。

* Kで始まる文字列は$5! = 120$通り。

ここまでで$120 \times 4 = 480$通り。140番目の文字列はKより前に来る。したがって先頭の文字はE, H, I, Kではない。

140番目はEを先頭とする順列の120個の次にくる。

140 - 120 = 20

先頭がHの場合、Hの次はE, I, K, N, Sである。

* HEで始まる文字列は$4! = 24$通り。

20番目の文字列はHEから始まる文字列ではない。

140 - 120 = 20

HEから始まる文字列の次にくるのは、HIから始まる文字列である。

HIで始まる文字列は$4! = 24$通り。

20番目の文字列はHIから始まる文字列に含まれる。

20 < 24なので、140番目の文字列はHIから始まる。

HIまで決定。HIの次はE, K, N, Sである。

HIから始まる順列の中で、20番目の順列を求める。

HIEKNS, HIEKSN, HIENTS, HIESTN, HIENSK,...

* HIEで始まる文字列は$3! = 6$通り。

* HIKで始まる文字列は$3! = 6$通り。

* HINで始まる文字列は$3! = 6$通り。

ここまでで$6 \times 3 = 18$通り。

20 - 18 = 2

20番目の文字列はHISから始まる文字列に含まれる。

* HISから始まる文字列は$3! = 6$通り。

20番目はHISから始まる順列の2番目。

HISまで決定。HISの次はE, K, Nである。

2番目の文字列を求める。

HISEKN, HISENK, HISKEN,...

HISEKNが最初の文字列。

HISENKが2番目の文字列。

したがって140番目の文字列はHISENK。

3. 最終的な答え

HISENK