더블 카운팅
덤프버전 :
분류
1. 개요[편집]
더블카운팅(Double Counting)은 조합론에서 어떠한 등식을 증명할 때 양 변의 의미가 같음을 밝힘으로써 식의 값도 같다고 증명하는 것이다. 즉, 하나의 집합을 두 가지의 방법으로 셀 수 있다는 것을 통해 두 식이 같음을 증명하는 방법이다.
예를 들면 다음 등식은 더블카운팅을 이용해 증명할 수 있다.
위 문제의 증명과정은 다음과 같다.[math(2+4+6+···+2(n-1)=n(n-1))] [출처]
이렇게 증명하기 어려워 보이는 문제도 더블카운팅을 이용해 쉽게 증명할 수 있다. 그렇기 때문에 더블카운팅의 포인트는 주어진 식을 다른 각도에서 다른 문제로 생각해보는 창의력이 중요하다고 할 수 있다.1부터 [math(n)]까지의 자연수중 서로 다른 두 수를 뽑아 만든 순서쌍의 집합을 [math(S_{n})]이라고 하자.
곱의 법칙에 따라 [math(S_{n})]의 원소의 개수는 [math(n(n-1))]이다.[이유]
또한 집합 [math(S)]의 순서쌍중 큰 수가 [math(i)]인 순서쌍의 개수는 [math(2(i-1))]개이다. 왜냐하면 순서쌍 [math((x,y)~~({\sf where}~x>y))]에서 [math(x=i)]며 [math(x>y)]이므로 가능한 자연수 [math(y)]는 [math(i-1)]개이다. 한편 [math((x,y))]와 [math((y,x))]의 개수는 같으니 [math(S_{x})]의 원소의 개수를 [math(2+4+6+···+2(n-1))]로도 쓸 수 있다.
결국 좌변과 우변 모두 집합 [math(S_{n})]의 원소의 개수를 구하는 방법이라고 할 수 있다. 즉 두 식의 의미가 같으니 두 식의 값도 서로 같을 수밖에 없다. 따라서 등식이 증명된다.
가령 위의 예시 문제에서 등식에서부터 자연수의 집합과 이를 2개씩 뽑아 만든 집합의 개수를 구하는 문제를 생각해내지 못하면 더블카운팅을 쓸 수 없다.
참고로 위의 예제는 이항정리의 특수한 케이스로, 아래의 식으로 정의된다:
분류
[math(\displaystyle \sum_{p=q}^{n} \binom{n}{p} \binom{p}{q} = 2^{n-q} \binom{n}{q} )]
[math(\binom{p}{q})]는 조합이다.
2. 유용성[편집]
개요에서 보았듯이 도대체 양변이 어떤 관련이 있는 등식이지? 란 생각이 들때 돌파구가 되어줄 수 있다. 또한 문제 자체를 다르게 보는 창의력이 상당히 요구되기 때문에 KMO 등 외부 수학 경시대회에서도 종종 출제된다.
이 문서의 내용 중 전체 또는 일부는 2023-11-22 18:21:15에 나무위키 더블 카운팅 문서에서 가져왔습니다.