02. 조합(Combination)

 

2. 1. 조합(Combination)

- 서로 다른 n개에서 순서를 생각하지 않고 r(n ≥ r) 개를 택하는 것을 _nC_r로 표현하고 조합(Combination)이라 부른다.

 

- _nC_r = _nP_r / r! = n! / r!(n - r)! .

 

- 순열의 수(Number of Permutation) = 조합의 수(Number of Combination) X 원소를 순서를 생각해 배열하는 방법의 수(n!).

 

- 순열은 순서를 생각하고, 조합은 순서를 생각하지 않고 단순히 뽑는 것을 말한다.

 

 

- 조합과 관련된 공식(Combination formula).

 

  1) _nC₀ = 1, _nC_n = 1, _nC₁ = n.

 

  2) _nC_r = _nC_{n – r} .

 

  3) _nC_r = _{n - 1}C_r + _{n - 1}C_{r - 1}.

 

 

- 적어도(at least)의 조건이 있다면 전체 경우의 수에서 반대인 경우를 뺀다.

 

 

- 도형문제와 관련된 공식.

 

  1) 직선의 개수(Number of straight line)(세 점이 일직선 위에 있지 않을 때): _nC₂ . [n은 점의 개수]

 

  2) 삼각형의 개수(Number of triangle)(세 점이 일직선 위에 있지 않을 때): _nC₃ . [n은 점의 개수]

 

  3) 평행사변형의 개수(Number of parallelogram): _nC₂ X _mC₂ . [n은 가로 평행선의 개수, m은 세로 평행선의 개수]

 

---

 

2. 2. 중복조합(Combination with repetition)

- 서로 다른 n개에서 순서를 생각하지 않고, 중복을 허락하여 r개를 택하는 것을 _nH_r로 표현하고 중복조합(Combination with repetition)이라 부른다.

 

- _nH_r = _{n + r - 1}C_r .

 

- 기명투표는 중복순열을, 무기명투표는 중복조합을 이용한다.

 

- 함수의 개수는 _nΠ_r , 일대일 함수는 _nP_r , 일대일 대응은 n! , x₁ < x₂ 이면 f(x₁) < f(x₂) 인 함수는 _nC_r , x₁ ≤ x₂ 이면 f(x₁) ≤ f(x₂) 인 함수는 _nH_r .

 

---