자연계열 1번

(풀이) 자장면, 짬뽕, 우동을 반드시 하나씩 포함 하므로 자장면, 짬뽕, 우동에서 7인분을 주문하는 경우의 수와 같다. 따라서$\displaystyle H(7,3)=C(9,2)=\frac{9\times8}{2}=36$

(풀이) 빨간 구슬을 $\displaystyle R_{1}, R_{2}$ 라 두고, 푸른 구슬을 $\displaystyle B_{1}, B_{2}$ 라 두면 $\displaystyle C(4,2)$는 다음과 같은 경우의 수를 모두 센 결과이다:$\displaystyle (R_{1},R_{2}),\ (R_{1},B_{1}),\ (R_{2},B_{1}),\ (R_{1},B_{2}),\ (R_{2},B_{2}),\ (B_{1},B_{2})$이 중 $\displaystyle (R_{1},B_{1}),(R_{2},B_{1}),(R_{1},B_{2}),(R_{2},B_{2})$는 한 번만 세어져야 하는데 중복해서 세어졌다 (빨강구슬, 파란구슬 각각 1개인 경우에 해당).

(풀이1) 제시문에 주어진 식을 이용하면$\displaystyle H(n,k)=C(n+k-1,k-1)$이고 $\displaystyle C(n,k)=C(n-1,k)+C(n-1,k-1)$이므로$\displaystyle H(n,k)=C(n+k-1,k-1)=C(n+k-2,k-1)+C(n+k-2,k-2)=H(n-1,k)+H(n,k-1)$

(풀이2) 제시문의 점화식을 이용하면$\displaystyle H(n,k)=\sum_{j=0}^{n}H(j,k-1)=H(n,k-1)+\sum_{j=0}^{n-1}H(j,k-1)$$\displaystyle H(n-1,k)=\sum_{j=0}^{n-1}H(j,k-1)$이므로 $\displaystyle H(n,k)=H(n,k-1)+H(n-1,k)$ 을 만족한다.

(풀이3) $\displaystyle H(n,k)$가 $\displaystyle k$ 종류의 음식에서 $\displaystyle n$그릇을 주문하는 방법의 수이므로(a) 특정음식을 배제하고 주문하는 방법의 수: $\displaystyle H(n,k-1)$(b) 특정음식을 최소한 한 그릇 포함하는 주문방법의 수: $\displaystyle H(n-1,k)$로 나누어 계산할 수 있다. 두 경우를 더하면, $\displaystyle H(n,k)=H(n,k-1)+H(n-1,k)$ 을 만족한다.

(풀이1) 특정학생 1명, 학생 A라 하자, 을 제외한 $\displaystyle (n-1)$명의 학생으로 그룹을 만드는 방법은 다음 두가지 경우로 나누어 생각할 수 있다.(a) $\displaystyle (n-1)$명에서 $\displaystyle (k-1)$개의 그룹을 만드는 경우: 학생 A는 반드시 1명으로 이루어진 새 그룹을 만들어야 한다. 따라서 경우의 수는 $\displaystyle G(n-1,k-1)$(b) $\displaystyle (n-1)$명에서 $\displaystyle k$그룹을 만드는 경우: 학생 A는 $\displaystyle k$개의 그룹 어디에나 들어갈 수 있다. 따라서 경우의 수는 $\displaystyle kG(n-1,k)$ 이다.두 경우의 수를 합하면 $\displaystyle G(n,k)=G(n-1,k-1)+kG(n-1,k)$가 된다.

(풀이2) 특정학생 1명을 고려하여특정학생1명으로 단독 그룹을 구성하는 방법의 수: $\displaystyle G(n-1,k-1)$(특정학생1명 + 1명)으로 그룹을 구성하는 방법의 수: $\displaystyle C(n-1,1)\times G(n-2,k-1)$(특정학생1명 + 2명)으로 그룹을 구성하는 방법의 수: $\displaystyle C(n-1,2)\times G(n-3,k-1)$$\displaystyle \cdots$(특정학생1명 + $\displaystyle (n-k)$명)으로 그룹을 구성하는 방법의 수: $\displaystyle C(n-1,n-k)\times G(k-1,k-1)$이들 경우의 수를 모두 합하면$\displaystyle G(n,k)=\sum_{l=0}^{n-k}C(n-1,l)\times G(n-l-1,k-1)$

(풀이1) (1)에서 구한 점화식을 이용하는 방법$\displaystyle G(2,1)=1$, $\displaystyle G(2,2)=1$, 따라서$\displaystyle G(3,2)=G(2,1)+2G(2,2)=3$, $\displaystyle G(4,2)=G(3,1)+2G(3,2)=7$,$\displaystyle G(4,3)=G(3,2)+3G(3,3)=6$, $\displaystyle G(5,2)=G(4,1)+2G(4,2)=15$$\displaystyle G(5,3)=G(4,2)+3G(4,3)=25$, $\displaystyle G(6,3)=G(5,2)+3G(5,3)=90$$\displaystyle G(6,3)=90$ 이다.

(풀이2) 6명을 세 그룹으로 나눌 때 가능한 그룹의 크기는 1-1-4, 1-2-3, 2-2-2 이고 각 경우 가능한 그룹구성의 방법의 수는 다음과 같다:1-1-4 $\displaystyle \quad C(6,4)\times C(2,1)\times C(1,1)/2!=15$1-2-3 $\displaystyle \quad C(6,3)\times C(3,2)=20\times3=60$2-2-2 $\displaystyle \quad C(6,2)\times C(4,2)\times C(2,2)/3!=15$따라서 $\displaystyle G(6,3)=15+60+15=90$