[이산수학] 순열, 이산적 확률, 재귀적 관계

순열, 이산적 확률, 재귀적 관계에 연관된 전반적인 논제들을 고찰하고 그에 따른 문제 해결 방법을 습득할 수 있음

경우의 수

어떤 사건이 일어나는 경우의 수를 구하기 위해 모든 경우를 일정한 기준에 따라 빠짐없이, 중복되지 않게 해야함

경우의 수를 구하는 방법에는 구하는 방법에는 트리를 이용한 방법과 표를 구하는 방법이 있음

#1 합의 법칙

두 사건 A, B가 일어날 경우의 수를 n(A) = m, n(B)=n이라 하면 , A 또는 B가 일어날 경우의 수는 m+n

#2 곱의 법칙

두 사건 A, B가 일어날 경우의 수를 n(A) = m, n(B)=n이라 하면, A,B가 동시에 일어날 경우의 수는 m*n

순열

서로 다른 원소들을 순서를 고려하여 일렬로 배열하는 것

1부터 n까지의 모든 자연수의 곱을 n의 계승 또는 n factorial이라고함

nPr = n(n-1)(n-2)….*(n-r+1) (0≤r≤n)*

#1 순열에 대한 공식

nPr = n! / (n-r)!

nPn = n!

nP0 = 1, 0! = 1

#2 중복 순열

서로 다른 n개의 원소중 r개를 중복을 허용하며, 선택하여 순서대로 나열한 것

nπr = n^r

같은 원소를 나열하는 순열의 개수

n! / (p! * q! * r! … s!) , p+q+r+…+s=n

조합

서로 다른 n개의 원소 중 r개를 중복하지 않고 선택하여 순서에 의미를 두지 않고 나열한 것

nCr = nPr / r!

#1 조합에 대한 공식

nCr = nCn-r

nC0 = nCn

#2 중복 조합

서로 다른 n개의 원소 중 중복을 허락하여 r개를 선택해 순서에 의미를 두지 않고 나열한 것

nHr = n + r - 1Cr

#3 이항 정리

이항식 (a+b)^n을 전개하였을 때 나오는 식을

조합으로 정리한 것을 이항 정리라 하고 이때 이항식의 계수를 이항 계수라고 한다

이산적 확률

확률

어떤 사건 A가 일어날 가능성을 수로 나타낸 것

사건 A가 일어날 경우의 수를 전체 경우의 수로 나눈 값

확률 변수 : 표본 공간에서 일정한 확률을 가지고 발햇아는 사건의 수치에 일대일 대응되는 변수 → 확률적인 과정에 따라 그 값이 결정되는 변수

이산 확률 변수 : 셀 수 있는 확률 변수

연속 확률 변수 : 적절한 구간 내의 모든 값을 취하는 확률 변수

→ 이를 통해 확률 분포 함수를 구현 가능

기댓값 : 확률 분포의 평균을 이용하여 결과를 예측

편차 : 각 값과 기댓값과의 차이

분산 : 기댓값에서 해당 값들이 얼마나 떨어져 있는지 보여주는 값

표준 편차 : 분산의 음이 아닌 제곱근으로 분산과 마찬가지 역할을 수행

#1 베이즈 정리

표본 공간이 n에서 서로 다른 배반적 사건 B1, B2, B3,…, Bn 중 하나는 반드시 일어난다고 할 때, 임의의 사건 A에 대해

P(Bi|A) =P(Bi)*P(A|Bi) / P(A) 가 성립한다

이 때, P(Bi)를 사전 확률 P(Bi|A)를 사후 확률이라함

재귀적 정의

수학적 귀납법에서와 같이 첫 번째 요소가 정의되고 n+1번째 요소는 바로 앞의 n번쨰와 그 이하의 요소와의 관계로 정의될 경우를 말하며 해당 관계를 재귀적 관계라고 함

재귀적 관계를 이용하는 문제를 해결하기 위한 2단계

주어진 문제를 원래의 문제와 같은 형태의 더 작은 문제로 분할 → 가장 작은 묹제로 분할된 문제들의 해를 구한 후 최종적으로 이들을 결합하여 주어진 문제의 해를 구함

해당 문제로는 팩토리얼, 피보나치 수, 하노이 탑 등 여러 문제가 존재하며 재귀적 성질을 통해 코드를 효과적으로 작성할 수 있다

이처럼 순열, 이산적 확률, 재귀적 관계를 고찰하여 여러 문제의 풀이를 습득하였음