원순열 고정의 의미, 회전의 의미

원순열 고정의 의미, 회전의 의미

순열에는 원순열도 있다. 원순열은 ‘원형으로 돌려서 같은 경우가 있으면 제외한다’는 것이 원리이다.

가령 다음과 같은 그림이 있다고 하자.

 

A, B, C, D 4명이 원탁에 앉은 그림이다.

2개의 그림이 얼핏 보면 다른 경우처럼 보이지만, 사실 같은 경우이다.

또한 위 그림처럼 계속 회전을 시킨다면 같은 경우가 총 4개가 나온다.

원순열의 원은 ‘동그란 모양(Round)’이 아닌 ‘동그란 모양으로 회전(Rotate)’의 뜻에 가깝다.

 

 

위 그림을 다음과 같이 만들어도 동일하기 때문이다.

 

 

원순열에서 중요한 것은 원모양으로 회전시켰을 때, 겹쳐지면 1가지 경우로 본다는 것이다.

원순열은 일렬로 나열하는 경우의 수에서 ‘회전’해서 겹치는 경우를 제외한다.

여기서 키워드는 ‘회전’이다. 그렇다면 회전해서 같아지는 경우가 몇 개씩 생기는지를 알면 원순열을 해결할 수 있게 된다.

 

 

삼각형은 회전해서 같은 경우가 3개씩 있으므로 모든 경우의 수에서 을 나누면 원순열의 경우의 수가 된다.

 

 

 

이것은 삼각형이 아닌 원도 마찬가지이다. 가운데 탁자가 삼각형 모양이든 원모양이든 관계없이 세 개의 자리가 기준이 된다. 어째서 위의 경우는 같은 경우일까. A의 입장에서 생각해보자. A의 입장에서 본다면 왼쪽은 B가 앉아있고 오른쪽은 C가 앉아있다. 위 세 가지의 경우 모두 A입장에서 보면 마찬가지인 것이다. 나의 왼쪽과 오른쪽에 누가 앉는가에 있어서는 동일한 것이다. 따라서 원순열에서는 같은 경우라고 보는 것이다.

다음 그림은 회전하면 몇 가지 경우의 수가 생길까.

 

 

직사각형 모양의 탁자에 8명이 앉아있다. 모든 자리를 회전시키면 2가지의 경우가 생긴다. A입장에서 바라보면 왼쪽은 B가 앉아있고 오른쪽에는 H가 앉아있으므로 달라진 것이 없는 것이다. 모든 경우의 수는 이와 같이 2가지 경우가 중복되므로 모든 경위의 수에서 2를 나누어 주면 된다.

 

 

이것이 원순열에 대한 회전의 관점이다.

 

원순열을 푸는 방법은 두 가지가 있다.

 

 

한 마디로 ‘회전’이냐 ‘고정’이냐이다. 먼저 소개한 관점이 바로 회전이다. 회전해서 같은 경우가 각각의 경우마다 있으므로 전체에서 나눈다는 것이다.

 

 

원순열에서 한 자리를 고정시켜 회전을 의미없게 만드는 관점 : 고정

두번째 원순열을 푸는 관점으로서 ‘고정’이라는 단어를 사용하는데 고정의 의미가 무엇인지 살펴보도록 해보자.

서로 다른 4명(A, B, C, D)가 탁자 주변을 빙빙 돌다가 어느 순간 자리에 앉는 게임을 한다고 하자. 이때 게임의 규칙을 하나 추가해서 아무나 한 명은 무조건 어떤 한 자리에 되돌아 와야 한다고 하자. 이것이 바로 고정의 의미이다.

 

 

아무나 중 한명으로 뽑힌 A는 계속 한 지정된 자리로 되돌아 와야 한다면 이렇게 생각할 것이다. ‘뭐야, 나는 수건돌리기 게임을 하나 마나잖아!’ 실제로 A는 게임을 하나 마나인 것이다. 자리가 이미 정해져있으므로 같은 자리에 앉아있는 것이나 다름없기 때문이다.

이걸 깨달은 A는 이제 가만히 앉아서 다른 사람이 자리를 바꾸는 것을 구경하게 된다. 구경을 하다보니 A는 왼쪽부터 순서대로 번호를 매길 수 있다는 것을 알게 된다.

 

 

4명 중 1명은 1인칭 관찰자가 되어 사라지게 되고 남은 3명은 관찰자의 시야에서 서로 자리를 바꾸는 보통 순열이 되는 것이다.

 

따라서 원순열에서 고정된 자리에 앉은 1명(위의 사례에서는 A)이 관찰자가 되어 왼쪽부터 번호를 매긴 자리에 남은 3명이 일렬로 나열하는 경우가 된다. 그렇다면 다음의 경우는 어떨까?

 

 

원순열에서 회전시켜 같은 경우의 수를 전체에서 나누는 관점 : 회전

 

 

총 8개의 자리에 8명이 앉는 경우의 수를 구한다고 하자. 회전의 관점에서 본다면 전체 경우의 수인 8에서 회전해서 나올 수 있는 모든 경우의 수인 2를 나눈 수가 된다.

 

원순열에서 회전해서 같은 중복되는 경우의 수는 아래처럼 회전할 때 모양이 겹쳐지는 수와 같다.

 

 

원순열에서 회전의 관점에서 보면 모든 경우의 수에서 회전해서 겹쳐지는 종류를 나누면 된다는 것을 알 수 있다.

 

이제 원순열에서 회전의 관점이 아닌 고정의 관점(1인칭 관찰자 관점)에서 바라보도록 하자.

1인칭 관찰자 시점에서는 한 명이 관찰자로서 기준이 되어야 한다. 아래처럼 한 자리가 고정된다고 생각하자.

 

 

이때 관찰자의 입장에서 바로 왼쪽부터 번호를 매길 수 있다.

 

 

고정된 한 사람은 함께 나열하지 않는다. 그렇다면 위의 원순열의 경우의 수는 나머지 7명을 일렬로 나열하는 방법의 수인 7!가 될까? 이때 주의해야 할 것이 있다. 바로 관찰자의 뷰(View)이다.

원순열에서는 관찰자가 바라보는 독특한 자리가 달라지면 다른 경우로 본다는 것이다. 이것이 무슨 말이냐면,

 

 

관찰자를 제외한 나머지 사람들을 일렬로 나열하는 경우를 계산하더라도 관찰자의 뷰(View) 또는 보는 위치(Position)가 달라지면 다른 경우로 본다는 것이다. 따라서 원순열에서 관찰자의 시점이 달라지는 수(자리의 종류)를 곱해주면 된다.

 

원순열에서 관찰자 1명을 제외한 7명을 일렬로 나열하는 경우의 수 × 관찰자의 뷰가 달라지는 경우

(8 − 1)! × 4 = 7! × 4 = 20160(가지)