순열과 조합

비밀번호와 같이 쓰여진 순서에 따라 다른 것이 있는가하면 집합의 원소와 같이 순서가 달라도 같은 것이 있다.

이처럼 무엇인가를 배열하거나 선택하는 경우의 수를 쉽게 구하기 위해 순열과 조합을 정의한다.

먼저 순서가 있는 서로 다른 $n$개의 수를 일렬로 나열하는 방법을 순열이라고 하고 ${}_n P_{n}$으로 적는다. 직관적으로 ${}_n P_{n}=n\times(n-1)\times(n-2)\times\cdots\times 3\times2\times1$임을 알 수 있는데 이를 편하게 적기 위해 계승 함수(factorial function)를 아래와 같이 정의한다.

$$n!=\cases{1\quad \quad\quad   \quad \quad   \quad      (n=0)\\n\times(n-1)! \;\quad   (n=1,2,3,\cdots )}$$

$1,2,3,4,5$로 만들 수 있는 다섯 자리 자연수 중에서 맨 앞에 $1$이 오는 경우를 모두 적어보자.

$$\begin{split} 12 345\quad   13 245 \quad   14 235\quad   15 234\\12 354\quad   13 254\quad   14 253 \quad   15 243\\12 435\quad   13 425\quad   14 325\quad   15 324\\12 453\quad   13 452\quad   14 352\quad   15 342\\12 534 \quad   13 524\quad   14 523 \quad   15 423\\12 543\quad   13 542\quad   14 532 \quad   15 432\end{split}$$

위에 적은 $24=4!$가지와 같은 양식이 되풀이 되므로 $5\times24$가지의 자연수가 있다. 위에 적은 것 중에서 맨 앞의 두가지가 다른 경우를 생각하면 $4$가지 종류가 있으므로 $5\times 4$가지가 $5$개중에서 $2$개를 뽑아 일렬로 나열하는 순열의 $ {}_{5} P_{2}$이다.

순열의 수를 구할 때 맨 앞에 올수 있는 수 $5$에 다음에 올 수 있는 수 $4$를 곱하여 구해도 되지만 일단 $5$개를 일렬로 세운 후 뒤에서 세 수는 모두 같은 것으로 보아 $3$개를 일렬로 세운 것을 $1$가지로 세는 방법 $\displaystyle{\frac{5!}{3!}}$을 써도 된다.

$${}_{5} P_{2} = 5 \times 4= \frac{5!}{3!}$$

이와 같이 순서가 있는 것(순열)을 먼저 생각하고 순서를 없애는 것(조합)을 생각하면 편할 때가 많다. 

순열(permutation)

순열(permutation)을 조금 더 생각해보자. http://en.wikipedia.org/wiki/Permutation

$X=\{1,2,3, \cdots,n\}$일 때, 함수 $f:X\rightarrow X$ 가운데 일대일 대응인 것으로 이루어진 집합을 $S$라고 하자.

$\sigma \in S$인 함수를 아래와 같이 표현할 수 있다.

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

한 줄로는 $\bigg(\sigma(1)\quad \sigma(2) \quad \sigma(3) \quad \cdots \quad \sigma(n)\bigg)$로 적을 수 있다.

예를 들어 $n=5$일 때

$$\sigma=\pmatrix{&1&2 &3 &4 &5&\\& 2&3 &4 &5&1& }=(2\;\;3\;\;4\;\;5\;\;1)$$

$n(X)=n$일 때, $n(S)=n!$임은 명백하다.

$\sigma^n =e$이면 $n$을 $\sigma$의 위수라고 한다.

순환하는 순서를 밝혀서 적는 다른 표현도 있다. 예를 들어

$$\sigma=\pmatrix{&1&2 &3 &4 &5&\\& 2&3 &1 &5&4& }=(1\;\;2\;\;3)(4\;\;5)=(2\;\;3\;\;1)(4\;\;5)=(4\;\;5)(1\;\;2\;\;3)$$

함수의 합성($\circ$)에 대하여 $S$는 군(group)을 이룬다.

$$\sigma=\pmatrix{&1&2 &3 &4 &5&\\& 2&3 &1 &5&4& }=(1\;\;2\;\;3)(4\;\;5),\;\;\tau=\pmatrix{&1&2 &3 &4 &5&\\& 2&3 &5&4&1& }= (1\;\;2\;\;3\;\;5) $$

$$\sigma \circ \tau =\pmatrix{&1&2 &3 &4 &5&\\& 2&3 &1 &5&4& }\circ \pmatrix{&1&2 &3 &4 &5&\\& 2&3 &5&4&1& }$$

$$=\pmatrix{&2&3 &5&4 &1&\\& 3&1 &4 &5&2& } \circ \pmatrix{&1&2 &3 &4 &5&\\& 2&3 &5&4&1& }=\pmatrix{&1&2 &3 &4 &5&\\& 3&1 &4 &5&2&}$$

이므로 아래와 같이 연산할 수 있다.

$$\sigma \circ \tau =(1\;\;2\;\;3)(4\;\;5)\circ (1\;\;2\;\;3\;\;5) =(1\;\;3\;\;4\;\;5\;\;2)$$

항등함수를 $e=(1)$라고 하면 $\forall \sigma \in S$에 대하여 $\sigma \circ e=e\circ \sigma =\sigma$이다.

한편, $\sigma$의 역함수를 $\sigma^{-1}$이라고 하면 $\sigma\circ \sigma^{-1}=\sigma^{-1}\circ \sigma=e$이다.

예를 들면

$$\sigma^{-1}=\pmatrix{&1&2 &3 &4 &5&\\& 2&3 &1 &5&4& }^{-1}=\pmatrix{& 2&3 &1 &5&4&\\&1&2 &3 &4 &5& }=\pmatrix{&1&2 &3 &4 &5&\\&3&1&2&5&4&}$$

$$\sigma^{-1}=\{(1\;\;2\;\;3)(4\;\;5)\}^{-1}=(1\;\;3\;\;2)(4\;\;5) $$

$n=3$일 때, 다시 말해 $X=\{1,2,3\} $으로 놓고 생각해 보자.

$S=\{(1),\;(1\;\;2\;\;3),\;(1\;\;3\;\;2),\;(1\;\;2),\;(1\;\;3),\;(2\;\;3)\}$이다.

이제 연산표를 만들어 보자.

 

$\circ$	$(1)$	$(1\;2\;3)$	$(1\;3\;2)$	$(1\;2)$	$(1\;3)$	$(2\;3)$
$(1)$	$(1)$	$(1\;2\;3)$	$(1\;3\;2)$	$(1\;2)$	$(1\;3)$	$(2\;3)$
$(1\;2\;3)$	$(1\;2\;3)$	$(1\;3\;2)$	$(1)$	$(1\;3)$	$(2\;3)$	$(1\;2)$
$(1\;3\;2)$	$(1\;3\;2)$	$(1)$	$(1\;2\;3)$	$(2\;3)$	$(1\;2)$	$(1\;3)$
$(1\;2)$	$(1\;2)$	$(2\;3)$	$(1\;3)$	$(1)$	$(1\;3\;2)$	$(1\;2\;3)$
$(1\;3)$	$(1\;3)$	$(1\;2)$	$(2\;3)$	$(1\;2\;3)$	$(1)$	$(1\;3\;2)$
$(2\;3)$	$(2\;3)$	$(1\;3)$	$(1\;2)$	$(1\;3\;2)$	$(1\;2\;3)$	$(1)$

이제 $\sigma=(1\;2\;3),\;\;\tau=(1\;2)$라고 하자.

$\sigma^2 =(1\;3\;2),\;\;\sigma^3 =(1),\;\;\tau^2=(1),\;\;\sigma\circ\tau=\tau\circ\sigma^2 =(1\;3),\;\;\sigma^2\circ\tau=\tau\circ\sigma=(2\;3)$이다.

$e=(1)$는 항등원이고 $\sigma^3 =e,\;\tau^2 =e$의 위수는 각각 $3,2$이다.

다시 적으면

$$S=\{e,\;\sigma,\;\sigma^2,\;\tau,\;\sigma\circ\tau,\;\tau\circ\sigma \}$$

원순열(circular permutation)

 

위 그림은 구조를 그림으로 나타낸 것이다. 붉은 화살표는 하나씩 뒤로 미는 순열($\sigma$)이고 파란 화살표는 자리를 바꾸는 순열($\tau$)을 합성하는 것이다. 아래는 $n=4$일 때 그림이다. $(1\;2\;3\;4)$와 $(1\;2\;3)$을 합성한 것으로 나타낼 수 있다.

 

동그랗게 배열한다면 붉은 화살표로 이어진 것들은 서로 같은 것이 된다. 다시 말해 회전해서 일치하는 것은 같은 것이다. 위에서 $(1),(1\;2\;3),(1\;3\;2)$는 동그랗게 배열하면 같은 것이 된다. $e=\sigma=\sigma^2$이 같으므로 $\tau=\sigma\circ\tau=\tau\circ\sigma $이다.

일반화하면 서로 다른 $n$를 둥글게 배열하는 순열은 $$\displaystyle{\frac{n!}{n}=(n-1)!}$$가지다.

더 자세히 공부하려면 http://suhak.tistory.com/2

같은 것이 들어 있는 순열(permutation)

아래 그림과 같이 순열에서 달랐던 것이 같은 것이 된다면 비율을 찾아 구하면 된다. 번호가 아닌 색으로 구별하면 어떻게 달라지는가 확인해 보자.