辞書式に並べる順列

スポンサーリンク
a,\ b,\ c,\ d,\ eの5文字を1個ずつ使ってできるすべての文字列をアルファベット順に 並べる.  (1)\ \ dbeac\ は何番目にあるか.       (2)\ \ 88番目は何か. \\ 辞書式に並べる順列}a,\ b,\ c,\ d,\ eをそれぞれ1,\ 2,\ 3,\ 4,\ 5}とし,\ 42513が何番目か}を求める. アルファベットのままではわかりづらいならば,\ このように数字に置き換えて考えればよい. 最高位を小さい数字順に固定し,\ それぞれ何通りあるかを求めていく.} 最高位が1の数は,\ 残りの4数を下4桁に並べることになるから,\ 4!=24\,通りある. 同様に考えていくと,\ 最高位が1,\ 2,\ 3の数は全部で24×3=72個あるとわかる. 目標は42513なので,\ 最高位が4になってからは千の位も固定して考えていく.} 41○○○となる数が6通りあり,\ ここまでの数は全部で72+6=78個である. つまり,\ 42○○○が79番目から始まる.\ ここまで来れば,\ 後は具体的に書き出す}ほうが早い. 421○○,\ 423○○,\ 425○○の順で書き出せば,\ 42○○○の5番目だとわかる. (1)とは逆に文字列を求める問題だが,\ やることは同じである. 最高位が1,\ 2,\ 3の数は24×3=72個,\ 最高位が1,\ 2,\ 3,\ 4の数は24×4=96個ある. よって,\ まず88番目の数の最高位は4}であるとわかる. 次に,\ 千の位を特定することを目指す. 42○○○の最後の数は72+6+6=84\ 番目,\ 43○○○の最後の数は84+6=90\ 番目}である. よって,\ 求める数が43○○○とわかり,\ 84+4=88より,\ 43○○○を順に4個書き出せばよい. 90番目の43521から戻ってもよいが,\ 混乱して間違えやすい.  43521,\ 43512,\ 43251 最後,\ 忘れずにアルファベットに戻して答える.