중복조합

■ 중복조합 ( )

▶ 증명1

3개의 문자 a, b, c 에서 4개를 뽑는 중복조합의 각 경우를 문자를 나타내는 ◯ 4개와 세 문자 a, b, c 사이의 경계를 나타내는 ▯ 2개를 이용하여 생각해보자.

 

예를 들어 aabc는 ◯◯▯◯▯◯로 나타낼 수 있고,

다음과 같은 방법으로 나타내어 수를 구하면 된다.

aaaa ◯◯◯◯▯▯

aaab ◯◯◯▯◯▯

aaac ◯◯◯▯▯◯

aabb ◯◯▯◯◯▯

bbcc ▯◯◯▯◯◯

abcc ◯▯◯▯◯◯

왼쪽의 문자와 오른쪽의 기호의 대응이 일대일대응이므로 두 집합의 원소의 개수는 서로 같다.

위에서 6개의 자리에서 기호 ◯가 들어갈 4개의 자리를 뽑는 조합의 수와 같다.

 

기호 ◯의 개수 4는 뽑는 수 4와 같고, 기호 ▯의 개수 2는 3개의 문자 a, b, c를 구분하는 수 3-1=2와 같으며, 6개의 자리를 뽑는 수 4와 구분하는 수 2의 합 4+(3-1)과 같다.

 

따라서 구하는 중복조합의 수 는 4개의 ◯와 (3-1)개의 ▯를 일렬로 나열하는 경우의 수와 같다. 즉 {4+(3-1)} 개의 자리 중에서 ◯를 놓을 4개의 자리를 택하는 조합의 수와 같으므로

                                      

이다.

 

일반적으로 중복조합의 수 는 r개의 ◯와 (n-1)개의 ▯를 일렬로 나열하는 경우의 수와 같다. 즉 {r+(n-1)}개의 자리 중에서 ◯를 놓을 r개의 자리를 택하는 조합의 수와 같으므로 다음이 성립한다.

                                      

 

▶ 증명2

3개의 숫자 1,2,3에서 4개를 택하는 중복조합에서 각 원소의 첫째수, 둘째수, 셋째 수, 넷째수에 각각 0,1,2,3을 더하면 다음과 같다.

1111 1234

1112 1235

1123 1246

1122 1245

2233 2356

1133 1256

위와 같이 1,2,3,4,5,6에서 중복을 허용하지 않고 4개를 택하는 조합의 수와 같다.

3개중에서 중복을 허락하여 4개를 뽑는 경우의 수는 3+(4-1)개 중에서 4개를 뽑는 경우의 수와 같으므로

이다.

같은 방법으로 서로 다른 n개의 숫자에서 r개를 택하는 중복조합 의 수는 각 원소의 첫째 수, 둘째 수, …, r째 수에 각각 0,1, 2, 3, …… , r-1을 더하여 생긴 서로 다른 n+(r-1)개의 수에서 r개를 택하는 조합의 수와 같다.

원순열의 수 확률과 통계 마인드맵