가상 작업 A, B, C, D를 기계 1, 2, 3, 4에 하나씩 배정해요. 한 작업에는 한 기계만, 한 기계에는 한 작업만 넣어요. 모든 배정을 구별하며 처리 시간과 다른 제약은 없어요. 금지된 작업·기계 조합이 두 개이면 가능한 배정 수도 항상 같을까요?
제약이 없으면 네 작업의 기계 선택 수는 입니다. 첫 계획에서는 A를 1에 넣는 것과 B를 1에 넣는 것을 금지해요. A가 1인 배정은 나머지 세 작업을 세 기계에 넣어 개이고, B가 1인 배정도 6개예요. 한 기계를 둘이 쓸 수 없으므로 두 금지가 동시에 발생하는 배정은 없어요. 허용 배정은 개예요.
둘째 계획에서는 A를 1에 넣는 것과 B를 2에 넣는 것을 금지해요. 각 금지 사건은 여전히 6개씩이지만, 둘이 동시에 발생하는 경우가 있어요. A가 1, B가 2에 고정되면 C와 D를 남은 두 기계에 넣는 방법은 두 개예요.
두 사건을 빼면서 동시에 해당하는 두 배정을 두 번 뺐으므로 한 번 돌려 넣는 포함배제 계산이에요. 두 계획 모두 금지 조합 두 개지만 허용 배정은 12개와 14개로 달라요.
배정표의 금지 칸을 단순히 세기만 해서는 전체 선택 수를 알 수 없어요. 그 칸들이 같은 행이나 열을 공유하는지, 즉 한 배정에서 함께 발생할 수 있는지를 확인해야 해요. 금지 조건의 개수와 조건 사이의 겹침은 다른 정보예요.
참고한 수학 개념: AMS · Rook Polynomials: A Straight-Forward Problem.
이 글의 생활 상황과 계산 예시는 수학 이야기에서 새로 구성했습니다.