대진표 경우의 수 (1)

[대진표 경우의 수]

대진표 경우의 수를 구하는 법을 알아보자. (토너먼트)

먼저 간단하게 4팀의 대진표 경우의 수를 구해보자.

구별하기 쉽게 팀은 1, 2, 3, 4 팀으로 하고 우리가 짜야할 대진표는 아래와 같다.

결론부터 말하면 대진표짜기는 "모든 경우의 수에서 바꿔도 똑같은 부분마다 2로 나눠가는 것" 이다.

1. 모든 경우의 수를 구한다. 단순 나열 4! = 24

2. 바꿔도 똑같은 부분을 찾을때마다 2로 나누어 준다.

1번 모든경우의 수는 아래와 같다. 

그러면 2번 바꿔도 똑같은 부분이란 건 무엇을 말하는 걸까

아래에 두 대진표를 비교해보자

team1과 team2의 자리를 바꿔준 대진표이다. 

두 팀의 자리를 바꿔주어도 대진표는 변함이 없다. 

어차피 첫경기에 team1과 team2가 맞붙는 같은 대진표가 되는 것이다. 

즉 우리가 구한 총 경우의 수에서 이런 같은 대진표들을 삭제해주는 작업을 해주어야 한다. 

위 그림처럼 총 경우에서 team1번 자리와 team2번 자리가 같은 경우의 수를 비교하였다.

왼쪽과 오른쪽은 대진표 상에서는 같은 경우의 수가 되므로 한쪽은 삭제가 가능하다. 

즉 나누기2 를 해주는 것이다. 

그러면 우리 대진표에서 바꿔도 되는 부분은 총 몇개 일까?

위와 같이 바꿔도 똑같은 부분이 총 3곳이다. 

그렇다면 우리 대진표에서 나올 수 있는 경우의 수는

총 3개이다. 

다음 포스팅에서는 좀더 복잡한 대진표를 다뤄보도록 하겠다. 

(부전승이 있으면 바꿔도 되는 부분이 아니다.)