합과 곱의 법칙, 중복 세기

메뉴 세 가지 가운데 하나를 고르는 것과, 메뉴, 크기, 추가 옵션을 차례로 하나씩 고르는 것은 다른 계산입니다. 앞의 것은 더하고 뒤의 것은 곱합니다. 경우의 수를 세는 문제는 대부분 이 두 법칙과, 두 번 센 것을 바로잡는 몇 가지 방법으로 풀립니다. 이 글에서는 집합의 표현과 연산의 합집합과 곱집합으로 두 법칙을 설명하고, 세는 도중에 흔히 생기는 중복을 다루는 방법을 익힙니다.

합의 법칙과 곱의 법칙

한 가지를 고를 때 그 방법이 겹치지 않는 두 무리로 나뉘고, 각 무리에 m가지와 n가지가 있으면 고르는 방법은 m + n가지입니다. 이것을 합의 법칙(sum rule)이라고 합니다. 집합으로 말하면 서로소인 두 유한집합에 대해 $|A\cup B|=|A|+|B|$입니다. 오전 강좌 3개와 오후 강좌 2개 가운데 정확히 하나를 고르면 5가지이지만, 같은 강좌가 두 목록에 모두 있다면 그 강좌를 두 번 세게 되므로 그냥 더할 수 없습니다.

첫 번째 선택에 m가지가 있고, 그 각각에 대해 두 번째 선택에 n가지가 있으면 둘을 차례로 고르는 방법은 mn가지입니다. 이것을 곱의 법칙(product rule)이라 하고, 집합으로는 곱집합의 크기 $|A\times B|=|A||B|$입니다. 상의 3종류와 하의 2종류를 하나씩 고르면 6가지입니다. 같은 이유로 길이 n인 비트열은 $2^n$개이고, 원소 n개인 집합의 부분집합도 원소마다 넣을지 뺄지를 고르므로 $2^n$개입니다.

곱의 법칙은 두 번째 선택의 가짓수가 첫 번째 선택과 상관없이 같을 때만 쓸 수 있습니다. 첫 강좌로 무엇을 고르느냐에 따라 이어 들을 수 있는 강좌가 각각 2개, 3개, 1개라면 전체는 3 × 3이 아니라 2 + 3 + 1 = 6가지입니다. 가짓수가 가지마다 다르면 가지별로 센 뒤 합의 법칙으로 더해야 합니다.

포함·배제로 겹친 부분을 바로잡는다

1부터 12까지의 정수 가운데 2의 배수이거나 3의 배수인 수는 2의 배수 6개와 3의 배수 4개를 더한 10개가 아니라 8개입니다. 6과 12는 두 무리에 모두 들어 있어 두 번 세었으므로 한 번 빼야 합니다. 집합의 대수와 분할의 포함·배제의 원리가 바로 이 계산이며, 세 집합에서는 다음과 같습니다.

부호를 외우는 대신 원소 하나가 몇 번 세어지는지 따지면 식을 검산할 수 있습니다. 세 집합 모두에 속한 원소는 처음 세 항에서 3번 더해지고, 두 집합씩의 교집합 세 항에서 3번 빠져 0번이 되므로, 마지막 항에서 다시 1번 더해야 합니다. 두 집합에만 속한 원소는 2번 더해지고 1번 빠져 1번 세어집니다. 1부터 30까지의 정수 가운데 2, 3, 5 가운데 하나 이상의 배수인 수를 이 식으로 세고, 목록을 만들어 직접 센 값과 비교해 보겠습니다.

from itertools import product

by_formula = 15 + 10 + 6 - 5 - 3 - 2 + 1
by_listing = sum(1 for n in range(1, 31) if n % 2 == 0 or n % 3 == 0 or n % 5 == 0)
print(by_formula, by_listing)

words = ["".join(w) for w in product("ABC", repeat=3)]
with_a = [w for w in words if "A" in w]
print(len(words), len(with_a), len(words) - 2 ** 3, sum(w.count("A") for w in words))

22 22
27 19 19 27

1부터 30까지 2의 배수는 15개, 3의 배수는 10개, 5의 배수는 6개이고, 6의 배수는 5개, 10의 배수는 3개, 15의 배수는 2개, 30의 배수는 1개입니다. 두 수의 공배수는 최소공배수의 배수이므로 교집합의 크기도 이렇게 셀 수 있습니다. 식으로 센 22와 직접 센 22가 같습니다. 코드의 둘째 부분은 다음 절에서 설명합니다.

더 깊이: 아무도 자기 자리에 앉지 않는 배치

n명이 자기 이름표가 붙은 n개의 자리에 앉을 때 아무도 자기 자리에 앉지 않는 배치, 곧 고정점이 없는 순열을 교란순열(derangement)이라 하고 그 수를 $D_n$으로 씁니다. 포함·배제로 세면, 정해 둔 k명이 모두 자기 자리에 앉는 배치는 나머지 $n-k$명만 줄 세우면 되므로 $(n-k)!$개이고, k명을 고르는 방법은 $\binom nk$가지입니다. 그래서 $D_n=\sum_{k=0}^{n}(-1)^k\binom nk(n-k)!=n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}$이고, $n=4$이면 $24-24+12-4+1=9$입니다.

OEIS의 A000166에 따르면 $D_0$부터 차례로 1, 0, 1, 2, 9, 44, 265입니다. 식의 합 $\sum_{k=0}^{n}(-1)^k/k!$은 $e^{-1}$을 나타내는 급수의 앞부분이므로, n명이 무작위로 앉았을 때 아무도 자기 자리에 앉지 않을 확률 $D_n/n!$은 n이 커질수록 $1/e\approx0.3679$에 다가갑니다. 더하는 항 $1/k!$이 빠르게 작아지므로 다가가는 속도도 빨라서, $n=4$에서 이미 $9/24=0.375$이고 $n=6$에서는 $265/720\approx0.3681$입니다.

그래서 이 확률은 사람이 넷이든 백 명이든 거의 같습니다. 실제로 $n\ge1$이면 $D_n$은 $n!/e$를 반올림한 정수와 같아서, $5!/e\approx44.1$을 반올림한 44가 $D_5$입니다.

반대 경우를 빼서 센다

문자 A, B, C로 만든 길이 3인 문자열은 곱의 법칙으로 $3^3=27$개입니다. 이 가운데 A가 적어도 하나 들어간 문자열을 세려면, A가 하나도 없는 문자열을 전체에서 빼는 것이 쉽습니다. A가 없으면 각 자리에 B나 C만 오므로 $2^3=8$개이고, 답은 27 − 8 = 19개입니다. 이처럼 반대 경우, 곧 여사건을 세어 전체에서 빼는 방법은 "적어도 하나"를 묻는 문제에 특히 잘 맞습니다.

같은 문제를 "A가 올 자리를 하나 고르고(3가지), 나머지 두 자리는 아무렇게나 채운다($3^2=9$가지)"로 계산하면 3 × 9 = 27이 나와 틀립니다. 코드의 마지막 값이 그 이유를 보여 줍니다. sum(w.count("A") for w in words)는 문자열마다 A의 개수를 더한 값인데, 이것이 27입니다. 자리를 먼저 고르는 방법은 A가 두 개인 문자열을 두 번, 세 개인 문자열을 세 번 세므로, 실제로는 A의 개수를 센 것이 됩니다. 같은 결과가 몇 가지 다른 과정으로 만들어지는지 확인하는 습관이 중복을 막아 줍니다.

비둘기집 원리의 일반형

함수와 일대일·전사에서 물건 n + 1개를 상자 n개에 넣으면 어떤 상자에는 두 개 이상 들어간다는 비둘기집 원리를 보았습니다. 이 원리는 더 일반적으로 쓸 수 있습니다. 물건 N개를 상자 k개에 넣으면 어떤 상자에는 적어도 $\lceil N/k\rceil$개가 들어갑니다. 모든 상자에 $\lceil N/k\rceil$개보다 적게, 곧 많아야 $\lceil N/k\rceil-1$개씩 들어 있다면 전체는 많아야 $k(\lceil N/k\rceil-1)$개인데, 이 값은 N보다 작기 때문입니다.

13명을 태어난 달로 나누면 같은 달에 태어난 두 사람이 반드시 있습니다. 정수 11개를 고르면 일의 자리가 같은 두 수가 있고, 그 두 수의 차는 10의 배수입니다. 일의 자리, 곧 10으로 나눈 나머지는 10가지뿐이기 때문입니다. 비둘기집 원리는 그런 것이 반드시 있다는 것만 알려 줄 뿐, 어느 상자인지는 알려 주지 않습니다.

정리

• 겹치지 않는 경우로 나뉘면 더하고(합의 법칙), 차례로 고르는 단계의 가짓수가 일정하면 곱합니다(곱의 법칙). 가짓수가 가지마다 다르면 가지별로 세어 더합니다.
• 겹치는 무리를 합칠 때는 포함·배제로 두 번 센 부분을 빼고, 세 무리가 모두 겹치는 부분을 다시 더합니다. 원소 하나가 정확히 한 번 세어지는지로 부호를 검산할 수 있습니다.
• "적어도 하나"는 전체에서 "하나도 없는" 경우를 빼서 세는 것이 편하고, 자리를 먼저 고르는 방법은 중복을 만듭니다.
• 물건 N개를 상자 k개에 넣으면 어떤 상자에는 적어도 $\lceil N/k\rceil$개가 들어가며, 이 원리는 어느 상자인지는 알려 주지 않습니다.

연습 문제

1. 1이 있는 비트열

길이 4인 비트열 가운데 1이 적어도 한 번 나오는 것은 몇 개인가요?

2. 폴더에 파일 나누기

파일 20개를 폴더 6개에 나누어 넣으면, 어떤 폴더에는 적어도 몇 개의 파일이 들어가나요?

3. 어느 것의 배수도 아닌 수

1부터 100까지의 정수 가운데 2, 3, 5 어느 것의 배수도 아닌 수는 몇 개인가요?

세기 전에 세는 대상이 순서가 있는 결과인지, 같은 결과가 여러 과정으로 만들어지지 않는지부터 적어 보세요. 다음 글 순열과 조합에서는 곱의 법칙과 중복 제거로 순열, 조합, 중복조합의 공식을 이끌어 냅니다.