3.4 순열과 교란순열과의 관계

순열과 조합처럼, 순열과 교란순열 사이의 관계를 찾아보자.

 

우선 간단한 경우에 대해 생각해 본다.

서로 다른 5개의 대상에 대한 '순열의 수'는 $5!=120$이다.

 

이 순열의 수를 다음과 같이 각 사건으로 분할하여 셈할 수 있다.

 

(1) 고정점이 없는 경우 : 
5개의 대상에 대하여 교란순열 ; $D(5)=44$
   $C(5,0)\times D(5) = 1\times 44 =44$

 

(2) 고정점이 1인 경우 : 
4개의 대상에 대해서 교란순열 ; $D(4)=9$
   $C(5,1)\times D(4) = 5\times 9 = 45$

 

(3) 고정점이 2개인 경우 : 
3개의 대상에 대해서만 교란순열 ; $D(3)=2$
   $C(5,2)\times D(3) = 10\times 2 = 20$

 

(4) 고정점이 3개인 경우 : 
2개의 대상에 대해서만 교란순열 ; $D(2)=1$
   $C(5,3)\times D (2) = 10\times 1=10$

 

(5) 고정점이 4개인 경우 : 
1개의 대상에 대하여 교란순열  ; $D(1)=0$
   $C(5,4)\times D(1) = 5\times 0 = 0$

 

(6) 고정점이 5개인 경우 :
0개의 대상에 대하여 교란순열 ; $D(1)=1$(편의상)
   $C(5,5)\times D(0) = 1\times 1 = 1$ 

(1)~(6)의 각 사건은 동시에 일어날 수 없으므로 '합의 법칙'에 의하여 
   $1+0+10+20+45+44 = 120 = 5!$

계산력이 좋다면, 재미있는 사실 하나를 발견한다. 

   $1\times 5 + 0\times 4 + 10\times 3 + 20\times 4 + 45\times 5 = 120$

(★) 이것은 일반적으로 성립한다. 

이다. 

 

이것을 일반화하면

   $\begin{align} n! = C(n,0)\cdot D(n) &+ C(n,1)\cdot D(n-1) + C(n,2)\cdot D(n-2)+\cdots \\ &\cdots+ C(n,n-1)\cdot D(1) + C(n,n)\cdot D(0) \\&= \sum_{k=0}^{n} C(n,k)\cdot D(n-k) \end{align}$
임을 알 수 있다. 

 

또한, (★) 다음도 성립한다. 

   $\begin{align} n!=0\cdot C(n,0)\cdot D(n) &+ 1\cdot C(n,1)\cdot D(n-1) + 2\cdot C(n,2)\cdot D(n-2) +\cdots \\ &\cdots+ (n-1)\cdot C(n,n-1)\cdot D(1) + n\cdot C(n,n)\cdot D(0) \\&= \sum_{k=0}^{n} k\cdot C(n,k)\cdot D(n-k) \end{align}$

이것은 단순한 계산(?)에 의한 결과다. 다음 사실을 이용하였다.
   $k\times C(n,k) = n\times C(n-1,k-1)$ 

$\begin{align} n! = n\cdot (n-1)! &= n \sum_{k=0}^{n-1} C(n-1,k)\cdot D(n-1-k) \\ &=  \sum_{k=1}^{n} n\cdot C(n-1,k-1)\cdot D(n-k) \\ &=  \sum_{k=1}^{n} k\cdot C(n,k)\cdot D(n-k) \\&= \sum_{k=0}^{n} k\cdot C(n,k)\cdot D(n-k)\end{align}$

---

이러한 원리는 서울 소재 어느 고등학교의 내신 문제로 출제되기도 하였다.

 

[문제]

자연수 $n$에 대하여 집합 $X = \big\{1, 2, 3, \cdots, n\big\}$에서 집합 $X$로의 '일대일 대응' 중에서 $k$개의 원소가 자기 자신으로 대응되는 함수의 개수를  $G(n,k)$라 할 때, 다음 물음에 답하여라. 
   (1) $G(4,1)$의 값은? 
   (2) $G(4,0)+G(4,1)+\cdots+G(4,4)$의 값은? 
   (3) $G(n,0)+G(n,1)+\cdots+G(n,n)$의 값은? 
   (4) $0\cdot G(n,0)+1\cdot G(n,1)+2\cdot G(n,2)+\cdots+n\cdot G(n,n)$의 값은? 
정답 :  (1) $4$  (2) $8$  (3) $n!$  (4) $n!$