AB와 BC가 모두 이웃이면 두 묶음을 따로 만들 수 있을까

A,B,C,D,E,F\text{ 여섯 사람이 일렬로 선다.}

A와B가 이웃하고 B와C도 이웃하는 줄의 수를 구하라. AB와BC를 별개의 두 묶음으로 세려 한 풀이를 검토한다.

B가 줄의 양쪽 이웃에 A와C를 두어야 한다. 세 사람의 허용된 연속 순서는 ABC와 CBA 두 가지다. ACB나 BAC에서는 B가 두 사람 모두와 이웃하지 않는다.

\text{줄의 수}=2\times4!=48.

ABC 또는 CBA를 한 묶음으로 두면 D,E,F와 함께 네 대상을 배치한다. 두 묶음에 B를 각각 넣으면 같은 사람을 두 번 사용하게 된다.

AB를 AB·BA 두 방향, BC를 BC·CB 두 방향으로 각각 바꾸어2×2를 곱하는 것은 맞지 않다. 두 조건은 B 한 명을 공유하므로 독립적인 내부 선택이 아니다. 연결 가능한 세 사람 순서를 직접 확인하면 둘뿐이다.

6!가지 줄을 같은 확률로 선택한다면 두 이웃 조건을 동시에 만족할 확률은48/720=1/15다. 각각의 이웃 확률1/3을 곱한1/9과 다르다. 여기서도 이웃 사건은 독립이 아니다.

세 사람이 모두 붙어 있다는 조건만 주면 내부 순서는3!=6가지라144개다. 그 조건은 이 문항보다 약하다. 세 사람이 붙은 여섯 경우에서 B가 가운데인 두 경우만 남겨야 한다.

해설에서는 묶음에 포함된 사람의 이름을 표시한다. 같은 이름이 두 묶음에 등장했으면 두 묶음이 별개 대상인지 확인해야 한다. 허용된 내부 순서 목록을 먼저 적으면 같은 사람을 중복 세거나 불가능한 방향을 곱한 줄을 찾을 수 있다.

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