순열

교란순열(완전순열)

문제 예지반은 매주 저번 주에 배운 내용을 테스트하는 시험을 본다. 시험을 본 후 10명의 학생들은 각자 시험지를 채점하는데, 채점자는 누구여도 좋으나 스스로의 시험지는 채점할 수 없다. 이때 시험지를 채점자에게 나누어주는 경우의 수는 몇 가지일까? 문제 이해 $n$명의 사람들에게 작성된 $n$개의 편지를 무작위로 나누어줬을 때 누구도 자신에게 작성된 편지를 받지 못하는 경우의 수를 교란 순열(또는 완전 순열)이라고 해요. 가령 $n=3$인 경우 다음과 같이 2가지 경우가 있어요. 편지 A B C 받은 사람 b c a 편지 A B C 받은 사람 c a b 이런 개념 자체는 중학교 2학년에도 나오지만 이때는 $n$이 커봐야 3에서 4 정도로 직접 그 경우의 수를 세도 무리가 없을 정도로 계산량이 크지 않아..

중복조합

중복조합이란 중복을 허용해서 조합하는 것이다. 일반적인 조합(${}_n\mathrm{C}_r$)은 중복을 허용하지 않는다. 가령 A, B, C 중 2개를 고를 때 AB나 BC만 가능하여 AA를 고를 수는 없다. 하지만 중복조합은 이미 고른 것을 또 고르는 것이 가능하다. A, B, C를 중복조합으로 조합하면 다음과 같이 여섯 가지 경우가 있다. AA, AB, AC, BB, BC, CC 중복조합은 다음과 같이 표기한다. $n$개중 $r$개를 중복을 허용하여 뽑는 경우의 수는 ${}_n\mathrm{H}_r$이다. 중복조합은 조합으로 바꾸어 계산하며 바꾸는 방법은 다음과 같다. ${}_n\mathrm{H}_r={}_{n+r-1}\mathrm{C}_r$ 이것이 성립하는 이유는 다음과 같다. 가령 4개의 공을 ..

경우의 수 - 순열과 조합

순열(Permutation)과 조합(Combination)은 경우의 수를 계산하는데 쓰이는 가장 일반적인 방법이다. 순열이란 순열은 쉽게 말해 $n$명중에서 $r$명을 임의로 뽑아 일렬로 나열할 수 있는 경우의 수이다. 예를 들어 5명 중에서 3명을 임의로 뽑아 나열하는 경우가 순열이다. 순열은 $P$를 이용하여 표현하며 $n$명중 $r$명을 뽑아 나열하는 순열은 다음과 같이 계산한다. ${}_n\mathrm P_r = \frac{n!}{(n-r)!}$ 예를 들면 구분되는 5명 중에서 임의의 3명을 뽑아 줄 세우는 경우의 수는 ${}_5\mathrm P_3=\frac {5!}{2!}=60$가지이다. 참고로, ${}_n\mathrm P_r$은 $P(n, r)$로도 쓰며 모두 같은 의미이다. 조합이란 순열은..