정의 2.3.1. 지수생성함수_{(exponential generating function)}

주어진 수열 $(a_n)$에 대하여 무한급수 형태의 함수 \[ EG(a_n;\, x) = \sum_{n=0}^{\infty} \frac{a_n}{n!} x^n = \frac{a_0}{0!} + \frac{a_1}{1!}x + \frac{a_2}{2!}x^2 + \cdots \] 를 $(a_n)$의 지수생성함수_{(exponential generating function)}라 한다.

$ $

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

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

A.

1. 지수함수의 테일러 전개를 이용하면 \[ EG(a_n;\, x) = \sum_{n=0}^{\infty} \frac{x^n}{n!} = e^x. \]
2. 앞의 $\myblue{\text{(1)}}$에 의하여 \[ EG(a_n;\, x) = \sum_{n=0}^{\infty} \frac{n}{n!} x^n = x\sum_{n=1}^{\infty} \frac{x^{n-1}}{(n-1)!} = xe^x \] $a_n = n \quad (n \geq 0)$
3. 이항정리에 의해 \[ EG(a_n;\, x) = \sum_{n=0}^{\infty} \frac{{}_{m}P_{n}}{n!} x^n = \sum_{n=0}^{\infty} \binom{m}{n} x^n = (1 + x)^m. \]
4. 쌍곡코사인 $\cosh$ 함수의 테일러 전개에 의해 \[ EG(a_n;\, x) = \sum_{n=0}^{\infty} \frac{x^{2n}}{(2n)!} = \cosh(x) = \frac{e^x + e^{-x}}{2}. \]
5. 쌍곡사인 $\sinh$ 함수의 테일러 전개에 의해 \[ EG(a_n;\, x) = \sum_{n=0}^{\infty} \frac{x^{2n+1}}{(2n+1)!} = \sinh(x) = \frac{e^x - e^{-x}}{2}. \tag*{$\myblue{\blacksquare}$} \]

$ $

참고. 위의 예제 2.3.2의 $\myblue{\text{(4)}}$와 $\myblue{\text{(5)}}$의 양변을 각각 더해주면 $\myblue{\text{(1)}}$을 얻는다. 일반적으로 지수생성함수는 일반생성함수와 같이 선형성을 갖는다. $ $

$ $

정리 2.3.3. 지수생성함수의 성질

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

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

$ $

예제 2.3.4.
Q. 알파벳 $a,\, b,\, c$만을 사용하여 $n$자리 단어를 만든다고 하자. 이 때, $a$는 홀수 번, $b$는 짝수 번 사용된 $n$자리 단어의 개수를 $a_n$이라 할 때, 수열 $(a_n)$에 대한 지수생성함수를 구하고, 이를 이용하여 $(a_n)$의 일반항을 구하여라.
A. 예를 들어 $n = 9$라 하고, $a$를 $3$번, $b$를 $4$번, 그리고 $c$를 $2$번 사용하여 $9$자리 단어를 만드는 경우의 수는 중복순열 \[ \binom{9}{3,\, 4,\, 2} \] 와 같다. 따라서 위와 같이 가능한 모든 중복순열을 다 더한것이 $a_9$이 되게 된다. 이제 다음 무한급수 \[ \Big( \frac{x}{1!} + \frac{x^3}{3!} + \cdots \Big)\Big( 1 + \frac{x^2}{2!} + \frac{x^4}{4!} + \cdots \Big) \Big( 1 + \frac{x}{1!} + \frac{x^2}{2!} + \cdots \Big) \] 를 생각해 보자. 위 식의 각 항에서 $\frac{x^3}{3!}$, $\frac{x^4}{4!}$, $\frac{x^2}{2!}$을 각각 택하여 곱해주면 \[ \frac{x^3}{3!} \cdot \frac{x^4}{4!} \cdot \frac{x^2}{2!} = \frac{9!}{3! \cdot 4! \cdot 2!} \cdot \frac{x^9}{9!} = \binom{9}{3,\, 4,\, 2} \frac{x^9}{9!} \] 를 얻는다. 따라서 위 무한급수의 전개식에서 $\frac{x^9}{9!}$의 계수가 $a_9$이 될 것이다. 일반적으로 위 전개식에서 $\frac{x^n}{n!}$의 계수가 $a_n$이므로, 위 무한급수가 수열 $(a_n)$의 지수생성함수 $EG(a_n;\, x)$가 됨을 알 수 있다. \begin{align*} EG(a_n;\, x) & = \bigg( \sum_{n=0}^{\infty} \frac{x^{2n+1}}{(2n+1)!} \bigg) \bigg( \sum_{n=0}^{\infty} \frac{x^{2n}}{(2n)!} \bigg) \bigg( \sum_{n=0}^{\infty} \frac{x^n}{n!} \bigg) \\[1ex] & = \frac{e^x - e^{-x}}{2} \cdot \frac{e^x + e^{-x}}{2} \cdot e^x \\[1ex] & = \frac{1}{4}(e^{3x} - e^{-x}) \\[1ex] & = \frac{1}{4} \bigg(\sum_{n=0}^{\infty} \frac{(3x)^n}{n!} - \sum_{n=0}^{\infty} \frac{(-x)^n}{n!} \bigg) \\[1ex] & = \sum_{n=0}^{\infty} \frac{1}{4} (3^n - (-1)^n) \frac{x^n}{n!}. \end{align*} 따라서 수열 $(a_n)$의 일반항은 $a_n = \frac{1}{4} (3^n - (-1)^n)$이다. $ $

$ $

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

$ $

지수생성함수를 이용하여 제2종 스털링 수에 대한 일반항 \[ S(n,\, m) = \frac{1}{m!} \sum_{k=0}^{m} (-1)^{k} \binom{m}{k} (m-k)^n \] 을 구해보자. 12갈래 방법에서 $n$개의 서로 다른 공을 $m$개의 서로 다른 상자에 빈 상자가 없도록 넣는 방법의 수는 \[ m! S(n,\, m) \] 와 같음을 확인했었다. 이제 수열 $a_n = m!(Sn,\, m)$을 정의하자. 그러면 $a_n$은 $m$개의 서로 다른 알파벳을 이용하여 $n$자리 단어를 만들 때, 각 단어를 적어도 한 번씩 사용하는 경우의 수와 같다. 따라서 $(a_n)$의 지수생성함수는 \begin{align*} EG(a_n;\, x) & = \Big( x + \frac{x^2}{2!} + \frac{x^3}{3!} + \cdots \Big)^{m} \\[1ex] & = (e^x - 1)^{m} \\[1ex] & = \sum_{k=0}^{m} \binom{m}{k} e^{(m-k)x} (-1)^{k} \\[1ex] & = \sum_{k=0}^{m} \binom{m}{k} (-1)^{k} \bigg( \sum_{n=0}^{\infty} (m-k)^n \frac{x^n}{n!} \bigg) \\[1ex] & = \sum_{n=0}^{\infty} \bigg( \sum_{k=0}^{m} \binom{m}{k} (-1)^{k} (m-k)^n \bigg) \frac{x^n}{n!} \end{align*} 이므로, 수열 $(a_n)$의 일반항은 \[ a_n = \sum_{k=0}^{m} \binom{m}{k} (-1)^{k} (m-k)^n \] 이다. 이제 위 식의 양변을 $m!$으로 나누어 주면 \[ S(n,\, m) = \frac{1}{m!} \sum_{k=0}^{m} (-1)^{k} \binom{m}{k} (m-k)^n. \]

$ $

이번에는 벨수 $B(n)$에 대한 지수생성함수를 구해보자. 먼저 벨수에 관한 점화식 \[ B(0) = 1; \quad B(n+1) = \sum_{k=0}^{n} \binom{n}{k} B(k) \] 에서 시작하자. 위 식의 양변에 $\frac{x^n}{n!}$을 곱하고 $\displaystyle \sum_{n=0}^{\infty}$를 취하면 \[ \sum_{n=0}^{\infty} B(n+1) \frac{x^n}{n!} = \sum_{n=0}^{\infty} \bigg( \sum_{k=0}^{n} \binom{n}{k} B(k) \bigg) \frac{x^n}{n!} \tag*{$\myblue{(2.4)}$} \] 을 얻는다. 먼저 식 $\myblue{(2.4)}$의 좌변은 수열 $(B(n+1))$의 지수생성함수이므로, 정리 2.3.3 $\myblue{\text{(c)}}$에 의해 \[ \text{(좌변)} = \frac{d}{dx} EG(B(n);\, x) \] 가 성립한다. 한편, 식 $\myblue{(2.4)}$의 우변에서 \[ c_n = \sum_{k=0}^{n} \binom{n}{k} B(k) \] 라 정의하면, 정리 2.3.3 $\myblue{\text{(d)}}$에 의해 \[ EG(c_n;\, x) = EG(B(n);\, x) EG(1;\, x) \] 가 성립하므로 \[ \text{(우변)} = e^x EG(B(n);\, x) \] 임을 알 수 있다. 따라서 $y = EG(B(n);\, x)$라 하면 $y(x)$는 다음 미분방정식 \[ y' = e^x y, \quad y(0) = 0 \] 를 만족한다. 위 미분방정식을 풀면 $y = e^{e^x - 1}$이므로 벨 수 $B(n)$에 대한 지수생성함수는 \[ EG(B(n);\, x) = e^{e^x - 1} \] 이다.

$ $

예제 2.3.6.
Q. 교란순열 $D_n$에 대한 점화식 \[ n! = \sum_{k=0}^{n} \binom{n}{k} D_{k} \] 을 이용하여 $(D_n)$에 대한 지수생성함수를 구하고, 이를 이용하여 $(D_n)$의 일반항을 구하여라.
A. 주어진 점화식의 양변에 $\frac{x^n}{n!}$을 곱하고 $\displaystyle \sum_{n=0}^{\infty}$를 취하면 \[ \sum_{n=0}^{\infty} n! \frac{x^n}{n!} = \sum_{n=0}^{\infty} \bigg( \sum_{k=0}^{n} \binom{n}{k} D_{k} \bigg) \frac{x^n}{n!} \] 이다. 먼저 위 식의 좌변은 \[ \text{(좌변)} = \sum_{n=0}^{\infty} x^n = \frac{1}{1 - x} \] 으로 정리할 수 있다. 또한 우변에서 \[ c_n = \sum_{k=0}^{n} \binom{n}{k} D_{k} \] 라 정의하면, 정리 2.3.3 $\myblue{\text{(d)}}$에 의해 \[ EG(c_n;\, x) = EG(D_n;\, x) EG(1;\, x) \] 가 성립하므로 \[ \text{(우변)} = e^x EG(D_n;\, x) \] 임을 알 수 있다. 따라서 코시 곱_{(Cauchy product)} 공식에 의해 \begin{align*} EG(D_n;\, x) & = \frac{e^{-x}}{1 - x} \\[1ex] & = \bigg( \sum_{n=0}^{\infty} x^n \bigg) \bigg( \sum_{n=0}^{\infty} (-1)^n \frac{x^n}{n!} \bigg) \\[1ex] & = \sum_{n=0}^{\infty} \bigg( \sum_{k=0}^{n} \frac{(-1)^k}{k!} \bigg) x^n \\[1ex] & = \sum_{n=0}^{\infty} \bigg( n! \sum_{k=0}^{n} \frac{(-1)^k}{k!} \bigg) \frac{x^n}{n!} \end{align*} 를 얻는다. 그러므로 교란순열 $(D_n)$의 일반항은 \[ D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}. \tag*{$\myblue{\blacksquare}$} \]

$ $