이웃하지 않는 공 나열

검은색 공 $4$개를 일렬로 나열하면 공의 양 끝과 사이사이에 총 $5$개의 자리가 생긴다. 노란색 공과 보라색 공이 이웃하지 않으려면 이 $5$개의 자리 중 어떤 자리에도 노란색 공과 보라색 공이 함께 들어갈 수 없다. 따라서 $5$개의 자리 중 노란색 공이 들어갈 자리의 개수를 $a$(단, $a \geq 1$)라 하면 보라색 공은 남은 $\left( 5 - a \right)$개의 자리에 들어갈 수 있다. 노란색 공 $4$개를 $a$개의 자리에 적어도 $1$개씩 넣는 경우의 수는 방정식 $x _{1} + \cdots + x _{a} = 4$를 만족시키는 $x _{1}$, $x _{2}$, $\cdots$, $x _{a}$의 양의 정수해의 개수와 같으므로 $\mathit{_{a}} {\mathrm{H}} \mathit{_{4 - a}} = \mathit{_{3}} {\mathrm{C}} \mathit{_{a - 1}}$ $\cdots$$\cdots$ ㉠ 보라색 공 $4$개를 남은 $\left( 5 - a \right)$개의 자리에 넣는 경우의 수는 $\mathit{_{5 - a}} {\mathrm{H}} \mathit{_{4}} = \mathit{_{8 - a}} {\mathrm{C}} \mathit{_{4}}$ $\cdots$$\cdots$ ㉡ (ⅰ) $a = 1$일 때 노란색 공이 들어갈 자리를 정하는 경우의 수는 ${} _{5} \mathrm{C} _{1}$이므로 ㉠, ㉡에 의하여 구하는 경우의 수는 ${} _{5} \mathrm{C} _{1} \times {} _{3} \mathrm{C} _{0} \times {} _{7} \mathrm{C} _{4} = 5 \times 1 \times 35 = 175$ (ⅱ) $a = 2$일 때 노란색 공이 들어갈 자리를 정하는 경우의 수는 ${} _{5} \mathrm{C} _{2}$이므로 ㉠, ㉡에 의하여 구하는 경우의 수는 $\mathit{_{5}} {\mathrm{C}} \mathit{_{2}} \times \mathit{_{3}} {\mathrm{C}} \mathit{_{1}} \times \mathit{_{6}} {\mathrm{C}} \mathit{_{4}} = 10 \times 3 \times 15 = 450$ (ⅲ) $a = 3$일 때 노란색 공이 들어갈 자리를 정하는 경우의 수는 ${} _{5} \mathrm{C} _{3}$이므로 ㉠, ㉡에 의하여 구하는 경우의 수는 ${} _{5} \mathrm{C} _{3} \times {} _{3} \mathrm{C} _{2} \times {} _{5} \mathrm{C} _{4} = 10 \times 3 \times 5 = 150$ (ⅳ) $a = 4$일 때 노란색 공이 들어갈 자리를 정하는 경우의 수는 ${} _{5} \mathrm{C} _{4}$이므로 ㉠, ㉡에 의하여 구하는 경우의 수는 $\mathit{_{5}} {\mathrm{C}} \mathit{_{4}} \times \mathit{_{3}} {\mathrm{C}} \mathit{_{3}} \times \mathit{_{4}} {\mathrm{C}} \mathit{_{4}} = 5 \times 1 \times 1 = 5$ 이상에서 구하는 모든 경우의 수는 $175 + 450 + 150 + 5 = 780$ [다른 풀이] 노란색 공, 보라색 공, 검은색 공을 각각 $\mathrm{A}$, $\mathrm{B}$, $\mathrm{C}$라 하자. $4$개의 $\mathrm{A}$와 $4$개의 $\mathrm{B}$를 나열할 때 $\mathrm{AB}$ 또는 $\mathrm{BA}$가 나타나는 횟수를 $k$라 하면 $\mathrm{AB}$ 또는 $\mathrm{BA}$의 사이에 $\mathrm{C}$가 들어가야 하므로 $1 \leq k \leq 4$ $4$개의 $\mathrm{A}$와 $4$개의 $\mathrm{B}$를 나열했을 때 사이사이와 양 끝의 $9$곳 중 $k$ 곳에 $\mathrm{C}$를 한 개씩 배치했으므로 남은 $4 - k$개의 $\mathrm{C}$를 배치하는 경우의 수는 $\mathit{_{9}} \mathrm{H} _{\mathit{4} - k}$ $4$개의 $\mathrm{A}$와 $4$개의 $\mathrm{B}$의 묶음의 개수를 각각 $x$, $y$라 하면 (ⅰ) $k = 1$일 때 $\mathrm{AAAABBBB}$ 또는 $\mathrm{BBBBAAAA}$ 따라서 구하는 경우의 수는 $2 \times \mathit{_{9}} \mathrm{H} _{3} = 2 \times \mathit{_{9+3-1}} \mathrm{C} _{3} = 2 \times 165 = 330$ (ⅱ) $k = 2$일 때 $\mathrm{A} - B - A$ 또는 $\mathrm{B} - A - B$ (a) $x = 1$, $y = 2$일 때 $4$개의 $\mathrm{B}$를 $2$개의 묶음으로 나누는 경우의 수는 방정식 $a + b = 4$의 자연수인 해의 개수와 같으므로 $\mathit{_{2}} \mathrm{H} _{4 - 2} = \mathit{_{2 + 2 - 1}} \mathrm{C} _{2} = 3$ 따라서 구하는 경우의 수는 $3 \times \mathit{_{9}} \mathrm{H} _{2} = 3 \times \mathit{_{9 + 2 - 1}} \mathrm{C} _{2} = 3 \times 45 = 135$ (b) $x = 2$, $y = 1$일 때 (a)와 같은 방법으로 구하는 경우의 수는 $135$ (a), (b)에서 구하는 경우의 수는 $135 + 135 = 270$ (ⅲ) $k = 3$일 때 $x = 2$, $y = 2$이므로 $\mathrm{A} - B - A - B$ 또는 $\mathrm{B} - A - B - A$ (ⅱ)-(a)에서 $4$개의 $\mathrm{A}$와 $4$개의 $\mathrm{B}$를 $2$개의 묶음으로 나누는 경우의 수는 각각 $3$이다. 따라서 구하는 경우의 수는 $2 \times 3 \times 3 \times \mathit{_{9}} \mathrm{H} _{1} = 18 \times \mathit{_{9 + 1 - 1}} \mathrm{C} _{1} = 18 \times 9 = 162$ (ⅳ) $k = 4$일 때 $x = 3$, $y = 2$ 또는 $x = 2$, $y = 3$이므로 $\mathrm{A} - B - A - B - A$ 또는 $\mathrm{B} - A - B - A - B$ $4$개의 $\mathrm{A}$를 $3$개의 묶음으로 나누는 경우의 수는 방정식 $a + b + c = 4$의 자연수인 해의 개수와 같으므로 $\mathit{_{3}} \mathrm{H} _{4 - 3} = \mathit{_{3 + 1 - 1}} \mathrm{C} _{1} = 3$ 따라서 구하는 경우의 수는 $2 \times 3 \times 3 \times \mathit{_{9}} \mathrm{H} _{0} = 18 \times \mathit{_{9 + 0 - 1}} \mathrm{C} _{0} = 18 \times 1 = 18$ 이상에서 구하는 모든 경우의 수는 $330 + 270 + 162 + 18 = 780$