[조합론] 7. 점화식(4: 지수생성함수, 카탈란 수)

[조합론] 7. 점화식(4: 지수생성함수, 카탈란 수)

순열을 나타내는 \(_{n}P_{r}\)의 생성함수는$$_{n}P_{0}+\,_{n}P_{1}x+\,_{n}P_{2}x^{2}+\cdots+\,_{n}P_{n}x^{n}=\sum_{k=0}^{n}{\frac{n!}{(n-k)!}x^{k}}$$이다. 이 식의 좌변에서 각각의 계수에 대해 차례로 \(\displaystyle\frac{1}{0!},\,\frac{1}{1!},\,\frac{1}{2!},\,\cdots,\,\frac{1}{n!}\)을 곱하면$$\frac{_{n}P_{0}}{0!}+\frac{_{n}P_{1}}{1!}x+\frac{_{n}P_{2}}{2!}x^{2}+\cdots+\frac{_{n}P_{n}}{n!}x^{n}=\sum_{k=0}^{n}{\frac{n!}{k!(n-k)!}x^{k}}=\sum_{k=0}^{n}{\binom{n}{k}x^{k}}=(1+x)^{n}$$이 된다.

수열 \(a_{n}\)에 대하여 다음의 멱급수$$E(x)=\sum_{n=0}^{\infty}{a_{n}\frac{x^{n}}{n!}}=a_{0}\frac{1}{0!}+a_{1}\frac{x}{1!}+a_{2}\frac{x^{2}}{2!}+a_{3}\frac{x^{3}}{3!}+\cdots$$를 이 수열의 지수생성함수(exponential generating function)라고 한다. 앞에서 순열 \(_{n}P_{r}\)의 지수생성함수는 \(E(x)=(1+x)^{n}\)임을 알 수 있다.

다음은 간단한 수열들에 대한 지수생성함수의 예시들이다.

(1) 수열 \(a_{n}=1\)의 지수생성함수는$$1+x+\frac{x^{2}}{2!}+\frac{x^{3}}{3!}+\cdots=\sum_{n=0}^{\infty}{\frac{x^{n}}{n!}}=e^{x}$$이다.

(2) 수열$$a_{n}=\begin{cases}1,&\,(n:\,\text{odd})\\0,&\,(n:\,\text{even})\end{cases}$$의 지수생성함수는$$1+\frac{x^{2}}{2!}+\frac{x^{4}}{4!}+\cdots=\frac{e^{x}+e^{-x}}{2!}=\cosh x$$이다.

(3) 등비수열 \(a_{n}=r^{n-1}\)의 지수생성함수는$$1+rx+\frac{r^{2}}{2!}x^{2}+\frac{r^{3}}{3!}x^{3}+\cdots=\sum_{n=0}^{\infty}{\frac{(rx)^{n}}{n!}}=e^{rx}$$이다.

지수생성함수는 중복순열 중에서 중복수에 제한이 있는 문제, 서로 다른 물건을 분배하는 문제 등의 해를 구하는데 사용되고, 순서가 중요한 배열의 수를 계산하는 데 유용하다.

알파벳 a, b, c를 중복해서 사용해서 길이가 4인 문자열을 만드는 문제에서 아무런 제한이 없다면 그 경우의 수는 \(3^{4}=81\)이다. 만약 문자열에 a가 적어도 2번 포함되어야 한다면 이 경우는 경우의 수를 구하기가 복잡하다.

a가 2번 이상 들어가는 집합은$$\begin{matrix}\{a,\,a,\,a,\,a\}&\{a,\,a,\,a,\,b\}&\{a,\,a,\,a,\,c\}\\ \{a,\,a,\,b,\,b\}&\{a,\,a,\,b,\,c\}&\{a,\,a,\,c,\,c\}\end{matrix}$$이고, 각 경우에 대한 순열의 개수는$$\begin{matrix}\displaystyle\frac{4!}{4!0!0!}&\displaystyle\frac{4!}{3!1!0!}&\displaystyle\frac{4!}{3!0!1!}\\ \displaystyle\frac{4!}{2!2!0!}&\displaystyle\frac{4!}{2!1!1!}&\displaystyle\frac{4!}{2!0!2!}\end{matrix}$$이다.

a가 2번 이상 들어가는 집합의 개수는 다음의 부정방정식의 정수해의 개수와 같고,$$a+b+c=4\,(a\geq2,\,b,\,c\geq0)$$이 부정방정식의 정수해 \(a,\,b,\,c\)에 대하여 \(\displaystyle\frac{(a+b+c)!}{a!b!c!}\,(a+b+c=4)\)들의 합이 구하고자 하는 경우의 수이다. 다음의 함수$$\begin{align*}E(x)&=\left(\frac{x^{2}}{2!}+\frac{x^{3}}{3!}+\frac{x^{4}}{4!}+\cdots\right)\left(1+x+\frac{x^{2}}{2!}+\frac{x^{3}}{3!}+\cdots\right)\\&=\sum{\frac{r!}{a!b!c!}\frac{x^{r}}{r!}}\end{align*}$$에서 \(a+b+c=4,\,a\geq2,\,b,\,c\geq0\)이고 \(\displaystyle\frac{x^{4}}{4!}\)의 계수는 부정방정식$$a+b+c=4\,(a\geq2,\,b,\,c\geq0)$$을 만족하는 모든 경우의 수이므로 따라서 \(\displaystyle\frac{x^{4}}{4!}\)의 계수가 구하고자 하는 문자열에 \(a\)가 적어도 2번 포함되는 경우의 수이다.

예: A, B, C 세 종류의 물건을 중복을 허용해서 뽑되 A는 2개 이하, B는 3개 이하, C는 4개 이하가 되도록 \(n\)개를 뽑아서 순서대로 나열하는 가지수를 \(a_{n}\)이라고 하면, \(a_{n}\)은?

풀이:$$U_{n}=\{(a,\,b,\,c)\,|\,a+b+c=n,\,0\leq a\leq2,\,0\leq b\leq3,\,0\leq c\leq4\}$$라고 하면$$a_{n}=\sum_{(a,\,b,\,c)\in U_{n}}{\frac{(a+b+c)!}{a!b!c!}}=\sum_{(a,\,b,\,c)\in U_{n}}{\frac{n!}{a!b!c!}}$$이고 지수생성함수$$\left(1+x+\frac{x^{2}}{2!}\right)\left(1+x+\frac{x^{2}}{2!}+\frac{x^{3}}{3!}\right)\left(1+x+\frac{x^{2}}{2!}+\frac{x^{3}}{3!}+\frac{x^{4}}{4!}\right)$$에서 \(\displaystyle\frac{x^{n}}{n!}\)의 계수가 \(\displaystyle a_{n}=\sum_{(a,\,b,\,c)\in U_{n}}{\frac{n!}{a!b!c!}}\)이다.

예: 1, 2, 3으로 이루어진 길이가 \(n\)인 숫자 중에서 1의 개수가 홀수개, 2의 개수가 짝수개인 것의 개수를 \(a_{n}\)이라고 하자. 지수생성함수와 \(a_{n}\)은?

풀이: 1의 개수가 홀수개에 대응되는 지수생성함수는 \(\displaystyle x+\frac{x^{3}}{3!}+\frac{x^{5}}{5!}+\cdots=\frac{e^{x}-e^{-x}}{2}=\sinh x\)이고

2의 개수가 짝수개에 대응되는 지수생성함수는 \(\displaystyle1+\frac{x^{2}}{2!}+\frac{x^{4}}{4!}+\cdots=\frac{e^{x}+e^{-x}}{2}=\cosh x\),

나머지 수의 선택에 대응되는 지수생성함수는 \(\displaystyle1+x+\frac{x^{2}}{2!}+\frac{x^{3}}{3!}+\cdots=e^{x}\)이므로 \(a_{n}\)의 지수생성함수는$$\begin{align*}E(x)&=\left(x+\frac{x^{3}}{3!}+\frac{x^{5}}{5!}+\cdots\right)\left(1+\frac{x^{2}}{2!}+\frac{x^{4}}{4!}+\cdots\right)\left(1+x+\frac{x^{2}}{2!}+\frac{x^{3}}{3!}+\cdots\right)\\&=\frac{e^{x}-e^{-x}}{2}\frac{e^{x}+e^{-x}}{2}e^{x}\\&=\frac{e^{3x}-e^{-x}}{4}\end{align*}$$이고$$\begin{align*}\frac{e^{3x}-e^{-x}}{4}&=\frac{1}{4}\sum_{n=0}^{\infty}{\left(\frac{(3x)^{n}}{n!}+\frac{(-x)^{n}}{n!}\right)}\\&=\sum_{n=0}^{\infty}{\frac{((3)^{n}+(-1)^{n})}{4}\frac{x^{n}}{n!}}\end{align*}$$이므로 따라서 \(\displaystyle a_{n}=\frac{3^{n}+(-1)^{n}}{4}\)이다.

카탈란 수

아래 그림에서

원점 \((0,\,0)\)에서 \((m,\,n)\)으로 가는 최단경로의 수는 가로와 세로를 각각 \(m\)번, \(n\)번 나열하는 경우의 수와 같고 따라서 \(\displaystyle\binom{m+n}{n}=\frac{(m+n)!}{m!n!}\)이 최단경로의 수이다.

아래 그림의 \(n\times n\) 정사각형에서 왼쪽 아래의 점에서 오른쪽 위의 점으로 갈 때 대각선보다 위에 놓인 점을 거치지 않고 가는 최단경로의 수를 구하자. 이때 이 최단경로의 수를 카탈란 수(Catalan number)라고 한다.

여기서 카탈란수를 \(C_{n}\)으로 나타내겠다. 즉 \(C_{1}=1,\,C_{2}=2,\,C_{3}=5,\,\cdots\)이다.

\(0,\,0\)에서 \((n,\,n)\)까지 도달하기 전에 마지막으로 지난 대각선 위의 점 \((k,\,k)\)를 고려하자. 그러면 대각선 위의 점을 지나지 않는 최단경로들의 집합 \(S\)를 \(k\)의 값에 따라 분할할 수 있다.(마지막으로 대각선 위의 점 \((0,\,0)\)을 지난 경로는 대각선 위의 어느 점도 지나지 않은 경로를 뜻한다)

\((n,\,n)\)에 도달하기 전에 마지막으로 지난 대각선 위의 점이 \((k,\,k)\)인 최단경로의 수는 아래 그림에 의해

\(C_{k}C_{n-k-1}\)이므로$$C_{n}=C_{0}C_{n-1}+C_{1}C_{n-2}+\cdots+C_{n-1}C_{0}=\sum_{k=0}^{n-1}{C_{k}C_{n-k-1}}\,(n\geq1)$$이고, \(C_{0}=0,\,C_{1}=1\)이다. 

카탈란수는 대각선 위에 놓인 점을 지나지 않는 최단경로의 수를 나타내지만 다음의 성질을 만족하는 이산적 대상의 개수로도 표현된다.

(1) \(n\)개의 +1과 \(n\)개의 -1을 더해 나갈 때, 처음부터의 부분합이 음이 되지 않도록 일렬로 늘어놓는 방법의 수

(2) \(n\)개의 마디를 가진 나무에 평면에 그리는 경우의 수

(3) 원둘레 위에 \(2n\)개의 점이 있을 때 어느 두 현도 만나지 않도록 두 점씩 잇는 경우의 수

(4) 볼록 \((n+2)\)각형의 꼭짓점을 이어 그 도형을 삼각형들로 분할하는 방법의 수, 이때 어느 두 대각선도 꼭짓점이 나닌 곳에서 만나면 안된다.

생성함수를 이용하여 카탈란수 \(C_{n}\)을 구하자. 생성함수를 \(\displaystyle f(x)=\sum_{n=0}^{\infty}{C_{n}x^{n}}=C_{0}+C_{1}x+C_{2}x^{2}+\cdots\)라고 하자. 그러면$$\begin{align*}\{f(x)\}^{2}&=(C_{0}+C_{1}x+C_{2}x^{2}+\cdots)(C_{0}+C_{1}x+C_{2}x^{2}+\cdots)\\&=\sum_{n=0}^{\infty}{(C_{0}C_{n}+C_{1}C_{n-1}+\cdots+C_{n}C_{0})x^{n}}\\&=\sum_{n=0}^{\infty}{C_{n+1}x^{n}}\end{align*}$$이고 \(\displaystyle x\{f(x)\}^{2}=\sum_{n=0}^{\infty}{C_{n+1}x^{n}}\)이므로 식 \(x\{f(x)\}^{2}=f(x)-1\)을 만족한다. 이 식에서 \(f(0)=1\)이어야 하고 앞에서 얻은 식을 \(f(x)\)에 대한 2차방정식으로 생각하고 풀면 \(f(0)=1\)이라는 조건에 의해$$f(x)=\frac{1-\sqrt{1-4x}}{2x}$$이다. \(\sqrt{1-4x}=(1-4x)^{\frac{1}{2}}\)의 매클로린 급수는$$\begin{align*}(1-4x)^{\frac{1}{2}}&=\sum_{n=0}^{\infty}{\binom{\frac{1}{2}}{n}x^{n}}\\&=1+\sum_{n=1}^{\infty}{\frac{\frac{1}{2}\left(-\frac{1}{2}\right)\cdots\left(-\frac{2n-3}{2}\right)}{n!}}(-4x)^{n}\\&=1+\sum_{n=1}^{\infty}{(-1)^{n-1}\frac{(2n-2)!}{2^{n}2^{n-1}n!(n-1)!}(-4x)^{n}}\\&=1-2\sum_{n=1}^{\infty}{\frac{(2n-2)!}{n!(n-1)!}x^{n}}\end{align*}$$이고 따라서$$\begin{align*}f(x)&=\frac{1}{2x}2\sum_{n=1}^{\infty}{\frac{(2n-2)!}{n!(n-1)!}x^{n}}=\sum_{n=1}^{\infty}{\frac{(2n-2)!}{n!(n-1)!}x^{n-1}}=\sum_{n=0}^{\infty}{\frac{(2n)!}{(n+1)!n!}x^{n}}\\&=\sum_{n=0}^{\infty}{\frac{1}{n+1}\binom{2n}{n}x^{n}}\end{align*}$$이고 \(\displaystyle C_{n}=\frac{1}{n+1}\binom{2n}{n}\,(n\geq1)\)이다.

참고자료:

조합 및 그래프이론, 김정진, 교우사