2014년 2월 10일에 작성한 텀블러 포스트이다.
박종안 외3인의 《이산수학》 제3판(경문사)에서 '순열' 단원에는 다음과 같은 연습문제가 있다.
가람이는 일곱 명의 친구를 7일 동안 하루에 세 명씩 저녁식사에 초대하려고 한다. 일곱 명의 친구 모두가 정확히 한번만 다른 모든 친구와 저녁식사를 할 수 있도록 초대하는 경우의 수를 구하여라.
일곱 명의 친구들에게 1 부터 7 까지 번호를 매기자. 임의의 친구 i는 자신을 뺀 나머지 여섯 명의 친구와 모두 한 번씩 짝을 이루어야 한다. 그리고 한번에 세 명씩 짝을 이루므로, 총 3번의 식사를 해야한다. 친구 1을 기준으로 생각하자. 여섯 명의 친구 2~7을 두 명씩 짝을 짓는 방법은 다음과 같다.
\[\binom{6}{2} \binom{4}{2} \binom{2}{2} \frac{1}{ 3! } = 15\]
친구 2~7을 두 명씩 (2, 3), (4, 5), (6, 7)로 짝 지었다고 하자. 2와 3은 한번 식사를 하므로, 남은 두번의 식사는 따로 해야 한다. '4와 5' 그리고 '6과 7'도 마찬가지다. 따라서 가능한 경우는 다음의 둘 밖에 없다.
| 1 2 3 |
1 4 5 |
1 6 7 |
2 4 6 |
2 5 7 |
3 4 7 |
3 5 6 |
| 1 2 3 |
1 4 5 |
1 6 7 |
2 4 7 |
2 5 6 |
3 4 6 |
3 5 7 |
끝으로 이 일곱쌍을 순서를 자유롭게 배열할 수 있으므로 가능한 경우의 수는 15×2×7! 이다.
한편, 우연히 영문 위키에서 "Kirkman's schoolgirl problem"이라는 유명한 문제를 찾았는데, 위의 연습문제 보다 훨씬 복잡하지만 유사한 조건을 가지고 있는 점이 눈에 띄어서 이 글을 쓰게 되었다. 아래는 영문 위키 원문 중의 일부를 번역한 것이다.
"커크맨의 여학생 문제"는 조합론(combinatorics)에서 '토마스 커크맨'(Thomas Penyngton Kirkman)에 의해 1850년에 "신사 숙년의 일기"(The Lady's and Gentleman's Diary, p.48)의 'Query VI'으로 제안된 문제이다.
문제는 다음과 같다.
열다섯 명의 여학생들이 연달아 칠일 동안 세 명씩 산책을 한다. 같은 학생과 두 번 이상 산책하지 않게 산책 일정을 정하라.
열다섯 여학생들에게 01 부터 15 까지 번호를 매기면, 아래의 배열은 하나의 해가 된다.
| 월 | 화 | 수 | 목 | 금 | 토 | 일 |
| 01, 06, 11 | 01, 02, 05 | 02, 03, 06 | 05, 06, 09 | 03, 05, 11 | 05, 07, 13 | 11, 13, 04 |
| 02, 07, 12 | 03, 04, 07 | 04, 05, 08 | 07, 08, 11 | 04, 06, 12 | 06, 08, 14 | 12, 14, 05 |
| 03, 08, 13 | 08, 09, 12 | 09, 10, 13 | 12, 13, 01 | 07, 09, 15 | 09, 11, 02 | 15, 02, 08 |
| 04, 09, 14 | 10, 11, 14 | 11, 12, 15 | 14, 15, 03 | 08, 10, 01 | 10, 12, 03 | 01, 03, 09 |
| 05, 10, 15 | 13, 15, 06 | 14, 01, 07 | 02, 04, 10 | 13, 14, 02 | 15, 01, 04 | 06, 07, 10 |
이 문제의 해는 "Kirkman triple system"의 한 예로 볼 수 있다. 참고로 동형이 아닌 일곱개의 해가 있다.