수학

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

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

수학적 증명방법

어떠한 수학적 이론을 증명하는 데는 여러 방법이 있을 수 있다. 기존에 증명된 다른 사실을 연역하여 증명할 수도 있으며(직접 증명법), 대우를 이용하여 증명할 수 도 있다. 이 글에서는 수학적 사실을 증명하는 테크닉들을 소개하고자 한다. 잘 기억해두고 유용히 쓸 수 있도록 하자. 귀류법 수학 교과에서도 소개되는 방법이다. 원명제를 부정하여 새로운 명제를 세우고(Ex. "불은 뜨겁다"→"불을 뜨겁지 않다") 그 명제를 대전제로 하여 논리를 펼쳤을 때 논리에 모순이 생김을 보여 원명제가 사실임을 보이는 것이다. 다음은 귀류법을 이용하여 소수가 무한함을 보이는 과정이다. 증명하고자 하는 명제: 소수는 무한하다. 부정한 명제: 소수는 유한하다. 대전제에 따라 소수는 유한하므로 소수들로 이루어진 수열 $P$에서 ..

경우의 수 - 순열과 조합

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