トップ› 九州大学› 1976年› 文系第5問

九州大学 1976年文系第5問解説

方針・初手

(1) 辞書式配列の順番を求める問題。先頭の文字を固定したときにできる順列の総数（階乗）を順次足し合わせることで、目的の順番が含まれるグループを絞り込んでいく。

(2) 「ともに $G$ と隣り合う」という条件から、$A$ と $C$ は $G$ の両隣に配置される必要がある。すなわち、$A, G, C$ がこの順、または $C, G, A$ の順で連続して並ぶ。これを1つのブロックとして扱い、「端にない」という条件の処理方法（余事象を考えるか、隙間に入れるか）によって解答を構成する。

解法1

(1) 7文字の順列の総数は $7! = 5040$ 通りである。先頭の文字を固定したとき、残りの6文字の順列は $6! = 720$ 通りある。 $A$ で始まる順列は $720$ 個あり、$B$ で始まる順列も $720$ 個ある。ここまでで順列は $720 \times 2 = 1440$ 個ある。 $720 < 1234 \leqq 1440$ より、第1234番目の順列の先頭の文字は $B$ である。

次に、先頭が $B$ で、2文字目を固定したときの順列は $5! = 120$ 通りある。 $BA, BC, BD, BE$ で始まる順列はそれぞれ $120$ 個あり、合計 $120 \times 4 = 480$ 個である。 $A$ で始まる順列の数と合わせると、$720 + 480 = 1200$ 個となる。 $1200 < 1234 \leqq 1200 + 120 = 1320$ より、2文字目の文字は $F$ である。第1234番目は、$BF$ で始まる順列の中で $1234 - 1200 = 34$ 番目となる。

先頭が $BF$ で、3文字目を固定したときの順列は $4! = 24$ 通りある。 $BFA$ で始まる順列は $24$ 個ある。 $24 < 34 \leqq 24 + 24 = 48$ より、3文字目の文字は $C$ である。第1234番目は、$BFC$ で始まる順列の中で $34 - 24 = 10$ 番目となる。

先頭が $BFC$ で、4文字目を固定したときの順列は $3! = 6$ 通りある。 $BFC$ に続く文字はアルファベット順に $A, D, E, G$ である。 $BFCA$ で始まる順列は $6$ 個ある。 $6 < 10 \leqq 6 + 6 = 12$ より、4文字目の文字は $D$ である。第1234番目は、$BFCD$ で始まる順列の中で $10 - 6 = 4$ 番目となる。

先頭が $BFCD$ で、5文字目を固定したときの順列は $2! = 2$ 通りある。 $BFCD$ に続く文字はアルファベット順に $A, E, G$ である。 $BFCDA$ で始まる順列は $2$ 個ある。 $2 < 4 \leqq 2 + 2 = 4$ より、5文字目の文字は $E$ である。第1234番目は、$BFCDE$ で始まる順列の中で $4 - 2 = 2$ 番目（最後）となる。

残りの文字は $A, G$ であり、これらを辞書順に並べたものが1番目、逆順にしたものが2番目である。 1番目：$BFCDEAG$ 2番目：$BFCDEGA$

したがって、求める順列は $BFCDEGA$ である。

(2) $A$ と $C$ がともに $G$ と隣り合うのは、$A, G, C$ がこの順に並ぶか、$C, G, A$ の順に並ぶときである。この3文字の並びを1つのまとまり $X$ と考える。$X$ の内部の並び方は $2$ 通りである。

$X$ と残りの4文字（$B, D, E, F$）の合計5つの要素を1列に並べる並べ方は、

$$5! = 120 \text{ (通り)}$$

このうち、$A$ または $C$ が端にくるのは、$X$ が全体の左端または右端に配置される場合である。 $X$ が左端に配置される並べ方は、残りの4文字をその右に並べるので、

$$4! = 24 \text{ (通り)}$$

$X$ が右端に配置される並べ方も同様に、

$$4! = 24 \text{ (通り)}$$

よって、$X$ が両端のいずれにも配置されない並べ方は、

$$120 - (24 + 24) = 72 \text{ (通り)}$$

$X$ の内部の並び方 $2$ 通りを考慮して、求める順列の総数は、

$$72 \times 2 = 144 \text{ (通り)}$$

解法2

(2)の別解

$A$ と $C$ がともに $G$ と隣り合うという条件から、$A, G, C$ または $C, G, A$ の並びを1つのまとまり $X$ とする。$X$ の内部の並び方は $2$ 通りである。

先に、残りの4文字 $B, D, E, F$ を1列に並べる。その並べ方は、

$$4! = 24 \text{ (通り)}$$

次に、この4文字の両端および文字の間の合計5箇所の隙間のいずれかに、$X$ を挿入する。ただし、「$A$ と $C$ がいずれも端にない」という条件から、$X$ を両端の隙間に挿入することはできない（$X$ を端に置くと、$A$ または $C$ が必ず端になってしまうため）。したがって、$X$ を挿入できる場所は、4文字の間の3箇所の隙間のいずれかである。その選び方は、

$$3 \text{ (通り)}$$

以上と $X$ 内部の並び方 $2$ 通りを掛け合わせて、求める順列の総数は、

$$24 \times 3 \times 2 = 144 \text{ (通り)}$$

解説

(1) は辞書式配列の典型問題である。先頭の文字から順に、階乗の数を用いてどのブロックに属するかを絞り込んでいく手順を正確に実行できるかが問われている。

(2) は「特定の要素が隣り合う」条件と「特定の要素が両端にこない」条件の複合問題である。「隣り合う」ものをブロック化することは定石であるが、その後の方針として解法1のように「全体から端にくる場合（余事象）を引く」か、解法2のように「他の要素を先に並べてから隙間に入れる」かの2通りのアプローチが考えられる。特に「〜が隣り合わない」や「〜が端にこない」といった条件の処理には、解法2のような「隙間に入れる」という発想が非常に有効であり、計算ミスも減らしやすいため習得しておきたい。