자연계열 1번

한 번 시행으로 일어날 수 있는 사건의 가짓수를 경우의 수라고 하며, 경우의 수의 계산은 확률 및 통계 분야의 문제해결에 필수적 요소이다. 경우의 수의 계산에는 일반적으로 순열과 조합의 수의 계산이 필요하며 이 계산에서 다음과 같은 논리적 오류가 발생할 수 있다.＊ [누락]: 일부 경우를 누락하여 세는 오류.＊ [중복]: 같은 경우를 중복하여 세는 오류.다음은 경우의 수를 계산하는 주요한 두 가지 방법이다.1) 직접계산: 가능한 경우를 중복 또는 누락되지 않게 나열하여 계산하는 방법2) 점화식계산: 집단의 개수 및 종류의 개수를 늘이거나 줄일 때 생기는 경우의 수들의 관계식을 통하여 계산하는 방법.

(가) 직접계산에 의한 순열 및 조합의 수의 계산:(순열) $\displaystyle n$명의 학생 중에서 $\displaystyle k$명의 학생을 차례로 선발하는 방법을 순열이라고 한다. 이 순열의 수를 $\displaystyle P(n,k)$라고 하자. 첫 번째 학생을 선발하는 방법은 $\displaystyle n$가지, 그리고 두 번째 학생을 선발하는 방법은 $\displaystyle (n-1)$가지, 이 과정을 연속적으로 반복하면, 마지막 $\displaystyle k$번째 학생을 선발하는 방법은 $\displaystyle (n-k+1)$ 가지이다. 따라서 순열의 수는$\displaystyle P(n,k)=n(n-1)\cdots(n-k+1)=\frac{n!}{(n-k)!}$이 된다. 단, $\displaystyle n\ge k$이며 $\displaystyle m!=m(m-1)\cdots1$, $\displaystyle 0!=1$이다.(조합) $\displaystyle n$명의 학생 중에서 $\displaystyle k$명의 학생을 선발하는 방법을 조합이라고 한다. 이 조합의 수를 $\displaystyle C(n,k)$라고 하자. $\displaystyle n$명의 학생 중에서 $\displaystyle k$명의 학생을 선발하고, 선발된 $\displaystyle k$명의 학생을 순서대로 나열하는 방법의 수가 $\displaystyle P(n,k)$와 같다는 사실로부터 $\displaystyle C(n,k)\,k!=P(n,k)$이다. 따라서$\displaystyle C(n,k)=\frac{P(n,k)}{k!}=\frac{n!}{(n-k)!\,k!}$가 된다. 단 $\displaystyle n\ge k$이다.(중복조합) 중복조합은 예를 들어 설명한다. 모두 10그릇의 자장면, 짬뽕, 우동을 주문할 때 (우동만 10그릇을 주문할 수도 있다), 서로 다른 주문방법의 수 $\displaystyle H(10,3)$을 구하는 문제를 생각해 보자. 이 문제의 해는 12칸의 빈 주문표에서 2칸를 선택하는 방법의 수와 동일하다: 즉, 표1과 같이 두 칸이 선택된 경우는, 표2와 같이 빈칸에 자장면, 짬뽕, 우동을 순서대로 기입하여 자장면(3그릇), 짬뽕(5그릇), 우동(2그릇)을 주문하는 경우로 이해하면 된다. 따라서, $\displaystyle H(10,3)=C(10+2,2)$이다.

일반적으로 $\displaystyle k$종류의 음식에서 $\displaystyle n$그릇을 주문하는 방법의 수 $\displaystyle H(n,k)$는$\displaystyle H(n,k)=C(n+k-1,k-1)$이 된다. 이때 $\displaystyle n$이 $\displaystyle k$ 보다 같거나 클 필요는 없다.

(나) 점화식에 의한 순열 및 조합의 수 계산:(순열) $\displaystyle n$명의 학생 중에서 $\displaystyle k$명의 학생을 차례로 선발하는 방법의 수는, $\displaystyle n$명의 학생 중에서 $\displaystyle (k-1)$명의 학생을 차례로 선발한 후, 남은 $\displaystyle (n-k+1)$명의 학생 중에서 한명을 더 선발하는 방법의 수와 같다. 따라서$\displaystyle P(n,k)=(n-k+1)P(n,k-1)$이 된다. 그런데 $\displaystyle P(n,1)=n$이므로 $\displaystyle P(n,k)=(n-k+1)(n-k+2)\cdots n$ 이 성립한다.(조합) $\displaystyle n$명의 학생 중에서 $\displaystyle k$명의 학생을 선발하는 방법의 수는, 학생 1명을 정해서, 그 학생이 선발된 경우와 선발되지 않은 경우로 나누어 계산할 수 있다. 즉, $\displaystyle (n-1)$명에서 $\displaystyle (k-1)$명을 선발하는 방법의 수와 $\displaystyle (n-1)$명에서 $\displaystyle k$명을 선발하는 방법의 수의 합이다. 따라서$\displaystyle C(n,k)=C(n-1,k)+C(n-1,k-1)$이 된다. 모든 자연수 $\displaystyle j$에 대하여 $\displaystyle C(j,1)=j$, $\displaystyle C(j,j)=1$ 이며, 이를 이용하여 $\displaystyle C(n,k)$을 구한다.(중복조합) 앞의 예와 같이 설명한다. 자장면, 짬뽕, 우동 10그릇을 주문하는 방법은 우동의 수에 따라 다음의 10가지의 경우로 분류 할 수 있다. 우동이 하나도 없는 경우 자장면 및 짬뽕에서 10개를 주문하므로 방법의 수는 $\displaystyle H(10,2)$, 우동이 하나만 있는 경우 자장면 및 짬뽕에서 9개를 주문하므로 방법의 수는 $\displaystyle H(9,2)$, 이 과정을 반복하여 마지막으로 모두가 우동인 경우 방법의 수는 $\displaystyle H(0,2)$이 된다. 따라서$\displaystyle H(10,3)=H(10,2)+H(9,2)+\cdots+H(0,2)=\sum_{j=0}^{10}H(j,2)$이 된다. 그리고 $\displaystyle k$종류의 음식에서 $\displaystyle n$그릇을 주문하는 방법의 수는$\displaystyle H(n,k)=\sum_{j=0}^{n}H(j,k-1)$이다. 모든 자연수 $\displaystyle j$에 대하여 $\displaystyle H(0,j)=1$, $\displaystyle H(1,j)=j$ 이며, 이를 이용하여 $\displaystyle H(n,k)$을 구한다.