이산 수학 - 조합

□ 순열 (permutation) : 중복 X, 순서 O

- n원소 집합에서 k개의 원소 선택 시

중복을 허용하지 않고 순서를 주면 ‘k-순열’

경우의 수는 : P(n, k)로 표시

k번째 원소 선택시 ( n-k+1 )

n!/(n-k)!

□ 조합 (Combination) : 중복 X, 순서 X

- n원소 집합에서 k 원소 부분집합을 선택하는 것을 'k조합' 또는 'n-선택-k'라고 한다.

중복을 허용하지 않고 순서도 상관하지 않는다.

경우의 수는 : C(n, k)로 표시

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

□ 중복 순열 (permutation with repetition) : 중복 O : 순서 O

- n원소 집합에서 k개의 원소를 나열할 때 'k-중복 순열'

n-원소 집합이 있을 때 k중복 순열의 경우의 수는

□ 중복 조합 (combination with repetition) : 중복 O, 순서 X

- n원소 집합에서 k개의 원소를 선택할 때 중복은 허용하고 순서를 고려하지 않으면 k-중복조합

S'(n, k)는 C(n+k-1, k) 이렇게 적용 가능하며 이후 조합의 C(n, k)와 동일하게 풀면 된다.

중복과 순서에 유의하자!

□ 패턴과 분할

패턴 : 개체 n개가 있는데, 그중 개체 n1개는 형태 1이고, 개체 n2개는 형태 2이고 개체 nr 개는 형태 r이라 가정하자. 이때 개체 n개로 형성될 수 있는 서로 다른 유형(순열)의 개수는 다음과 같다.

n!/(n1!)(n2!)...(nr!)

즉 각 유형은 n!의 순열중에서 (n1!)(n2!)…(nr!) 번 나타난다.

분할 : n개의 원소를 갖는 집합을 k구획으로 분활하는 방법의 수는 S(n, k)이다.

S(n, k) = (k)S(n-1, k) + S(n-1, k-1) 이것을 죽어라 적용 시킨다.

s(7, 3) = 3s(6, 3) + s(6, 2) = 180+31

s(6, 3) = 3s(5, 3) + s(5, 2) = 39+21

s(5, 3) = 3s(4, 3) + s(3, 3) = 12+1

s(4, 3) = 3s(3, 3) + s(2, 2) = 3+1 s(6, 2) = 2s(5, 2) + s(5, 1) = 30+1

s(5, 2) = 2s(4, 2) + s(4, 2) = 14+7s(5, 2) = 2s(4, 2) + s(4, 1) = 14+1

s(4, 2) = 2s(3, 2) + s(3, 1) = 6+1 s(4, 2) = 2s(3, 2) + s(3, 1) = 6+1

s(3, 2) = 2s(2, 2) + s(2, 1) = 2+1 s(3, 2) = 2s(2, 2) + s(2, 1) = 2+1