합과 곱의 법칙, 중복 세기

세 가지 메뉴 중 하나를 고르는 것과, 메뉴·크기·추가옵션을 차례로 고르는 것은 다른 계산입니다. 집합 연산을 바탕으로 더할 때와 곱할 때의 조건을 구분합니다.

합의 법칙은 겹치지 않는 선택

서로소인 선택 A와 B의 경우의 수가 m,n이면 A 또는 B를 고르는 경우는 m+n입니다. 오전 강좌 3개와 오후 강좌 2개 중 정확히 하나만 고르면 5가지입니다. 같은 강좌가 두 목록에 중복 등록되어 있으면 단순히 더할 수 없습니다.

곱의 법칙은 첫 단계 선택 m개 각각에서 다음 단계 선택 n개가 있을 때 mn개입니다. 상의 3종류와 하의 2종류를 하나씩 고르면 조합은 6개입니다. 선택에 따라 다음 경우 수가 다르면 각 가지의 수를 더합니다. 첫 강좌에 따라 가능한 후속 강좌가 각각 2,3,1개이면 전체는 2+3+1=6이지 무조건 3×3은 아닙니다.

중복한 원소를 다시 빼기

1~12 정수 중 2의 배수 또는 3의 배수는 6+4−2=8개입니다. 교집합인 6,12를 두 번 더했으므로 한 번 뺐습니다. 집합의 포함배제와 같은 계산입니다.

세 집합에서는

$$|A\cup B\cup C|=|A|+|B|+|C| -|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|.$$

세 곳 모두에 속한 원소는 처음 3번 더하고 교집합에서 3번 빼 0번 남았으므로 마지막에 다시 1번 더합니다. 마지막 항은 삼중 교집합이고 합집합이 아닙니다. 각 원소가 최종 한 번씩 세어지는지 확인하면 외운 부호를 검산할 수 있습니다.

적어도 하나는 전체에서 0개인 경우 빼기

알파벳 {A,B,C}로 만든 길이가 3인 문자열은 3³=27개입니다. A가 적어도 하나 있는 문자열은 27−2³=19개입니다. A가 없는 문자열에서 각 자리는 B,C 두 선택이기 때문입니다. '적어도 하나'를 A 위치를 하나 골라 3×3²로 계산하면 A가 여러 개인 문자열을 중복 셉니다.

비둘기집 원리

n개 상자에 n+1개 물건을 넣으면 어떤 상자에는 적어도 2개가 들어갑니다. 13명을 태어난 달 12개로 나누면 같은 달에 태어난 두 사람이 있습니다. 더 일반적으로 N개 물건을 k개 상자에 넣으면 어떤 상자에는 적어도 $\lceil N/k\rceil$개가 있습니다. 모든 상자에 그만큼 있다는 뜻은 아닙니다.

스스로 풀어보기

문제 1. 숫자 0,1로 만든 길이 4비트열 중 1이 적어도 한 번 있는 것은 몇 개인가요?

풀이: 전체 2⁴=16개에서 0000 하나를 빼 15개입니다. 1의 위치를 하나 지정하면 1100처럼 두 1이 있는 비트열을 중복 셀 수 있습니다.

문제 2. 20개 파일을 6개 폴더에 나누면 어떤 폴더에 적어도 몇 개 파일이 있나요?

풀이: $\lceil20/6\rceil=4$개입니다. 모두 3개 이하라면 전체가 최대 18개라 20개를 담을 수 없습니다. 4개 이상인 폴더가 존재하지만 어느 폴더인지는 개수 조건만으로 특정할 수 없습니다.

세는 대상이 순서 있는 결과인지부터 확인하세요. 선택·배열의 구체 공식은 순열과 조합에서 유도합니다.