확률과 통계 보고서

토너먼트 대진표의 경우의 수

1. 두 가지 풀이법

현재 교과서에서는 토너먼트 대진표의 경우의 수가 거의 사라졌지만, 아직 몇몇 참고서에서는 이를 다루기도 한다. 참고서에서는 이를 ‘집합의 분할’로 푼다.

위와 같은 대진표에 4팀을 배치하는 경우의 수는 원소가 4개인 집합을 원소가 각각 2개, 2개인 집합으로 분할하는 경우의 수와 같다. 따라서, 경우의 수는 다음과 같다.

₄C₂×₂C₂×12!

이 방법으로 위의 대진표도 경우의 수를 구할 수 있다. 먼저 왼쪽의 4팀과 2팀을 분할한 뒤, 왼쪽의 4팀을 다시 2팀, 2팀으로 분할한다.

(4팀과 2팀을 분할하는 경우의 수) = ₆C₂×₂C₂ = 15
(2팀과 2팀을 분할하는 경우의 수) = ₄C₂×₂C₂×12! = 3
∴ (모든 대진표의 경우의수) = 15×3 = 45

위의 과정을 한 번에 쓰면 다음과 같다.

₆C₂×₂C₂×₄C₂×₂C₂×12! = 45

그러나 내가 토너먼트 대진표 문제를 풀 때는 저렇게 집합의 분할을 쓰지 않았다. 순열과 중복 제거로 풀었다. 다시 첫번째 대진표를 보자.

일단 네 팀을 순서대로 놓는다. 이를테면 A, B, C, D 순으로 놓았다고 하자. 이 때 A와 B는 서로 자리가 바뀌어도 같은 대진표이다. 마찬가지로 C와 D의 자리도 바꿀 수 있고, 마지막으로 (A, B)와 (C, D)의 자리를 바꿀 수도 있다. 따라서 대진표가 같은 순열이 2³ = 8개 생긴다. 모든 순열에서 각각 8개씩 서로 같은 대진표가 있으므로, 모든 대진표의 경우의 수는 다음과 같다.

4!2³ = 3

이것이 내가 가장 먼저 생각했던 방법이다. 나는 오히려 참고서의 풀이가 집합의 분할로 되어있다는 것에 경악했다. 이처럼 간단한 방법이 있는데 왜 참고서는 그것을 알려주지 않는지 의문이 들었다. 1학년 때 수학 선생님 앞에서 이 방법으로 풀었을 때, 선생님께서도 모르셨던 것 같았다. 이후 인터넷으로도 찾아보고 선배들에게도 물어보았는데, 인강에서는 처음부터 두번째 방법으로 알려줬다고 하며, 블로그나 지식인을 보면 두 방법이 혼용되고 있다.

이 방법이 얼마나 강력한지 한 번 더 확인하기 위해 두번째 대진표의 경우의 수도 구해보자.

각 자리를 왼쪽부터 A, B, C, D, E, F라 할 때, A와 B, C와 D, E와 F, (A,B)와 (C,D)를 서로 바꿔써도 같은 대진표이므로, 중복을 고려하여 순열의 수를 구하면,

6!2⁴

척 보기에도 훨씬 간단하게 구한 것 같다. 서로 바꾸어도 같은 대진표가 되는 자리만 잘 추려내면 간단한 식을 세워 풀 수 있다. 식이 간단하면 당연히 실수도 줄어들 것이다.

더 괴랄한 대진표도 이 방법이면 별로 두렵지 않다.

오로지 수험생을 괴롭힐 목적으로 만들어진 이 대진표를 두 가지 방법으로 풀어보자. 첫번째는 집합의 분할이다.

(ABCDEFGHIJ와 KLM을 나누는 경우의 수) = ₁₃C₁₀×₃C₃
(ABCDE와 FGHIJ을 나누는 경우의 수) = ₁₀C₅×₅C₅×12! 자세히 보면 ABCDE와 FGHIJ는 겉보기만 다를 뿐 같은 대진표이므로 2!으로 나누어주어야 한다.
(ABC와 DE를 나누는 경우의 수) = ₅C₃ ×₂C₂
(FG와 HIJ를 나누는 경우의 수) = ₅C₂ ×₃C₃
(AB와 C를 나누는 경우의 수) = ₃C₂ ×₂C₂
(HI와 J를 나누는 경우의 수) = ₃C₂ ×₂C₂
(KL과 M을 나누는 경우의 수) = ₃C₂ ×₂C₂

비교하기 좋게 정리하면 이렇게 된다.

₁₃C₁₀ ×₃C₃×₁₀C₅ × ₅C₅×12! × ₅C₃×₂C₂ × ₅C₂×₃C₃ × ₃C₂ ×₂C₂ × ₃C₂ ×₂C₂ × ₃C₂ ×₂C₂ = 972972000

식이 복잡해보이지만 답도 복잡한 걸 보면 그럴 만도 하구나 싶다. 이번에는 순열과 중복제거로 풀어보자. A-B, D-E, F-G, H-I, K-L, ABCDE-FGHIJ로 총 6가지 중복이 나온다. (특히 여섯번째 쌍의 중복은 첫번째에서 찾은 것과 같다.) 따라서 모든 대진표의 수는 이렇게 풀 수 있다.

13!2⁶ = 972972000

너무도 간단히 풀린다…. 이걸 보면 위에서 써내려간 9줄의 풀이는 무엇을 위한 것이었는지 모르겠다.

2. 심오한 연관성

어떻게 같은 문제에 대해 두가지 풀이법이 나왔을까? 수많은 자연수의 두 곱이 서로 같은 결과를 내는 것은 부자연스러워 보인다. 두 풀이법은 분명 명확한 연관성을 가지고 있을 것이다.

바로 위의 문제를 가지고 계속 이야기해보자. 첫번째 풀이의 조합 식을 팩토리얼 분수꼴로 풀어쓰면 다음과 같다.

13!10!3! × 10!5!5! × 12! × 5!3!2! × 5!3!2! × 3!2! × 3!2! × 3!2!

약분하면 다음과 같다

13!10!3! × 10!5!5! × 12! × 5!3!2! × 5!3!2! × 3!2! × 3!2! × 3!2! = 13!2⁶

어라? 두번째 풀이와 같은 식이 되었다. 이것은 분명한 의미를 가지고 있다.

처음에 우리는 13개 팀을 10개와 3개로 나누었다(첫번째 분수). 그리고 이 10개는 다시 5개와 5개로 나뉜다(두번째 분수). 자세히 보면 분할된 결과를 다시 분할하는 것을 알 수 있다. 따라서 이전의 분할에서 분모에 있던 팩토리얼 값이 다시 이후의 분할의 분자에서 나타나게 된다. 이들은 곱하는 과정에서 약분된다. 3개 이상의 팀이 묶인 것은 결국 다시 분할되므로, 3 이상의 팩토리얼 값은 결국 약분되어 사라진다. 그러면 마지막은 간단한 분수만 남게 된다. 분자에는, 분할된 결과가 아닌, 즉 분모에 다시 올 수 없는, 모든 팀의 개수가 팩토리얼로 남고, 분모에는 2(정확히는 2!)의 곱셈만 남게 된다.

약분의 비밀을 파헤쳐냈다. 이제 남은 건 분모의 2의 지수가 같아지는 이유뿐이다. 두번째 방법에서 2의 지수가 의미하는 것은 양쪽이 같은 대진표인 곳의 개수였다. 한편 첫번째 방법에서 2!으로 나누는 경우는 1차전의 개수와, 1차전을 제외하고 양쪽 대진표가 같은 경우의 수의 합과 같다. 그런데 1차전은 항상 양쪽에 한 팀씩 있는, 말하자면 양쪽의 대진표가 같은 경우다. 따라서 첫번째 방법과 두번째 방법에서 2의 지수가 의미하는 바는 정확히 같다.

집합의 분할을 쓰는 것은 너무 일반적인 방법을 쓰려다보니 괜히 돌아가는 길을 택하는 상황인 것 같다. 내가 쓰던 풀이는 야매도 편법도 아니다. 정확한 논리적 관계가 성립하는 방법이다. 산술적으로는 집합의 분할과 같은 식이지만 더 간단한 식이다. 특별한 지시가 없는 한 ‘순열과 중복 제거’의 방법으로 푸는 것이 훨씬 ‘바람직한’ 것 같다.

3. 집합의 분할 vs 중복이 있는 순열

토너먼트를 푸는 두 방법이 약분하고 정리하면 같은 식이 된다는 것을 보니, 일반적인 집합의 분할을 순열과 중복 제거 문제로 치환하여 풀 수도 있을 것이라는 강한 의구심이 든다.

서로 다른 n개를 p, q, r(p+q+r=n)개로 나누는 경우의 수를 조합으로 구해보자.

일단 다음을 계산하고,

m = _nC_p×_n-pC_q×_n-p-qC_r = _nC_p×_n-pC_q×_rC_r

p, q, r 중에 중복되는 숫자들을 제거하기 위해 m을 적당히 팩토리얼로 나눈 것이 분할의 경우의 수이다. 일반화해서 설명하려니 어려운데, 직접 예제를 풀어보자.

이 경우에 (3, 3, 4)에서 3이 두 번 나오므로, 2!으로 한 번 나눴다.

이 문제를 토너먼트처럼 순열로 해석해서 풀 수도 있다. 먼저 10명의 학생들에게 1부터 10까지 번호를 붙여준다. 이제 조 이름, 이를테면 A, B, C가 적힌 쪽지를 각각 3개, 3개, 4개 만들어서 일렬로 나열한다. 첫번째 쪽지는 1번 학생에게 주고, 두번째 쪽지는 2번 학생에게, … 그렇게 하면 중복이 있는 순열이 된다.

이때 A조와 B조의 학생들이 서로 조를 바꾸면 중복해서 세는 경우가 생긴다. 이렇게 중복되는 경우는 A-B 밖에 없으므로 2!으로 한 번 나누면 된다.

10!3!3!4!×12! = 2100

조금만 생각하면 알겠지만, 이 문제도 토너먼트처럼, 집합의 분할 풀이법을 팩토리얼 분수로 풀어서 약분하면 중복이 있는 순열 풀이법과 같은 식이 나온다. 그런데 팩토리얼까지 한 번에 풀어버리면 아주 사소한 차이가 생긴다. 먼저 집합의 분할을 보면,

10×9×83×2×1×7×6×53×2×1×1×12

₄C₄의 경우 1이란 것을 쉽게 계산할 수 있기 때문에 1로 바로 풀었다.

다음은 중복이 있는 순열이다.

10×9×8×7×6×5×4×3×2×13×2×1×3×2×1×4×3×2×1×12

맨 뒤에 어차피 약분될 찌꺼기가 붙어있다. 정말 미묘한 차이지만, 중복이 있는 순열로 풀면 익숙해지기 전에는 지면을 낭비할 수도 있다. 물론 익숙해지면 지면도 낭비하지 않고, 중복이 있는 순열이 분자의 숫자들이 더 순차적으로 풀리므로 이게 편할지도 모른다.

토너먼트는 확실히 순열로 푸는 게 편하다. 분할로 풀어도 다 약분하면 결국은 분모에 2! 밖에 안 남을 것이니, 거듭제곱의 지수만 잘 세어서 넣는 게 훨씬 빠르기 때문이다. 그러나 이를 일반화해서 집합의 분할과 중복이 있는 순열을 비교하면 토너먼트에서 보였던 명확한 메리트는 사라지고, 두 방법은 도긴개긴이 된다. 어느 놈이 더 간결하다 하는 것도 없는 것 같고 계산량도 비슷하니 말이다.

하지만 집합의 분할을 순열로 해석하는 과정에서 재미를 찾을 수는 있다. 비슷한 방법으로 순열 자체도 다시 중복이 있는 순열로 해석할 수 있고, 조합도 마찬가지다. 여기에서 설명하기에는 주제를 벗어나니 다음에 기회가 되면 다루도록 하겠다.