[코딩테스트] 순열, 조합, 중복순열, 중복조합

1. 순열 (Permutation)

 

설명: 순서를 고려하며, 중복 없이 선택하는 경우.

• 공식:

 P(n, r) = \frac{n!}{(n-r)!} 

여기서  n 은 원소의 개수,  r 은 선택할 개수.

 

예제: 숫자 1, 2, 3 중에서 2개를 선택 (순서 고려).

• P(n, r) = n!/(n-r)!

• P(3, 2) =3!/(3-2)! = 6 

• 결과: 12, 13, 21, 23, 31, 32 (총 6개)

 

 

2. 조합 (Combination)

 

설명: 순서를 고려하지 않고, 중복 없이 선택하는 경우.

• 공식:

 C(n, r) = n!/r(n-r)!

 

예제: 숫자 1, 2, 3 중에서 2개를 선택 (순서 무시).

• C(3, 2) = 3! / 2 * (3-2)!= 3 

• 결과: 12, 13, 23 (총 3개)

 

3. 중복 순열 (Repetition Permutation)

 

설명: 순서를 고려하며, 중복을 허용하여 선택하는 경우.

• 공식:

 n^r 

여기서  n 은 원소의 개수,  r 은 선택할 개수.

 

예제: 숫자 1, 2, 3 중에서 2개를 중복 허용하여 선택 (순서 고려).

• 3^2 = 9 

• 결과: 11, 12, 13, 21, 22, 23, 31, 32, 33 (총 9개)

 

 

4. 중복 조합 (Repetition Combination)

 

설명: 순서를 고려하지 않고, 중복을 허용하여 선택하는 경우.

• 공식:

 C{\prime}(n, r) = C(n + r - 1, r) = \frac{(n + r - 1)!}{r!(n - 1)!} 

 

예제: 숫자 1, 2, 3 중에서 2개를 중복 허용하여 선택 (순서 무시).

• C{\prime}(3, 2) = C(3 + 2 - 1, 2) = C(4, 2) = \frac{4!}{2!(4-2)!} = 6 

• 결과: 11, 12, 13, 22, 23, 33 (총 6개)