순열의 조합

반복이 허용될 때 n 개 원소를 가진 집합에서 r개를 뽑을 때는 n^r 이 나옵니다.

 

반복에 의한 조합

3개의 책이 있다고 가정해봅시다. (computer science book, physics book, history book)

 

최소한 6개의 카피본을 선택해야 한다고 가정할 때 얼마나 많은 중복을 가진 것에서 선택을 할 수 있을까요?

 

이런식으로 book-end 를 사용해서 책을 나눠주면 됩니다. 

 

전체 자리는 8자리로 합니다. 그 다음 8자리에서 해야하는 것은 book-end 위치만 정의를 해주시면 됩니다. book end 위치를 정한다고 생각하면 C(8, 2)로 해주시면 됩니다. 

 

예를 통해서 중복이 허용하는 경우를 생각해보겠습니다. 

 

빨강, 파랑, 녹색 공들이 있을 때 각각의 더미는 8개의 공을 가지고 있다고 가정해봅시다.

A) 얼마나 많이 8개의 공을 선택할 수 있는가?

B) 뽑을 때 모든 색이 있어야 한다.

 

A) C(8+3-1, 3-1) = C(10,2) = 45

 

B) C(5+3-1, 3-1)

 

예제2

X1 + X2 + X3 = 11

일 때 X1, X2, X3를 구해봅시다. 

 

11개의 목록을 선택하면 되는데요.

 

C(3+11-1, 11) = C(13,11) = C(13, 2) = 78 가지가 있습니다. 

 

경우의 수를 따지는 문제가 있을 때 반복이 허용되는 경우와 허용되지 않는 경우, 순열과 조합의 경우가 있습니다. 

 

MISSISSIPPI 경우의 수 

이것을 얼마나 많은 조합을 만들 수 있을까요?

 

11!는 중복되는 수가 있기 때문에 아닙니다. 

 

C(11, 2)

C(9, 4)

C(5, 4)

 

이런 식으로 각각 순서를 정해주면 됩니다 .

 

따라서 이것을 곱하면 나옵니다. 

 

그럼 SUCCESS 는 어떻게 해야 할까요? 

S 가 3개, C가 2개, E가 1개, U가 1개입니다.

 

C(7,3) * C(4,2) * C(2,1) * C(1,1) 해주시면 됩니다.