순열과 조합: 놀라운 가능성의 계산
Permutations and Combinations: Counting the Amazing Possibilities
엘리스는 이상한 나라에서 이제는 자료를 처리하는 이산수학의 세계로 깊이 들어갔습니다. 하트 여왕의 궁전에서 파티를 준비해야 하는 미션이 주어졌고, 엘리스는 파티에 필요한 모든 경우의 수를 계산해야 했습니다.
엘리스는 먼저 여왕의 병사들을 정렬하는 방법에 대해 고민했습니다. 병사들이 파티의 줄을 서는 순서를 재배열하기 위한 모든 가능한 조합을 고려해야 했습니다. 병사들이 각각 다르게 줄을 서는 방식은 순열(permutation)을 사용해 카운팅할 수 있습니다. 순열은 원소들의 순서가 중요한 경우의 수를 계산할 때 사용되는 개념입니다.
또 다른 경우, 파티에 초대될 손님들 중에서 참석자를 기록하려면 조합(combination)을 사용해야 했습니다. 조합은 원소들의 순서가 중요하지 않은 경우의 수를 계산하는 것과 관련이 있습니다.
순열과 조합의 기본 개념
순열은 "서로 다른 n개의 원소 중 r개를 선택하여 순서대로 배열하는 경우"로 정의됩니다. 예를 들어, A, B, C라는 세 사람을 줄 세우는 방법은 다음과 같습니다.
ABC
ACB
BAC
BCA
CAB
CBA
따라서, 이 경우 총 6개의 순열이 가능합니다.
공식으로 나타내면: ( P(n,r) = \frac{n!}{(n-r)!} ) 이를 사용하여 순열의 수를 계산할 수 있습니다.
조합은 "서로 다른 n개의 원소 중 r개를 선택하여 순서에 상관없이 그룹을 만드는 경우"로 정의됩니다. 예를 들어, 네 명의 손님 중 2명을 선택하는 방법은 다음과 같습니다.
AB
AC
AD
BC
BD
CD
따라서, 이 경우 총 6개의 조합이 가능합니다.
공식으로 나타내면: ( C(n,r) = \frac{n!}{r! \times (n-r)!} ) 이를 사용하여 조합의 수를 계산할 수 있습니다.
엘리스의 모험
파티에서 엘리스는 하트 여왕의 명령에 따라 참석자들을 배치해야 했습니다. 그녀는 순열을 사용하여 병사들의 줄을 세우는 모든 경우를 계산했고, 조합을 활용하여 참석할 여왕의 친구들을 선택했습니다.
체스터 고양이는 엘리스에게 특별한 연습문제를 내주었습니다: "만약 A, B, C, D 네 명의 병사 중 어떤 두 명을 선택한다면, 몇 가지 가능성이 있을까요?" 엘리스는 조합 공식을 이용하여 답을 구했고, 결과적으로 6가지가 나왔다는 걸 알게 되었습니다.
