순열과 조합[심화]

출처:http://sky-n-space.blogspot.com/2017/09/100.html

3명의 사람들을 일렬로 세우는 경우의 수는 얼마나 될까?

123 213 312

132 231 321

첫번째 칸에 올 수 있는 사람의 가짓수는 3가지, 두번째 칸에 올 수 있는 사람의 가짓수는 2가지, 마지막 칸에 올 수 있는 사람의 가짓수는 1가지로써 3×2×1=6가지가 3명의 사람들을 일렬로 세우는 경우의 수이다.

그렇다면 이 개념을 확장하여 n명의 사람들을 일렬로 세우는 경우의 수는 n×(n-1)×(n-2)×...×2×1=n!가지다.

---

8명의 사람에서 3명을 골라 줄을 세우는 경우의 수는 얼마나 될까?

머리속에 일렬로 나열된 세 의자를 상상하자. 왼쪽에서 가장 1번째 의자에 8명의 사람 중에 1명이 앉는다. 총 8가지의 가짓수가 존재한다. 그 다음에 2번째 의자에는 첫번째 의자에 앉은 사람을 제외한 7명의 사람이 앉을 수 있다. 3번째, 즉 마지막 의자에는 1번째 의자, 2번째 의자에 앉은 사람을 제외한 6명의 사람이 앉을 수 있다.

8×7×6=336

336가지의 경우의 수가 존재한다.

위의 문제를 통해 알 수 있는 것이 무엇인가?

우리는 n명의 사람이 존재하고 그 중에서 r명의 사람을 골라 줄을 세운다면 

n×(n-1)×...(n-r+1)가지의 경우의 수가 존재할 것이라는 것을 직관적으로 알 수 있다.

n명의 사람에서 r명을 골라 줄을 세우는 가짓수는 _nP_r이라고 작성하겠다.

 

만일 위의 문제가 줄을 세우지 않고 8명의 사람에서 3명만 고르는 가짓수만 물어본다면 어떤 방식으로 문제를 풀어야 할까?

우리는 n명의 사람을 줄 세우는 경우의 수는 n!=n×(n-1)×(n-2)×...×2×1라는 것을 알고 있다.

그렇다면 n명의 사람에서 r명을 골라 줄을 세우는 것과 단지 n명의 사람에서 r명을 고르는 것의 차이는 무엇인가?

바로 n!이 곱해지고 나눠지는 관계이다. n명의 사람에서 r명을 골라 나열하는 가짓수에서 r!을 나누면 n명의 사람에서 r명을 고르는 가짓수가 탄생한다는 것을 알 수 있다.

n명의 사람에서 r명을 고르는 가짓수는 _nC_r이라고 작성하겠다.

---

a+b+c=10을 만족하는 음이 아닌 정수쌍 (a,b,c)는 얼마나 있을까?

보기만 해도 엄청난 노가다가 필요할 것 같이 생겼다. 하지만 이러한 공식이 존재하여 위의 문제는 쉽게 풀린다.

A1+A2+...+An=R을 만족하는 음이 아닌 정수쌍 (A1,A2,...,An)의 가짓수는 _nH_r이라고 하고 _nH_r=_n+r-1C_r이다.

따라서 위의 문제의 경우의 수는 3H10=12C10=12C2=66가지다.

(12C10과 12C2가 같은 이유는 12명 중에서 10명을 고르는 것과 12명 중에서 골라지지 않을 2명을 제외하는 것이 결국 같은 행동이기 때문이다.)

 

기본적인 것을 알았으니 문제들을 풀어보자.

---

#1. 어떤 사람이 3개의 상자에서 1개를 택하여 그 상자 안에 존재하는 공을 무작위로 뽑는다. 이때, 빨간 공을 뽑을 경우의 수는?

1번 상자	빨간 공 3개 파란 공 4개
2번 상자	빨간 공 2개 파란 공 6개
3번 상자	빨간 공 11개 파란 공 3개

3+2+11=16가지다.

 

#2. 7명의 사람을 3그룹으로 분류하는 가짓수는? (단, 그룹에는 적어도 1명의 사람이 존재)

 

포함과 배제의 원리에 의해

각 사람은 3그룹 중 무작위로 한 곳에 들어갈 수 있다. → 총 3^7가지

어떤 1그룹에 한 명도 들어가지 않은 경우를 빼준다. → 총 3C1×2^7가지

어떤 2그룹에 한 명도 들어가지 않은 경우를 더해준다. → 총 3C2×1^7가지

 3^7-3C1×2^7+3C2×1^7=2187-384+3=1806

총 1806가지의 경우의 수가 있다.

 

+)

미완