PS를 위한 수학 - 교란 순열(완전순열)
교란 순열
교란 순열derangement 혹은 완전순열complete permutation은
$N$명의 사람들이 모자를 벗었다가 다시 쓰는데 자신이 썼던 모자가 아닌 다른 모자를 쓰는 경우의 수이다.
이 개념은 이런 재밌는 영상으로도 배워볼 수 있다.
이 글에서는 $D_n$이란 기호를 쓰도록 하자.
점화식
따라서 $O(N)$에 구할 수 있다.
왜 위와 같은 점화식이 성립하는지 생각해보자.
n = 1
자신이 벗은 모자를 자신이 다시 쓸 수 없으므로 경우의 수는 $0$개이다.
$n=2$
두 명이 벗은 모자를 서로 바꿔서 쓰는 경우의 수밖에 없으므로 $1$개이다.
$\text{otherwise}$
$n$명중에 $i~~(1 \le i \le n)$번째 사람이 모자를 벗었다가 다시 쓴다고 하자.
그리고 다시 쓴 모자를 $j$번째 사람이 썼던 모자라고 하자. $(i \ne j)$
$j$번째 사람이 $i$의 모자를 다시 집는다면,
$i$와 $j$는 각각 모자를 바꿔서 썼으므로, 나머지 $n-2$ 명의 사람에 대해서 경우의 수를 따져야 하므로 $D_{n-2}$ 라는 수가 등장한다.
$j$번째 사람이 $i$의 모자를 집지 않는다고 하자.
그럼 $j$를 $i$로 바꿔주어도 무방하다.
어차피 $j$는 $i$를 집지 않기 때문이다.
따라서 $n$명에서 $i$번째 사람을 제외한 사람들끼리 교란순열을 구하는 것과 동일해지기 때문에 $D_{n-1}$란 수가 등장한다.
위 두 경우는 서로 독립적인 경우이므로 $D_{n-2}+D_{n-1}$란 수가 등장한다.
처음에 $i$는 아무 수나 기준으로 골라도 무방하고, $j$를 고르는 경우의 수는 $n-1$이다.
$(i,j)$ 쌍이 나오고 $i$는 총 $n-1$개의 $j$로 쌍을 만들고 위 로직을 시행할 수 있기 때문이다.
이 수를 곱해서 결국
$D_n=(n-1)(D_{n-1}+D_{n-2})$ 이다. $\square$
Comments