11-2 계수법칙과 순열

1. 기본 계수법칙

① 기본 계수법칙

  - 어떤 사건이 일어나는 방법이 전부 m가지일 때, 그 사건이 일어나는 '경우의 수'를 m가지라고 함.

  - 경우의 수에는 곱의 법칙과 합의 법칙이 있음

 

② 곱의 법칙

  - 사건 A,B가 동시에 발생할 경우의 수

  - 하나의 작업이 n개의 연속된 작업으로 이루어진 경우에 사용(그리고, ~이고)

  - 두 사건 A,B가 일어날 경우의 수가 N(A) = n, N(B) = m일때, 동시에 일어날 경우의 수는 nXm임.

  - 4비트로 표현할 수 있는 이진수는 몇개인가? 2^4 = 16

 

③ 합의 법칙 

  - 사건 A또는 B가 발생할 경우의 수

  - 작업들이 서로 독립적인 경우 적용(또는, ~이거나) 

 

2. 순열

① 순열

  - 물체의 집합에서 일정한 개수를 선택하는 문제를 풀 때 사용할 수 있으며, 선택만 하는 것은 조합문제,

    선택한 수서도 고려해야하면 순열 문제

  - 이러한 순열과 조합은 다시 중복을 허용하는 경우와 허용하지 않는 경우로 나뉨.

 

  - 순열 :  서로 다른 n개의 원소 중 r개를 중복하지 않고 선택하여 순서대로 나열하는 것.

  - P(n,r) = n*(n-1)....(n-r+1) = n!/(n-r)!

 

② 같은 것이 있는 순열

  - 원소들은 많은 계수 문제에서 반복적으로 사용 가능

2. 중복순열

① 중복순열

  - n개의 원소를 갖는 집합에서 중복을 허용하고 순서를 고려해서 r개의 원소를 뽑는 경우의 수

     = n^r