수형도와 교란순열

• 수형도

경우의 수는 어떻게 풀어야 할지 모르겠을 때 노가다라도 하면 답을 구할 수 있는 게 매력이라고 생각한다.

하지만 노가다도 효율적으로 해야 한다. 효율적인 노가다를 위한 방법이 수형도이다. 예제를 통해 수형도가 뭔지 알아보도록 하자.

 

• 예제) 4명의 사람이 모자를 쓰고 있었는데 어쩌다보니 모자가 다 섞여버렸다. 모자를 아무거나 골라서 썼을 때 4명 모두가 자신의 모자가 아닌 다른 사람의 모자를 썼을 경우의 수를 구하여라

풀이) 사람을 각각 1, 2, 3, 4라고 하고 수형도를 그려보면

다음과 같이 나온다. 따라서 경우의 수는 9가지 이다.

수형도를 이용하면 모든 경우의 수를 빠짐없이 셀 수 있다.

 

• 교란순열

교란순열이란 위의 예제처럼 각 원소의 위치가 바뀌었을 때 모든 원소가 원래 위치가 아닌 다른 위치에 위치하는 순열이다.

위의 예제는 원소의 개수가 4개였지만 원소의 개수가 더 많아지면 수형도로는 경우의 수를 구하기가 힘들다.

원소의 개수가 n개인 교란순열의 점화식을 구해보자.(원소가 n개일 때 교란순열의 값을 Dn이라 하자)

 

n명의 사람을 1~n이라고 하자.

만약 1번의 모자를 2번이 썼다고 가정하자. 그러면 경우를 2가지로 나누어 볼 수 있다.

1) 1번이 2번 모자를 썼을 경우

이 경우의 수는 나머지 n-2명끼리 모자를 바꿔 쓰는 경우의 수와 같으므로

와 같다.

 

2) 1번이 2번 모자가 아닌 다른 사람의 모자를 썼을 경우

이 경우의 수는 1번과 나머지 n-2명이 서로 모자를 바꿔 쓰는 경우의 수와 같으므로

와 같다.

*이 경우에서는 1번이 2번 모자도 쓰면 안 되기 때문에 2번 모자를 1번모자라고 생각하면 좀 더 이해하기 쉽다.

 

=>1번이 2번모자를 썼을 경우의 수는

임을 알 수 있다.

 

1번이 3~n번의 모자를 쓰는 경우의 수도

와 같다.

 

따라서

임을 알 수 있다.