교란 순열Permalink

교란 순열derangement 혹은 완전순열complete permutation은

$N$명의 사람들이 모자를 벗었다가 다시 쓰는데 자신이 썼던 모자가 아닌 다른 모자를 쓰는 경우의 수이다.

이 개념은 이런 재밌는 영상으로도 배워볼 수 있다.

이 글에서는 $D_n$이란 기호를 쓰도록 하자.

점화식Permalink

따라서 $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$

연습문제Permalink

BOJ 10978 - 기숙사 재배정

BOJ 1947 - 선물 전달