교란순열

교란순열의 개수를 구해보자 

교란순열이란  원래 위치에 있는 원소가 하나도 없는 순열이다. 

사람들이 각각 자신의 모자를 벗었다가 아무 모자나 다시 쓰는데 모든 사람이 자기 것이 아닌 모자를 쓰는 순열이라고 할 수 있다.

 

길이가 n 인 순열에서 교란순열의 개수를 어떻게 알 수 있을까?

교란 순열의 개수를 구하는 공식은

$$n! \sum_{k=0}^n \frac{(-1)^k}{k!}$$

 

이를 유도해 보자

 

가장 쉽게 생각해서 모든 순열개수 n!에서 교란순열이 아닌 수열의 개수를 빼주면 된다.

한 개 이상의 수가 원래 자리에 있는 순열의 개수를 구해보면 4C1*3!이다 

하지만 이렇게 구한 수를 이용해서 4!- 4C1*3!을 하게 된다면 2개 이상의 수가 원래 자리에 있는 순열은 중복해서 빠지게 된다. 그렇기 때문에 중복해서 빼진 것을 다시 더하고 다시 중복해서 더해진 것을 빼주는 과정을 거치면 될 것 같은데 그렇게 하기 위해서 우리는 정확히 얼만큼 중복되어 있는지를 알아야 한다.

 

1,2,3,4 가 있을 때 1개 이상이 원래 자리에 있는 순열을 보면

1           2          3           4

1 2 3 4   2 1 3 4   3 1 2 4   4 1 2 3 

1 2 4 3   2 1 4 3   3 1 4 2   4 1 3 2

1 3 2 4   2 3 1 4   3 2 1 4   4 2 1 3

1 3 4 2   2 3 4 1   3 2 4 1   4 2 3 1

1 4 2 3   2 4 1 3   3 4 1 2   4 3 1 2

1 4 3 2   2 4 3 1   3 4 2 1   4 3 2 1

이다.

이때 1,2 2개가 원래 자리에 있는 순열은 1일때 1번 2일때 1번 총 두번 나오는 것을 알 수 있다. 

또한 1, 2, 3 3개가 원래 자리에 있는 순열은 1일 때 2일 때 3일 때 총 세번 나오는 것을 알 수 있다.

 

1 2         1 3         1 4          2 3        2 4        3 4

1 2 3 4   1 2 3 4   1 2 3 4   1 2 3 4   1 2 3 4   1 2 3 4

1 2 4 3   1 4 3 2   1 3 2 4   4 2 3 1   3 2 1 4   2 1 3 4

 

이때 1, 2, 3 3개가 원래 자리에 있는 순열은 1 2일 때 2 3일 때 1 3일 때 총 세 번 나오는 것을 알 수 있다.

n개 이상 겹치는 순열에서 m개 겹치는 순열은 mCn번 중복됨을 알 수 있다.

이를 표로 그려 보면

n	1	2	3	4
$${}_1 \mathrm{ C }_n$$	$${}_1 \mathrm{ C }_1(=1)$$
$${}_2 \mathrm{ C }_n$$	$${}_2 \mathrm{ C }_1(=2)$$	$${}_2 \mathrm{ C }_2(=1)$$
$${}_3 \mathrm{ C }_n$$	$${}_3 \mathrm{ C }_1(=3)$$	$${}_2 \mathrm{ C }_3(=3)$$	$${}_3 \mathrm{ C }_3(=1)$$
$${}_4 \mathrm{ C }_n$$	$${}_4 \mathrm{ C }_1(=4)$$	$${}_4 \mathrm{ C }_2(=6)$$	$${}_4 \mathrm{ C }_3(=4)$$	$${}_4 \mathrm{ C }_4(=1)$$

이다. 

여기서 다시 우리의 목표를 살펴보자면 총 개수 4! 에서 1개, 2개, 3개, 4개가 원래 자리에 있는 순열개수를 뺀 값을 구하는 것이다. 즉 1번씩만 빼야 한다.

 

여기서 잠깐 아래 식을 보자

$$\sum_{b=0}^a {{}_a \mathrm{ C }_b} x^b = (x+1)^b$$

여기에서 양변에 -1을 대입하고 b = 1 부터 시작하게 하면

$$\sum_{b=1}^a {{}_a \mathrm{ C }_b} (-1)^b = 0^b - {{}_a \mathrm{ C }_0} (-1)^0 = -1$$

임을 알 수 있다.

 

즉 길이 n인 교란수열의 개수는

$$ (전체 수열개수) - (1개 이상이 원래 자리에 있는 순열 개수) + (2개 이상이 원래 자리에 있는 순열 개수) - ...... (-1)^n(n개 이상이 원래 자리에 있는 순열 개수) $$

으로 표현할 수 있다.

따라서 이는

$$ n! - (n-1)!*{{}_n \mathrm{ C }_1} + (n-2)!*{{}_n \mathrm{ C }_2} - (n-3)!*{{}_n \mathrm{ C }_3} + ... (-1)^n*(n-n)!*{{}_n \mathrm{ C }_n}$$

$$= n! - \frac{n!}{1!} +  \frac{n!}{2!} -  \frac{n!}{3!} + ... (-1)^n*\frac{n!}{n!}$$

$$= n!(1-\frac{1}{1!} + \frac{1}{2!} - \frac{1}{2!} + ... (-1)^n*\frac{1}{n!}$$
$$= n! \sum_{k=0}^n \frac{(-1)^k}{k!}$$이다.