순열(Permutation)과 조합(Combination)

이번 포스팅에서는 순열과 조합에 대해서 알아보는 시간이다. 순열과 조합 두개를 모두 일컬어 'Combinatorial Analysis'라고도 부른다.

 

1. 순열(Permutation) : 서로 다른 n개를 일렬로 나열하는 것이다.(line arrangement for 'n' different objects)

                             이때 순서(order)는 고려한다.

순열

그림으로 예시를 들어보자면 그림 속 왼쪽의 그림과 같이 된다. n개 중에서 r개를 일렬로 쭉 세울 대

nPr이라는 수식이 나오게 되고 !(팩토리얼)로 풀어내게 되면 위와 같은 수식이 된다.

 

참고로 0! 은 왜 1일까? 에 대해서 고민한다면 0! 이라는 것은 '아무것도 나열하지 않는것 ' 이라는 것을 의미하기 떄문에 아무것도 나열하지 않는 것도 하나의 경우의 수이기 때문에 1이 된다.

 

다음은 오른쪽 그림의 Group Permutation인데 이는 중복이 있는 수열을 말한다. 그림 속의 예시와 같이 설명한다면 공 10개가 있고 이 중 5개는 빨간 공, 3개는 흰색 공, 2개는 검은색 공이 있다. 이 때 나올 수 있는 모든 경우의 수를 구할 때 분자에는 10! 이라는 전체 공 갯수의 경우의 수를 입력하고 분모에는 중복되는 갯수(=똑같은 색의 공의 갯수)만큼의 !를 입력시켜 각각 곱해주는 식을 분모에 넣어준다. 

 

2. 원순열(Circular Permutation) 

원 순열에 대해서는 필기를 통해서 이해하는 게 더 빠를 것 같다.

 

원순열

왼쪽 그림처럼 원 모양의 테이블에 n명의 사람이 앉는 경우의 수를 구한다고 해보자. 분자에는 똑같이 기존처럼 모든 경우의 수 n!를 넣어준다. 이 때 분모에는 n이라는 총 갯수를 넣어주어야 하는데 이유는 왼쪽그림 속 A의 경우 B의 경우가 같기 때문이다. 즉 옆으로 하나씩 이동한다고 해도 결국 똑같은 순서로 앉아 있기 때문이다.

 

하지만 오른쪽 그림처럼 직사각형의 경우일 때는 어떻게 할까? 방금 한 것처럼 위의 식 그대로 적용한 후 하나의 요소를 곱해주어야 하는데 그 요소는 그림 속 예시를 들면 1이 처음의 저 자리와 똑같은 자리(즉, 반대편)로 가기 위해서는 5번의 과정을 거치기 때문에 5를 곱해주어야 하는 것이다.

 

3. 조합(Combination)

 

조합

그림 속 1.10.5는 신경쓰지 말고 나머지 부분의 필기에 주목하면 된다. 우선 조합이란 n개의 객체들 중에서 r개의 객체들을 선택하는 것인데 이 때 순서를 고려하지 않는다. 즉, 순서가 어찌됬든 똑같은 요소만 있으면 하나로 센다.

 

따라서 왼쪽 중간의 nCr 수식이 조합의 공식이다. 요즘은 이항계수 수식() 으로 많이 쓰기 때문에 저렇게 알아두면 될 것 같다. 

 

그리고 오른쪽의 경우처럼 n+m의 갯수 중에서 r개를 뽑아야 하는 복잡한 과정일 때는 어떻게 할까? 바로 옆에 있는 공식을 외우면 되지만 이 공식이 어떻게 나오는지에 대해 예시를 들면서 이해해보자.

 

우선 전체 중 n명의 남자들, m명의 여자들이 있다. 이 중 r명을 뽑는건데, 핵심은 n과 m의 사건을 서로 독립사건으로 하는 것이다. 즉, 밑의 표처럼 남자를 0명 여자를 r명 뽑았을 경우, 남자를 1명 여자를 r-1명 뽑았을 경우...... 끝에는 남자를 r명 여자를 0명 뽑았을 때의 확률을 모두 더해주면 아까 보았던 공식이 나오게 된다.

 

4. 이항정리(Binominal Theorem)

 

이항정리

이항 정리는 그림 속 필기를 통해서 이해하면 될 것 같다. 한 가지 기억해야 할 점은 만약 구하고자 하는 수식의 지수가 제곱이상 되어 있다면 미분을 했더라도 또 한 번 미분해서 구하면 된다는 것이다.

 

이런 이항 정리는 나중의 이항 분포를 위해 배운다는 내용인데 강의 속에서는 이항분포에 대해서 자세히는 다루지 않았고 간단한 개념정리와 공식만 짚어주셨다. B(n, p)라 하면 n번 시행, 일어날 확률 p를 나타낸다. 그리고 평균(m) = np, 분산(표준편차의 제곱)=np(1-p)이다.

 

5. 멱급수(Power series)

 

멱급수

계산 과정을 보는 것처럼 f(x)를 쉽게 구하기 위해서 각 변에 x를 곱해준 식과 기존의 식을 뺀다. (단, -1<x<1)

따라서 f(x)는 1/1-x 라는 값이 나오게 된다. 

 

만약 g(x)라는 함수가 저런 시그마 수식을 갖고 있는 식이라 했을 때, 미분을 하게 되면 아까 구했던 f(x)와 똑같은 식이 된다. 

 

6. Stirling's Formula

스털링 공식은 n!이라는 숫자가 무수히 커질 때 근삿값을 이용하는 규칙이다. 그림을 보고 살펴보자.

 

스털링 근삿값

그림 속 글씨로 써져있다시피 근삿값을 이용하는 이유는 숫자가 무수히 커질 때는 그 때의 오차는 영향이 없다는 것이다. 만약 우리가 갖고 있는 숫자가 10인데 오차가 1이라 하면 영향을 많이 줄 수 있지만 우리가 10만이라는 숫자를 갖고 있을 때 100이라는 오차는 영향이 미미하여 근삿값을 이용하라는 것이다.

 

7. Reliability(신뢰도) 

 

신뢰도의 정의

신뢰도라 함은 어떤 시스템에서 동작이 잘 작동하는 동안의 기간이라고 보면 된다. 신뢰도에 관한 함수 R(t)를 정의한다면 위의 설명과 같다. 단, t = 1시간이고 신뢰도가 99%일때, 1시간이라는 시간동안 1%로 에러가 발생할 수 있다는 것을 의미하지 어느 시점에 1%의 에러가 발생하는 것을 명시해주진 않는 것을 기억하자.

 

이제는 예시로 직렬, 병렬 그리고 직렬과 병렬이 혼합된 복잡한 문제로 확률을 계산해보자.

 

8-1. 직렬연결(Series Connection)

 

Series Connection(직렬 연결)

Cascading이라고도 한다. 위 그림 처럼 C의 1부터 r까지의 각 모듈을 직접적으로 연결해 놓은 구조다. 이러한 구조에서 전체가 잘 동작할 확률 R(t)를 구한다고 하면 각 C의 1부터 r까지의 모듈을 다 곱해주면 된다. 

 

하지만 이러한 직렬 연결은 중간의 하나의 모듈에서 에러가 나온다면 잘 동작하지 않으므로 망가지기 쉽고 실제 산업에 직렬연결만을 사용해서 쓰이진 않는다.

 

8-2. 병렬연결(Parallel Connection)

 

병렬연결

병렬 연결은 위 그림처럼 하나의 모듈만 잘 동작한다면 output이 제대로 전달해진다. 즉 적어도(at least)의 개념인데

이 '적어도'의 확률을 구하기 위해서는 ' 1 - 모두의 확률 ' 을 적용해주면 된다. 이 그림에서는 전체 확률(1)에서 모든 모듈들이 각각 오류가 날 경우를 곱해준 확률을 빼주면 되는 것이다. 따라서 수식은 위처럼 된다.

 

8-3. 복합적인 연결 문제 예시

 

지금까지 보았던 직렬, 병렬 각 연결들로만 구조가 이루어진다면 얼마나 편안할까. 하지만 현실은 그렇지 못하며 복잡한 문제들 투성이다. 밑 그림 처럼 구조가 생겼을 때 전체 R(t)를 구해보도록 하자.

 

복합 연결

(여기서 R과 C를 구분했지만 R과 C의 관계는 단순합니다. 모듈이 C이며 동작하는 것을 R이라고 합니다.)

위 그림은 R1과 R4, R2와 R5는 직렬, R1-R4, R2-R5끼리는 병렬로 연결되어 있다. 문제는 R3다. 전체 동작확률을 구하기 위해서는 이 R3를 기준으로 Case 분류를 해주는 것이다.

1. Rx : C3라는 모듈이 잘 동작할 때 전체 R이 동작할 확률
2. Ry : C3라는 모듈이 동작하지 않을 때 전체 R이 동착할 확률

이 때, C3를 조건으로 Rx, Ry를 나누었기 때문에 서로 독립(배반)사건이다.

그렇다면 위에서 정의한 두가지의 확률을 합했을 때 최종적으로 우리가 구하고자 하는 전체 R을 구할 수가 있다.

그렇다면 이제 정확한 경우의 수를 구하기 위해서 Rx, Ry를 구체적으로 풀어보자! 

 

Rx, Ry의 구조를 그려보면 오른쪽 그림과 같아진다. 이 그림을 식으로 풀어낼 때 우리가 앞서 배웠던 직렬, 병렬 확률 계산 방법을 이용해서 풀어내면 그림 속 수식과 같아지고, 이를 아까 Rx, Ry가 들어있는 전체 R을 구하는 식에 각각 대입해보면 최종적인 R이 발생할 확률을 구할 수 있다. 

 

최종 식을 풀어보면 그림 속 맨 밑의 줄 같이 풀어지는데 R= R1R4 + R2R5 + .... + R1R2R3R4R5 여기서 R1R4의 의미는 R1번과 R4번이 잘 동작한다면 나머지는 오작동이여도 전체 R이 무조건 잘 작동한다는 것이다.