4장 3절

#9. 4명의 아이에게 10개의 서로 다른 장난감을 나누어 주되, 첫 번째 아이는 1개 이상, 두 번째 아이는 2개 이상 주는 방법의 개수를 구하여라.

(풀이) 우선 문제를 바꾸어 "같은 종류"의 장난감을 나누어 주는 것으로 하고 풀어 보자. 이것은 다음과 같은 디오판투스 방정식의 음아닌 정수해의 개수를 구하는 문제로 볼 수 있다. \[ x_1 + x_2 + x_3 + x_4 = 10,\quad x_1 \ge 1,\; x_2 \ge 2 \] 답은 ${}_4H_7$이다. 이 문제를 생성함수를 써서 다음과 같이 풀 수도 있다. \begin{align*} g(x) &= (x+x^2+x^3+\cdots)(x^2 + x^3 + x^4 + \cdots) (1 + x + x^2 + \cdots)^2 \\[1.5ex] &= \frac{x^3}{(1-x)^4} \end{align*} 이제 $g(x)$의 $x^{10}$의 계수를 구하면 된다. 이것은 $(1-x)^{-4}$의 $x^7$의 계수와 같으므로 ${}_4H_7$이다. ✓

원래 문제는 "서로 다른" 장난감을 나누어 주는 것이므로 디오판투스 방정식 문제로 볼 수 없다. 지수생성함수를 이용하여 풀도록 하자. \begin{align*} G(x) &= \left(x + \frac{x^2}{2!} + \frac{x^3}{3!} + \cdots \right) \left(\frac{x^2}{2!} + \frac{x^3}{3!} + \frac{x^4}{4!} + \cdots \right) \left(1 + x + \frac{x^2}{2!} + \cdots \right)^2 \\[1.5ex] &= (e^x - 1)(e^x - x - 1)e^{2x} = e^{4x} -2e^{3x} + e^{2x} -xe^{3x} + xe^{2x} \end{align*} $G(x)$의 $x^{10}/10!$의 계수를 구하면 된다. 그런데 이 수는 상당히 크다. 계산을 쉽게 하기 위하여 문제를 바꾸어 장난감의 개수가 4인 경우에 대하여 답을 구해 보자. \[ 4^4 - 2\cdot 3^4 + 2^4 - 3^3\cdot 4 + 2^3\cdot 4 = 256 - 162 + 16 - 27\cdot 4 + 8\cdot 4 = 34 \]

(고찰 1) 경우의 수를 구하는 문제는 결국 어떤 집합의 원소의 개수를 구하는 것으로 볼 수 있다. 이 문제에서의 "집합"은 1,2,3,4를 원소로 하는 길이 10의 수열인데 이 수열에는 1이 1개 이상, 2가 2개 이상 나타나야 한다. 수열의 원소는 아이를 나타내고 수열의 원소의 위치는 장난감을 나타낸다.

장난감이 4개인 경우에 1이 1개 이상, 2가 2개 이상 나타나는 길이 4의 수열이 몇 개나 되는지 직접 세어 보기로 하자. 2가 3개, 1이 1개 있는 경우는 ${4 \choose 1} = 4$개이다. 2가 2개, 1이 2개인 경우는 ${4 \choose 2} = 6$개이다. 2가 2개, 1이 1개인 경우는 ${4\choose 2}\cdot{2\choose 1}\cdot 2 = 24$개이다. 이들을 모두 합하면 $4 + 6 + 24 = 34$가 된다.

(고찰 2) 이 문제에서 원소의 개수를 세어야 할 집합을 길이 4의 수열 $(s_1, s_2, s_3, s_4)$로 볼 수도 있다. 이 수열의 항은 장난감들의 집합이다. 수열이 만족해야 할 조건은 $|s_1| \ge 1$과 $|s_4| \ge 2$이다. 장난감이 4개 있는 경우에는 원소의 예로 $(\{3\}, \{2,4\},\{1\},\varnothing)$를 들 수 있다. 이것은 (고찰 1)의 표상을 따르면 $(3,2,1,2)$에 대응된다.

#10. 6명을 4개의 방에 다음과 같이 배치하는 방법의 수를 구하여라.

1. 각 방에 1명 이상 배치한다.
2. 특정한 2개의 방에는 각각 1명 이상씩 배치한다.

(고찰) '방'은 구별이 되는 것인지가 불분명하다. 책의 해답을 보면 구별 되는 것으로 간주한다는 것을 알 수 있다. 따라서 생성함수가 아니라 지수생성함수를 써야 한다.

(풀이) 문제 #9와 비교해 보면, 사람은 장난감에 대응되고 방은 아이에 대응된다. 왜냐하면 사람은 여러 명이 하나의 방에 배치될 수 있으며 장난감은 여러 개가 한 아이에게 주어질 수 있기 때문이다.

(1)에서의 지수생성함수는 $G(x) = (e^x - 1)^4$이다. ($(e^x - 1)^6$이 아니다.) $G(x)$의 전개식에서 $x^6/6!$의 계수를 구하면 된다.

(2)에서의 지수생성함수는 $G(x) = (e^x - 1)^2 e^{2x}$이다.

#11. 좌표평면의 원점에서 출발하여 오른쪽 또는 위쪽으로 1씩 움직이는 동점이 직선 $y=n-3x$에 이르는 방법의 수 $a_n$을 $n\ge 0$에 관한 식으로 나타내어라.

(풀이) 오른쪽으로 이동하는 것을 $r$, 위쪽으로 이동하는 것을 $u$로 나타내었을 때 $r$을 $k$개, $u$를 $n-3k$개 사용하여 이루어진 수열들을 $k=0,\ldots,\lfloor n/3 \rfloor$에 대하여 구하여 이들의 개수를 세면 $a_n$이 나올 것이다. 따라서 $a_n = \sum_{k=0}^{\lfloor n/3 \rfloor} {{n-2k}\choose k}$이다. 그런데 이것은 닫힌 형식이 아니다. 다른 풀이를 생각해 보자.

(고찰) 점화식을 사용해 보자. 초기조건은 $(a_0,a_1,a_2,a_3) = (1,1,1,2)$이다. $r,u$로 이루어진 수열이 $r$로 시작하는 경우와 $u$로 시작하는 경우로 나누어 생각한다. 좌표평면을 그려 생각해 보면 $r$로 시작할 때는 $a_{n-3}$개의 경로가 있다. $u$로 시작할 때는 $a_{n-1}$개의 경로가 있다. 따라서 점화식 \[ a_n = a_{n-1}+a_{n-3}\quad(n\ge 3) \] 을 얻는다. 이것은 동차선형점화식이다. 그런데 특성근은 1개의 실근과 2개의 복소근을 가지므로 계산이 많이 복잡해진다. 닫힌 형식의 일반항을 구하기는 쉽지 않다.

지수생성함수를 구하는 것도 원리적으로는 가능하지만 계산이 상당히 복잡하므로 현실적으로 어렵다.

점화식을 이용하여 $n=3,4,\ldots,20$까지 $a_n$을 구해 보라. (엑셀 사용) 그리고 $a_n = \sum_{k=0}^{\lfloor n/3 \rfloor} {{n-2k}\choose k}$을 wolframalpha.com을 이용하여 몇 개의 $n$에 대해서 계산하여 점화식을 사용하여 구한 값들과 일치함을 확인해 보자.

#12. 다음을 증명하여라.

1. $\sum_{n=0}^\infty a_n x^n \cdot \sum_{n=0}^\infty b_n x^n = \sum_{n=0}^\infty c_n x^n$일 때 $c_n = \sum_{k=0}^n a_n b_{n-k}$이다.
2. $\sum_{n=0}^\infty a_n x^n/n! \cdot \sum_{n=0}^\infty b_n x^n/n! = \sum_{n=0}^\infty c_n x^n/n!$일 때 $c_n = \sum_{k=0}^n {n \choose k} a_n b_{n-k}$이다.

(2)에서 $x^n/n!$의 계수는 $x^n$의 계수에 $n!$을 곱한 것임을 이용한다.

#19. 수열 $(1,2,3,4,5,5,5,\ldots)$의 생성함수를 구하여라.

(풀이) \begin{align*} g(x) &= 1 + 2x +3x^2 + 4x^3 + 5x^4(1+x+x^2 + \cdots) \\[1.5ex] &= h(x) + \frac{5x^4}{1-x},\text{ where} \\[1.5ex] h(x) &= 1 + 2x + 3x^2 + 4x^3 \\[1.5ex] x h(x) &= x + 2x^2 + 3x^3 + 4x^4 \\[1.5ex] (1-x)h(x) &= 1 + x + x^2 + x^3 - 4x^4 = \frac{1-x^4}{1-x} - 4x^4 = \frac{1 - 5x^4 + 4x^5}{1-x} \\[1.5ex] \therefore\; g(x) &= \frac{(1 - 5x^4 + 4x^5) + 5x^4 - 5x^5}{(1-x)^2} = \frac{1 - x^5}{(1-x)^2}\;\checkmark \end{align*}

#20. (1) $1+x + x^2 + x^3 + \cdots = \frac{1}{1-x}$의 양변을 미분하고 $x$를 곱한다. 이걸 다시 미분하여 (3)을 얻는다. (2)는 첫 등식의 양변을 2번 미분하여 얻는다.