중복 조합

$a_{1}+a_{2}+...+a_{k}=d$이고 $0 \le a_{i} \le m$인 $a$에 관한 순서쌍의 개수를 찾고싶다!

예를 들어서 다음 경우를 보자.

$a+b+c=15$이고 $m=9$

기본적으로 전체 경우에서 망한 경우를 뺀다고 생각해보면 전체 경우는 $_{3}H_{15}$이다.

망한 경우는 $a$또는 $b$또는 $c$가 10이상인 경우로 $a$가 10이상이라고 생각한다면 $a^{\prime}+b+c=5$

즉, $_{3}H_{5}$가 되고 $b$ ,$c$도 마찬가지이므로 $_{3}C_{1}$을 곱하여 망한 경우는 $_{3}C_{1}*$$_{3}H_{5}$가 된다.

따라서 구하고자 하는 경우의 수는 $_{3}H_{15}-$$_{3}C_{1}*$$_{3}H_{5}=73$이다.

 

이제 여러분은 계산할 수 있다!

$a+b+c=20$이고 $m=9$인 경우에 대해 직접 답을 유추해보자.

 

.

.

.

.

.

.

 

 

답이 33이라 생각한다면 땡이다.

같은 방법으로 계산하면 $_{3}H_{20}-$$_{3}C_{1}*$$_{3}H_{10}=33$이다. 하지만 중요한 사항을 고려해주지 않았다.

앞서 우리는 $a, b, c$가 각각 10이 되는 경우를 고려했다. 하지만 현재 합이 20보다 큰 상황에서 $a, b$가 동시에 10이 되는 경우가 존재한다. 즉, 각각이 10이 되는 경우를 고려하면 2개가 10이되는 경우를 중복으로 센다는 것이다. 이를 해결하기 위해선 중복으로 센 것을 한 번 더 더해주면 된다! 따라서 답은 다음과 같다.

$_{3}H_{20}-$$_{3}C_{1}*$$_{3}H_{10}+$$_{3}C_{2}*$$_{3}H_{0}=36$

이것을 포함 배제의 원리라고 한다.

 

이제 감을 좀 잡았을 것이므로 이를 일반화 시켜보자. 

아래 과정을 따라가면 된다.

1. 전체 경우에서 망한 경우를 뺀다

2. 포함 배제의 원리를 적용한다.

전체 경우는 $_{k}H_{d}$

망한 경우는 $_{k}C_{1}*$$_{k}H_{d-m}$

포함 배제의 원리를 적용하면 $_{k}C_{2}*$$_{k}H_{d-2m}$

다시 적용하면 $_{k}C_{3}*$$_{k}H_{d-3m}$

...

이 된다.

따라서 답은

$_{k}H_{d}-$$_{k}C_{1}*$$_{k}H_{d-m}+$$_{k}C_{2}*$$_{k}H_{d-2m}-$$_{k}C_{3}*$$_{k}H_{d-3m}...$

좀 더 알아보기 쉽게 써보면

$d=mp+l$ ($0 \le l < m$) 일때