원탁

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

1. 한 원탁에 $8$명을 앉히는 경우의 수는?

우리의 친구 Lucky Pierre를 소환하자. Lucky Pierre를 앉힐 사람 중 한 명이라 생각하고 그의 위치를 먼저 정한다고 생각하면 이 문제를 쉽게 해결할 수 있다. 원탁에 앉히는 것이므로 그를 어디에 위치시키든 모두 동일한 경우이다. 먼저 Lucky Pierre의 위치를 정했다고 하자. 이제 남은 다른 위치에는 모두 순서가 생긴다. 즉 Lucky Pierre의 오른쪽으로 몇 번째 위치라는 순서가 생긴다. 따라서 나머지 $7$명의 사람들은 $7!$가지 방법으로 앉을 수 있다. 즉 구하는 답은 $7!$이다.

2. King Arthur의 기사 $12$명을 원탁에 앉히는 경우의 수는?

답은 $11!$이다. (Lancelot이 사실은 Lucky Lancelot Pierre인지 누가 알았겠는가?) 지금까지의 논의를 다음의 관찰으로 쉽게 일반화 할 수 있다.

관찰 한 원탁에 사람 $n$명을 앉히는 경우의 수는 $(n-1)!$이다.

3. 커플 $8$쌍을 일렬로 앉히되, 각 커플은 이웃하여 앉도록하는 경우의 수는?

각 커플 안에서 사람을 $2!$가지 방법으로 배열할 수 있다. 커플들을 일렬로 배열하는 방법은 $8!$가지 이므로 구하는 답은 $2^{8}\times 8!$이다.

4. 커플 $8$쌍을 원탁에 앉히되, 각 커플은 이웃하여 앉도록하는 경우의 수는?

각 커플 안에서 사람을 $2!$가지 방법으로 배열할 수 있다. 그리고 물론 Pierres를 포함한 커플들을 원탁에 $7!$가지 방법으로 배열할 수 있으므로 구하는 답은 $2^{8}\times 7!$이다.

대부분의 셈하기 문제를 해결함에 있어서 어떤 원하는 결과를 얻기 위해 필요한 물리적인 행동을 마음속으로 해보는 것은 큰 도움이 된다. 예를 들어 위의 4번 문제를 생각할 때, 우리의 친구 Lucy Pierre와 Lucky Pierre를 생각하면 편리하다. 원탁에 이들을 위치시킬 때, 마음속으로 Lucky를 Lucy의 오른쪽에 둘 것인지 혹은 왼쪽에 둘 것인지를 묻는 것이다. 그리고 다른 커플 각각에 대해서도 오른쪽에 누구를 앉히는가도 물어본다. 마지막으로 Pierres를 이미 원탁에 둔 상태에서 나머지 오른쪽 왼쪽 멤버가 정해져있는 커플들을 Pierres의 오른쪽 방향에 어떤 순서로 배치할 것인지를 물어본다. 이 쉬운 질문들에 답하고나면 원하는 최종적인 답을 얻을 수 있다. 다른 방법으로는 각 커플을 카드 $1$장으로 생각하여 원탁에 두른 후 각 커플의 멤버 $2$명의 순서를 바꾸는 것을 허용하여 답 $7!\times(2!)^{8}$을 얻을 수도 있다.

5. 미국 사람 $4$명, 벨기에 사람 $7$명, 케나다 사람 $10$명을 원탁에 앉히는 경우의 수는?

이 문제의 정답은 명백히 $20!$인가?

6. $4$개의 $\mathrm{C}$, $8$개의 $\mathrm{R}$을 일렬로 나열하되 $\mathrm{C}$끼리는 인접하지 않도록 나열하는 경우의 수는?

먼저 $8$개의 $\mathrm{R}$을 일렬로 나열한다. 이는 오직 한 가지 방법으로 할 수 있다. 그리고 그림 ${}_{\wedge}\mathrm{R}_{\wedge}\mathrm{R}_{\wedge}\mathrm{R}_{\wedge}\mathrm{R}_{\wedge}\mathrm{R}_{\wedge}\mathrm{R}_{\wedge}\mathrm{R}_{\wedge}\mathrm{R}_{\wedge}$를 살펴보면 $4$개의 C들 중 최대 $1$개를 써넣을 수 있는 $9$개의 공간이 있음을 알 수 있다. C를 써넣을 공간 $4$개를 $\binom{9}{4}$가지 방법으로 택할 수 있으며 물론 C들은 이러한 공간에 $1$가지 방법으로 넣어진다. 따라서 C끼리는 인접하지 않도록 써진 $4$개의 C, $8$개의 R로 만든 word는 $\binom{9}{4}$개가 있다. 앞으로 wedge ${}_{\wedge}$가 많은 셈하기 문제에서 공간의 위치를 나타내는데 사용되는 요긴한 도구임을 알게 될 것이다.

Homework.

1. 교사 $11$명 중에서 $5$명을 뽑아 위원회를 만드는 방법은 몇 가지인가?
2. Poker hands가 쥐는 $5$장으로 이뤄진 패는 몇 가지가 있는가?
3. Bridge hands가 쥐는 $13$장으로 이뤄진 패는 몇 가지가 있는가?
4. Poker 게임에서 풀하우스(세 장의 같은 종류의 카드와 두 장의 같은 종류의 카드)는 몇 가지가 있는가?
5. John이 그의 $10$명의 친구 중 누군가를 저녁식사에 초대하는데, 적어도 한 명은 초대하는 경우의 수는?
6. $\mathrm{DABBADABBADO}$의 letters를 배열하는 경우의 수는?
7. 대수학 책 $5$권, 기하학 책 $7$권, 미적분학 책 $4$권이 있다. 모든 책은 서로 구별된다고 할 때, 이 책들 중에서 같은 과목이 아닌 두 권의 책을 택하는 경우의 수는?
8. 적어도 한 개 과일을 선택한다고 할 때, $5$개의 사과, $7$개의 오렌지가 있다면 얼마나 많은 다른 선택을 할 수 있는가?
9. 알파벳을의 $26$-letter permutation 중 모음 두 개가 연속해서 있지 않는 것은 몇 개인가?
10. 인접한 두 letter는 일치하지 않는 $10$-letter word는 몇 개가 있는가?
11. 알파벳 $10$개로 이루어진 집합 중 연이은 letters를 원소로 갖는 것은 몇 개인가?
12. 남자 $5$명과 여자 $7$명을 한 줄로 앉히는데 남자끼리는 이웃하지 않도록 하는 경우의 수는?
13. 남자 $5$명과 여자 $7$명을 원탁에 앉히는데 남자끼리는 이웃하지 않도록 하는 경우의 수는?

Which of these questions can we answer now?

1. 중복을 허용하지 않고 순서를 고려하여 셀 때 서로 다른 $n$개에서 $r$개를 선택하는 경우의 수는?
2. 중복을 허용하고 순서를 고려하여 셀 때 서로 다른 $n$개에서 $r$개를 선택하는 경우의 수는?
3. 중복을 허용하지 않고 순서는 고려하지 않고 셀 때 서로 다른 $n$개에서 $r$개를 선택하는 경우의 수는?
4. 중복을 허용하고 순서는 고려하지 않고 셀 때 서로 다른 $n$개에서 $r$개를 선택하는 경우의 수는?

1. 사람들을 모두 배치시킨 후에 한번에 자리에 앉히는 것이 셈하기를 수월하게 해주는 경우가 많기 때문이다.