노란색 공 4개, 보라색 공 4개, 검은색 공 4개를 모두 일렬로 나열한다 노란색 공은 보라색 공과 이웃하지 않아야 한다 같은 색 공끼리는 서로 구별하지 않는다 검은색 공 4개를 먼저 놓으면 양끝을 포함해 5개의 칸이 생긴다 한 칸에 노란색과 보라색이 함께 들어가면 반드시 이웃이 생긴다

2027학년도 6월 모의고사 확률과 통계 30번 풀이 | 이웃 금지 배열과 칸 분배 [270630p]

들어가기 앞서…

노란색 공과 보라색 공을 먼저 배열하려고 하면 이웃하는 순간을 계속 확인해야 한다.
이 문제에서는 두 색 사이를 끊어 줄 수 있는 검은색 공을 먼저 놓는 것이 핵심이다.

검은색 공 4개를 놓으면 양끝까지 포함해 5개의 칸이 생긴다.
이 칸 안에 노란색과 보라색이 함께 들어가면 반드시 두 색이 이웃하므로, 원래 조건은 “각 칸은 비어 있거나 한 가지 색만 가진다”는 조건으로 바뀐다.

문제

문제 텍스트 주관식

노란색 공 $4$ $4$개, 보라색 공 $4$ $4$개, 검은색 공 $4$ $4$개가 있다.

이 $12$ $12$개의 공을 모두 일렬로 나열할 때, 노란색 공이 보라색 공과 이웃하지 않게 나열하는 경우의 수를 구하시오.

단, 같은 색 공끼리는 서로 구별하지 않는다.

정답

$780$ $780$

풀이

검은색 공 4개가 만드는 5개의 칸을 본다

검은색 공 4개를 먼저 놓으면 노란색 공과 보라색 공이 들어갈 수 있는 칸이 다음처럼 5개 생긴다.

\_ \ B \ \_ \ B \ \_ \ B \ \_ \ B \ \_

양끝 칸까지 포함해야 하므로 칸은 4개가 아니라 5개이다.
검은색 공끼리는 구별되지 않지만, 이렇게 생긴 5개의 칸은 왼쪽부터 위치가 다르므로 서로 다른 칸으로 본다.

한 칸 안에는 검은색 공이 없다.
따라서 그 칸에 노란색 공과 보라색 공이 함께 들어가면 색이 바뀌는 지점에서 반드시 $YP$ $YP$ 또는 $PY$ $PY$가 생긴다.
즉 두 색이 이웃한다.

반대로 각 칸이 비어 있거나 한 가지 색만 가지고 있으면, 서로 다른 칸 사이에는 검은색 공이 끼어 있다.
그러므로 노란색 공과 보라색 공이 이웃할 수 없다.

검은색 공 4개를 먼저 놓으면 양끝을 포함해 5개의 칸이 생기고, 한 칸에 노란색과 보라색이 섞이면 YP 또는 PY가 생겨 금지된다는 구조. — 검은색 공은 노란색과 보라색 사이를 끊는 분리자 역할을 한다.

따라서 원래 조건은 다음 조건으로 바뀐다.

5개의 칸 각각은 비어 있거나, 노란색 공만 들어 있거나, 보라색 공만 들어 있어야 한다.

이제 칸 선택과 같은 색 공 4개의 분배를 분리해서 세면 된다.

같은 색 공 4개를 선택된 칸에 나누는 방법을 준비한다

한 색 공 4개를 선택된 칸에 나누어 넣는 방법부터 정리한다.
선택된 칸이 $r$ $r$개일 때 각 칸에는 적어도 1개가 들어가야 하므로, $4$ $4$를 $r$ $r$개의 양의 정수의 합으로 나타내는 수를 세면 된다.

선택된 칸의 수 $r$ $r$	$1$ $1$	$2$ $2$	$3$ $3$	$4$ $4$
나누어 넣는 방법	$1$ $1$	$3$ $3$	$3$ $3$	$1$ $1$

같은 색 공 4개를 선택된 r개의 칸에 1개 이상씩 나누어 넣을 때 r=1,2,3,4에 대한 분배 수가 1,3,3,1로 정리되는 표. — 선택된 칸에는 그 색 공이 적어도 1개 들어가야 하므로 양의 분할을 쓴다.

두 색이 모두 있어야 하므로 노란색 또는 보라색 공이 들어간 칸의 총개수는 최소 2개이다.
전체 칸은 5개이므로 최대 5개이다.
이제 총 사용 칸 수가 $2,3,4,5$ $2,3,4,5$인 경우를 나눈다.

총 2칸 또는 3칸을 쓰는 경우를 센다

총 2칸을 쓰는 경우는 노란색 칸 1개, 보라색 칸 1개뿐이다.
노란색 칸을 고르고 남은 칸에서 보라색 칸을 고르면 된다.
각 색은 한 칸에 4개가 모두 들어가므로 분배 방법은 각각 1가지이다.

\binom{5}{1}\binom{4}{1}=20

총 3칸을 쓰는 경우는 노란색 칸 1개와 보라색 칸 2개이거나, 그 반대이다.
두 경우는 색 이름만 바뀐 대칭이다.

노란색 칸이 1개, 보라색 칸이 2개라고 하면 노란색 칸은 $\binom{5}{1}$ $\binom{5}{1}$가지, 보라색 칸은 남은 4개 중 $\binom{4}{2}$ $\binom{4}{2}$가지로 고른다.
보라색 공 4개를 2개 칸에 적어도 1개씩 넣는 방법은 3가지이다.

2\times\binom{5}{1}\binom{4}{2}\times3=180

총 2칸을 쓰는 경우 20가지와 총 3칸을 쓰는 경우를 색 대칭으로 묶어 180가지로 계산하는 그림. — 총 2칸과 3칸을 쓰는 경우는 색 대칭을 이용해 짧게 센다.

총 4칸을 쓰는 경우를 센다

총 4칸을 쓰는 경우의 가능한 분배는 $(1,3)$ $(1,3)$, $(3,1)$ $(3,1)$, $(2,2)$ $(2,2)$이다.
순서쌍은 노란색 칸의 수와 보라색 칸의 수를 뜻한다.

$(1,3)$ $(1,3)$과 $(3,1)$ $(3,1)$은 대칭이다.
노란색 칸이 1개, 보라색 칸이 3개인 경우를 세면 $\binom{5}{1}\binom{4}{3}\times3$ $\binom{5}{1}\binom{4}{3}\times3$가지이고, 대칭인 경우까지 2배 한다.
여기서 $3$ $3$은 한 색 공 4개를 3개 칸에 양의 개수로 나누어 넣는 방법의 수이다.

$(2,2)$ $(2,2)$인 경우에는 노란색 칸 2개를 고르고, 남은 칸 중 보라색 칸 2개를 고른다.
두 색 모두 4개 공을 2개 칸에 나누어 넣어야 하므로 각각 3가지씩이다.

따라서 총 4칸을 쓰는 경우의 수는 다음과 같다.

2\times\binom{5}{1}\binom{4}{3}\times3 +\binom{5}{2}\binom{3}{2}\times3\times3 =390

총 5칸을 쓰는 경우를 센다

총 5칸을 쓰는 경우의 가능한 분배는 $(1,4)$ $(1,4)$, $(4,1)$ $(4,1)$, $(2,3)$ $(2,3)$, $(3,2)$ $(3,2)$이다.
한 색 공은 4개뿐이므로 한 색이 5칸을 쓰는 경우는 없다.

$(1,4)$ $(1,4)$과 $(4,1)$ $(4,1)$은 대칭이다.
한 색이 1개 칸, 다른 색이 4개 칸을 쓰는 경우는 다음과 같다.
4개 칸에 공 4개를 적어도 1개씩 넣는 방법은 모두 1개씩 넣는 1가지뿐이다.

2\times\binom{5}{1}\binom{4}{4}

$(2,3)$ $(2,3)$과 $(3,2)$ $(3,2)$도 대칭이다.
노란색 칸이 2개, 보라색 칸이 3개인 경우를 세면 $\binom{5}{2}\binom{3}{3}$ $\binom{5}{2}\binom{3}{3}$가지로 칸을 고르고, 공을 나누어 넣는 방법은 각각 3가지와 3가지이다.