Binomial Coefficient는 단순한 공식이 아니라 부분집합을 세는 수이다. 이 관점을 사용하면 이항정리와 Pascal 항등식을 자연스럽게 설명할 수 있고, 겹치는 경우를 보정하는 Inclusion–Exclusion Principle로 확장할 수 있다.
Binomial Theorem
전개식에서 를 만들려면 개의 괄호 중 개에서 를 선택하고 나머지에서 를 선택해야 한다. 그 방법 수가 이므로 이항계수가 계수로 나타난다.
특히 , 를 대입하면
이고 을 다시 대입하면
을 얻는다. 오른쪽은 원소 집합의 부분집합을 크기별로 나누어 센 결과이다.
Pascal’s Triangle과 Identity
Pascal’s Identity는
이다. 대수적으로 factorial 식을 통분해 증명할 수 있지만, 조합론적 증명이 의미를 더 잘 보여준다.
개 원소 중 개를 고를 때 특정 원소 를 고르는지에 따라 두 경우로 나눈다.
- 를 포함하면 나머지 개 중 개를 선택한다.
- 를 포함하지 않으면 나머지 개 중 개를 선택한다.
두 경우는 서로 겹치지 않고 전체를 덮으므로 Pascal’s Identity가 성립한다.
Inclusion–Exclusion Principle
두 집합에서는
이다. 세 집합에서는 한 원소가 세 번 더해지고 pairwise intersection에서 세 번 빠지므로 triple intersection을 다시 한 번 더한다.
일반적으로
이다. 교집합에 포함되는 집합 수가 홀수이면 더하고 짝수이면 뺀다.
Derangement
명이 자신의 선물을 하나씩 가져와 무작위로 다시 나눠 갖는다고 하자. 아무도 자기 선물을 받지 않는 순열을 Derangement라고 한다.
전체 순열 집합에서 를 번째 사람이 자기 선물을 받는 사건으로 두면, 적어도 한 명이 자기 선물을 받는 순열은 이다.
특정 명의 위치를 고정한 순열 수는 이고, 고정할 사람을 고르는 방법은 이다. 따라서 Derangement의 수 은
이다. 정리하면
이고
이다. 즉 사람이 많아질수록 아무도 자기 선물을 받지 않을 확률은 약 에 가까워진다.
Bijection Rule
두 집합 사이의 Bijection을 만들면 한쪽의 경우의 수를 다른 문제로 옮길 수 있다. 원소 집합의 부분집합은 길이 의 Binary String과 Bijection을 이룬다. 각 자리에서 원소를 포함하면 1, 포함하지 않으면 0으로 표시한다.
따라서 Power Set의 원소 수가 임을 다시 얻는다. 이항계수 는 정확히 1이 개인 Binary String의 수이기도 하다.
중복 제거의 기준
Counting 문제에서 다음 질문을 반복하면 Inclusion–Exclusion가 필요한지 판단하기 쉽다.
- 내가 나눈 경우들이 서로 겹치는가?
- 한 결과가 몇 번 세어졌는가?
- 교집합을 빼면 더 높은 차수의 교집합을 지나치게 뺀 것은 아닌가?
단순히 “또는”이 보인다고 항상 더할 수 있는 것은 아니다. 사건들이 disjoint일 때만 바로 Sum Rule을 적용한다.
정리
이항정리는 각 항을 만드는 선택을 Binomial Coefficient로 센 결과이다. Pascal’s Identity는 특정 원소의 포함 여부로 경우를 분할하면 증명된다. Inclusion–Exclusion는 여러 조건이 겹칠 때 중복 계수를 교대로 보정하며, Derangement는 그 대표적인 응용이다.
연습 문제
- 을 조합론적으로 설명한다.
- 1부터 100까지의 정수 중 2 또는 3의 배수의 개수를 구한다.
- 를 Inclusion–Exclusion로 계산한다.
풀이
1번
명 중 위원회를 만들고 그중 한 명을 대표로 지정한다고 하자. 위원회 크기가 일 때 왼쪽은 위원회 가지와 대표 가지를 곱해 센다.
다른 방법으로 먼저 대표를 가지로 고른 뒤, 나머지 명은 위원회에 들어오거나 들어오지 않는 두 선택이 있으므로 가지이다. 두 방식이 같은 대상을 세므로 등식이 성립한다.
2번
2의 배수는 50개, 3의 배수는 33개, 둘 다인 6의 배수는 16개이다. 따라서
개이다.