[Probability and Statistics] 순열과 조합

Probability and Statistics in HelloMinchan

[Probability and Statistics] 순열과 조합

(글쓴날 : 2020.05.29)

 

---

* 이 글은 글쓴이가 공부한 내용을 정리하며 올리는 글입니다.

* 글의 내용은 개념원리 확률과 통계 기반으로 공부하여 작성하였습니다.

---

 

 

순열과 조합

---

1) 합의 법칙

합의 법칙이란 어떤 사건들이 동시에 일어나지 않을 때, 각 사건들이 일어날 경우의 수는 각 사건들의 경우의 수의 합과 같다는 것이다.

(단순하게 생각하면 각 사건들이 독립적일 시, 사건들의 경우의 수를 그냥 다 더해서 세는 것이다.)

 

ex) 두 개의 주사위를 던질 때, 주사위의 합이 10 또는 12가 될 경우의 수

10 또는 12가 될 경우의 수 = 10이 될 경우의 수 + 12가 될 경우의 수

10이 될 경우의 수 = 3 {(4,6), (5,5), (6,4)}

12가 될 경우의 수 = 1 {(6,6)}

따라서, 10 또는 12가 될 경우의 수 = 4 {(4,6), (5,5), (6,4), (6,6)}

 

위의 예시에서 10이 될 경우와 12가 될 경우라는 사건이 동시에 일어날 수 없기에 합의 법칙이 성립한다.

---

2) 곱의 법칙

곱의 법칙이란 어떤 사건들이 동시에 일어날 때, 해당 경우의 수는 각 사건들의 경우의 수의 곱과 같다는 것이다.

(생각해보면 당연하다.)

 

ex) 서울에서 천안까지 길이 3개 있고, 천안에서 부산까지 길이 5개 있을 때, 서울에서 부산까지 갈 수 있는 길의 개수

서울 ▶ 부산 길의 개수 = 서울 ▶ 천안 길의 개수 * 천안 ▶ 부산 길의 개수

---

3) 순열

순열이란 서로 다른 n개중 서로 다른 r개를 순서에 상관하여 뽑는 경우의 수이다.

 

ex) 짜장면, 피자, 치킨을 아침, 점심, 저녁에 언제 먹을지 정하는 경우의 수

 

위의 예시에서 만약 아침, 점심, 저녁이라는 순서가 상관이 없다면, 경우의 수는 무조건 1이 될 것이다.

짜장면 ▶ 피자 ▶ 치킨 순으로 먹나,

피자 ▶ 치킨 ▶ 짜장면 순으로 먹나,

치킨 ▶ 피자 ▶ 짜장면 순으로 먹나

모두 다 같은 경우이기 때문이다. (입안에 들어가면 다 똑같으므로...)

이는 밑에 나올 조합의 경우이다.

 

영어로 Permutation이고, 따라서 약자로 P를 사용하며, nPr과 같은 식으로 표기한다.

 

* 공식 : n! / (n - r)!

 

순열의 성질로는

1) nPn = n!

2) nP0 = 1

이 있다.

공식에 대입하면 0! = 1이라는 약속에 근거하여 쉽게 증명이 가능하다.

 

7P3을 계산해보면, r만큼의 빈 공간을 _, _, _ 이렇게 만들어 각 공간마다 들어갈 수 있는 가능한 경우의 수를 만들어가면 된다. 첫 번째 공간에는 모든 수가 가능하므로 7개, 두 번째 공간에는 첫 번째 공간에서 뽑은 수를 제외한 6개, 세 번째 공간에는 이전 공간에서 뽑은 수를 제외한 5개이다.

따라서, 공식에 대입하여 약분해 계산하기 보다 그냥 단순하게 n부터 -1씩 감소시키며 r번 곱하는 게 편할 것 같다.

---

4) 조합

조합이란 서로 다른 n개중 서로 다른 r개를 순서에 상관없이 뽑는 경우의 수이다.

 

ex) 짜장면, 피자, 치킨 중 배달 시킬 음식 2개를 고르는 경우의 수

 

위의 예시는 순서가 상관이 없기에, 피자, 치킨을 고른 것과 치킨, 피자를 고른 것은 당연히 같은 경우이다.

 

* 공식 : n! / (n - r)! * r!

 

조합의 성질로는

1) nCn = 1

2) nC0 = 1

3) nCr = nCn-r

4) nCr = n-1Cr-1 + n-1Cr

이 있다.

일반 수능 및 내신에서는 3번 성질이 제일 중요시 되는 것 같다.

허나, 나의 경우 4번에 눈길이 가는데 동적 계획법으로 구현하는 파스칼의 삼각형의 원리와 관계가 있기 때문이다.

 

4번의 증명은 크게 2가지 방식으로 할 수 있는데,

첫 번째 방식은 간단하게 공식에 대입하는 것이다. (우항과 좌항이 같다를 입증하면 자명하다.)

두 번째 방식은 {1,2,3,4,5}와 같은 집합에서 3개를 고르는 경우를 예로 들어 할 수 있다.

1을 특정 원소로 가정하여, 1을 포함한 경우의 수(n-1Cr-1)와, 1이 포함되지 않은 경우의 수(n-1Cr)를 더하면 결국, nCr이 된다는 점을 들어 증명할 수 있는데,

만약, 1을 포함할 경우 전체 n에서 1을 이미 골랐으므로 1을 뺀 n-1개 중 r-1개를 고르는 경우가 되어 n-1Cr-1이 되고, 1이 포함되지 않은 경우 전체 n에서 1을 빼고 고른 것과 같으므로 n-1개 중 r개를 고르는 경우가 되어 n-1Cr이 된다.

따라서, 1을 포함한 경우의 수와 1이 포함되지 않은 경우의 수의 합이라는 말은 전체 경우의 수라는 말과 동치이므로 4번 성질이 증명된다.

---