이산수학

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