순열(Permutation)과 조합(Combination)

오늘은 순열과 조합에 대해서 정리해보려 합니다.

경우의 수는 알고리즘을 풀 때 자주 나오는 개념이기도 하고 설명해보라고 하면

막상 순열은 ... 순서가 중요하고 조합은 순서가 중요하지 않고? 딱 요 정도로 밖에 말을 못 하더라고요.

이해되지 않는 부분이 있다고 해서 횡설 수설 늘여놓는 것보다는
어떤 부분이 이해되지 않는다면 그것을 사람들과 이야기하고 설명할 수 있게 다시 시도해보세요.

완벽하게 설명할 줄 모르면 모르는 것이라고 하셨던 Joe Bliztzstein교수님..ㅇㅈ

---

순열 Permutation

순열은 서로 다른 n개 중에서 r개를 선택하는 경우의 수입니다.

순열은 순서가 중요합니다.

 

공식은 아래와 같습니다. 

서로 다른 n개 중에서 r개를 선택하는 경우의 수를 구하는 예를 들어보겠습니다.

ex) 4명 중 2명을 뽑아서 첫 번째로 뽑힌 사람에게는 아이맥을 주고

두 번째로 뽑힌 사람에게는 아이패드를 줍니다. (상상만 해도 좋음)

여기서 뽑는 경우의 수를 구할 때 위 순열 공식을 사용해봅니다.

 

그런데 왜? 순열 공식을 사용하시는지 즉 왜 순서가 중요한지 느낌 오셨나요? 

1등한테는 아이맥을 주고 2등한테는 아이패드를 줍니다.

1등한테 아이패드를 주고 2등에게 아이맥을 주는 거랑 엄연히 다릅니다.

 

순서가 중요합니다. (1등 무조건 아이맥 받아야죠.)

 

다시 공식에 적용해봅니다. 

서로 다른 4명 중에서 순서대로 2명을 뽑아서 선물을 줄 거니깐 아래와 같이 풀 수 있습니다.

 

총 12가지의 경우의 수가 나오게 됩니다.

 

 

조합 Combination

조합은 서로 다른 n개 중에서 r개를 선택하는 경우의 수입니다.

얼핏 순열과 개념이 비슷해 보이지만 다릅니다.

조합은 순서가 중요하지 않습니다. 

 

공식은 아래와 같습니다.

서로 다른 n개 중에서 r개를 선택하는 경우의 수를 구하는 예를 들어보겠습니다.

ex) 4명 중 2명을 뽑아서 아이맥을 준다고 해봅시다. (상상만 해도 좋음)

여기서 뽑는 경우의 수를 구할 때 위 조합 공식을 사용해봅니다.

 

여기서는 왜? 조합 공식을 사용하시는지 즉 왜 순서가 필요 없는지 느낌 오셨나요?

순열은 1등한테는 아이맥을 주고 2등한테는 아이패드를 줍니다. 

조합은 두 명을 뽑아서 아이맥을 줍니다. 

(1등 2등의 개념도 없죠. 순서는 필요 없습니다.)

 

공식에 적용해보겠습니다.

서로 다른 4명 중에서 2명을 뽑아서 선물을 줄 거니깐 아래와 같이 풀 수 있습니다.

총 6가지의 경우의 수가 나오게 됩니다.

 

순열과 조합은 서로 다른 n개 중에서 r개를 선택하는 경우의 수로 비슷해 보이지만 순서가 중요한지의 여부에 따라서 다르다는 점.