완전순열(Derangement)이란, 순열 중 원소가 같은자리에 다시 놓이지 않는 순열을 의미합니다.
예를 들어 n개의 자연수 중 k가 k번째 오지 않게 배열하는 경우의 수, 또는 시험지를 학생끼리 교환하여 채점하되 자신의 것을 채점하지 않는 경우의 수가 완전순열입니다.
n=4 일때 완전순열은 9로, 각 경우는 다음과 같습니다.
2143/2413/2341
3142/3412/3421
4123/4321/4312
또한 완전순열(!n)의 점화식은 다음과 같습니다.
이것만으로도 아주 재미있는 주제이고, 완전 원순열과같이 다른 변형문제를 떠올려볼 수도 있겠습니다. 그러나 완전순열은 고등학교 확률과 통계 수준으로도 쉽게 설명될 수 있으므로 자세한 설명은 생략하겠습니다.
이제 완전순열에 대해 이해했으니, 완전순열과 비슷하지만 살짝 다른 경우를 생각해 봅시다. 순열 중 원소가 이웃했던 원소와 다시 이웃하지 않는 순열은 어떻게 구할 수 있을까요? 이를 이 문제에선 간단히 완전 이웃 순열이라합시다.
일직선상에 나열된 n개의 의자에 n명의 학생들이 앉을 때, 모든 학생이 자신과 이웃한 번호의 학생과 이웃해 앉지 않을 경우의 수로 생각해도 좋습니다.
n=4 일때 완전 이웃 순열은 2로, 다음과 같습니다.
(초기상태는 1234로 가정합니다.)
3142/2413
좋아요
0
글쎄요
0
어려워요
0
-
완전순열의 점화식처럼 각 항을 순서대로 놓는 경우를 모두 곱할려고 했는데 완전이웃순열은 완전순열보다 더 복잡하네요...
-
점화식을 이용한 접근도 가능하지만 어떤 항을 순열의 가장자리에 놓느냐 가장자리에 놓지 않느냐에 따라 다음에 놓을 항이 들어갈 경우의 수가 변하기 때문에 점화식으로 할려면 시간이 좀 많이 걸릴 것 같아요.
-
/resources/comment/2018/06/af3c54605ca4c07c3aa014821ba7592e.jpg
풀이인데 어딘가 많이 엉성하네요
답이 최하단의 점화식 2개 인데 F(n)이랑 F'(n)을 구분해서 두개를 연립해야 할 것 같습니다
