combinatorics

자연수 \(r\)의 분할(partition)이란, 합하여 \(r\)이 되는 자연수들의 모임이다. 만일 \(n\)개의 자연수를 합하여 \(r\)을 만들었다면, '\(r\)이 \(n\)개의 부분(part)들로 분할되었다'라고 말한다. 예를 들어, \(5\)는 \(7\)개의 분할, \( 5;\, 4+1,\ 3+2;\, 3+1+1,\ 2+2+1;\, 2+1+1+1;\, 1+1+1+1+1, \) 을 갖는다. \(5\)의 분할을 셀 때, 예를 들어 \(3+2\)와 \(2+3\)은 동일한 것으로 여긴다는 것에 유의하자. 또한 \(5\)를 한 개의 부분으로 분할하는 방법은 한 가지; \(5\)를 두 개의…

다음 문제를 생각해보자. The Hatcheck Problem. 안쪽에 자신의 이름이 적힌 모자를 하나씩 쓰고 있는 \(n\)명의 사람이 어떤 공연장에 들어가며 출입구에 모자를 맡겼다고 하자. 이들이 공연장에서 나오며 출입구에 맡겼던 \(n\)개의 모자를 각자 하나씩 받았나왔다고 할 때, 자신의 모자를 돌려 받은 사람이 한 명도 없는 경우의 수는? 이 Hatcheck Problem은 굉장히 오래된 문제이다(출입구에 모자를 맡기다니!). 그래도 재미있다. \(n\)개의 양의 정수 \(1, 2,…

여기서는 기초 조합론 수준의 이항정리를 간단히 살펴본다. 일반화된 이항정리와 관련된 글은 "일반화된 이항정리의 두 가지 증명"이라는 제목의 포스트(바로가기)를 참조하라. 식 \((a+b)^{n}\)을 전개했을 때, \(a^{i}b^{j}\)의 계수는 무엇일까? 식 \((a+b)^{n}\)을 \( \underbrace{(a+b)(a+b)(a+b)(a+b)\cdots(a+b)}_{\text{\(n\)개의 \((a+b)\)의 곱}} \) 으로 나타내어, \(n\)개의 인수 중 \(i\)개의 인수에서 \(a\)를 택하고 나머지 \(j\)개의 인수에서 \(b\)를 택하여 곱한 것으로 항 \(a^{i}b^{j}\)가 만들어진다는 것을 알 수 있다. 따라서 \((a+b)^{n}\)를 전개하여 얻는…

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

콘 아이스크림 \(12\)가지의 맛을 고를 수 있는 아이스크림 가게에서, 중복을 허용하지 않고 \(5\)개의 싱글 콘 아이스크림을 주문하는 경우의 수는 \(\binom{12}{5}\)임을 알고 있다. 또한 중복을 허용하여 싱글 콘 아이스크림을 주문하는 경우의 수는 \(\binom{12+5-1}{5}\)인 것도 알고 있다. 이제 하나의 콘에 두 가지 맛을 고를 수 있는 더블 콘 아이스크림을 생각해보자. 물론 콘에 아이스크림을 담는 순서를 고려해야 한다는 진정한 아이스크림 미식가와 아이스크림을 담는…

서로 다른 \(n\)개의 물건에서 중복을 허용하여 \(r\)개를 선택하는 경우의 수를 찾아보려 한다. 이를 위해 Mississippi problem을 활용할 것이다. 먼저 다음의 기초적인 문제의 답을 확실히 할 수 있어야 한다. 기둥들을 일렬로 세워 울타리를 만드는데, 인접한 두 기둥은 \(2\)m만큼 떨어져있게 심고, 맨 끝의 기둥 끼리는 \(20\)m만큼 떨어져 있게한다고 할 때, 기둥이 총 몇 개 필요한가? 일렬로 있는 \(10\)개의 물건을 서로 분리하기 위해,…

여기서는 원탁에 자리배치를 하는 경우의 수를 생각해볼 텐데, 적어도 이 책에서의, 원탁의 자리배치의 개수를 셈할 때의 관습은 다음과 같다. 두 자리배치 $s_{1}, s_{2}$에 대하여, $s_{1}$의 각 사람마다 그의 오른쪽에 앉은 사람이, $s_{2}$에서 일치할 때, $s_{1}, s_{2}$는 동일한 자리배치인 것으로 본다. 즉 원탁 배열은 회전하여 일치하는 것 끼리는 같은 것으로 본다는 것이다. 의자들은 고르게 분포되어 있으며 사람들 모두가 원탁 둘레로 배치될…

앞으로 종종 각 문제가 다음 문제로 이어지는 일련의 문제를 나열할 것이다. 이들을 처음 읽을 때는 마지막 질문에 답할 수 없을지라도, 다른 질문들을 해결해보며 차분히 읽어나가면 마지막 질문에 대한 답도 “분명히” 눈에 보일 수 있을 것이다. 앞으로 \(\mathrm{A_{1}, A_{2}, A_{3}}\)는 각각 하나의 letter로 여긴다. 아마 먼저 세 개의 \(\mathrm{A}\)를 서로 다른 색의 \(\mathrm{A}\)로 여기고 나중에는 구별할 수 없는 \(\mathrm{A}\)로 여기는 것이…

비둘기의 수가 비둘기집의 개수보다 많다면 (그리고 비둘기들이 모두 비둘기집으로 들어간다면) 반드시 어떤 비둘기집에는 두 마리 이상의 비둘기가 들어 있다. 좀 더 구체적으로 \(n+1\)마리 혹은 더 많은 비둘기를 \(n\)개의 비둘기집에 배정하면, 비둘기 중 적어도 두 마리는 같은 비둘기집에 배정된다. 더 일반적으로는, 비둘기의 수가 비둘기 집의 수의 \(k\)배 보다 더 많다면, 반드시 어떤 비둘기집에는 \(k+1\)마리 이상의 비둘기가 들어가 있다. 이러한 원리를 비둘기집의…

More Quickies. 서로 다른 \(5\)개의 라틴책, 서로 다른 \(7\)개의 그리스책이 있을 때, 하나의 라틴책과 하나의 그리스책을 고르는 경우의 수는? 하나의 \(2\)-letter word를 만드는 경우의 수는? 하나의 \(2\)-letter word를 만드는데, letter들이 서로 다른 것으로 만드는 경우의 수는? 하나의 \(2\)-letter word를 만드는데, 한 자음 뒤에 한 모음이 따라 오도록 만드는 경우의 수는? \(3\)명의 남자와 \(8\)명의 여자에서, 한 남자와 한 여자를 택하는 경우의…

이 글에서는 가능한 한 앞으로 중복되는 부연 설명을 피하기 위해 이 블로그에 올리는 조합론 혹은 이산수학 관련 포스트 전반에 걸쳐 적용되는 몇 가지 관습 혹은 관례를 명시한다. 사람은 항상 서로 구별된다. 그리고 편의상 오렌지는 서로 구별되지 않는다. 마찬가지로 사과, A, 빨간공, 그리고 특별한 언급이 없는 한 100원짜리 동전도 그들끼리는 서로 구별되지 않는다. 예를 들어, 복숭아, D, 초록공 등에도 일반적으로 동일한…

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