数学A 場合の数 問題 31 解説

方針・初手

重複する文字 $k,k$ と $u,u$ があるので、単純な順列ではなく、同じ文字の入れ替えを同一視して数える。

残り $n$ 個の文字のうち、同じ文字がそれぞれ $r_1,r_2,\ldots$ 個あるとき、並べ方は

$$ \frac{n!}{r_1!r_2!\cdots} $$

である。

辞書式順序で番号を求めるときは、左から順に見て、目的の文字より小さい文字をその位置に置いた場合の個数を加えていく。

解法1

(1)

$a$ で始まる文字列を考える。先頭を $a$ に固定すると、残りは

$$ g,k,k,o,u,u $$

の $6$ 文字である。

このうち $k$ が $2$ 個、$u$ が $2$ 個あるので、並べ方は

$$ \frac{6!}{2!2!}=180 $$

である。

したがって、$a$ で始まる文字列は $180$ 通りである。

(2)

$ga$ で始まる文字列を考える。先頭から $g,a$ を固定すると、残りは

$$ k,k,o,u,u $$

の $5$ 文字である。

このうち $k$ が $2$ 個、$u$ が $2$ 個あるので、並べ方は

$$ \frac{5!}{2!2!}=30 $$

である。

したがって、$ga$ で始まる文字列は $30$ 通りである。

(3)

$gk$ で始まる文字列を考える。先頭から $g,k$ を固定すると、残りは

$$ a,k,o,u,u $$

の $5$ 文字である。

このうち $u$ が $2$ 個あるので、並べ方は

$$ \frac{5!}{2!}=60 $$

である。

したがって、$gk$ で始まる文字列は $60$ 通りである。

(4)

求める文字列は

$$ goukaku $$

である。

アルファベット順は

$$ a<g<k<o<u $$

である。

まず、$goukaku$ より前に来る文字列の個数を数える。

1文字目が $g$ より小さいものは、$a$ で始まる文字列である。これは （1） より

$$ 180 $$

通りである。

次に、1文字目を $g$ に固定して、2文字目が $o$ より小さいものを数える。残っている文字は

$$ a,k,k,o,u,u $$

であり、$o$ より小さい文字は $a,k$ である。

$ga$ で始まる文字列は （2） より

$$ 30 $$

通りである。

$gk$ で始まる文字列は （3） より

$$ 60 $$

通りである。

したがって、ここまでで

$$ 180+30+60=270 $$

通りが $goukaku$ より前にある。

次に、先頭2文字を $go$ に固定する。残りは

$$ a,k,k,u,u $$

であり、3文字目の $u$ より小さい文字は $a,k$ である。

$goa$ で始まる文字列では、残りは

$$ k,k,u,u $$

であるから、個数は

$$ \frac{4!}{2!2!}=6 $$

である。

$gok$ で始まる文字列では、残りは

$$ a,k,u,u $$

であるから、個数は

$$ \frac{4!}{2!}=12 $$

である。

よって、さらに

$$ 6+12=18 $$

通りが前にある。

ここまでで

$$ 270+18=288 $$

通りである。

次に、先頭3文字を $gou$ に固定する。残りは

$$ a,k,k,u $$

であり、4文字目の $k$ より小さい文字は $a$ である。

$goua$ で始まる文字列では、残りは

$$ k,k,u $$

であるから、個数は

$$ \frac{3!}{2!}=3 $$

である。

したがって、$goukaku$ より前にある文字列の総数は

$$ 288+3=291 $$

通りである。

番号は $1$ 番から付けるので、$goukaku$ の番号は

$$ 291+1=292 $$

である。

解説

この問題では、重複する文字を含む順列の数え上げと、辞書式順序における順位計算が中心である。

順位を求めるときは、目的の文字列そのものを直接並べて探すのではなく、左から順に固定しながら、「その位置で目的の文字より小さい文字を置いた場合」を数えるのが基本である。

特に $goukaku$ の順位では、$g$ より前の $a$ 始まり、$go$ より前の $ga,gk$ 始まり、$gou$ より前の $goa,gok$ 始まり、$gouk$ より前の $goua$ 始まりを順に加えればよい。

答え

(1)

$180$ 通り

(2)

$30$ 通り

(3)

$60$ 通り

(4)

$292$ 番目