[[분류:증명]]
[include(틀:수학기초론)]
[include(틀:이산수학)]
[목차]

== 개요 ==
더블카운팅(Double Counting)은 [[조합론]]에서 어떠한 등식을 증명할 때 '''양 변의 의미가 같음'''을 밝힘으로써 식의 값도 같다고 증명하는 것이다. 즉, 하나의 집합을 두 가지의 방법으로 셀 수 있다는 것을 통해 두 식이 같음을 증명하는 방법이다.

예를 들면 다음 등식은 더블카운팅을 이용해 증명할 수 있다.
> [math(2+4+6+···+2(n-1)=n(n-1))] [*출처 문제 출처: 올림피아드 프라임 조합I]
위 문제의 증명과정은 다음과 같다.
> 1부터 [math(n)]까지의 자연수중 서로 다른 두 수를 뽑아 만든 순서쌍의 집합을 [math(S_{n})]이라고 하자.
> 곱의 법칙에 따라 [math(S_{n})]의 원소의 개수는 [math(n(n-1))]이다.[*이유 집합 [math(S)]의 순서쌍은 자연수 n개중 1개를 뽑고 이어 n-1(이미 뽑힌 한개 제외)개중 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개씩 뽑아 만든 집합의 개수를 구하는 문제를 생각해내지 못하면 더블카운팅을 쓸 수 없다.

참고로 위의 예제는 [[이항정리]]의 특수한 케이스로, 아래의 식으로 정의된다:
{{{#!wiki style="text-align: center"
[br][math(\displaystyle \sum_{p=q}^{n} \binom{n}{p} \binom{p}{q} = 2^{n-q} \binom{n}{q} )]}}}
[math(\binom{p}{q})]는 [[조합]]이다.
== 유용성 ==
개요에서 보았듯이 도대체 양변이 어떤 관련이 있는 등식이지? 란 생각이 들때 돌파구가 되어줄 수 있다. 또한 문제 자체를 다르게 보는 창의력이 상당히 요구되기 때문에 [[KMO]] 등 외부 수학 경시대회에서도 종종 출제된다.