경우의 수

교란순열(완전순열)

문제 예지반은 매주 저번 주에 배운 내용을 테스트하는 시험을 본다. 시험을 본 후 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개의 공을 ..

분할과 분배 Pt. 2

이전글 이전글에 이어서 이번 글에서는 나머지 2가지 경우에서 공을 상자에 나눠담는 경우를 생각해 볼 것이다. 이전글에서 이어지는 내용도 일부 있으니 파트 1을 먼저 읽고 오는 것을 추천한다. 이 글에서는 상자를 구분할 수 없는 경우에 대해 알아본다. 공을 구분할 수 없고 상자를 구분할 수 없는 경우 $n$개의 같은 공을 $k$개의 같은 상자에 빈상자를 허용하지 않으며 넣는다고 하자. $i$번째 상자에 들어가는 공의 개수를 $n_i$라고 하면 다음과 같은 식이 성립할 것이다. $n_1+n_2+\cdots+n_k=n$, 여기서 $(n_i \geq 1)$, $(i=1, 2, 3, \cdots, k)$ 즉, $n$을 $k$개의 자연수의 합으로 나타내는 경우의 수와 같으며 이를 $p(n,\:k)$라고 한다. 여기..

분할과 분배 Pt.1

다음글 분할과 분배는 기본적으로 전체를 여러개의 소부분으로 나누는 문제이다. 이를테면 $n$개의 과제를 $k$명이 나눠가지는 경우의 수이다. 분할과 분배는 종류에 따라 8가지로 나뉜다. 공을 상자에 나눠담을 때 1.공을 구분할 수 있는가 2.상자를 구분할 수 있는가 3.빈상자가 있어도 되나이다. 이 8개의 조건이 모여 총 8개의 부분경우를 만든다. 이 글에서는 이중 4가지만을 다루겠다. 공을 구분할 수 있고, 상자를 구분할 수 있는 경우 $n$개의 구분되는 공을 $k$개의 구분되는 상자에 넣는 경우를 본다. 만일 빈 상자를 허용하는 경우, $n$개의 공은 각각 $k$개의 상자로 들어갈 수 있으며, 이는 각각의 공이 $k$개의 선택지를 가지고 있음을 말한다. 즉, 곱의 법칙에서 $k^n$임을 알 수 있다...

경우의 수 - 경로의 수 Pt. 2

알림: 이 글은 경로의 개수 Pt. 1의 심화 내용입니다. 앞선 글을 이해하지 못한 상태로 이 글을 읽으시면 많이 어려우실 수 있습니다. 우리는 앞서 격자모양의 지도에서 최단거리를 구하는 방법을 탐구하였다. 이번에서도 특별한 경우에서 최단경로를 구해보자. 들어가기 먼저 이번 글에서 내내 다루게 될 한 개의 문제를 소개하겠다. 문제: 왼쪽과 같은 지도가 있다. A에서 B까지의 최단경로 중 푸른색 선분 위의 점을 통과하지 않는 경로의 개수를 구하여라 A점을 제외한 붉은색 선분 위의 점을 통과하지 않는 경로의 개수를 구하여라. 이번 글에서는 위의 문제만 다룰 것이다. 문제의 조건과 상황을 잘 이해하자. 예를 들면 1번의 경우 Fig1-1a와 같은 경로는 되는 경로이며 Fig1-1b와 같은 경로는 되지 않는 경..

경우의 수 - 경로의 수 Pt. 1

차례 1. 경로의 수 문제 2. 최단경로의 개수(111 방법) 3. 최단경로의 개수(동자 순열의 활용) 4. 최단경로의 개수(조합의 활용) 5. 최단경로가 아닌 경로의 개수 6. 경로의 수의 활용 앞으로 여러 문제가 나올 것입니다. 그 문제마다 해설을 바로 보기보단 직접 생각해 보시기 바랍니다 :) 경로의 수 문제 수학 교과에서 다음과 같은 문제를 본 적이 있을 것이다. 문제: A에서 B까지 지도의 격자점만을 지나 이동하는 최단경로의 개수를 구하시오. 앞으로 경로의 수에서는 기본적으로 이렇게 생긴 문제를 가지고 조금씩 변형해가며 문제를 풀 것이다. 우선은 이렇게 생긴 문제의 해법에 대해 알아보자. 최단경로의 개수: 111 방법 이 방법은 가장 쉽고 간단한 방법이다. 일반적으로 생각했을 때, 최단경로로 이..

경우의 수 - 순열과 조합

순열(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)$로도 쓰며 모두 같은 의미이다. 조합이란 순열은..