완전순열(교란순열)

어떤 배열의 원소 Xi의 위치가 i라고 할 때 모든 원소들이 자기의 위치에 존재하지 않을 때 이를 완전 순열이라고 한다.

X2

X1

X4

X3

점화식을 통해 원소의 개수에 따라 완전순열의 개수를 구할 수 있다.

공식은 다음과 같다

a(n) = (n-1) * (a(n-1) + a(n-2))

증명을 하면,

1 부터 N까지 오름 차순으로 이뤄진 배열이 있다고 하자 여기서 배열내의 원소중 1의 위치를 X로 옮기려고 한다. 이럴 경우 두가지 경우가 발생한다.

- X를 1의 위치로 옮기는 경우 -> N-2의 개수로 완전순열을 구하는 경우와 같다.

- X를 1의 위치로 옮기지 않는 경우 -> N-1의 개수로 완전순열을 구하는 경우와 같다.

1이 선택 할 수 있는 X 의 개수는 N-1개 이므로 이를 점화식으로 나타내면 위와 동일하게

a(N) = (N-1) * (a(N-1) + a(N-2)) 가 나온다.

위의 경우처럼 단순히 원소들이 자기의 위치에 존재하지 않는 경우만 생각하면 별 쓰임이 없을 것 같은데,

여러 원소들을 분산해서 써야하는 경우를 생각하면 쓸데가 있다.

(결론은 기억은 해두자)