[이산수학] 경우의 수, 순열, 조합

경우의 수

모든 경우를 일정한 기준에 따라 빠짐없이, 중복되지 않게 해야 한다. 경우의 수를 구하는 방법은 트리를 이용하는 방법, 표를 이용하는 방법이 있다.

합의 법칙

두 사건 A, B(A∩B = ∅)가 일어날 경우의 수를 n(A) = m, n(B) = n이라 하면, A 또는 B가 일어날 경우의 수는 m+n이다.

n(A∪B) = n(A) + n(B) = m+n

곱의 법칙

두 사건 A, B에서 n(A) = m, n(B) = n이라 하면, A, B가 동시에 일어날 경우의 수는 m•n이다.

n(A x B) = n(A) x n(B) = m•n

순열

서로 다른 원소들을 순서를 고려하여 일렬로 배열하는 것. 서로 다른 n개의 원소를 한 줄로 배열하는 순열의 수는 n!이라고 한다.

 

1부터 n까지의 모든 자연수의 곱을 n의 계승 또는 n factorial이라고 하며, 간단하게 n!로 쓴다

n! = n x (n-1) x (n-2) x ... 3 x 2 x 1

 

서로 다른 n개의 원소 중에서 r개를 택하는 순열의 수는 nPr이라고 나타낸다.

nPr = n x (n-1) x (n-2) x ... x (n-r+1) (단, 0 < r ≤ n)

nPr을 n!을 사용하여 나타내면 n! / (n-r)! 이 된다.

 

같은 것을 포함하는 순열의 경우에는 즉, n개 중에서 같은 것이 각각 p, q, r개씩 있을 때, n개를 일렬로 배열하여 만들 수 있는 순열의 수는 

n! / p! • q! • r! 단 ( p + q + r = n)

조합

서로 다른 n개의 원소 중에서 순서를 생각하지 않고 r개를 택할 때, 이것을 n개의 원소에서 r개를 택하 조합이라고 하며 nCr로 나타낸다. 

nCr = nPr / r! = n! / r!(n-r)! (단, 0 < r ≤ n)