교란순열(완전순열) 점화식과 일반항

오늘은 이전에 올렸었던

교란순열(완전순열)의 심화버전 포스팅입니다.

 

교육과정에 있는 내용은 아니지만,

단순히 수형도를 세는 것에서 벗어나고 싶은

학생들을 위한 내용이랄까요..?ㅎㅎ

 

이전 포스팅

아래에 링크거니 참고하실 분은 하세요.

 

https://ladyang86.tistory.com/71

[경우의 수] 시험 꿀팁 교란순열 (완전순열)

그럼 시작해볼까요?

 

오늘의 포스팅은

수학1의 점화식, 수학(하)의 집합 단원을

알아야 이해할 수 있습니다! 

 

교란순열이 무엇인지 기억나시죠?

간단하게 자기 자리에 자기가 앉지 않는

순열의 수라고 생각하시면 됩니다.

교란순열 점화식

사실 저번 포스팅에도 썼지만

4개까지는 자주 나오니 그냥 외우세요.

 

일반적으로 n개의 교란순열의 점화식을

구하는 방법부터 살펴볼게요.

 

먼저 A1의 경우, a1을 제외한 나머지 (n-1)개의 원소가 올 수 있습니다.

이 중 A1의 아래에 a2가 온 경우를

먼저 세어볼게요.

 

나머지 경우의 수는 어차피 같을 테니까요. 

 

Case1) A2의 아래에 a1이 온 경우

이 때는 A1과 A2가 서로 상대방의 것을 갖고 있네요. 서로 값을 교환했다고 보면 되겠죠?

 

이 경우는 나머지 A3부터 An까지 n-2개의 원소들이 완전순열(교란순열)을 이루면 됩니다.

 

즉, A2=a1인 경우에는 D(n-2)개가 나오겠네요.

 

Case2) A2의 아래에 a1이 오지 않는 경우

자 이제 A2부터 An에 원소를 나열해야 합니다. A2에는 a1이 올 수 없는 상태죠. 그런데 a2는 이미 A1에 배치되어 있기 때문에, 우리가 나열할 때는 고려하지 않습니다. 그런데 생각해보면 a1 역시 A1 아래에는 올 수 없는 상태죠. 즉 a1이 A2에는 올 수 없지만 나머지 모든 곳에는 갈 수 있습니다. 이건 사실상 a2의 역할을 a1이 대신 하고 있다고 보면 됩니다. 그러니 A2의 아래 a1이 오지 않는 경우는 결국 n-1개의 원소가 교란순열을 이루는 경우와 같습니다.

 

정리 해볼까요? A1=a2인 경우에는 Case1) + Case2) 의 두 경우를 고려해주면 됩니다. 그런데 나머지 경우도 똑같은 수가 나오죠.!! 따라서 정리하면 D(n) = (n-1){D(n-1)+D(n-2)}가 됩니다.

점화식 유도가 어려운 건 아니니,

경우의 수가 기억나지 않거나,

숫자가 커진다면 한 번 이용해봄직 하죠.ㅎㅎ

 

교란순열 일반항

일반항은 포함 배제의 원리를 사용합니다. 

포함 배제의 원리는 유한집합에서

합집합의 원소를 세는 방법입니다.

우리가 2개, 3개인 경우를 이미 배웠습니다.

 

복습해볼까요?

 

원소의 개수가 2개일 때

 

원소의 개수가 3개일 때

뭔가 규칙성이 보이는 것 같진 않나요?ㅎㅎ

 

만약 집합이 4개가 되면 어떨까요?

 

1개짜리 다 더하고,

두 개짜리 교집합 다 빼고,

세 개 교집합 한 거 다 더하고,

4개 교집합 한 거 빼면 됩니다.!

 

식으로 쓴 거 밑에 있으니

이따 확인해보셔요.ㅎㅎ

 

이건 n개로 늘어나는 경우에도 마찬가지입니다.

증명은 수학적 귀납법을 쓰면 되는데,

나중에 따로 실어볼게요. 

 

자, 그럼

교란순열 일반항 개수 세러 가봅시다!

 

쉬운 예시를 위해

위에서 언급한 4개짜리 집합을

살펴보겠습니다.

 

교란순열의 개수는

전체에서 합집합을 제외해서 구해줍니다.

 

전체 - (A1이 자기 위치에 있거나 A2가 자기 위치에 있거나 ...An이 자기 위치에 있는 경우)

 

우선 합집합의 경우의 수를 구한 다음, 전체 경우인 n!에서 빼줄거에요

 

휴.. 식이 좀 기네요.

이건.. 일반항을 유도해서 쓰기보단,

그냥 뭐.. 점화식을 추천합니다.ㅋㅋ

 

아무튼 오늘 배운 거,

정리해볼까요?

그럼 다음에도 유익한 포스팅 갖고 올게요!