조합론

포함-배제의 원리란?포함-배제의 원리(Inclusion-Exclusion Principle)란 여러 집합들의 합집합의 크기를 구하는 데 사용하는 공식이다.포함-배제의 원리는 교집합의 크기로 합집합의 크기를 구하거나, 혹은 그 반대의 경우에 적용할 수 있다. 살펴보기두 집합의 합집합의 크기는 아래와 같은 공식으로 쉽게 구할 수 있다.$$ | A \cup B | = | A | + | B | - | A \cap B | $$ 집합의 개수를 하나만 더 늘려보자. 세 집합의 합집합의 크기는 어떻게 구할까?그림에서 볼 수 있듯이, $ | A | + | B | + | C | $를 하면 교집합 부분이 중복으로 더해진다.따라서 $ - | A \cap B | - | B \cap C | - | A \cap C | $를 해주어..

N+1개의 물건을 N개의 상자에 넣으면, 적어도 하나의 상자에는 두 개 이상의 물건이 들어간다. 오늘은 당연하면서도 다양한 곳에 적용할 수 있는 비둘기집 원리에 대해 알아보겠다. 증명 N+1개의 물건과 N개의 상자가 있을 때, 각 상자에는 한 개 이하의 물건만 들어가있다고 가정해보자. 각 상자에는 최대 1개의 물건이 있을 것이므로, 총 물건의 수는 많아야 N개이다. 그런데 N+1개의 물건이 있으므로, 이는 모순이다. 따라서 N+1개의 물건과 N개의 상자가 있을 때, 적어도 하나의 상자에는 두 개 이상의 물건이 들어간다. 귀류법을 이용해 쉽게 증명하였다. 귀류법이란 명제의 결론이 부정임을 가정했을 때 모순 발생함을 보여 명제가 참임을 증명하는 방법이다. 예시 한 반에 13명 이상의 학생이 있다면, 최소 2..