3岐阜大学 2008年 数学 第3問解答・解説

(1) $X=\mathrm{GIFU}$を一つの記号とみる。$F$は一字なのでこの連続部分は高々一つである。

残る$G,I,U$と合わせた異なる4記号の順列だから、$4!=24$通り。

(2) $B=\mathrm{FU}$を一つの記号とみる。$F$が一字なので縮約の仕方は一意である。残り$G,G,I,I,U$の列は$5!/(2!2!)=30$通り。先頭$k$字の後に$B$を挿入するとき、$B$より左に$GI$があるためには、先頭$k$字に$GI$が含まれればよい。そのような列数を$N_k$とすると $$N_0=N_1=0,\quad N_2=6,\quad N_3=12,\quad N_4=17,\quad N_5=21.$$ $k=2$では先頭$GI$以外の3字を並べて$3!=6$通り。$k=3$では$GI$の開始位置が1又は2で各6通り、両方の同時成立はない。 $k=4$では先頭4字に$GI$のない列を除く。末字$U$なら先頭は$IIGG$だけ。末字$G$の場合、先頭$I,I,G,U$の12列から$GI$を含む6列を除いて6列。末字$I$も同様に6列。したがって$N_4=30-(1+6+6)=17$。 $k=5$で$GI$のない列は、$U$の左右で$I$を$G$より先に並べる必要がある。$U$より左の字数が0,1,2,3,4の場合の数はそれぞれ1,2,3,2,1。例えば2字の場合は$II,IG,GG$の3通りである。よって$N_5=30-9=21$。 挿入位置と縮約後の列は一意に復元できるので重複はなく、求める数は $$\displaystyle \sum\limits _{k=0}^{5}N_k=6+12+17+21=56\text{通り}.$$