1. 問題の内容
SHIKENの6文字を並び替えてできる順列を辞書式順序で並べる。EHIKNSを1番目とするとき、140番目の文字列を求める。
2. 解き方の手順
SHIKENの6文字をアルファベット順に並べるとEHIKNSとなる。140番目の文字列を求めるために、各文字を先頭に固定した場合の順列の数を考える。
6文字の順列の総数は通りである。
* 先頭の文字を固定した場合の順列の数は、通りである。
* 140番目の文字列を求めるので、先頭がEのものは120個あるため、先頭はEではない。
* 次にHを先頭に固定すると、E,Hから始まる順列の数は となり、140を超えるので、先頭はHではない。
* 次にIを先頭に固定すると、E,H,Iから始まる順列の数はとなり、140を超えるので、先頭はIではない。
* 次にKを先頭に固定すると、E,H,I,Kから始まる順列の数はとなり、140を超えるので、先頭はKではない。
* 次にNを先頭に固定すると、E,H,I,K,Nから始まる順列の数はとなり、140を超えるので、先頭はNではない。
* 次にSを先頭に固定すると、E,H,I,K,N,Sから始まる順列の数はとなり、140を超えるので、先頭はSではない。
先頭がEの場合を考える。1番目はEHIKNS, 120番目はESNKHIである。
140番目の文字列は、Eから始まる文字列ではない。
次にHを先頭に固定した場合を考える。EHIKNSを1番目と考えると、Hから始まる文字列は、Eから始まる文字列の次にくる。140番目の文字列はHから始まる文字列ではない。
先頭の文字から順に決めていく。
* Eで始まる文字列は通り。
* Hで始まる文字列は通り。
* Iで始まる文字列は通り。
* Kで始まる文字列は通り。
ここまでで通り。140番目の文字列はKより前に来る。したがって先頭の文字はE, H, I, Kではない。
140番目はEを先頭とする順列の120個の次にくる。
140 - 120 = 20
先頭がHの場合、Hの次はE, I, K, N, Sである。
* HEで始まる文字列は通り。
20番目の文字列はHEから始まる文字列ではない。
140 - 120 = 20
HEから始まる文字列の次にくるのは、HIから始まる文字列である。
HIで始まる文字列は通り。
20番目の文字列はHIから始まる文字列に含まれる。
20 < 24なので、140番目の文字列はHIから始まる。
HIまで決定。HIの次はE, K, N, Sである。
HIから始まる順列の中で、20番目の順列を求める。
HIEKNS, HIEKSN, HIENTS, HIESTN, HIENSK,...
* HIEで始まる文字列は通り。
* HIKで始まる文字列は通り。
* HINで始まる文字列は通り。
ここまでで通り。
20 - 18 = 2
20番目の文字列はHISから始まる文字列に含まれる。
* HISから始まる文字列は通り。
20番目はHISから始まる順列の2番目。
HISまで決定。HISの次はE, K, Nである。
2番目の文字列を求める。
HISEKN, HISENK, HISKEN,...
HISEKNが最初の文字列。
HISENKが2番目の文字列。
したがって140番目の文字列はHISENK。
3. 最終的な答え
HISENK