문자열의 개수

[출제의도] 중복순열을 활용하여 문제해결하기 문자열 $aaa$와 이웃한 자리를 △, 문자열 $aaa$와 이웃하지 않는 자리를 □로 나타내면 조건 (가)를 만족시키는 문자열의 형태는 $aaa$△□□□, △$aaa$△□□, □△$aaa$△□, □□△$aaa$△, □□□△$aaa$의 $5$가지이고 조건 (나)에 의하여 △에 나열될 수 있는 문자는 $b$ 또는 $c$이다. (ⅰ) $aaa$△□□□일 때 (a) △에 $b$가 나열된 경우 $3$개의 □에 세 문자를 나열하는 경우의 수는 서로 다른 $3$개에서 $3$개를 택하는 중복순열의 수와 같으므로 $\displaystyle {} _{3} \prod _{3} = 27$ 이때 조건을 만족시키지 않는 문자열은 $aaabbba$, $aaabbbb$, $aaabbbc$, $aaabaaa$, $aaabccc$의 $5$가지이다. 그러므로 만들 수 있는 문자열의 개수는 $27 - 5 = 22$ (b) △에 $c$가 나열된 경우 (a)와 같은 방법으로 구하면 만들 수 있는 문자열의 개수는 $22$ (a), (b)에 의하여 만들 수 있는 문자열의 개수는 $22 + 22 = 44$ (ⅱ) △$aaa$△□□일 때 $2$개의 △에 $a$가 아닌 두 문자를 나열하는 경우의 수는 서로 다른 $2$개에서 $2$개를 택하는 중복순열의 수와 같으므로 $\displaystyle {} _{2} \prod _{2} = 4$ $2$개의 □에 세 문자를 나열하는 경우의 수는 서로 다른 $3$개에서 $2$개를 택하는 중복순열의 수와 같으므로 $\displaystyle {} _{3} \prod _{2} = 9$ 이때 조건을 만족시키지 않는 문자열은 $baaabbb$, $baaaccc$, $caaabbb$, $caaaccc$의 $4$가지이다. 그러므로 만들 수 있는 문자열의 개수는 $4 \times 9 - 4 = 32$ (ⅲ) □△$aaa$△□일 때 $2$개의 △에 $a$가 아닌 두 문자를 나열하는 경우의 수는 서로 다른 $2$개에서 $2$개를 택하는 중복순열의 수와 같으므로 $\displaystyle {} _{2} \prod _{2} = 4$ $2$개의 □에 세 문자를 나열하는 경우의 수는 서로 다른 $3$개에서 $2$개를 택하는 중복순열의 수와 같으므로 $\displaystyle {} _{3} \prod _{2} = 9$ 그러므로 만들 수 있는 문자열의 개수는 $4 \times 9 = 36$ (ⅳ) □□△$aaa$△일 때 (ⅱ)와 같은 방법으로 구하면 만들 수 있는 문자열의 개수는 $32$ (ⅴ) □□□△$aaa$일 때 (ⅰ)과 같은 방법으로 구하면 만들 수 있는 문자열의 개수는 $44$ (ⅰ) ~ (ⅴ)에 의하여 만들 수 있는 모든 문자열의 개수는 $44 + 32 + 36 + 32 + 44 = 188$