a b b c c c d 일렬 배열, 같은 문자 이웃하지 않는 경우의 수 구하기

a, b, b, c, c, c, d 배열: 같은 문자끼리 이웃하지 않는 경우의 수

주어진 문자열 'a', 'b', 'b', 'c', 'c', 'c', 'd'를 일렬로 배열할 때, 같은 문자끼리 서로 이웃하지 않도록 배열하는 경우의 수를 구하는 문제는 조합론에서 자주 등장하는 유형입니다. 이 문제를 해결하기 위해서는 포함-배제의 원리나 분할 후 배열하는 방법을 사용할 수 있습니다. 여기서는 좀 더 직관적인 분할 후 배열하는 방법을 중심으로 설명하겠습니다.

1단계: 중복이 없는 문자 먼저 배열하기

먼저, 중복되지 않는 문자 'a'와 'd'를 배열합니다. 이 두 문자를 배열하는 경우의 수는 2! = 2가지입니다. (ad 또는 da)

2단계: 중복되는 문자 배열하기

이제 'a'와 'd'가 배열된 상태에서, 그 사이사이와 양 끝에 중복되는 문자들을 배치할 공간을 확보합니다. 예를 들어 'a'와 'd'가 'a _ d' 와 같이 배열되었다면, '_' 부분에 다른 문자들을 배치할 수 있습니다. 'a'와 'd'를 배열하면 총 3개의 공간이 생깁니다. (예: _ a _ d _ )

3단계: 같은 문자가 이웃하지 않도록 배치하기

가장 까다로운 부분은 'b' 두 개와 'c' 세 개를 이웃하지 않도록 배치하는 것입니다. 이 경우, 'b'와 'c'를 먼저 분리하여 배치한 후, 'a'와 'd' 사이에 끼워 넣는 방식을 고려할 수 있습니다.

또는, 포함-배제의 원리를 적용하는 것이 더 효율적일 수 있습니다. 전체 경우의 수에서 같은 문자가 이웃하는 경우를 빼는 방식입니다.

전체 경우의 수: 총 7개의 문자가 있으며, 'b'가 2개, 'c'가 3개 중복됩니다. 따라서 전체 경우의 수는 7! / (2! * 3!) = 5040 / (2 * 6) = 5040 / 12 = 420가지입니다.

포함-배제의 원리 적용:

'b' 두 개가 이웃하는 경우: 'bb'를 하나의 묶음으로 생각하면, (bb), a, c, c, c, d 총 6개의 문자를 배열하는 것과 같습니다. 경우의 수는 6! / 3! = 720 / 6 = 120가지입니다.
'c' 세 개가 이웃하는 경우: 'ccc'를 하나의 묶음으로 생각하면, (ccc), a, b, b, d 총 5개의 문자를 배열하는 것과 같습니다. 경우의 수는 5! / 2! = 120 / 2 = 60가지입니다.
'b' 두 개가 이웃하고 'c' 세 개가 이웃하는 경우: (bb), (ccc), a, d 총 4개의 문자를 배열하는 것과 같습니다. 경우의 수는 4! = 24가지입니다.

주의: 'c' 세 개가 이웃하는 경우 중에는 'cc' 두 개가 이웃하는 경우도 포함됩니다. 따라서 이 문제는 '적어도 하나'의 이웃하는 쌍을 제외하는 것이 아니라, '모든' 같은 문자가 이웃하지 않는 경우를 찾는 것이므로, 더 복잡한 계산이 필요합니다. 일반적으로 이러한 문제는 '생성 함수'나 '전순열(derangement)' 개념과 결합하여 해결하기도 합니다. 하지만 여기서는 더 쉬운 접근 방식을 사용해 보겠습니다.

4단계: 'c' 먼저 배치 후 'b' 배치하기

이러한 유형의 문제는 중복이 가장 많은 문자부터 배치하는 것이 유리할 때가 많습니다. 먼저 'c' 세 개를 서로 이웃하지 않도록 배치하는 경우의 수를 구합니다.

'c' 3개 먼저 배열: 'c' 3개를 서로 이웃하지 않게 배열하는 것은 불가능합니다. 왜냐하면 3개의 'c'를 배치하면 최소 2개의 'c'는 반드시 이웃하게 됩니다. 따라서, 이 문제는 '모든' 같은 문자가 이웃하지 않는 경우를 찾는 것이 아니라, '특정' 같은 문자끼리 이웃하지 않는 경우를 찾는 것으로 해석해야 합니다. 문제의 의도를 'b끼리 이웃하지 않고, c끼리 이웃하지 않는 경우'로 가정하고 풀이하겠습니다.

다시 접근: 'a', 'd'를 먼저 배치 후 'b', 'c' 배치

'a', 'd' 배치: 2! = 2가지 (ad, da)
'a', 'd' 사이 공간 확보: _ a _ d _ (3개의 공간)
'b' 2개 배치: 3개의 공간에 'b' 2개를 배치합니다. 'b'끼리 이웃하지 않아야 하므로, 서로 다른 공간에 배치해야 합니다. 3개의 공간 중 2개를 선택하여 배치합니다. 3P2 = 3 * 2 = 6가지. (예: b a b d _, b a _ d b, _ a b d b)
'c' 3개 배치: 이제 'a', 'd', 'b'가 배치된 상태에서 남은 공간과 기존 공간을 활용하여 'c' 3개를 배치합니다. 이 때 'c'끼리 이웃하지 않아야 합니다.

이 방식은 너무 복잡해지므로, 포함-배제의 원리를 다시 한번 적용하되, 좀 더 명확하게 정의하여 사용해 보겠습니다.

5단계: 포함-배제의 원리 재적용 (더 정확하게)

전체 경우의 수: 7! / (2! * 3!) = 420가지
A: 'b' 두 개가 이웃하는 경우의 수. 'bb'를 하나로 묶어 (bb), a, c, c, c, d 를 배열. 6! / 3! = 120가지.
B: 'c' 두 개가 이웃하는 경우의 수. 'cc'를 하나로 묶어 (cc), a, b, b, c, d 를 배열. 6! / 2! = 720 / 2 = 360가지.
A ∩ B: 'b' 두 개가 이웃하고, 'c' 두 개가 이웃하는 경우의 수. (bb), (cc), a, b, c, d 를 배열. 5! = 120가지.

우리가 원하는 것은 'b'끼리 이웃하지 않고, 'c'끼리 이웃하지 않는 경우입니다. 이를 구하기 위해 전체에서 'b'가 이웃하는 경우 또는 'c'가 이웃하는 경우를 제외합니다.

|A ∪ B| = |A| + |B| - |A ∩ B| = 120 + 360 - 120 = 360가지.

이것은 'b'가 이웃하거나 'c'가 이웃하는 경우의 수입니다. 따라서 'b'도 이웃하지 않고 'c'도 이웃하지 않는 경우의 수는:

전체 경우의 수 - |A ∪ B| = 420 - 360 = 60가지.

하지만 이 계산은 'c'가 3개이므로 'cc'가 이웃하는 경우를 세는 것으로는 부족합니다. 'ccc'가 되는 경우까지 고려해야 합니다.

정확한 풀이 (분할 후 배치 - 재시도)

'c' 3개 배치: 먼저 'c' 3개를 서로 이웃하지 않도록 배치하는 것은 불가능합니다. 따라서 'a', 'b', 'd'를 먼저 배치하고 그 사이사이에 'c'를 넣는 방식으로 가야 합니다.
'a', 'b', 'b', 'd' 배치: 'b' 두 개가 이웃하지 않도록 배열합니다. 총 4개의 문자를 배열하는데, 'b'가 이웃하지 않아야 합니다. 'a', 'd'를 먼저 배치 (2가지: ad, da). 그 사이와 양 끝 (3곳)에 'b' 2개를 배치. 3P2 = 6가지. 따라서 'a', 'b', 'b', 'd'를 'b'끼리 이웃하지 않게 배열하는 경우의 수는 2 * 6 = 12가지입니다. (예: babd, badb, dbab, dba...)
'c' 3개 배치: 이제 위에서 배열된 12가지 경우에 대해, 'c' 3개를 각 문자의 사이사이와 양 끝에 배치합니다. 예를 들어 'babd'가 있다면, _ b _ a _ b _ d _ 총 5개의 공간이 생깁니다. 이 5개의 공간에 'c' 3개를 배치하되, 'c'끼리 이웃하지 않아야 합니다. 즉, 5개의 공간 중 3개를 선택하여 배치하면 됩니다. 5C3 = 10가지.

따라서, 'a', 'b', 'b', 'c', 'c', 'c', 'd'를 일렬로 배열할 때, 같은 문자끼리 이웃하지 않도록 배열하는 경우의 수는 12가지 (a, b, b, d 배열) * 10가지 (c 배치) = 120가지입니다.

최종 검증: 이 문제는 특정 문자의 개수가 많을 때 포함-배제의 원리보다 분할 후 배치하는 것이 더 직관적이고 오류가 적을 수 있습니다. 'b'와 'c'처럼 중복되는 문자가 있을 때, 가장 많이 중복되는 문자부터 먼저 고려하거나, 또는 중복이 적은 문자부터 고려하여 공간을 확보한 뒤 나머지 문자를 배치하는 전략을 사용합니다. 위에서 제시된 'a', 'b', 'b', 'd'를 먼저 배열하고 'c'를 끼워 넣는 방식이 가장 합리적인 풀이로 보입니다.

따라서, 같은 문자끼리 이웃하지 않도록 배열하는 경우의 수는 120가지입니다.