여러분은 파티를 준비하고 있고, 초대할 손님 명단을 작성 중입니다. 파티가 즐겁게 진행되려면 몇 명을 초대해야 할까요? 여기서 핵심은 초대된 사람들 사이의 관계입니다. 모든 손님이 서로 잘 아는 사이라면 이야깃거리가 금방 고갈될 수 있습니다. 반대로, 모든 손님이 서로 모르는 사이라면 어색한 분위기가 형성될 수도 있죠. 따라서, 손님들 사이의 관계가 적당히 섞여 있는 것이 중요합니다. 그렇다면, 이 균형을 유지하면서도 파티가 흥미롭게 진행되려면 어떻게 해야할까요? 이런 질문을 던져봅시다. 적어도 3명이 서로 알거나, 3명이 서로 모르는 그룹이 생기도록 하려면 최소 몇 명의 손님을 초대해야 할까요? 파티 플래너 문제와 그래프앞서 본 문제를 파티 플래너 문제라고 부릅니다. 이 문제를 이해하기 위해서는 그래프..

4명의 학생이 시험을 치른 후 자신의 시험지가 아닌 서로의 시험지를 채점해 주는 경우의 수는어떻게 될까요? 이 경우의 수를 세는 문제는 1708년 피에르 레이몬드(Pierre Raymond de Montmort가 처음으로 고안했습니다. complete permutation 완전순열 또는derangement라고 불리는 이경우의 수는 모든 원소의 위치를 바꾸는 순열입니다. 유한집합 S의 원소의 개수를 n개라했을 때 이 완전순열의 경우의 수를 준계승 영어로 서브팩토리얼이라고 하며 기호로는 다음과 같이 느낌표를 앞에 씁니다. 그렇다면 이 경우의수를 어떻게 구할 수 있을까요? 이 경우의 수는 다음과 같이 귀납적으로 정의되어 있습니다. !n = (n-1)(!(n-1)+!(n-2) 완전순열의 경우의 수는 X에서 X로..