본문 바로가기

기타/수학

순열과 조합

순열

 

서로 다른 n 개의 원소에서 r 개를 뽑아 한 줄로 세우는 것

nPr = n x (n-1) x ...(n-r+1)  = n!/(n-r)!

순서 o

 

ex) 서로 다른 5개의 문자열 중 3개를 뽑아 문자열 만드는 것

a b c d e 중 3개를 뽑아 문자열을 만든 다고 하면

5 x 4 x 3 = 60 개의 문자열을 만들 수 있음

 

조합

 

서로 다른 n 개의 원소에서 r 개를 뽑는데 순서 상관이 없는 것

nCr = nPr / r! = n!/(r!(n-r)!)

 

ex) 서로 다른 5개의 문자열 중 3개만 뽑는 것. (순서 상관 없음)

만약에 a b c d e 에서 a,b,c 를 뽑는다고 하면

순열의 경우에는 

a b c , a c b, b a c, b c a, c a b, c b a

이렇게 6가지 경우 ( = 3!) 는 모두 다른 것.

그러나 조합에선 위 경우는 모두 1가지로 같은 경우로 봄.

 

그래서 5개에서 3개를 뽑아 순서있는 문자열을 만든다음 6으로 나눠줌

5 x 4 x 3 / 3 x 2

 

같은 문자가 있는 문자열의 조합은 어떻게 구하는가 ?

 

ex) a a b b b c

 

여기서도 마찬가지

각 문자열을 다 다르다고 생각하고 조합을 구한다면

ex) a1 a2 b1 b2 b3 c

    a2 a1 b2 b1 b3 c

     .....

모두 다른 경우임

 

그러나 실제로 같은 경우로 생각하기 때문에

각 문자열의 경우의 수를 나눠준다.

a 2개로 만들 수 있는 문자열 조합 수 -> 2!

b 3개로 만들 수 있는 문자열 조합 수 -> 3!

 

5!/(2! x 3!) = 10 가지임