순열, 이산적 확률, 재귀적 관계

Oak_Cassia·2021년 11월 29일
0

Descrete Mathematics

목록 보기
8/9

경우의 수

rule of sum
두 사건 A,B (AB0A \cap B \neq 0) 가 일어날 경우의 수를

  • n(A)=m
  • n(B)=n
    이라고 하면

A 또는 B가 일어날 경우의 수는 m+n 이다.
n(ABA \cup B)=n(A)+n(B)=m+n


rule of product
두 사건 A,B 에서

  • n(A)=m
  • n(B)=n
    이면

A, B가 동시에 일어날 확률은 mn 이다.
n(ABA \cap B)=n(A)
n(B)=m*n

순열

서로 다른 원소들을 순서를 고려하여 일렬로 배열하는 것.
서로 다른 n개의 원소를 한 줄로 배열하는 순열의 개수는
n×(n1)×(n2)×...×2×1=n!n\times (n-1)\times (n-2)\times ...\times 2\times 1=n!
1부터 n까지의 모든 자연수의 곱을 n의 계승 또는 n factorial 이라고 읽으며 n!n!로 나타낸다.
0!=10!=1
1!=11!=1
n!=n(n1)!n!=n(n-1)!

서로 다른 n개의 원소 중에서 r개를 선택하는 순열의 수
nPrnPr= n×(n1)×(n2)×...×(nr+1)n\times (n-1)\times (n-2)\times ...\times (n-r+1)0<rn0 <r \leq n
nPrnPr=n!(nr)!n! \over (n-r)!
P(n, r)로 표현하기도 한다.

같은 것을 포함하는 순열
n개 중 같은 것이 각 p개, q개, ..., r개씩 있을 때, n개를 일렬로 배열하여 만들 수 있는 순열의 수는 n!p!q! ... r!n!\over{p!q!\ ...\ r!} 단p+q+...+r=n

조합

서로 다른 n개의 원소 중, 순서를 생각하지 않고 r개를 택할 때. 이것을 n개의 원소에서 r개를 택하는 조합이라 하고, 그 조합의 수를 nCr로 나타낸다.
nCr=nPrr!=n!(nr)!r!nCr={nPr\over r!}={n! \over (n-r)!r!}
C(n,r)C(n,r) , Cn, rC_{n, \ r} 로 표현

이항정리(binomial theorem)

(a+b)n(a+b)^n을 전개 했을 때, r=0nnCr anrbr\sum^n_{r=0}nCr\ a^{n-r}b^r
이 때 nCr을 이항계수(binomial coefficient)라 한다.

파스칼의 삼각형에서는 이항 계수가 다음과 같이 만들어 진다.
n,r이 음이 아닌 정수이고 1rn11 \leq r \leq n-1일 때
n1Cr1+n1Cr=nCr_{n-1}C_{r-1}+_{n-1}C_{r}=_nC_{r}

조합론적 증명: n개의 물체에서 r개를 고른다 하자. n개중 1개를 고정, A라 한다. 그럼 구하고자 하는 경우의 수는 A가 포함되는 경우포함되지 않는 경우 2가지로 나눈다.
전자의 경우 나머지 n-1개중 r-1개를 고르고
후자의 경우 n-1개중 r개를 고르면 되므로
합의 법칙에 의해 n1Cr1+n1Cr=nCr_{n-1}C_{r-1}+_{n-1}C_{r}=_nC_{r}
대수적 증명:
n1Cr1+n1Cr=(n1)!(r1)!(nr)!+(n1)!r!(nr1)!=(n1)!rr!(nr)!+(n1)!(nr)r!(nr)!=n!r!(nr)!_{n-1}C_{r-1}+_{n-1}C_{r}={(n-1)!\over(r-1)!(n-r)!}+{(n-1)!\over r!(n-r-1)!}={(n-1)!r \over r!(n-r)!}+{(n-1)!(n-r)\over r!(n-r)!}={n!\over r!(n-r)!}

확률변수
변수 X가 취할 수 있는 모든 값이 x1,x2, ... ,xnx_1, x_2, \ ...\ ,x_n이고 X가 이들 값을 취할 확률 p1,p2, ... ,pnp_1, p_2, \ ...\ ,p_n 이 정해져 있을 때, X를 확률 변수라 한다.
X가 이산적인 값을 취할 때 이러한 확률을 이산적 확률(discrete probability)이라고 한다.

확률분포
확률 변수 X가 취하는 값 xix_i와 X가 xix_i를 취할 확률 pip_i와의 대응 관계를 X의 확률분포라고 한다.

X의 기대값, 평균 i=1nxipi=x1p1+x2p2+...+xnpn=E(x)=m\sum_{i=1}^nx_ip_i=x_1p_1+x_2p_2+...+x_np_n=E(x)=m

분산(variance): 확률 변수 X의 평균이 m일 때 E((xm)2)=V(x)=σ2(x)E((x-m)^2)=V(x)=σ^2(x)
i=1n(xim)2pi=(x1m)2p1+(x2m)2p2+...+(xnm)2pn\sum_{i=1}^n(x_i-m)^2p_i=(x_1-m)^2p_1+(x_2-m)^2p_2+...+(x_n-m)^2p_n

표준 편차(standard deviation)
분산의 양의 제곱근 σ(x)=V(X)\sigma (x)=\sqrt V(X)

베이즈의 정리(bayesian theorem)
어떤 사건이 서로 배반하는 원인 둘에 의해 일어난다고 할 때 실제 사건이 일어났을 때 이것이 두원인 중 하나일 확률을 구하는 정리.
P(HE)=P(EH)P(H)P(E)P(H|E)={P(E|H)P(H) \over P(E)}

P(HE)P(H|E) 사후확률(posterior)
어떤 사건이 만든 상황에서, 그 사건이 일어난 후 앞으로 일어나게 될 다른 사건의 가능성을 구하는 것
P(HE)=P(EH)P(H)P(E)=P(EH)P(H)P(EH)P(H)+P(EHc)P(Hc)P(H|E)={P(E|H)P(H) \over P(E)}={P(E|H)P(H)\over P(E|H)P(H)+P(E|H^c)P(H^c)}

P(H): 사전확률(prior)
Hypothesis: 가설, 어떤 사건이 발생했다는 주장
Evidence: 새로운 정보

베이즈 정리는 본래 역확률 문제를 해결하기 위한 방법이었다.
P(H|E)를 알고 있을 때 전제와 관심사건의 관계가 정반대인 P(E|H)를 구하는 방법
최근 빅데이터를 통해 기존 사건의 확률을 대략적으로 알아낼 수 있게 됨으로 사회적 통계나 주식에서 빅데이터를 이용한 베이즈 정리 활용이 이용된다.

하지만 베이즈 정리를 이전의 경험과 현재의 증거를 토대로 어떤 사건의 확률을 추론하는 알고리즘으로 볼 수도 있다.
1. 어떤 사람이 병A에 걸려있을 확률을 몰라서, 인구 일반이 해당 질병에 걸릴 확률인 1%의 유병률을 가정
2. 정확도가 90%인 검사를 받았더니 양성
3.어떤 사람이 양성 판정을 받았다는 새로운 사실을 토대로 이 사람이 실제 병에 걸려있을 확률을 알아낼 수 있다.
이 문제에서 베이즈 정리가 알려주는 것은 '어떤 사건 A가 일어났다고 가정할 때 B라는 자료를 얻게 될 확률'을 알고 있다면 자료에 근거해서 어떤 사건이 일어날 확률을 새로 계산할 수 있다.
수학적인 일반화: n개의 사건 A1A_1~AnA_n이 표본 공간 S를 분할할 때 공사건이 아닌 사건 B에 대하여 P(B)는 확률의 덧셈정리에 의해 아래와 같이 나타낼 수 있다.
P(b)=P(A1)P(BA1)+P(A2)P(BA2)+...+P(An)P(BAn)P(b)=P(A_1)P(B|A_1)+P(A_2)P(B|A_2)+...+P(A_n)P(B|A_n)
이 때 조건부 확률(AiB)(A_i|B)
P(AiB)=P(BA)P(B)=P(Ai)P(BAi)P(A1)P(BA1)+P(A2)P(BA2)+...+P(An)P(BAn)P(A_i|B)={P(B \cap A)\over P(B)}={P(A_i)P(B|A_i)\over P(A_1)P(B|A_1)+P(A_2)P(B|A_2)+...+P(A_n)P(B|A_n)}

확률을 사각형으로 표현하면 쉽다.

비둘기집 원리(pigeonhole principle)

n개의 비둘기 집에 n+1 마리 이상의 비둘기가 들어갔다면, 두 마리 이상의 비둘기가 들어간 비둘기 집이 적어도 하나 있다는 법칙

재귀적 정의(recursive definition)

수학적 귀납법에서와 같이 첫 번째 요소가 정의 되고, n+1번째의 요소는 바로 앞의 n번째와 그 이항의 요소와의 관계로서 정의되는 경우를 말하며, 재귀적 관계로 표현된다.
1. 주어진 문제를 원래의 문제와 같은 형태의 더 작은 문제들로 분할한다.
2. 가장 작은 문제로 분할된 문제들의 해를 구한 후, 최종적으로 이들을 결합하여 주어진 문제의 해를 구한다.(분할정복?)

피보나치 수(Fibonacci numbers)

다음과 같이 재귀적 관계식으로 정의된다.
fib(0)=0, fib(1)=1
fib(n)=fib(n-1)+fib(n-2)

심심해서 만들어봤다...

#include<iostream>
using namespace std;


int fib(int max)
{
	if (max == 0) return 0;
	if (max == 1) return 1;
	return fib(max - 2) + fib(max - 1);
}

int main()
{
	int z = 0;
	int o = 1;

	for (int i = 0; i < 10; i++)
	{
		int c = z + o;
		
		cout << "fib" << i + 2 << " = " << z << '+' << o << endl;

		z = o;
		o = c;
		
		
	}
	cout << fib(10) << endl;

}

하노이 탑(tower of Hanoi)

void hanoi(int n, char from, char tmp, char to)
{
	if (n == 1)
		printf_s("원반 1을 %c에서 %c로 옮긴다.\n",from,to);
	else
	{
		hanoi(n - 1, from, to, tmp);
		printf_s("원반 %d을 %c에서 %c로 옮긴다.\n",n, from, to);
		hanoi(n - 1, tmp, from, to);
	}
}
profile
rust로 뭐할까

0개의 댓글