조합론

Quickies. 아래의 문제들을, 각 질문에 바로 답할 수 있을 때까지, 다른 날짜에 세 번 이상 풀어보는 것을 강력히 권한다. 각 질문을 읽으면서 바로 답할 수 있을 정도가 되어야 한다. \(16\)쌍의 여학생-남학생 커플에서 5명의 여학생을 택하는 경우의 수는? \(7\)개의 글자 AAABBBB를 배열하는 경우의 수는? \(12\)개의 글자 AAABBBBCCCCC를 배열할 때, C끼리는 이웃하지 않도록 배열하는 경우의 수는? \(10\)명의 사람을 일렬로 앉히는 경우의 수는?…

그렇다. 셈하는 것은 어렵다. “Counting”이란 전혀 쉬워 보이지 않는 말인 “계수적 조합론(enumerative combinatorics)”의 줄임말이다. 이는 “How many ways are there to . . .”로 시작하는 질문을 다루는 이산수학의 한 과목이라 할 수 있다. 예를 들어, 우리는 곧 “\(8\)가지 맛을 고를 수 있는 아이스크림 콘 \(12\)개를 주문하는 경우의 수는?”과 같은 질문의 답을 알게 될 것이다. 이 과목이 끝날 때는 “\(k\)개의 색을…