Pigeon Hole Principle   비둘기집 원리

(2017-10-18)

Dirichlet Box Principle


1. 비둘기집 원리

  ㅇ n,k (n > k) 일 때, n 마리의 비둘기를 k 개의 비둘기집에 넣을때, 
     - 적어도 2 마리 이상 들어간 집이 있게 됨

  ㅇ 또는, n(A) > n(B) 이면, 
     - 유한 집합 A에서 B로 가는 단사 함수가 될 수 없음
        . 단사 함수 : B의 각 원소에 대응하는 A의 원소가 기껏해야 하나 만 갖을 때 (1:1 함수)

  ㅇ 비둘기집 원리는, 배열의 존재성 문제를 증명할 때 필요함

조합론/셈법(Counting)
   1. 조합론   2. 셈법   3. 치환   4. 순열   5. 조합   6. 경우의 수 계산 (요약)   7. 이항/다항 정리   8. 비둘기집 원리  


Copyrightⓒ written by 차재복 (Cha Jae Bok)               기술용어해설 후원
"본 웹사이트 내 모든 저작물은 원출처를 밝히는 한 자유롭게 사용(상업화포함) 가능합니다"