어떤 문제인가
이 문제는 주어진 조건에 맞게 공들을 일렬로 나열하는 경우의 수를 구하는 문제입니다.
여기서 사용할 핵심 개념은 다음과 같습니다:
- 같은 것이 있는 순열: 같은 색의 공끼리는 구별하지 않으므로, 순서를 바꿨을 때 같은 경우로 취급해야 합니다.
- 이웃하지 않게 나열하기 (칸막이 모델): 특정 원소들이 이웃하지 않도록 할 때는, 이웃해도 상관없는 원소(여기서는 검은색 공)를 먼저 나열하여 '칸막이' 역할을 하게 만든 뒤, 그 사이사이에 다른 원소들을 끼워 넣는 아이디어를 사용합니다.
- **조합($\binom{n}{r}$ 또는 $_nC_r$)과 분할**: 빈자리에 공을 나누어 담는 방법을 계산하기 위해 조합의 개념을 활용합니다.
단계별 풀이
1단계: 검은색 공을 먼저 배치하여 '빈칸' 만들기
노란색 공($Y$)과 보라색 공($P$)이 서로 이웃하지 않으려면, 두 색깔의 공 사이에는 반드시 검은색 공($B$)이 최소한 하나는 끼어 있어야 합니다.
따라서 아무런 제약이 없는 검은색 공 4개를 먼저 일렬로 나열합니다. 검은색 공은 모두 같으므로 나열하는 방법은 $1$가지뿐입니다.
$$B \quad B \quad B \quad B$$
이 검은색 공들 사이와 양 끝에 노란색 공과 보라색 공이 들어갈 수 있는 5개의 빈칸(영역)이 생깁니다. 이 영역들을 왼쪽부터 순서대로 $S_1, S_2, S_3, S_4, S_5$라고 부르겠습니다.
$$\underline{\quad S_1 \quad} \ B \ \underline{\quad S_2 \quad} \ B \ \underline{\quad S_3 \quad} \ B \ \underline{\quad S_4 \quad} \ B \ \underline{\quad S_5 \quad}$$
2단계: 빈칸에 공을 넣을 때의 규칙 이해하기
노란색 공과 보라색 공은 서로 이웃할 수 없습니다. 만약 어떤 하나의 영역(예를 들어 $S_2$)에 노란색 공과 보라색 공이 동시에 들어가게 된다면, 그 영역 안에는 검은색 공이 없으므로 노란색과 보라색이 서로 붙어 있게 됩니다.
따라서 아주 중요한 규칙이 생깁니다:
> **"5개의 영역($S_1 \sim S_5$) 각각에는 노란색 공만 들어가거나, 보라색 공만 들어가야 하며, 두 색이 동시에 들어갈 수는 없다. (물론 비어 있을 수는 있다.)"**
즉, 5개의 영역 중 노란색 공이 들어갈 영역들과 보라색 공이 들어갈 영역들은 서로 완전히 겹치지 않아야 합니다.
3단계: 영역 나누기 (변수 설정)
- 노란색 공 4개를 넣을 영역의 개수를 $k$개라고 합시다. ($1 \le k \le 4$)
- 보라색 공 4개를 넣을 영역의 개수를 $m$개라고 합시다. ($1 \le m \le 4$)
전체 영역이 5개뿐이므로, 노란색이 들어갈 영역과 보라색이 들어갈 영역의 합은 5를 넘을 수 없습니다.
$$k + m \le 5$$
4단계: 경우의 수 공식 세우기
특정한 $k$와 $m$에 대해 공을 배치하는 방법의 수는 다음과 같이 세 단계로 곱해서 구합니다.
- 영역 선택하기: 5개의 영역 중 노란색 공을 넣을 $k$개의 영역을 고르고, 남은 $5-k$개의 영역 중 보라색 공을 넣을 $m$개의 영역을 고릅니다.
$$\binom{5}{k} \times \binom{5-k}{m}$$
- **노란색 공 4개를 $k$개의 영역에 나누어 담기**: 각 영역에는 적어도 1개의 공이 들어가야 합니다. (공 4개를 $k$개의 자연수로 분할하는 방법)
이것은 칸막이 모델을 생각하면 쉽습니다. 공 4개 사이의 공간 3개 중 $k-1$개의 칸막이를 설치하는 것과 같으므로 경우의 수는 다음과 같습니다.
$$\binom{4-1}{k-1} = \binom{3}{k-1}$$
- **보라색 공 4개를 $m$개의 영역에 나누어 담기**: 마찬가지로 계산합니다.
$$\binom{3}{m-1}$$
따라서, 특정한 $(k, m)$에 대한 경우의 수 $N(k, m)$은 다음과 같습니다.
$$N(k, m) = \binom{5}{k} \binom{5-k}{m} \binom{3}{k-1} \binom{3}{m-1}$$
5단계: 가능한 모든 $(k, m)$ 쌍에 대해 계산하기
$k \ge 1, m \ge 1, k+m \le 5$를 만족하는 자연수 쌍 $(k, m)$에 대해 계산해 봅시다. 대칭성에 의해 $N(k, m) = N(m, k)$가 성립합니다.
- **경우 1: $k+m = 2 \implies (1, 1)$**
$$N(1, 1) = \binom{5}{1} \binom{4}{1} \binom{3}{0} \binom{3}{0} = 5 \times 4 \times 1 \times 1 = 20$$
- **경우 2: $k+m = 3 \implies (1, 2), (2, 1)$**
$$N(1, 2) = \binom{5}{1} \binom{4}{2} \binom{3}{0} \binom{3}{1} = 5 \times 6 \times 1 \times 3 = 90$$
대칭성에 의해 $N(2, 1) = 90$이므로, 이 경우의 합은 $90 + 90 = 180$입니다.
- **경우 3: $k+m = 4 \implies (1, 3), (3, 1), (2, 2)$**
$$N(1, 3) = \binom{5}{1} \binom{4}{3} \binom{3}{0} \binom{3}{2} = 5 \times 4 \times 1 \times 3 = 60$$
$$N(2, 2) = \binom{5}{2} \binom{3}{2} \binom{3}{1} \binom{3}{1} = 10 \times 3 \times 3 \times 3 = 270$$
이 경우의 합은 $60 (N(1,3)) + 60 (N(3,1)) + 270 = 390$입니다.
- **경우 4: $k+m = 5 \implies (1, 4), (4, 1), (2, 3), (3, 2)$**
$$N(1, 4) = \binom{5}{1} \binom{4}{4} \binom{3}{0} \binom{3}{3} = 5 \times 1 \times 1 \times 1 = 5$$
$$N(2, 3) = \binom{5}{2} \binom{3}{3} \binom{3}{1} \binom{3}{2} = 10 \times 1 \times 3 \times 3 = 90$$
이 경우의 합은 $5 (N(1,4)) + 5 (N(4,1)) + 90 (N(2,3)) + 90 (N(3,2)) = 190$입니다.
6단계: 모든 경우의 수 더하기
이제 구한 모든 경우의 수를 더해줍니다.
$$\text{전체 경우의 수} = 20 + 180 + 390 + 190 = 780$$
답
$$780$$
확인해보기
이 문제에서 "노란색 공과 보라색 공이 이웃하지 않는다"는 조건 때문에, 검은색 공으로 나누어진 5개의 영역 중 하나의 영역에 노란색 공과 보라색 공이 동시에 들어갈 수 없는 이유를 스스로의 언어로 설명해 보세요.