[프로그래밍수학] 순열과 조합

엘리스에서 제공한 강의와 자료를 보고 정리한 내용입니다.

 

✅ 경우의 수

사건은 같은 조건에서 여러 번 할 수 있는 실험이나 관찰로 얻어진 결과를 의미한다.

경우의 수는 사건에서 일어날 수 있는 경우의 가짓수를 말한다.

예를 들어 주사위를 던졌을 때 1, 2, 3, 4, 5, 6의 결과가 나올 수 있으니 이때의 경우의 수는 6이다.

 

✔️ 합의 법칙

사건 A 또는 B가 일어나는 경우 전체 경우의 수는 두 사건의 경우의 수를 더한 값이 된다.

사건 A의 경우의 수가 a이고 사건 B의 경우의 수가 b라면 사건 A 또는 B가 일어날 경우의 수는 a + b이다.

이렇듯 합의 법칙은 각 사건이 동시에 일어나지 않을 때 사용한다.

 

✔️ 곱의 법칙

사건 A와 B가 동시에 일어나는 경우 전체 경우의 수는 두 사건의 경우의 수를 곱한 값이 된다.

사건 A의 경우의 수가 a이고 사건 B의 경우의 수가 b라면 사건 A와 B가 동시에 일어날 경우의 수는 a x b이다.

곱의 법칙은 합의 법칙과 달리 사건이 동시에 일어나는 경우에 사용한다.

이때 "동시"라는 것은 같은 시각을 의미하는 것이 아닌 경우의 수를 구하는 과정에서 두 사건 모두 일어나야 한다는 뜻이다.

 

 

✅ 순열

순열(Permutation)은 어떤 것을 나열할 때 몇 가지의 경우의 수가 있는지 계산하는 법을 의미한다.

이름 그대로 순서대로 뽑아서 줄 세우는 것과 같다.

순열은 P로 표기하며 n개 중 r개를 뽑아서 줄 세우는 것을 식으로 표현하면 다음과 같다.

 

 

이를 해석하자면,

1. 첫 번째로 뽑을 때는 n개 중 하나를 뽑을 수 있다.
2. 두 번째로 뽑을 때는 1. 에서 뽑은 것을 제외한 n-1개 중에서 하나를 뽑을 수 있다.
3. 세 번째로 뽑을 때는 1. 과 2. 에서 뽑은 것을 제외한 n-2개 중에서 하나를 뽑을 수 있다.
4. r 번째로 뽑을 때는 1.과 2. 3. ... (r-1). 에서 뽑은 것을 제외한 n-(r-1)개 중에서 하나를 뽑을 수 있다.

 

✔️ 같은 원소가 있을 경우

나열하려는 것 중 같은 원소가 있을 때는 구별되지 않아 순서를 매길 수 없다.

따라서 각 원소 a1, a2, a3, ... , an에 대해 갯수가 p1, p2, p3, ..., pn이 있을 때 다음과 같은 식으로 표현할 수 있다.

 

 

 

✅ 조합

조합(Combination)은 순서에 상관없이 n개 중 r개를 뽑는 경우의 수를 의미한다.

순열과의 차이점은 순서를 고려하지 않는다는 점이다.

조합은 C로 표기하며 n개 중 r개를 뽑는 경우의 수를 식으로 표현하면 다음과 같다.

 

 

조합은 다음과 같이 나타내기도 한다.

 

 

 

🔍 참조

경우의 수 https://mathbang.net/109

순열 https://mathbang.net/545

조합 https://mathbang.net/547