경우의 수 확률 세기

곱셉의 법칙

이와 같은 메뉴를 보고 각각 하나를 주문하고 싶다고 생각을 해봅시다.

 

이 경우에 3 * 3 * 4 = 24개가 될 것입니다. 

 

원소가 m개의 집합에서 원소가 n개인 집합으로의 1대1 함수

• m > n : 1 대 1 함수가 존재할 수 없습니다.
• m <= n : 정의역의 원소를 a1 ~ am이라고 하면 a1에서 상을 선택할 수 있는 방법은 n가지입니다. a2에서는 n-1가지, a3에서는 n-2가지... am에서는 n-m+1 입니다.

결국 가능한 모든 가지 수는 n(n-1)(n-2) ... (n-m+1) 입니다.

 

 

비둘기집 원리

4개의 공간에 6개의 공을 넣어야 한다면 우리는 필연적으로 2개 이상의 공이 들어가는 1개 이상의 공간이 있다는 것을 알 수 있습니다. 

 

이것이 처음의 비둘기집의 원리입니다. 

 

n개의 공이 k개의 장소에 들어가야 할 때 k < n, 어떤 공간은 2개 이상의 공을 가지는 곳이 있다는 것입니다.