수열에 대한 생성함수_{(generating function)}를 이용하면, 이산적으로 정의된 수열의 성질을 주어진 생성함수를 해석적 도구를 통해 분석함으로써 유도해 낼 수 있다.

$ $

정의 2.2.1. 일반생성함수_{(ordinary generating function)}

주어진 수열 $(a_n)$에 대하여 무한급수 형태의 함수 \[ G(a_n;\, x) = \sum_{n=0}^{\infty} a_n x^n = a_0 + a_1x + a_2x^2 + \cdots \] 를 $(a_n)$의 일반생성함수_{(ordinary generating function)}라 한다.

$ $

참고. 생성함수는 무한급수의 수렴성에 관한 문제는 고려하지 않는 형식적 무한급수_{(formal power series)}이다. $ $

$ $

예제 2.2.2.
Q. 다음 수열 $(a_n)$에 대한 생성함수를 구하여라.

1. $a_n = 1 \quad (n \geq 0)$
2. $a_n = n \quad (n \geq 0)$
3. $a_n = \binom{m}{n} \quad (n \geq 0)$
4. $a_n = 1,\, 0,\, 1,\, 0,\, \ldots \quad (n \geq 0)$

A.

1. 등비수열의 합 공식을 이용하면 \[ G(a_n;\, x) = \sum_{n=0}^{\infty} x^n = \frac{1}{1 - x}. \]
2. 앞의 $\myblue{(1)}$에 의하여 \begin{align*} G(a_n;\, x) & = \sum_{n=0}^{\infty} n x^n = x \sum_{n=1}^{\infty} n x^{n-1} \\[1ex] & = x \bigg[ \sum_{n=0}^{\infty} x^n \bigg] = x \bigg[ \frac{1}{1 - x} \bigg] \\[1ex] & = \frac{x}{(1 - x)^2}. \end{align*}
3. 이항정리에 의해 \[ G(a_n;\, x) = \sum_{n=0}^{\infty} \binom{m}{n} x^n = (1 + x)^m. \]
4. 앞의 $\myblue{(1)}$를 응용하면 \[ G(a_n;\, x) = \sum_{n=0}^{\infty} x^{2n} = \sum_{n=0}^{\infty} (x^2)^{n} = \frac{1}{1 - x^2}. \tag*{$\myblue{\blacksquare}$} \]

$ $

예제 2.2.3.
Q. 다음 함수 \[ G(a_n;\, x) = \sqrt{1 - x} \] 는 어떤 수열 $(a_n)$의 생성함수이다. $(a_n)$을 구하여라.
A. 일반화된 이항정리에 의해 \begin{align*} G(a_n;\, x) & = \sqrt{1 - x} \\[1ex] & = \sum_{n=0}^{\infty} \binom{\frac{1}{2}}{n}(-x)^n = \sum_{n=0}^{\infty} \binom{\frac{1}{2}}{n}(-1)^n x^n. \end{align*} 따라서 $a_n = \binom{\frac{1}{2}}{n} (-1)^n$. $ $

$ $

정리 2.2.4. 생성함수의 성질

두 수열 $(a_n)$과 $(b_n)$의 생성함수를 각각 $G(a_n;\, x)$, $G(b_n;\, x)$라 하자.

1. $c_n = \alpha a_n + \beta b_n$으로 정의하면 \[ G(c_n;\, x) = \alpha G(a_n;\, x) + \beta G(b_n;\, x). \]
2. $c_0 = c_1 = \cdots = c_{k-1} = 0$, $c_n = a_{n-k}$로 정의하면 \[ G(c_n;\, x) = x^k G(a_n;\, x). \]
3. $\displaystyle c_n = \sum_{k=0}^{n} a_k b_{n-k}$로 정의하면 \[ G(c_n;\, x) = G(a_n;\, x) G(b_n;\, x). \]
4. $\displaystyle c_n = \sum_{k=0}^{n} a_k$로 정의하면 \[ G(c_n;\, x) = \frac{G(a_n;\, x)}{1 - x}. \]

$ $

예제 2.2.5.
Q. 다음 수열 $(a_n)$에 대한 생성함수를 구하여라.

1. $a_n = n^2 \quad (n \geq 0)$
2. $a_n = 1^2 + 2^2 + \cdots + n^2 \quad (n \geq 0)$

A.

1. 예제 2.2.3$\myblue{\text{(2)}}$에서 시작하자. \[ \frac{x}{(1 - x)^2} = \sum_{n = 0}^{\infty} n x^n. \] 위 식의 양변을 $x$에 대하여 미분하면 \[ \frac{1 + x}{(1 - x)^3} = \sum_{n = 1}^{\infty} n^2 x^{n-1}. \] 따라서 위 식의 양변에 $x$를 곱하여 $(a_n)$의 생성함수를 구할 수 있다. \[ \frac{x(1 + x)}{(1 - x)^3} = \sum_{n = 0}^{\infty} n^2 x^{n} = G(a_n;\, x). \]
2. 예제 2.2.4$\myblue{\text{(d)}}$에 의해 \[ G(a_n;\, x) = \frac{G(n^2;\, x)}{1 - x} = \frac{x(1 + x)}{(1 - x)^4}. \tag*{$\myblue{\blacksquare}$} \]

$ $

예제 2.2.6.
Q. 수열 $(a_n)$의 생성함수 $G(a_n;\, x)$가 주어졌을 때, $c_n = a_n - a_{n-1}$의 생성함수를 구하여라.
A. $(a_{n-1})$의 생성함수는 $x G(a_n;\, x)$이므로 \[ G(c_n;\, x) = G(a_n;\, x) - x G(a_n;\, x). \tag*{$\myblue{\blacksquare}$} \]

$ $

예제 2.2.7.
Q. 양의 정수 $n \in \mathbb{N}$에 대한 방정식 \[ x + y + z = n \] 이 주어졌다고 하자. 생성함수를 이용하여 다음 수열의 일반항을 구하여라.

1. $a_n$은 위 방정식의 음이 아닌 정수해 $(x,\, y,\, z)$의 개수
2. $a_n$은 $x \geq 1$, $y \geq 2$, $z \geq 3$을 만족하는 위 방정식의 음이 아닌 정수해 $(x,\, y,\, z)$의 개수
3. $a_n$은 $x \leq 3$을 만족하는 위 방정식의 음이 아닌 정수해 $(x,\, y,\, z)$의 개수 (단, $n \geq 4$)

A.

1. 주어진 조건을 만족하는 $(x,\, y,\, z)$의 개수는 다음 무한급수 \[ (1 + x + x^2 + \cdots )(1 + x + x^2 + \cdots )(1 + x + x^2 + \cdots ) \] 의 전개식에서의 $x^n$의 계수와 같다. 따라서 위의 무한급수가 수열 $(a_n)$의 생성함수 $G(a_n;\, x)$가 된다. 이제 일반화된 이항정리에 의해 \begin{align*} G(a_n;\, x) & = (1 + x + x^2 + \cdots )^3 \\[1ex] & = \frac{1}{(1 - x)^3} \\[1ex] & = \sum_{n=0}^{\infty} \binom{-3}{n} (-x)^n \\[1ex] & = \sum_{n=0}^{\infty} \binom{3 + n - 1}{n} x^n. \end{align*} 따라서 $a_n = \binom{3 + n - 1}{n} = {}_{3}H_{n}$을 얻는다.
2. 주어진 조건을 만족하는 $(x,\, y,\, z)$의 개수는 다음 무한급수 \[ (x + x^2 + x^3 + \cdots )(x^2 + x^3 + x^4 + \cdots )(x^3 + x^4 + x^5 + \cdots ) \] 의 전개식에서의 $x^n$의 계수와 같다. 따라서 위의 무한급수가 수열 $(a_n)$의 생성함수 $G(a_n;\, x)$가 된다. \begin{align*} G(a_n;\, x) & = \big[ x(1 + x + x^2 + \cdots ) \big] \big[ x^2(1 + x + x^2 + \cdots ) \big] \\[1ex] & \qquad \cdot \big[ x^3(1 + x + x^2 + \cdots ) \big] \\[1ex] & = x^6(1 + x + x^2 + \cdots )^3 \\[1ex] & = x^6 G({}_{3}H_{n};\, x). \end{align*} 따라서 정리 2.2.4$\myblue{\text{(b)}}$에 의해 \[ a_0 = a_1 = \ldots = a_5 = 0, \quad a_n = {}_{3}H_{n-6}. \]
3. 주어진 조건을 만족하는 $(x,\, y,\, z)$의 개수는 다음 무한급수 \[ (1 + x + x^2 + x^3)(1 + x + x^2 + \cdots )(1 + x + x^2 + \cdots ) \] 의 전개식에서의 $x^n$의 계수와 같다. 따라서 위의 무한급수가 수열 $(a_n)$의 생성함수 $G(a_n;\, x)$가 된다. \begin{align*} G(a_n;\, x) & = (1 + x + x^2 + x^3)(1 + x + x^2 + \cdots )^2 \\[1ex] & = \frac{1 - x^4}{1 - x} \cdot \frac{1}{(1 - x)^2} \\[1ex] & = \frac{1 - x^4}{(1 - x)^3} \\[1ex] & = G({}_{3}H_{n};\, x) - x^4G({}_{3}H_{n};\, x) \\[1ex] & = G({}_{3}H_{n};\, x) - G({}_{3}H_{n - 4};\, x) \end{align*} 따라서 $a_n = {}_{3}H_{n} - {}_{3}H_{n-4}$이다. $ $

$ $

예제 2.2.8.
Q. $10$개의 상자에 각각 다른 종류의 과일이 있다. 각 상자에서 $2$개에서 $4$개 사이의 과일을 선택하여 총 $30$개의 과일을 꺼내는 방법의 수를 구하여라.
A. 위 과일선택 문제에 대한 생성함수는 \[ (x^2 + x^3 + x^4)^{10} \] 이며, 위 생성함수의 $x^{30}$의 계수가 문제의 답이 된다. 위 식을 정리하면 \[ (x^2 + x^3 + x^4)^{10} = x^{20} (1 + x + x^2)^{10} \] 이므로 $(1 + x + x^2)^{10}$의 $x^{10}$의 계수를 찾으면 된다. 이 식을 좀 더 정리하면 \[ (1 + x + x^2)^{10} = \frac{(1 - x^3)^{10}}{(1 - x)^{10}} \] 이고 \begin{align*} (1 - x^3)^{10} & = \sum_{n = 0}^{10} \binom{10}{n} (-x)^n \\[1ex] \frac{1}{(1 - x)^{10}} & = \sum_{n=0}^{\infty} {}_{10}H_{n} x^n \end{align*} 이므로 $x^{10}$의 계수는 \[ \sum_{k=0}^{10} \binom{10}{k} (-1)^k {}_{10}H_{10-k}. \tag*{$\myblue{\blacksquare}$} \]

$ $

예제 2.2.9.
Q. 사과, 바나나, 포도, 수박의 네 종류의 과일이 있다고 하자. 이 중 다음 네 조건

• 사과는 항상 짝수 개수를 선택한다.
• 바나나는 $5$개 묶음으로만 선택한다.
• 포도는 최대 $4$개까지만 선택한다.
• 수박은 최대 $1$개를 선택한다.

을 만족하도록 $10$개의 과일을 선택하는 경우의 수는?
A. 사과, 바나나, 포도, 수박을 조건에 맞게 선택하는 경우의 수에 대한 생성함수는 각각 다음과 같다. \begin{align*} A(x) & = 1 + x^2 + x^4 + \cdots = \frac{1}{1 - x^2}, \\[1ex] B(x) & = 1 + x^5 + x^{10} + \cdots = \frac{1}{1 - x^5}, \\[1ex] C(x) & = 1 + x + x^2 + x^3 + x^4 = \frac{1 - x^5}{1 - x}, \\[1ex] D(x) & = 1 + x. \end{align*} 그러므로 주어진 조건을 만족하도록 $n$개의 과일을 선택하는 경우의 수 $(a_n)$에 대한 생성함수는 \begin{align*} A(x)B(x)C(x)D(x) & = \frac{1}{1 - x^2} \cdot \frac{1}{1 - x^5} \cdot \frac{1 - x^5}{1 - x} \cdot (1 + x) \\[1ex] & = \frac{1}{(1 - x)^2} \\[1ex] & = \sum_{n=0}^{\infty} {}_{2}H_{n} x^n \\[1ex] & = \sum_{n=0}^{\infty} (n+1) x^n \end{align*} 을 얻는다. 따라서 수열 $(a_n)$의 일반항이 $a_n = n+1$이므로 $a_{10} = 11$가지임을 알 수 있다. $ $

$ $

양의 정수 $n$에 대하여, $n$의 분할수 $p(n)$에 대한 생성함수를 구해보자. 앞서 정리 1.5.10에서 $p(n)$의 개수는 다음 방정식 \[ x_1 + 2x_2 + 3x_3 + \cdots nx_n = n \] 의 음이 아닌 정수해 $(x_1,\, x_2,\, \ldots,\, x_n)$과 같음을 확인했었다. 이제 각각의 $k = 1,\, 2,\, \ldots,\, n$에 대하여 $y_k = kx_k$로 정의하면 \[ y_1 + y_2 + y_3 + \cdots + y_n = n \] 이고 각각의 $y_k$가 가질 수 있는 값들은 \[ y_k = 0,\, k,\, 2k,\, 3k,\, \ldots \] 이므로 $p(n)$에 대한 생성함수는 \begin{align*} G(p(n);\, n) & = \prod_{k=1}^{n} (1 + x^k + x^{2k} + x^{3k} + \cdots) \\[1ex] & = \prod_{k=1}^{\infty} \frac{1}{1 - x^k} \end{align*} 이다. 위 급수를 실제로 급수전개 하면 \[ G(p(n);\, n) = 1 + x + 2x^2 + 3x^3 + 5x^4 + 7x^5 + 11x^6 + \cdots \] 가 되어 $x^n$의 계수가 분할수 $p(n)$과 일치함을 알 수 있다.

$ $

또한 생성함수를 이용하여 분할에 대한 오일러의 정리, 정리 1.5.9$\myblue{\text{(d)}}$를 증명할 수 있다.

$ $

정리 2.2.10. 분할에 대한 오일러의 정리

양의 정수 $n$에 대하여, 각 부분이 홀수인 $n$의 분할의 수는, 각 부분이 서로 다른 $n$의 분할의 수와 같다.

$ $

증명. 각 부분이 홀수인 $n$의 분할의 수를 $p_o(n)$, 각 부분이 서로 다른 $n$의 분할의 수를 $p_d(n)$으로 나타내자. 먼저 $p_d(n)$의 개수는 다음 방정식 \[ x_1 + 2x_2 + 3x_3 + \cdots nx_n = n \] 에서 모든 $x_k$가 $0$ 또는 $1$의 값을 갖는 음이 아닌 정수해 $(x_1,\, x_2,\, \ldots,\, x_n)$의 개수와 같다. 따라서 \[ G(p_d(n);\, x) = \prod_{i=1}^{\infty} (1 + x^k) \] 를 얻는다. 한편, $p_o(n)$의 개수는 다음 방정식 \[ x_1 + 3x_3 + 5x_5 + \cdots = n \] 의 음이 아닌 정수해 $(x_1,\, x_3,\, x_5, \ldots)$의 개수와 같다. 이를 이용하면 \begin{align*} G(p_o(n);\, x) & = \prod_{k=1}^{\infty} (1 + x^{2k-1} + x^{2(2k-1)} + x^{3(2k-1)} + \cdots) \\[1ex] & = \prod_{k=1}^{\infty} \frac{1}{1 - x^{2k-1}} \end{align*} 이다. 이제 간단한 계산을 통해 \begin{align*} G(p_d(n);\, x) & = \prod_{i=1}^{\infty} (1 + x^k) \\[1ex] & = (1+x)(1+x^2)(1+x^3)(1+x^4) \cdots \\[1ex] & = \frac{\cancel{1-x^2}}{1-x^{\phantom{1}}} \cdot \frac{\cancel{1-x^4}}{\cancel{1-x^2}} \cdot \frac{\cancel{1-x^6}}{1-x^3} \cdot \frac{\cancel{1-x^8}}{\cancel{1-x^4}} \cdots \\[1ex] & = \frac{1}{1-x} \cdot \frac{1}{1-x^3} \cdot \frac{1}{1-x^5} \cdots \\[1ex] & = \prod_{k=1}^{\infty} \frac{1}{1 - x^{2k-1}} \\[1ex] & = G(p_o(n);\, x) \end{align*} 임을 알 수 있다. 즉, $p_d(n)$과 $p_o(n)$의 생성함수가 같으므로 모든 $n$에 대하여 $p_d(n) = p_o(n)$임을 알 수 있다. $ $

$ $

이번에는 생성함수를 이용하여 선형동차점화식의 해를 구하는 방법을 살펴보자. 먼저 다음 정리를 증명 없이 받아들이기로 하자.

$ $

정리 2.2.11.

$c_1,\, c_2,\, \ldots,\, c_k$가 상수이고 $c_k \neq 0$일 때, 수열 $(a_n)$의 점화식 \[ a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots c_k a_{n-k} \quad (n \geq k) \] 을 만족한다고 하자. $(a_n)$의 특성다항식을 $C(t)$라 하면 \[ G(a_n;\, x) = \frac{g(x)}{x^k C\big( \frac{1}{x} \big)} \] 가 성립한다. 여기서 $g(x)$는 차수가 $k-1$ 이하인 $x$에 관한 다항식이다.

$ $

참고. 특성다항식 $C(t)$의 정의에 의해 \begin{align*} x^k C\big( \frac{1}{x} \big) & = x^k \Big( \frac{1}{x^k} - \frac{c_1}{x^{k-1}} - \frac{c_2}{x^{k-2}} - \cdots - \frac{c_{k-1}}{x} - c_k \Big) \\[1ex] & = 1 - c_1x - c_2x^2 - \cdots - c_{k-1}x^{k-1} - c_kx^k \end{align*} 이다. $ $

$ $

정리 2.2.11.에 의해 \[ g(x) = G(a_n;\, x) \Big( x^k C\big( \tfrac{1}{x} \big) \Big) \] 로 나타낼 수 있고, $(a_n)$의 초기값 $a_0,\, \ldots,\, a_{k-1}$을 이용하면 \[ g(x) = (a_0 + a_1x + a_2x^2 + \cdots a_{k-1}x^{k-1} + \cdots )\Big( x^k C\big( \tfrac{1}{x} \big) \Big) \] 이므로 위 식의 우변을 계산하여 차수가 $(k-1)$차 이하인 항을 취한 것이 $g(x)$가 된다. 이렇게 구한 $g(x)$를 이용하여 $G(a_n;\, x)$를 구할 수 있다.

$ $

예제 2.2.12.
Q. 수열 $(a_n)$에 대한 점화식 \[ a_n = 2a_{n-1} + a_{n-2} - 2a_{n-3} \] 과 초기값 $a_0 = 1$, $a_1 = 3$, $a_2 = -5$가 주어졌을 때, 수열 $(a_n)$의 일반항을 구하여라.
A. 초기조건과 특성다항식을 이용하면 \begin{align*} G(a_n;\, x) & = 1 + 3x - 5x^2 + \cdots \\[1ex] x^3 C\big( \tfrac{1}{x} \big) & = 1 - 2x - x^2 + 2x^3 \end{align*} 이므로 정리 2.2.11.에 의해 \begin{align*} g(x) & = G(a_n;\, x) x^3 C\big( \tfrac{1}{x} \big) \\[1ex] & = (1 + 3x - 5x^2 + \cdots) (1 - 2x - x^2 + 2x^3) \\[1ex] & = 1 + x - 12x^2 + \cdots \end{align*} 에서 차수가 $2$차 이하인 항을 취한 $g(x) = 1 + x - 12x^2$이 된다. 이를 이용하면 \begin{align*} G(a_n;\, x) & = \frac{g(x)}{x^3 C\big( \tfrac{1}{x} \big)} \\[1ex] & = \frac{1 + x - 12x^2}{1 - 2x - x^2 + 2x^3} \\[1ex] & = \frac{1 + x - 12x^2}{(x - 1)(x + 1)(2x - 1)} \\[1ex] & = \frac{-5}{x - 1} + \frac{-2}{x + 1} + \frac{2}{2x - 1} \\[1ex] & = \frac{5}{1 - x} - \frac{2}{1 - (-x)} - \frac{2}{1 - 2x} \\[1ex] & = 5 \sum_{n=1}^{\infty} x^n - 2 \sum_{n=1}^{\infty} (-x)^n - 2 \sum_{n=1}^{\infty} (2x)^n \\[1ex] & = \sum_{n=1}^{\infty} \big( 5 - 2(-1)^n - 2^{n+1} \big) x^n. \end{align*} 따라서 $a_n = 5 - 2(-1)^n - 2^{n+1}$이다. $ $

$ $

예제 2.2.13.
Q. 수열 $(a_n)$에 대한 점화식 \[ a_n = 2a_{n-1} - a_{n-2} \] 과 초기조건 $a_0 = 0$, $a_1 = 1$이 주어졌을 때, 수열 $(a_n)$의 일반항을 구하여라.
A1. 주어진 수열에 대한 특성다항식은 \[ C(t) = t^2 - 2t + 1 = (t - 1)^2 \] 이므로 $C(t) = 0$은 중근 $t = 1$을 갖는다. 따라서 다음 수열 \[ \big( (\beta_0 + \beta_1n) 1^n \big) = (\beta_0 + \beta_1) \] 은 주어진 점화식을 만족한다. 이제 주어진 초기조건 $a_0 = 0$, $a_1 = 1$을 이용하여 다음 선형연립방정식 \[ \systeme[\beta_0\beta_1]{\beta_0 = 0, \beta_0 + \beta_1 = 1} \] 을 풀면 $\beta_0 = 0$, $\beta_1 = 1$을 얻는다. 따라서 $(a_n)$의 일반항은 $a_n = n$이다.

A2. $x^2C \big(\frac{1}{x}\big) = 1 - 2x + x^2$이므로 \[ g(x) = (0 + x + \cdots)(1 - 2x + x^2) = x + \cdots \] 로부터 $g(x) = x$가 되어야 함을 알 수 있다. 그러므로 \begin{align*} G(a_n;\, x) & = \frac{x}{1 - 2x + x^2} \\[1ex] & = \frac{x}{(1 - x)^2} \\[1ex] & = \frac{1}{(1 - x)^2} + \frac{1}{1 - x} \\[1ex] & = \sum_{n = 0}^{\infty} {}_{2}H_{n} x^n - \sum_{n = 0}^{\infty} x^n \\[1ex] & = \sum_{n = 0}^{\infty} ({}_{2}H_{n} - 1) x^n \\[1ex] & = \sum_{n = 0}^{\infty} n x^n. \end{align*} 따라서 $(a_n)$의 일반항은 $a_n = n$이다. $ $

$ $