자연계열 2번

사다리 타기는 우리 주위에서 흔히 볼 수 있는 놀이 중 하나이며 순번을 정하거나 술래를 정할 때 자주 사용된다. 사다리 타기의 원칙은 사다리를 따라 위에서 아래로 움직일 때 가로줄을 만나면 그 가로줄을 따라 바로 옆의 세로줄로 이동하는 것이다. 사다리를 구성하는 가로줄들은 인접한 세로줄들만을 연결하며 서로 만나지 않아야 한다. 사다리의 모양이 복잡해지면 혹시 한 항목이 여러 개와 연결되거나 아무 것과도 연결되지 않은 경우가 생길지 모른다는 생각이 들기도 한다. 그러나 어떤 모양으로 사다리를 그려도 각기 위와 아래 항목이 하나씩만 짝지워진다는 사실에는 변함이 없다.

2 이상의 자연수 $\displaystyle N$에 대하여 집합 $\displaystyle \{1,2,\cdots,N\}$을 $\displaystyle A_N$으로 표기하기로 하자. 집합 $\displaystyle A_N$에서 $\displaystyle A_N$으로의 일대일 대응을 $\displaystyle N$-치환(置換, permutation) 또는 간단히 치환이라고 한다. 항등 함수는 치환의 한 예이다. $\displaystyle N$-치환 $\displaystyle \sigma$를 아래와 같이 나타내기도 한다.

$\displaystyle \begin{pmatrix}1&2&3&\cdots&N\\\sigma(1)&\sigma(2)&\sigma(3)&\cdots&\sigma(N)\end{pmatrix}$

[그림 6]은 5-치환의 예로서 $\displaystyle \begin{pmatrix}1&2&3&4&5\\2&4&3&5&1\end{pmatrix}$로 나타낼 수 있다.

치환과 사다리는 서로 관련되어 있다. 세로줄의 시작번호와 끝 번호가 차례로 $\displaystyle 1,2,\cdots,N$인 사다리를 $\displaystyle N$-사다리라 하자. $\displaystyle N$-치환은 $\displaystyle N$-사다리를 표현하는 좋은 도구이다. [그림 7]의 3-사다리는 3-치환 $\displaystyle \begin{pmatrix}1&2&3\\3&2&1\end{pmatrix}$과 동등하다.

두 $\displaystyle N$-치환 $\displaystyle \sigma_1,\sigma_2$의 합성 $\displaystyle \sigma_2\circ\sigma_1$를 $\displaystyle N$-치환의 곱이라고 부르고 $\displaystyle \sigma_2\sigma_1$로 쓰기로 한다. 두 $\displaystyle N$-치환의 곱도 여전히 $\displaystyle N$-치환이다. 임의의 $\displaystyle N$-치환 $\displaystyle \sigma$의 역함수 $\displaystyle \sigma^{-1}$도 $\displaystyle N$-치환이며 이를 $\displaystyle \sigma$의 역치환이라고 한다. 예를 들어 [그림 6]이 표현하는 치환의 역치환은 $\displaystyle \begin{pmatrix}1&2&3&4&5\\5&1&3&2&4\end{pmatrix}$이고 [그림 7]의 3-사다리에 대응하는 3-치환의 역치환은 자기 자신이다.

집합 $\displaystyle A_N$에 속하는 서로 다른 $\displaystyle n$ 개의 자연수 $\displaystyle i_1,i_2,\cdots,i_n$이 존재하여 $\displaystyle \sigma(i_1)=i_2,\sigma(i_2)=i_3,\cdots,\sigma(i_{n-1})=i_n,\sigma(i_n)=i_1$을 만족하고 나머지 원소들은 자신에게 대응시키는 치환 $\displaystyle \sigma$를 사이클이라고 하고 $\displaystyle \sigma=(i_1\;i_2\;\cdots\;i_n)$으로 표기하며 $\displaystyle n$을 $\displaystyle \sigma$의 길이(length)라고 한다. [그림 6]이 표현하는 치환은 길이가 4인 사이클 $\displaystyle (1\;2\;4\;5)$이다.

치환 중에서 두 원소만 서로 바꾸어 대응시키고 나머지는 자신에게 대응시키는 것을 호환(互換, transposition)이라고 한다. 즉, $\displaystyle 1\le i<j\le N$인 자연수 $\displaystyle i,j$에 대하여

$\displaystyle \sigma(k)=\begin{cases}j&(k=i)\\i&(k=j)\\k&(k\ne i,k\ne j)\end{cases}$

로 주어지는 치환을 호환이라고 부르고 $\displaystyle (i\;j)$ 또는 $\displaystyle (j\;i)$로 나타내기로 한다. 호환은 길이가 2 인 사이클이다. 연속된 두 자연수로 구성된 호환을 인접 호환이라고 한다. 예를 들어, $\displaystyle (2\;4)$는 호환이며 인접 호환은 아니다. 한편, $\displaystyle (4\;5)$는 인접 호환이다. $\displaystyle N$-사다리의 가로줄은 인접 호환에 해당한다.

일반적으로 치환에 대하여 아래 정리가 성립한다.

정리. 모든 치환은 호환들의 곱으로 나타낼 수 있다.

[그림 8]은 치환의 곱 $\displaystyle (1\;4\;5)(1\;2)$를 나타낸다. 합성함수의 정의로부터 이 치환은 [그림 6]이 표현하는 치환과 동일함을 알 수 있다. 즉, $\displaystyle (1\;2\;4\;5)=(1\;4\;5)(1\;2)$가 성립한다. 이와 비슷한 방법으로 $\displaystyle (1\;4\;5)=(1\;5)(1\;4)$를 얻을 수 있다. 결과적으로 $\displaystyle (1\;2\;4\;5)=(1\;5)(1\;4)(1\;2)$가 성립한다.

서로 다른 세 자연수 $\displaystyle i,j,k$에 대하여 다음 관계식이 성립한다.

㉠ $\displaystyle (i\;j)(j\;k)(i\;j)=(i\;k)$