알고리즘 수학적 개념 순열과 조합

순열과 조합

순열(順列, permutation)은 서로 다른 n개의 원소를 가지는 어떤 집합에서 중복 없이 순서에 상관있게 r개의 원소를 선택하거나 혹은 나열하는 것이다.

조합과 마찬가지로 n개의 원소로 이루어진 집합에서 r개의 원소로 이루어진 부분집합을 만드는 것과 같다.

순열은 조합과 달리 순서를 따져서 부분집합을 만든다.

 

과일 3개 집합에서 부분 집합 만들 수 있는 경우는 6가지 된다.

 

순열 공식

순열은 일반화 과정을 거쳐, Permutation의 약자 P로 표현한다.

N: 원소의 총 개수를 의미

R: 그중 뽑는 개수를 의미

중복을 허용하지 않기 때문에 반드시 R <= N을 만족해야 한다

 

---

조합

조합(組合, combination)은 서로 다른 n개의 원소를 가지는 어떤 집합에서 중복 없이 순서에 상관없게 r개의 원소를 선택하는 것이다.

n개의 원소로 이루어진 집합에서 r개의 원소로 이루어진 부분집합을 만드는 것과 같다.

조합은 순서에 상관없이 원소를 선택해 부분집합을 만든다.

 

 

사과 1개와 오렌지 1개가 있으면 하나의 경우의 수로 치기 때문에 과일 3개 집합에서 부분 집합 만들 수 있는 경우는 3가지 된다.

 

조합 공식