12. 쪽지 시험 (13점)
정보 교과 수업을 듣는 7명의 학생이 있다. 이 중 4명은 수강생이고, 다른 3명은 청강생이다.
오늘 수업 시작 직전에 쪽지 시험을 치러서, 각 학생이 시험지 하나씩을 풀었다. 교수님은 이제 각 학생이 시험지를 하나씩 맡아서 채점을 하게 하고자 한다.
수강생은 자기 자신의 시험지를 채점할 수 없으나, 청강생은 자기 자신의 시험지를 채점해도 된다.
시험지를 분배하는 7! = 5 040가지의 방법 가운데, 이러한 조건을 만족하는 방법의 수는?
========== 풀이 ==========
7명이 있는데 모두 자신의 시험지를 선택하지 않는 방법의 개수를 구해야 합니다.
1명이 있다고 합시다 몇가지 방법이 존재할 까요 ?
1명일 때는 나를 제외한 다른 사람의 시험지가 없으므로 개수는 0 입니다. f(1) = 0
2명일 경우는 한가지 방법만이 존재 합니다. f(2) = 1
3명이 경우, A,B,C 라고 하면, A가 B,C를 선택하면 B가 A를 선택하는 경우와 C를 선택하는 경우가 있습니다. 즉 , [B,C,A], [C,A,B] 2가지가 존재합니다.
f(3) = 2
4명인 경우 A,B,C,D라고 하면 A는 A를 제외한 [B,C,D]를 선택할 수 있습니다.
A -> B를 선택하는 경우 B->A를 선택하면 C->D, D->C : f(2) , B->C를 선택하는 경우 C->D, D->A : f(2), B->D를 선택하는 경우 C->A, D->C : f(2)
A->C를 선택하는 경우 나머지가 A,B,D 즉 f(3)의 경우와 동일합니다.
A->D를 선택하는 경우도 나머지가 A,B,C가 남아 f(3)의 경우와 동일합니다. 이렇게 식을 일반화 하면 3명 부터는 f(n) = n-1 x ( f(n-1) + f(n-2) )로 일반화가 가능합니다.
f(1) = 0
f(2) = 1
f(3) = 2 x ( f(2) + f(1) ) = 2 x ( 1 + 0 ) = 2
f(4) = 3 x ( f(3) + f(2) ) = 3 x ( 2 + 1 ) = 9
f(5) = 4 x ( f(4) + f(3) ) = 4 x ( 9 + 2 ) = 44
f(6) = 5 x ( f(5) + f(4) ) = 5 x ( 44 + 9 ) = 265
f(7) = 6 x ( f(6) + f(5) ) = 6 x ( 265 + 44 ) = 1854
즉 모두 다른 사람의 시험지를 채점하는 경우는 1854가지의 경우가 생깁니다.
그런데 청강생인 경우 자신의 시험지도 채점이 가능합니다.
청강생 한명이 자신의 시험지를 채점하는 경우는 f(6) = 265가지의 경우가 생깁니다. 청강생이 3명이므로 265 * 3 = 795
청강생 2명이 자신의 시험지를 채점하는 경우는 f(5) = 44 이며 AB, BC, AC 즉 2명의 경우의 수가 3가지가 존재 하므로 44 * 3 = 132
청강생 3명이 자신의 시험지를 채점하는 경우 f(4) = 9
위 경우의 수를 모두 더하면 1854 + 795 + 132 + 9 = 2790
정답 2790