확률과 통계(11)

※본 글에는 수식이 사용되었습니다. 모바일에서는 수식이 깨져 보이지 않을 수 있는 점 참고 바랍니다. 만일 수식이 깨져 보일 경우 데스크톱 모드를 사용하여 주시길 부탁드립니다.

---

 지금까지 우리가 다룬 조합은 중복을 허용하지 않고 택하는 조합이다. 그러나 현실에서 우리는 중복을 허용하여 고르는 경우가 상당히 빈번하여 이 방법을 적용하기 힘든 상황이 올 수 있다.. 배스킨라빈스에서 아이스크림의 맛을 고르는 경우만 해도 그렇다. 본문에서는 이러한 상황을 해결할 수 있는 중복조합에 대하여 다루고자 한다.

중복조합

 중복조합이란 서로 다른 원소에서 순서를 고려하지 않고 택하되, 같은 원소를 중복하여 택하는 것을 허용하는 조합이다. 서로 다른 n개의 원소에서 중복을 허용하여 r개를 택하는 경우의 수는 다음과 같이 표현한다.

$$ {}_{n}\mathrm{H}_{r} \text{, } \mathrm{H} \left( n \text{, } r \right) $$

 이 중복조합의 수를 구하는 연산을 우리가 아는 연산으로 바꾸어 나타내 보자. 아래의 n개의 원소 중 중복을 허용하여 r개를 택하는 경우의 수를 구해보자.

$$ a_{1} \text{, } a_{2} \text{, } a_{3} \text{, } \cdots \text{, } a_{n-1} \text{, } a_{n} $$

 이 n개의 원소 중 중복을 허용하여 r개를 고른 것을 종류별로 구분하여 다음과 같이 나타낼 수 있다.

$$ \underbrace{ a_{1} \text{ } a_{1} \cdots a_{1} / a_{2} \text{ } a_{2} \cdots a_{2} / a_{3} \text{ } a_{3} \cdots a_{3} / \cdots / a_{n-1} \text{ } a_{n-1} \cdots a_{n-1} / a_{n} \text{ } a_{n} \cdots a_{n} }_{r} $$

 여기서 ( / ) 표시 사이에 들어가는 수를 정해주면 결국 중복조합으로 뽑는 경우의 수와 같아진다. 이 수를 정해주는 방법은 간단하다. 일단 ( / ) 표시를 제외하고 택하는 자리의 수는 r개이다. 또한 각 원소를 구분해주기 위해 사용해야 하는 ( / ) 표시의 수는 (n-1)개이므로 나열하는 ( / ) 표시와 원소의 수는 (n+r-1)이다.

 여기서 각 ( / ) 표시 사이의 들어갈 원소의 수를 결정하는 것은 위 그림과 같이 정해주면 된다. 먼저 원소와 ( / ) 표시가 들어갈 자리의 수가 (n+r-1)이므로 각 자리에 들어갈 ( / ) 표시의 자리 r개를 정해주는 경우의 수는 다음과 같다.

$$ {}_{n+r-1}\mathrm{C}_{r} $$

 이렇게 ( / ) 표시의 자리를 결정해주면 각 ( / ) 표시 사이에는 한 종류의 원소가 들어갈 것이므로 원소들의 수는 결정되었다. 또한 우리가 구하는 경우의 수는 조합이므로 ( / ) 표시 사이에 들어가는 원소의 순서를 정할 필요가 없다. 따라서 구하는 경우의 수는 아래와 같다.

$$ {}_{n}\mathrm{H}_{r} = {}_{n+r-1}\mathrm{C}_{r} $$

 따라서 중복조합은 우리가 알고 있는 일반적인 조합으로 바꾸어 표현이 가능하다.

 

 

 

진실은 복잡함이나 혼란 속에 있지 않고, 언제나 단순함 속에서 찾을 수 있다.

-아이작 뉴턴

---