수학/경우의 수

교란순열(완전순열)

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

카탈란수의 활용

이전 글 이전 글에서 카탈란 수는 적당한 대응을 통해 많은 문제를 푸는 데 사용할 수 있다고 하였다. 그 문제들의 목록은 다음과 같다. 경로의 수 문제 다각형 나누기 문제 이진트리 문제 괄호 열고 닫기 문제 입출력 문제 한 요소가 다른 요소보다 항상 크게 유지하는 문제 이 글에서는 각 문제를 카탈란 수에 대응시키는 방법에 대해 알아보겠다. 1. 경로의 수 문제 이 문제는 이전 글에서 다루었으니 넘어가겠다. 설명 2. 한 요소가 다른 요소보다 항상 크게 유지하는 문제 같은 개수의 X와 Y를 활용해 만드는 단어 중 단어의 처음에서 X와 Y의 개수를 셌을 때 항상 X의 개수가 Y의 개수 이상인 단어의 개수를 구하여라. 이 문제는 경로의 수 문제로 대응하여 카탈란 수로 대응할 수 있다. 길이가 $2n$인 단어를..

카탈란 수의 점화식

다음 글 이 글의 마지막 부분에서 카탈란 수는 (0, 0)에서 (n, n)까지 $y=x$ 그래프보다 위에 있는 점을 통과하지 않고, 격자점만을 지나며 이동하는 경우의 수라고 하였다. 카탈란 수는 다음 일반항으로 정의되는 수열이다. $C_n=\frac{1}{n+1}{}_{2n}\mathrm{C}_n$ 이 일반항이 어떻게 유도되었는지는 이전 글을 찾아보기 바란다. 이번에는 이 수열의 성질을 응용하는데 초점을 맞출 것이다. 카탈란 수는 다음 점화식을 가지고 있다. $C_{n+1}$$=\displaystyle\sum_{i+j=n}C_i C_j$$=C_0C_n+C_1C_{n-1}$$+\cdots $$+C_{n-1}C_1+C_nC_0$ 이는 카탈란 수가 경로의 수 문제와 대응됨을 생각하면 어렵지 않게 설명할 수 있..

분할과 분배 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 방법 이 방법은 가장 쉽고 간단한 방법이다. 일반적으로 생각했을 때, 최단경로로 이..