순열
서로 다른 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 가지임