수형도를 활용하는 곱의 법칙 문제 풀이 (고1 수학 경우의 수, 모두 다르게 대응하는 디레인지먼트 문제)
수형도(樹形圖, Tree Diagram)는 문제에서 가능한 모든 경우의 수를 시각적으로 표현하기 위해 사용되는 도구로서 나무처럼 가지를 치며 확장되는 형태로 표현합니다.
안녕하세요? holymath입니다. 이 카테고리의 포스팅은 2015개정 고등학교 1학년 수학의 개념을 보다 쉽게 이해할 수 있도록 해설하는 글입니다.수학을 공부할 때는 공식과 문제 푸는 요령을 외워서 푸는 게 아니라 개념이 만들어진 근본적인 원리와 개념들 사이의 연관성을 생각하면서 공부해야 합니다. 이 포스팅을 통해 교과서나 참고서에 있는 수학 개념을 제대로 이해하는데 도움이 되기를 바랍니다.
이전에 경우의 수에서 많이 사용되는 곱의 법칙에 대해 알아본 적이 있었는데요. 이번 포스팅에서는 곱셈 법칙을 설명하는 도구인 수형도를 활용한 경우의 수 문제를 풀어보도록 하겠습니다.
● 모두 다르게 대응하는 경우의 수 문제
수형도는 곱의 법칙을 이해하기 위한 가시적 도구로 쓰이지만 단순히 수를 몇 번 곱한 것으로는 구할 수 없는 복잡한 경우의 수 문제도 많이 존재하죠. 다음의 문제는 수형도를 어떻게 활용해야 하는지를 보여줍니다.
4명의 학생과 각 학생의 이름이 적힌 4장의 카드가 있다. 학생들이 무작위로 카드를 하나씩 집었을 때 4명 모두 자신과 다른 이름의 카드를 집을 경우의 수를 구하시오. (단, 학생들의 이름은 모두 다르다.)
예제 1번에서 개체 하나를 늘린 문제입니다. 따라서 다음과 같이 빨간색 A에다 파란색 B를 먼저 배치했을 때의 경우의 수를 구한 다음 4를 곱하면 총경우의 수를 구할 수 있겠죠.
이제 빨간색 B에다가 파란색 알파벳을 배치하는 방법은 위의 그림처럼 4가지입니다. 그다음 빨간색 C, D, E에다 나머지 알파벳을 배치해야 하는데 여기서는 다음과 같이 두 가지로 경우로 나눌 수 있어요.
예를 들어 빨간색 A, B에 파란색 B, C를 배치했으면 나머지 C, D, E에 배치할 알파벳은 D, E, A죠. 즉, 이 중에서 두 알파벳 D, E는 빨간색 D, E와 일치하고 나머지 A는 다른 알파벳입니다. 그런데 그림에서 두 번째 경우처럼 빨간색 A, B에 파란색 B, A를 배치하면 C, D, E에 배치할 알파벳은 똑같은 C, D, E입니다. 즉, 이 경우만 경우의 수가 다르게 나타나고 빨간색 B에 C 또는 D 또는 E가 배치되는 경우는 모두 똑같은 경우의 수가 나올 거라는 걸 추측할 수 있어요.
이제 C, D, E에 D, E, A를 배치하는 방법은 다음과 같이 3가지입니다. 알파벳이 겹치지 않는 C에는 D, E, A 모두 배치될 수 있으며 각 경우마다 D, E에 나머지 알파벳을 배치할 방법은 한 가지뿐이에요.
한편, C, D, E에 같은 C, D, E를 배치하는 방법은 다음과 같이 2가지뿐입니다.
따라서 빨간색 A에 파란색 B를 배치했을 때 총경우의 수는 다음과 같습니다.
$3\times 3+2=11$
빨간색 A에 C, D, E가 배치되는 경우에도 경우의 수는 모두 같으므로 구하는 총경우의 수는
$11\times 4=$ $44$
참고로 위의 문제와 같이 원래의 것과 모두 다르게 대응하는 경우의 수를 구하는 문제를 '디레인지먼트(Derangement)'라고 하며 '완전 순열' 또는 '교란 순열'이라고도 합니다. 'Derangement'는 혼란스러운 배열이라는 의미를 가지고 있으며 이 단어의 앞 글자를 따서 해당 경우의 수를 $D(n)$ 또는 $D_n$으로 나타냅니다. 즉, 우리가 앞에서 푼 문제의 결과에 의하면 $D_4=9$이고 $D_5=44$이죠.
디레인지먼트의 경우의 수는 다음과 같은 공식으로 구할 수 있다는 것이 알려져 있습니다.
따라서 이 공식을 알고 있었다면 예제 1과 2의 답은 다음의 계산으로부터 구할 수도 있었어요.
이 공식은 전체 집합에서 특정 조건을 만족하는 부분집합들의 수를 계산할 때, 서로 중복되는 경우를 제거하면서 개수를 세는 방법인 포함 배제 원리(Inclusion-Exclusion Principle)를 이용합니다. 고등학교 1학년의 수준을 넘으므로 간단히만 얘기하면 괄호 안에서 $1$은 전체 경우의 수를 의미하며 $\frac{1}{k!}$은 $k$개의 원소가 제자리에 돌아오는 경우를 의미합니다. 이것을 원소의 개수에 따라 배제하고 포함하는 것을 반복하는 원리입니다.
● 기출문제 연습
수형도를 활용한 기출문제도 하나 풀어보겠습니다.
$1$부터 $9$까지의 자연수가 하나씩 적힌 $9$장의 카드가 있다. 갑은 숫자 $2$, $5$, $9$가 적힌 카드를, 을은 숫자 $1$, $7$, $8$이 적힌 카드를, 병은 숫자 $3$, $4$, $6$이 적힌 카드를 각각 가지고 있다. 갑, 을, 병 세 사람이 동시에 카드에서 한 장씩 꺼낼 때, 카드에 적힌 숫자가 가장 큰 사람이 갑이 되는 경우의 수는? [2014 고1 3월 학평 14번 (4점)]
갑은 숫자 $2$, $5$, $9$를 가지고 있으므로 각 수가 가장 큰 수가 되는 경우의 수를 구하는 문제입니다. 그런데 $2$는 가장 큰 수가 될 수는 없죠. 병이 가진 숫자가 $3$, $4$, $6$이라 전부 $2$보다 크니까요. 따라서 갑이 가진 숫자가 가장 큰 경우는 다음과 같이 $5$인 경우와 $9$인 경우로 나눠서 수형도를 그릴 수 있습니다.
따라서 답은 $11$입니다.
♥ 이해가 잘 되셨다면 좋아요와 선플은 포스팅 강의 제작에 큰 힘이 됩니다. ♥ 이해가 잘 안 되신 부분은 댓글을 통해 질문을 주세요. ♥본문의 내용은 추가, 보완될 수 있습니다.
댓글 영역