순열, 반전수, 홀짝성

순열(permutation)의 반전수(inversion count)와 홀짝성(parity)은 이산수학을 하다 보면 굉장히 자주 튀어나온다. 순열이라는 개념 자체가 우리에게 매우 친숙하고 일상생활에서도 자주 보이다 보니, 이 순열들의 성질이 자주 쓰일 수밖에 없는 것 같다. 긴 서론 없이 바로 시작하자.

순열

즉 정의역과 공역이 같은 전단사함수는 전부 순열이라고 부른다. 위의 정의에 따르면 \(X\)가 무한집합을 포함해 어떤 집합이어도 상관없지만, 이 글에서는 \(X\)가 유한집합, 특히 \(\{1, 2, \cdots, n\}\) 꼴의 집합인 경우에 집중할 것이다.

\(1\) 이상 \(n\) 이하의 자연수의 집합을 매번 일일이 쓰기 번거롭기 때문에 간단한 표기를 만든 것이다.

직관적으로 순열은, 어떤 물체들의 순서를 뒤섞는 것이라고 볼 수 있다. 일렬로 나열된 책들의 순서를 바꾸는 것은 하나의 순열이다. 반에서 아이들이 자리를 바꾸는 것 역시 하나의 순열이다. 루빅스 큐브에서 조각들이 서로 위치를 바꾸며 섞이는 것도 순열이다. 순열은 아주 많은 곳에서 발견할 수 있다.

증명은 이 글을 읽는 여러분이라면 스스로 할 수 있을 것이라 믿는다.

순열의 표현

순열 하나를 표현하는 데 \(\sigma(1) = 2, \sigma(2) = 1, \sigma(3) = 3\)이라고 매번 쓰는 것은 매우 번거롭고 읽기도 어려우므로, 간단하게 표현하는 방법을 알아보자.

두 줄 표기법

\([n]\) 위에서의 순열 \(\sigma\)를 다음과 같이 두 줄로 표기한다.

\(\pmatrix{ 1 & 2 & \cdots & n \\ \sigma(1) & \sigma(2) &\cdots & \sigma(n)}\)

즉 첫 줄에 \(1\)부터 \(n\)까지를 쓰고, 각 숫자 아래에 그 숫자가 어떤 숫자로 보내지는지를 쓴다. 예를 들어 위의 순열은 아래와 같이 쓸 수 있다.

\(\pmatrix{ 1 & 2 & 3 \\ 2 & 1 & 3}\)

첫 줄에 꼭 \(1\)부터 \(n\)까지를 순서대로 쓸 필요는 없다. 아무 순서대로나 쓴 다음, 첫 번째 줄의 수를 \(\sigma\)에 넣은 결과가 그 수의 바로 아래에 나오게만 하면 된다. 즉 같은 순열을 다음과 같이도 쓸 수 있다.

\(\pmatrix{ 2 & 1 & 3 \\ 1 & 2 & 3}\)

직관적으로, 두 줄 표기법에서 두 개의 열(세로줄)을 고른 다음 그 열들의 위치를 바꿔도 같은 순열을 나타낸다는 것을 알 수 있다. 두 줄 표기법은 누가 어디로 가는지를 명확하게 나타내 준다는 장점이 있다.

한 줄 표기법

두 줄 표기법에서 첫 줄을 \(1\)부터 \(n\)까지 순서대로 써야 한다는 약속을 한다면, 매번 첫 줄을 쓸 필요도 없을 것이다. 그러므로 첫 줄을 지워 버리고 다음과 같이 순열을 표기할 수 있다.

\(\sigma(1) \ \sigma(2) \ \cdots \ \sigma(n)\)

예를 들어 위의 순열을 간단하게 \(213\)으로 표기된다. 한 줄 표기법은 두 줄 표기법에 비해 표기의 자유도가 떨어지지만(반드시 고정된 순서로만 표기해야 하니까) 대신 공간을 매우 절약할 수 있다.

그림!

순열은 결국 원소들끼리 서로 위치를 바꾸는 것 아닌가! 그렇다면 누가 어디로 가는지 가장 확실하게 시각적으로 보여주는 방법은 다름 아닌 동그라미와 화살표를 이용한 그림이다. 예를 들어 순열

\(\pmatrix{ 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ 6 & 7 & 3 & 11 & 8 & 9 & 10 & 1 & 5 & 2 & 4}\)

은 다음과 같은 그림으로 표현할 수 있다.

여기서 이 그림이 여러 개의 사이클들로 이루어져 있다는 사실을 관찰하자. 곧 증명하겠지만, 이는 모든 순열의 공통적인 특징이다.

순열의 합성

순열도 결국 함수이기 때문에 다른 평범한 함수들처럼 합성이 가능하다. 예시를 위해 다음 두 개의 \([4]\) 위에서의 순열을 생각하자.

\(\sigma_1 = \pmatrix{ 1 & 2 & 3 & 4 \\ 2 & 4 & 1 & 3}, \sigma_2 = \pmatrix{ 1 & 2 & 3 & 4 \\ 1 & 4 & 3 & 2}\)

두 순열의 합성 \(\sigma_2 \circ \sigma_1\)은 다음과 같이 "\(\sigma_1\)을 먼저 한 뒤 \(\sigma_2\)를 하는" 순열로 생각할 수 있다. 함수 합성은 뒤에 써 있는 것부터 계산한다는 것을 상기하자.

따라서 우리는 다음을 알 수 있다.

\(\sigma_2 \circ \sigma_1 = \pmatrix{ 1 & 2 & 3 & 4 \\ 4 & 2 & 1 & 3}\)

순열은 매우 자주 합성되기 때문에 순열의 합성에서는 \(\circ\) 기호를 생략하는 경우가 많다. 마치 수의 곱셈에서 곱셈 기호를 생략하는 것과 비슷하다. 따라서 위의 합성은 그냥 \(\sigma_2 \sigma_1\)이라고 써도 된다.

함수의 합성은 결합법칙이 성립하기 때문에 순열의 합성에서도 당연히 결합법칙이 성립한다. 즉 \(\sigma_3 (\sigma_2 \sigma_1) = (\sigma_3 \sigma_2) \sigma_1\)이 항상 성립하며, 덕분에 우리는 세 개 이상의 순열의 합성에서도 괄호를 떼고 \(\sigma_3 \sigma_2 \sigma_1 \)처럼 쓸 수 있다.

항등순열과 역순열

그렇다, 그냥 항등함수. 일명 "아무것도 안 하기" 순열이다. 항등함수는 항상 전단사함수이기 때문에 항등순열은 반드시 존재한다.

항등순열은 \(i\), \(\mathrm{id}\), \(e\), \(1\) 등으로 쓴다. 이 글에서는 가장 혼동의 우려가 적은 \(\mathrm{id}\)를 사용한다.

순열들이 다루기 편리한 이유는 정의역과 공역이 같을 뿐 아니라 전단사임이 보장되기 때문이다. 따라서 마음대로 합성할 수 있고 마음대로 역함수를 취할 수 있다. 역함수와 항등함수의 정의에 의해, \(\sigma\sigma^{-1} = \sigma^{-1}\sigma = \mathrm{id}\)이다.

"\(\tau\)를 한 뒤 \(\sigma\)를 하는 것"을 거꾸로 하면 \(\sigma\)를 먼저 거꾸로 하고 \(\tau\)를 그 다음에 거꾸로 해야 한다는 것이다. 양말을 신고 신발을 신는 것을 거꾸로 하면 신발을 벗고 양말을 벗는 것이다. 일반적인 전단사함수들에 대해서도 성립하는 성질이며 그 증명은 고등학교 수학에도 나오므로 생략.

순열의 사이클 분할

직관적으로, \(k\)-사이클은 \(k\)개의 원소들을 골라 원형으로 한 칸씩 밀고, 나머지는 건드리지 않는 순열이라고 생각하면 된다.

즉, 그냥 뒤로 돌아가는 사이클. 별 거 없는 정리이며 증명도 매우 쉽다. 심심하면 스스로 해 보자.

즉, 서로소인 사이클은 '서로 겹쳐서 간섭하는 일 없이' 각자 할 일을 하는 사이클들이다.

위에서 순열의 합성에서는 일반적으로 교환법칙이 성립하지 않는다고 하였지만, 두 순열이 서로소인 사이클일 때만큼은 성립한다. 생각해 보면 당연한 게, 두 순열이 완전히 따로 노는 사이클들이니 이쪽 사이클을 먼저 돌리든 저쪽 사이클을 먼저 돌리든 결국 둘 다 한 칸씩 돌아가는 건 똑같을 것이다. 엄밀한 증명을 위해서는 \((\sigma_1 \sigma_2)(x) = (\sigma_2 \sigma_1)(x)\)가 모든 \(x \in [n]\)에 대해 성립함을 \(x\)의 값에 따라 조건을 나누어서 보이면 된다. 전체 과정은 생략한다.

예시를 이해하고 나면 정리가 이해될 것이고, 왜 유일한 것인지도 직관적으로 알 수 있을 것이다. 엄밀히 증명하려면 강한 수학적 귀납법을 사용해서, 하나의 수에서 시작해 \(\sigma\)를 계속 적용하다 보면 언젠가는 원래 수로 돌아와야 함을 보이고, 그 과정에서 생긴 사이클을 빼고 나면 더 작은 순열이 된다는 논리를 쓴다. 매우 귀찮고 긴 과정이므로 역시 전체 과정은 생략한다.

위의 정리에 따라 모든 순열은 서로 영향을 주지 않는 사이클들의 합성으로 나타낼 수 있으므로, 위에서 소개한 순열의 세 가지 표기법에 더해 사이클 표기법이라는 새로운 표기법을 사용할 수 있게 된다.

전치와 이웃전치

간단히 말해 두 원소를 서로 맞바꾸는 순열로, 항등순열을 제외하면 가장 간단한 형태의 순열이다. 전치가 강력한 이유는 모든 순열을 전치들의 합성으로 쓸 수 있다는 것인데, 순열을 한 번에 분석하기는 까다롭지만 단 두 개의 원소만 바뀌는 전치는 분석하기 쉽기 때문에 아래에서 반전수를 분석할 때 좋은 도구가 될 것이다.

증명: 구성적 증명이 가능하다. 다음을 직접 확인해 보자.

\((a_1 \ a_2 \ \cdots \ a_k) = (a_1 \ a_k) \cdots (a_1 \ a_3) (a_1 \ a_2) \)

확인하기 위해서는 좌변과 우변이 각각 \(a_i\)를 어디로 보내는지 확인해 보면 된다.

증명: 위에서 모든 순열은 서로소인 사이클의 합성으로 표현할 수 있다는 것을 알았다. 따라서 주어진 순열을 사이클로 분해한 다음, 각각의 사이클을 위의 정리를 이용해 전치이 합성으로 나타내면 된다.

직관적으로는 꽤 당연한 사실이다. 학생 \(n\)명이 자리를 원하는 대로 바꾸고자 할 때 한 번에 두 명씩만 골라서 서로 바꾸는 과정을 반복하면 (조금 오래 걸리긴 할지라도) 언젠가는 원하는 배치를 얻을 수 있을 것이다.

이웃전치는 전치 중에서도 특수한 형태로, 말 그대로 이웃한 두 개의 원소를 바꾸는 전치를 의미한다. 물건이 일렬로 나열되어 있을 때 인접한 두 물건의 위치를 맞바꾸는 것 정도로 생각할 수 있다.

증명: \(a < b\)라 가정해도 일반성을 잃지 않는다. 다음과 같이 구성적 증명이 가능하다.

\((a \ b) = (a \ a+1)(a+1 \ a+2) \cdots (b-1 \ b-2)(b \ b-1)(b-1 \ b-2) \cdots (a+1 \ a+2)(a \ a+1)\)

등식이 성립한다는 것을 확인하기 위해서는 역시 양변이 \(a, a+1, \cdots, b-1, b\)를 각각 어디로 보내는지 따라가 보면 되며, 합성된 이웃전치가 홀수 개임은 쉽게 보인다.

증명: 두 칸 위의 정리를 이용해 주어진 임의의 순열을 전치의 합성으로 나타낸다. 이제 한 칸 위의 정리를 이용해 각각의 전치를 이웃전치의 합성으로 나타낸다. 완성!

순열의 반전수

즉 순열이 얼마나 크기 관계를 많이 뒤집었는지를 나타낸다. 반전수가 작은 순열은 반전수가 큰 순열보다 크기 관계를 더 많이 유지한다.

증명: \(i<j\)이면 \(\mathrm{id}(i) = i < j = \mathrm{id}(j)\)이므로 \(\mathrm{id}\)의 반전은 없고, 따라서 반전수는 \(0\)이다.

증명 아이디어: \(\sigma\)의 반전의 집합을 \(I\), \(\sigma^{-1}\)의 반전의 집합을 \(I'\)라 하자. 함수 \(f: I \to I'\)를 \(f\left((i,j)\right) = (\sigma(j),\sigma(i))\)로 정의하고 \(f\)가 잘 정의된 전단사함수임을 보이면 된다. 잘 정의됨(즉, \((i,j) \in I\)이면 \((\sigma(j),\sigma(i))\in I'\)임), 전사임, 단사임을 보이는 과정은 어렵지 않으며, 여기서는 생략한다.

증명: \(\tau = (a \ a+1)\)이라 하자. \(P = \left\{(i, j) \vert 1 \le i < j \le n, (i,j) \neq (a,a+1) \right\}\)로 정의하자. 즉 반전의 후보인 쌍들 중 \((a,a+1)\)을 제외한 것의 집합으로 정의한다. 이제 다음과 같이 함수 \(f: P \to P\)를 정의하자.

\(f\left((i,j)\right) = (\tau(i),\tau(j)) \)

우선 \(f\)가 잘 정의되었다는 것을 보여야 하는데, 이를 위해서는 \((i,j)\in P\)이면 \((\tau(i),\tau(j))\in P\)라는 것을 보이면 된다. 그러고 나서 \(f\)가 전단사함수라는 것도 증명할 수 있다. 둘 다 어렵진 않지만 경우의 수를 열심히 나누어야 하는 과정이므로 자세한 과정은 생략하며, 스스로 해 보자.

이제 \((i,j)\)가 \(\sigma\)의 반전인 것과 \(f((i,j))\)가 \(\sigma\tau\)의 반전인 것이 동치임을 보여야 한다. 즉, \(\sigma(i) > \sigma(j) \iff \sigma\tau(\tau(i)) > \sigma\tau(\tau(j))\)임을 보여야 하는데, \(\tau\)가 전치라서 \(\tau\tau = \mathrm{id}\)이므로 이는 자명하다.

즉 우리는 \(P\)에 속하는 \(\sigma\)의 반전과 \(P\)에 속하는 \(\sigma\tau\)의 반전의 개수가 같다는 것을 알았다. 이 개수를 \(v\)라고 하자. 이제 \(P\)에 속하지 않는 반전만 세면 되는데, 반전이 될 수 있는 후보 중 \(P\)에 속하지 않는 것은 \((a,a+1)\) 하나뿐이다.

• 만약 \(\sigma(a) > \sigma(a+1)\)이라면 \((a,a+1)\)은 \(\sigma\)의 반전이고, \(\sigma\tau(a) = \sigma(\tau(a)) = \sigma(a+1) < \sigma(a) = \sigma(\tau(a+1)) = \sigma\tau(a+1)\)이기 때문에 \(\sigma\tau\)의 반전은 아니다. 따라서 \(\mathrm{inv}(\sigma) = v+1, \mathrm{inv}(\sigma\tau) = v\)이다.
• 만약 \(\sigma(a) < \sigma(a+1)\)이라면, 같은 방법으로 \(\mathrm{inv}(\sigma) = v, \mathrm{inv}(\sigma\tau) = v+1\)을 얻는다.

따라서 어떤 경우에도 \(\mathrm{inv}(\sigma\tau) = \mathrm{inv}(\sigma) \pm 1\)이 성립한다.

순열의 부호와 홀짝성

드디어, 이 글을 쓴 목적이 나왔다. 참 빨리도 나온다.

뜬금없는 정의처럼 보이겠지만, 순열의 반전수의 홀짝성은 매우 유용한 성질을 가지고 있다! 따라서 반전수의 개수 자체가 아닌 개수의 홀짝성만 보여주는 값인 부호를 정의한 것이다.

증명: 위에서 이미 증명한 결과에 의해, \(\mathrm{inv}(\sigma\tau) = \mathrm{inv}(\sigma) \pm 1 \)이므로 두 값의 홀짝성이 다르다. 따라서 \(\mathrm{sgn}(\sigma\tau)\)와 \(\mathrm{sgn}(\sigma)\)도 서로 반대 부호이다.

증명: 각각의 \(\tau_i\)가 이웃전치라고 할 때 \(\sigma = \tau_1 \tau_2 \cdots \tau_k\)이라고 쓰면,

\(\begin{align} & \ \mathrm{sgn}(\sigma) \\ = & \ \mathrm{sgn}(\tau_1 \tau_2 \cdots \tau_k) \\ = & \ -\mathrm{sgn}(\tau_1 \tau_2 \cdots \tau_{k-1}) \\ = & \ \mathrm{sgn}(\tau_1 \tau_2 \cdots \tau_{k-2}) \\ = & \ \cdots \\ = & \ (-1)^k \end{align}\)

이므로 정리가 성립한다.

증명: 위에서 전치는 홀수 개의 이웃전치의 합성으로 표현할 수 있다는 것을 증명했으므로, 전치는 반드시 홀순열이다.

짧지만 사실상 이 글에​서 가장 중요한 정리라 해도 과언이 아니다! 이렇게까지 고생해 면서 정의한 순열의 홀짝성이 왜 유용한지가 이 한 문장 안에 담겨 있다. 두 순열을 합성하면 부호는 곱해진다는 것으로, 순열의 홀짝성을 불변량으로 이용하고자 할 때 계속해서 쓰이는 성질이다.

증명: \(\sigma\)와 \(\tau\)를 각각 이웃전치의 합성으로 나타내자. 사용한 이웃전치의 개수를 각각 \(a\)개, \(b\)개라고 하면 \(\mathrm{sgn}(\sigma) = (-1)^a, \mathrm{sgn}(\tau) = (-1)^b\)이다. 또한, \(\sigma\tau\)는 방금 나타낸 방법들을 그대로 사용해 \(\sigma\)와 \(\tau\)를 각각 이웃전치의 합성으로 나타내면 \(a+b\)개의 이웃전치의 합성으로 나타낼 수 있으므로, \(\mathrm{sgn}(\sigma\tau) = (-1)^{a+b}\)이다. 따라서, \(\mathrm{sgn}(\sigma\tau) = (-1)^{a+b} = (-1)^a (-1)^b = \mathrm{sgn}(\sigma)\mathrm{sgn}(\tau)\)가 성립한다.

증명 1: 위에서 증명한 정리를 사용한다. \(\mathrm{sgn}(\mathrm{id}) =\mathrm{sgn}(\mathrm{id} \circ \mathrm{id}) = \mathrm{sgn}(\mathrm{id}) \mathrm{sgn}(\mathrm{id}) = (\mathrm{sgn}(\mathrm{id}) )^2 \), 그런데 순열의 부호는 \(\pm 1\)이므로 제곱하면 반드시 \(1\)이다.

증명 2: 위에서 \(\mathrm{inv}(\mathrm{id})=0\)을 보였으므로, \(\mathrm{sgn}(\mathrm{id}) = (-1)^0 = 1\)이다.

증명 1: \(\mathrm{sgn}(\sigma) \mathrm{sgn}(\sigma^{-1}) =\mathrm{sgn}(\sigma \sigma^{-1}) = \mathrm{sgn}(\mathrm{id}) = 1 \), 따라서 둘의 부호는 같아야 한다.

증명 2: 위에서 \(\mathrm{inv}(\sigma) = \mathrm{inv}(\sigma^{-1})\)임을 보였으므로, 둘의 부호 역시 같다.

이미 본 정리 같은가? 이웃전치라는 단어가 그냥 전치로 바뀌었다.

증명: 각각의 \(\tau_i\)가 전치일 때, \(\sigma = \tau_1 \tau_2 \cdots \tau_k \)라 하자. 이때 모든 전치는 홀순열이므로,

\(\mathrm{sgn}(\sigma) = \mathrm{sgn}(\tau_1 \tau_2 \cdots \tau_k) = \mathrm{sgn}(\tau_1)\mathrm{sgn}(\tau_2)\cdots\mathrm{sgn}(\tau_k)=(-1)^k\)

따라서 정리가 성립한다.

증명: 위에서 \(k\)-사이클은 \(k-1\)개의 전치의 합성으로 나타낼 수 있다고 했다. 따라서 \(k\)가 홀수이면 \(k-1\)은 짝수이므로 \(k\)-사이클은 짝순열, \(k\)가 짝수이면 \(k-1\)은 홀수이므로 \(k\)-사이클은 홀순열이다.

증명: \([n]\) 위에서의 짝순열의 집합을 \(E\), 홀순열의 집합을 \(O\)라고 하자. 함수 \(f: E \to O\)를 \(f(\sigma) = (1 \ 2) \sigma \)라고 정의하자. \(\sigma\)가 짝순열이면 \((1 \ 2)\sigma\)는 홀순열이므로(왜 그런지는 이제 바로 알 수 있어야 한다) 이 함수는 잘 정의되었으며, 역함수 \(f^{-1}(\sigma') = (1 \ 2) \sigma' \)의 존재를 통해 전단사함수라는 것을 알 수 있다. 따라서 \(E\)와 \(O\)의 원소들은 일대일 대응되므로 원소의 개수가 같다.

\([n]\) 위에서의 순열의 총 개수는 \(n!\)개이므로, 짝순열과 홀순열의 개수가 같기 위해서는 각각이 \(\dfrac{n!}{2}\)개가 되어야 한다.

그래서 왜 유용한가요

잠시 순열의 반전수와 홀짝성의 정의를 생각해 보면, 우리가 순열을 어떻게 표현하거나 분해하는지와는 상관없이 순수하게 그 순열 자체의 성질만으로 정의되어 있다. 그런데 정리에 따르면 순열을 전치들의 합성으로 표현하면 사용된 전치의 개수의 홀짝성은 순열의 홀짝성에 따라 결정된다고 한다. 그 순열을 분해한 방법에 관계없이.

즉, 순열의 홀짝성은 아주 좋은 불변량을 제공한다! 만약 어떤 순열이 짝수 번의 전치로 만들어질 수 있다면, 그 순열을 홀수 번의 전치로 만들 수 있는 방법은 없다. 물론 그 반대도 성립한다. 조합론적 증명을 조금 해 보았다면 불변량을 찾는 것이 얼마나 중요한지 알고 있을 것이다.

그리고 순열의 홀짝성이 강력한 도구인 또 하나인 이유는, 다름아닌 일일이 또 유도하고 증명하려면 매우 귀찮기 때문이다. 여러분이 이 글을 하나하나 따라오면서 읽었다면 이미 느꼈을 거라 믿는다. 하지만 순열의 홀짝성이라는 개념을 그냥 끌고 오면 이 모든 과정을 건너뛰고 유용한 결과만을 사용할 수 있다.

그래도 이렇게 열심히 배워놓고 사용 한 번 안 해볼 순 없으니 유명한 예시를 두 가지만 살펴보자.

15퍼즐

순열의 홀짝성을 설명할 때 빼놓아서는 안 되는, 단연 가장 유명한 응용이다.

15퍼즐(15 puzzle)은 가로세로 4칸, 총 16개의 칸으로 이루어진 격자판과 1부터 15까지의 숫자가 써 있는 타일을 이용한 퍼즐이다. 처음 상태에서는 아래와 같이 순서대로 타일이 놓여 있고, 마지막 한 칸은 비어 있다.

15퍼즐에서는 현재 빈칸의 위치와 인접한 타일 하나를 골라서 그 타일을 빈칸의 위치로 밀 수 있다. 그렇게 되면 원래 그 타일이 있던 자리에 빈칸이 새로 생기고, 타일을 계속 움직일 수 있게 된다.

퍼즐의 목표는 섞인 상태가 주어지면 이렇게 타일을 밀어서 원래 상태로 되돌리는 것이다. 이제 다음과 같이 14와 15의 위치만 바뀌어 있고 나머지 모든 타일은 제자리에 있는 15퍼즐이 주어질 때, 이 퍼즐을 해결할 수 있을까?

풀이

타일끼리 서로 위치를 바꾸고 있으므로, 순열을 이용하는 것이 매우 편리해 보인다. 다만 빈 칸이 있고 빈 칸도 계속해서 위치가 바뀌기 때문에, 그냥 빈칸을 16이 써 있는 타일처럼 취급해 버리자.

우선 15퍼즐의 각 칸에(즉 타일이 아니라 위치에) 1부터 16까지 차례대로 숫자를 매기자. 아래에 있는 그림에서 파란색 숫자가 각 위치에 부여된 숫자이다.

15퍼즐의 상태가 주어지면 다음과 같은 \(\sigma: [16] \to [16]\)을 생각하자.

\(\sigma(x) = x\text{번 자리에 있는 타일 번호}\)

이렇게 정의하면 \(\sigma\)가 순열이 되는 것은 쉽게 보일 수 있다. 예를 들어 다음과 같은 상태는 순열 \(\pmatrix{ 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 \\ 6 & 13 & 2 & 9 & 16 & 8 & 5 & 14 & 1 & 4 & 11 & 15 & 12 & 7 & 3 & 10}\)으로 나타낼 수 있다.

우리에게 주어진 초기 상태는 \((14 \ 15)\)로, 우리의 목표인 맞춰진 상태는 \(\mathrm{id}\)로 나타낼 수 있다.

우리가 \(x\)번 타일을 한 번 밀면, 그 타일과 16번 타일의 위치가 서로 바뀐다. 타일을 밀기 전에 \(x\)번 타일이 있던 자리 번호를 \(i\), 빈칸이 있던 자리 번호를 \(j\)라고 하자. 밀기 전 상태를 나타내는 순열이 \(\sigma\)였다면 민 후의 상태는 \(\sigma(i \ j)\)이다. 왜 그런지는 아래 그림의 예시를 통해 이해해 보자.

그런데 앞에서 순열을 합성하면 그 부호는 곱해진다는 것을 증명했다. 그리고 모든 전치의 부호는 \(-1\)이다. 따라서 어떤 순열에 전치를 한 번 합성할 때마다 그 순열의 부호는 바뀐다. 다시 말하면 타일을 한 번 밀 때마다 상태를 나타내는 순열의 홀짝성이 바뀐다.

처음 상태 \((14 \ 15)\)는 홀순열이고 목표 상태 \(\mathrm{id}\)는 짝순열이므로, 만약 퍼즐을 푸는 방법이 존재한다면 반드시 타일을 홀수 번 밀어야 한다.

이제 퍼즐을 다른 각도에서 살펴보자. 퍼즐에 있는 각 칸을 아래와 같이 체스판처럼 검은색과 흰색으로 칠한다.

이제 빈칸, 즉 16번 타일의 위치에 주목하자. 16번 타일이 다른 타일들과 구별되는 특징은 이동이 일어날 때마다 반드시 움직일 수밖에 없다는 것이다. 즉 우리가 타일을 미는 총 횟수는 16번 타일이 이동하는 횟수와 같다.

체스판처럼 칠한 판에서 인접한 두 칸의 색은 항상 다르다. 따라서 16번 타일은 한 번 이동할 때 반드시 위치한 칸의 색을 바꾼다. 처음 상태와 목표 상태 모두 16번 타일은 16번 위치에 있으므로 16번 타일 위치의 색은 흰색에서 시작해서 검은색으로 바뀌었다가 다시 흰색으로 바뀌는 것을 반복해 최종적으로 흰색으로 끝난다. 이를 위해서는 반드시 짝수 번 움직일 수밖에 없다. 즉, 타일을 미는 총 횟수는 반드시 짝수 번이다.

이런! 방금 순열의 홀짝성을 이용해 타일을 미는 횟수가 홀수 번이어야 한다고 했는데, 이젠 짝수 번이어야 한다고 한다. 이는 모순이므로, 주어진 상태에서는 이 15퍼즐을 풀 수 없다.

루빅스 큐브

루빅스 큐브 역시 조각들이 서로 위치를 바꾸는 퍼즐이기 때문에 순열이 유용하게 사용된다. 순열의 홀짝성을 잘 이용하면 큐브 조각들의 위치를 결정하는 방법들 중 절반은 불가능하다는 사실을 빠르게 보일 수 있다. 자세한 내용은 이 글을 참고하자!

맺음말

7000단어 내내 정의 정리 정의 정리만 반복하는 지루한 글이었을 것이지만, 잘 읽었다면 순열의 홀짝성을 이해하기 위한 과정을 아주 충실히 차근차근 밟아온 것이다. 이 글이 어떻게든 도움이 되었으면 좋겠다!