포함배제의 원리(inclusion–exclusion principle)

 

 

자 그럼 다음 문제를 포함배제의 원리를 이용해 공식을 유도해 보도록 하자.

 

n명의 사람들이 모두 모자를 쓰고 왔었는데, 이것을 모두 벽에 걸어 두었다가 회의가 끝난 후 모자를 다시 썼을 때 아무도 자기 자신의 모자를 쓰고 있지 않는 경우의 수를 구하여라.(완전순열 또는 교란순열이라 한다.)

풀이

 

STEP1

먼저 다음과 같이 가정하도록 하자.

 

 

STEP2

그러면 구하는 경우의 수는 다음과 같다.

그리고 이는 다음과 같은 식으로 구할 수 있다.

 

STEP3

그러면 이제 다음의 경우를 구해 보도록 하자.

여기에서 ②번 가정에 의해 다시 정리하면 다음과 같다.

그리고

이유는 다음과 같다.예를 들어

STEP4

자 이제 식을 정리해보도록 하자.