辞書式に並べたとき何番目問題

上野竜生です。数字を並べ替えたり文字を辞書式に並べ替える場合の問題を解説します。

辞書式に並べたとき何番目

スポンサーリンク

数字の並べ替え

「1」「2」「3」「4」「5」「6」「7」の7つの数字を並べ替えてできる5040個の数字を小さいほうから順に並べ替える。
(1) 「3617542」は何番目にくるか?
(2) 2020番目に来るものは何か?
答え(1) 1□□□□□□ の形になるものは6!=720個。
2□□□□□□ も720個。
31□□□□□ は5!=120個。
32□□□□□ も120個。
34□□□□□ も120個。
35□□□□□ も120個。
3612□□□ は3!=6個。
3614□□□ も6個。
3615□□□ も6個。
36172□□ は2個。
36174□□ も2個。
3617524
3617542
なので720+720+ 120+120+120+120 + 6+6+6+ 2+2+2
=1440+480+18+6
=1944   答.1944番目
(2) 同様に数えていきます。
(1)と同様にすると
35□□□□□ までの合計は720+720+120+120+120+120=1920個。
361□□□□ が24個。
362□□□□ も24個。
364□□□□ も24個
365□□□□ も24個でここまでの合計は1920+24+24+24+24=2016個。
3671245 ・・・2017番目
3671254 ・・・2018番目
3671425 ・・・2019番目
3671452 ・・・2020番目(答)
このように丁寧に数えるのみです。
(1)ではどこまで計算すればいいか見えていますが(2)では途中でオーバーしていないか気を付けながら数える必要があります。

文字の並べ替え

「う」「が」「が」「き」「く」「す」「す」を並べ替えてできる文字列を辞書式に順番に並べ替える。たとえば1番目の文字列は「うががきくすす」であり,2番目の文字列は「うががきすくす」・・・である。
(1) 「すうがくがすき」は何番目の文字列か?
(2) 1000番目の文字列は何か?

先ほどの例題との違いは数字ではなく文字になっていることと同じ文字が複数使われていることです。これにより前の問題より丁寧にカウントする必要が出ます。

答え(1)
う□□□□□□ の形になるのは\(\displaystyle \frac{6!}{2!2!}=180 \)個。
が□□□□□□ の形になるのは\(\displaystyle \frac{6!}{2!}=360\)個。<下に解説あり>
き□□□□□□ の形になるのは\(\displaystyle \frac{6!}{2!2!}=180 \)個。
く□□□□□□ の形になるのは\(\displaystyle \frac{6!}{2!2!}=180 \)個。
すうがが□□□ の形になるのは3!=6個。
すうがき□□□ の形になるのは3!=6個。
すうがくがきす ・・・1個
すうがくがすき ・・・1個
以上より180+360+180+180+6+6+1+1=914番目。
(2)
(1)と同様にして
く□□□□□□ までの個数は900個。
すう□□□□□ の個数は\(\displaystyle \frac{5!}{2!}=60 \)個
すがう□□□□ の個数は4!=24個。
すががう□□□ の個数は3!=6個。
すががき□□□ の個数は3!=6個。 ここまでで996個。
997番目は すががくうきす
998番目は すががくうすき
999番目は すががくきうす
1000番目は すががくきすう

う□□□□□□ の形になるのは\(\displaystyle \frac{6!}{2!2!}=180 \)個。
が□□□□□□ の形になるのは\(\displaystyle \frac{6!}{2!}=360\)個。の部分について
う□□□□□□ の形になるとき□の中に「ががきくすす」が入ります。並べ方は6!個ですが2つの「が」と2つの「す」はどちらが先でもいいので2!×2!=4個ずつ同じものが重複しています。なので4で割ります。
が□□□□□□ の形になるとき□の中に「うがきくすす」が入ります。並べ方は6!個ですが2つの「す」はどちらが先でもいいので2!=2個ずつ同じものが重複しています。なので2で割ります。
一見2つは同じに見えるので「同様にして」とごまかして同じ個数でカウントしてしまう罠が潜んでいるのです。

数学はもちろん他の科目も勉強できる「スタディサプリ」なら人気講師の授業動画で、塾にいかなくてもまるで塾にいったかのような勉強ができます。塾と比較すると格安で、しかも無料おためしもできます。当サイトオススメのサイトです。


スタディサプリについて解説したページはこちら
スポンサーリンク

シェアする

  • このエントリーをはてなブックマークに追加

フォローする