세 색을 두 개씩 놓을 때, 같은 색이 붙은 줄을 어떻게 빼야 할까요?

A·A·B·B·C·C를 일렬로 놓고 같은 글자가 이웃하지 않게 해요. 전체90줄에서 이웃 사건3×30−3×12+6=60줄을 빼면30줄이에요. 같은 AA 묶음 안에서2를 또 곱하지 않는지 확인해요.

여러 색의 연필 끝이 중심을 향해 모인 배열

사진: Chevre · CC BY-SA 3.0 · 원본 출처

A,A,B,B,C,C를 일렬로 놓는다.A,A,B,B,C,C\text{를 일렬로 놓는다.}

같은 글자가 이웃하지 않는 서로 다른 줄의 수를 구해 볼까요? 같은 글자 둘은 구별하지 않아요.

전체는6!/(2!2!2!)=90줄이에요. 같은 색 두 개가 붙는 사건을 E_A,E_B,E_C로 둬요. AA를 한 묶음으로 세면 E_A는5!/(2!2!)=30줄이에요. 다른 두 사건도 같아요.

AA와BB가 함께 붙으면 두 묶음과C,C 네 대상이므로4!/2!=12줄이에요. 세 쌍이 모두 붙으면 세 묶음의 순서3!=6줄이에요. 따라서 적어도 한 같은 색 이웃이 있는 줄은

3(30)−3(12)+6=60.3(30)-3(12)+6=60.

답은90−60=30줄이에요.

같은 쌍 안에서 2를 곱하지 않는다

AA는 두 글자가 같으므로 내부를 바꾸어도 같은 배치예요. AA 묶음의 내부 순서가2가지라고 곱하면 잘못 중복 세어요. 반대로 E_A,E_B,E_C를 단순히 더하면 두 쌍 이상 붙은 줄을 여러 번 세어요.

ABCABC는 허용되고 AABBCC는 허용되지 않아요. AABBCC는 세 사건에 모두 들어가 처음 세 번 더해지고, 세 교집합에서 세 번 빠진 뒤 마지막에 한 번 돌아와요. 최종적으로 한 줄로 세어지는지 확인해요.

목록을 만들 때 첫 글자A를 고정한 경우부터 분류해 볼 수도 있어요. 다만 그 목록에서 같은 조건이 반복되는지 확인하는 기준이 필요해요. 해설의 세 사건 계산은 나열 목록을 검산할 다른 방법이 돼요.

문항에 색별 개수가 두 개라는 전제가 있어 같은 색 이웃 사건을 한 묶음으로 표현할 수 있어요. 개수가 더 많아지면 어느 이웃을 세었는지 다시 정해야 해요.90이라는 전체 수가 같더라도 정육면체 면 배치의 이웃 관계와 이 줄의 이웃 관계는 달라요.

출처·착안: Colleen Young, 「Systematic Listing Strategies」. 문항과 예시 답안은 새로 작성했다.

이 글 공유하기

개인정보 및 방문 통계 안내