순열과 조합
수학이야기/확률통계
2007. 9. 19. 15:53
비밀번호와 같이 쓰여진 순서에 따라 다른 것이 있는가하면 집합의 원소와 같이 순서가 달라도 같은 것이 있다. 이처럼 무엇인가를 배열하거나 선택하는 경우의 수를 쉽게 구하기 위해 순열과 조합을 정의한다. 먼저 순서가 있는 서로 다른 $n$개의 수를 일렬로 나열하는 방법을 순열이라고 하고 ${}_n P_{n}$으로 적는다. 직관적으로 ${}_n P_{n}=n\times(n-1)\times(n-2)\times\cdots\times 3\times2\times1$임을 알 수 있는데 이를 편하게 적기 위해 계승 함수(factorial function)를 아래와 같이 정의한다. $$n!=\cases{1\quad \quad\quad \quad \quad \quad (n=0)\\n\times(n-1)! \;\quad (..