PART III — 세기
수열을 손에 들고 있기 어려우면, 한 함수로 묶어서 들고 다닌다 — 그게 생성함수입니다. 이 챕터에서는 수열 \( a_0, a_1, a_2, \dots \)를 형식 멱급수 \( A(x) = \sum a_n x^n \)으로 인코딩한 다음, 함수에 대한 대수적 조작이 곧 수열에 대한 카운팅 조작이 되는 마법을 살펴봅니다. 동전 거스름돈을 세고, 부분분수로 계수를 끄집어내고, 점화식을 폐형(closed form)으로 풀어보면서 이 도구가 왜 조합론의 스위스 군용 칼이라 불리는지 체감하게 됩니다.
수학자가 수열을 다루는 방법은 여러 가지가 있지만, 그중에서도 가장 강력한 트릭 하나는 “수열을 함수로 변환하기”입니다. 수열 \( (a_0, a_1, a_2, \dots) \)가 있으면, 우리는 다음과 같이 멱급수 한 줄로 묶어버립니다.
정의 16.1.1 (생성함수)
수열 \( (a_n)_{n \ge 0} \)의 (보통) 생성함수란 형식 멱급수 \[ A(x) = \sum_{n=0}^{\infty} a_n x^n = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots \] 를 말합니다. 즉, 수열을 \( x^n \)의 계수에 “끼워 넣은” 다항식 비슷한 무한합이에요.
여기서 \( x \)는 어떤 구체적인 숫자가 아니라 그냥 자리표시자(placeholder)입니다. 수열의 정보를 잃지 않고 보관하기 위한 옷걸이라고 생각하면 좋아요. \( x = 0.3 \) 같은 걸 대입할 일은 일단 없습니다. 그래서 “수렴 반경이 어떻게 되나” 같은 해석학적 걱정은 16.5에서 따로 정리할 거예요.
가장 처음 만나야 할 항등식 한 줄이 있습니다. 모든 항이 1인 수열 \( (1, 1, 1, 1, \dots) \)의 생성함수는 무엇일까요?
\[ 1 + x + x^2 + x^3 + \cdots = \frac{1}{1 - x}. \]이 식은 고등학교 등비급수 공식에서 \( |x| < 1 \) 조건으로 외우던 그 식이지만, 형식 멱급수 세계에서는 양변이 “같은 수열을 인코딩한다”는 뜻으로 그대로 받아들이면 됩니다. 곱해서 확인해 볼까요. \( (1-x)(1 + x + x^2 + \cdots) \)를 분배법칙으로 풀면 \( 1 + x + x^2 + \cdots - x - x^2 - x^3 - \cdots \)가 되어 가운데 항들이 깔끔히 상쇄되고 1만 남습니다.
예제 16.1.2 (자주 쓰이는 생성함수 모음)
아래 항등식들은 “주머니에 넣고 다니는” 기본 도구입니다.
\[ \frac{1}{1-x} = \sum_{n \ge 0} x^n, \qquad \frac{1}{1-cx} = \sum_{n \ge 0} c^n x^n, \] \[ \frac{1}{(1-x)^2} = \sum_{n \ge 0} (n+1) x^n, \qquad \frac{x}{(1-x)^2} = \sum_{n \ge 0} n\, x^n. \]마지막 식은 “\( a_n = n \)”인 수열의 생성함수예요. 첫 번째 식의 양변을 \( x \)에 대해 미분해서 얻을 수도 있습니다 (형식적으로요).
노트 — 수열과 함수, 어느 쪽이 본체?
처음에는 “식이 본체”라고 생각하기 쉽지만, 생성함수의 세계에서는 수열이 본체이고 함수는 그 수열을 보관하는 가방입니다. \( \frac{1}{1-x} \)라고 쓰면 사실은 “모든 항이 1인 수열”을 부르는 별명을 부른 셈이에요. 별명을 익히면 수열을 다루기 훨씬 가벼워집니다.
생성함수가 단순히 “수열을 식으로 바꾸기” 놀이에서 그쳤다면 이렇게 큰 단원을 차지할 이유가 없죠. 진짜 마법은 두 수열의 생성함수를 곱하면, 그 곱이 어떤 카운팅을 자동으로 수행해 준다는 데 있습니다.
정리 16.2.1 (수열 곱 = 컨벌루션)
두 생성함수 \( A(x) = \sum a_n x^n \)과 \( B(x) = \sum b_n x^n \)을 곱하면 \[ A(x) B(x) = \sum_{n=0}^{\infty} c_n x^n, \quad \text{단, } c_n = \sum_{k=0}^{n} a_k\, b_{n-k}. \] 여기서 \( c_n \)은 \( a \)와 \( b \)의 컨벌루션(convolution)이라 부릅니다.
이 컨벌루션이 왜 카운팅을 해주냐면, “전체 무게 \( n \)을 만들 때, \( A \) 쪽에서 무게 \( k \), \( B \) 쪽에서 무게 \( n-k \)를 가져와 짝지은 경우의 수”를 각 \( k \)에 대해 더한 값이기 때문입니다. 두 결정의 합으로 만들어지는 모든 카운팅 문제가 자동으로 컨벌루션이 되는 거예요.
예제 16.2.2 (동전 거스름돈)
1원, 2원, 5원짜리 동전이 무한히 많을 때, \( n \)원을 만드는 방법의 수 \( c_n \)을 구하고 싶다고 합시다. 1원 동전을 \( i \)개, 2원 동전을 \( j \)개, 5원 동전을 \( k \)개 쓰면 \( i + 2j + 5k = n \)이 돼야 해요. 1원 동전만 봐서 “1원을 \( i \)개 쓰는 방법”의 생성함수는 \[ 1 + x + x^2 + x^3 + \cdots = \frac{1}{1-x}, \] 2원짜리는 \( 1 + x^2 + x^4 + \cdots = \frac{1}{1-x^2} \), 5원짜리는 \( \frac{1}{1-x^5} \)이 됩니다. 이 셋을 곱한 \[ C(x) = \frac{1}{(1-x)(1-x^2)(1-x^5)} \] 에서 \( x^n \) 계수가 바로 \( c_n \)이에요. 곱셈 한 번이 “세 동전을 어떻게 조합하는가”라는 카운팅을 통째로 처리해 준 셈입니다.
일반화하면 이렇습니다. 어떤 “부품” 종류 \( i \)에서 무게 \( w \)인 부품을 사용한다면 그 부품의 생성함수는 \( x^w \)이고, 같은 종류를 0개 이상 쓸 수 있다면 \( 1 + x^w + x^{2w} + \cdots = \frac{1}{1-x^w} \)입니다. 부품 종류가 여럿이면 각각의 생성함수를 곱해서 전체 카운팅 생성함수를 만들 수 있어요. 이걸 흔히 “선택의 곱은 생성함수의 곱”이라고 외우면 직관에 잘 박힙니다.
노트 — 합 vs 곱
또 하나 알아둘 규칙: 두 카운팅이 “겹치지 않는 경우의 합”이라면 생성함수도 더해집니다. 즉 합 규칙은 덧셈, 곱 규칙은 곱셈이에요. 4장의 카운팅 규칙이 그대로 함수 세계로 옮겨 온 모습입니다.
생성함수를 곱셈으로 잘 만들었다면, 이제 거기서 “수열의 \( n \)번째 항”을 다시 꺼내야 활용도가 올라갑니다. 만약 식이 다항식의 비율 — 즉 유리식 \( \dfrac{P(x)}{Q(x)} \) — 형태라면, 부분분수 분해가 거의 만능 도구가 돼요.
정리 16.3.1 (부분분수 — 단순 극점 버전)
분모 \( Q(x) = (1 - r_1 x)(1 - r_2 x)\cdots(1 - r_d x) \)가 서로 다른 일차 인수들의 곱이고 \( \deg P < \deg Q \)라면, 적당한 상수 \( A_1, \dots, A_d \)가 유일하게 존재해서 \[ \frac{P(x)}{Q(x)} = \frac{A_1}{1 - r_1 x} + \frac{A_2}{1 - r_2 x} + \cdots + \frac{A_d}{1 - r_d x}. \] 이때 \( x^n \)의 계수는 \( A_1 r_1^n + A_2 r_2^n + \cdots + A_d r_d^n \)이 됩니다.
왜 좋냐고요? 각 항 \( \dfrac{A_i}{1 - r_i x} \)는 16.1에서 본 등비급수 \( A_i \sum_n r_i^n x^n \)이기 때문입니다. 그래서 합쳐 놓은 \( x^n \) 계수도 “여러 등비수열의 합”으로 깔끔하게 떨어져요. 카운팅 결과를 풀어쓰는 닫힌 형태(closed form)가 곧장 튀어나옵니다.
예제 16.3.2 (계수 추출 예)
\( G(x) = \dfrac{1}{(1-x)(1-2x)} \)의 \( x^n \) 계수를 구해봅시다. 부분분수로 \( \dfrac{1}{(1-x)(1-2x)} = \dfrac{A}{1-x} + \dfrac{B}{1-2x} \)로 두고 양변에 \( (1-x)(1-2x) \)를 곱하면 \( 1 = A(1-2x) + B(1-x) \). \( x = 1 \)을 대입하면 \( 1 = -A \)에서 \( A = -1 \), \( x = 1/2 \)을 대입하면 \( 1 = B \cdot \tfrac{1}{2} \)에서 \( B = 2 \). 따라서 \[ G(x) = \frac{-1}{1-x} + \frac{2}{1-2x}, \] \( x^n \)의 계수는 \( -1 + 2 \cdot 2^n = 2^{n+1} - 1 \)입니다. 어디서 본 수열이죠? 네, 비둘기집/하노이 탑 등에서 자주 등장하는 \( 2^{n+1} - 1 \)이에요.
노트 — 중근이 있을 때
분모에 \( (1 - r x)^2 \)처럼 같은 인수가 두 번 들어가면, 부분분수 항도 \( \dfrac{A}{1-rx} + \dfrac{B}{(1-rx)^2} \) 두 개가 필요합니다. 두 번째 항의 전개는 \( \sum_{n \ge 0} (n+1) r^n x^n \)이라는 점만 기억하면 똑같이 처리할 수 있어요. 중근 \( k \)개라면 \( (1-rx)^j \) 항을 \( j = 1, \dots, k \)까지 모두 모으면 됩니다.
드디어 이번 챕터의 하이라이트입니다. 선형점화식을 폐형으로 풀고 싶을 때 생성함수가 어떻게 작동하는지를 피보나치로 직접 따라가 봅시다.
피보나치 수열은 \( F_0 = 0,\ F_1 = 1 \), 그리고 \( n \ge 2 \)에 대해 \( F_n = F_{n-1} + F_{n-2} \)로 정의돼요. 이 수열의 생성함수를 \( F(x) = \sum_{n \ge 0} F_n x^n \)이라 두고, 점화식을 그대로 “함수의 식”으로 옮겨봅시다.
핵심 아이디어는 점화식 양변에 \( x^n \)을 곱하고 \( n \ge 2 \)에 대해 모두 더하는 것입니다. \[ \sum_{n \ge 2} F_n x^n = \sum_{n \ge 2} F_{n-1} x^n + \sum_{n \ge 2} F_{n-2} x^n. \] 좌변은 \( F(x) - F_0 - F_1 x = F(x) - x \). 우변 첫 항은 \( x \sum_{n \ge 2} F_{n-1} x^{n-1} = x(F(x) - F_0) = x F(x) \). 두 번째 항은 \( x^2 \sum_{n \ge 2} F_{n-2} x^{n-2} = x^2 F(x) \). 정리하면 \[ F(x) - x = x F(x) + x^2 F(x), \] \[ F(x)(1 - x - x^2) = x, \qquad F(x) = \frac{x}{1 - x - x^2}. \] 수열에 대한 점화식이 분모 한 줄짜리 닫힌 식으로 쪼그라들었어요.
정리 16.4.1 (피보나치 폐형 — Binet 공식)
\( \phi = \dfrac{1 + \sqrt{5}}{2} \), \( \psi = \dfrac{1 - \sqrt{5}}{2} \)라 두면, 모든 \( n \ge 0 \)에 대해 \[ F_n = \frac{1}{\sqrt{5}} \left( \phi^n - \psi^n \right). \]
증명 (생성함수 + 부분분수)
분모 \( 1 - x - x^2 \)을 인수분해해야 하는데, \( 1 - x - x^2 = (1 - \phi x)(1 - \psi x) \)임을 확인하면 됩니다. 실제로 전개하면 \( 1 - (\phi + \psi)x + \phi\psi\, x^2 \)이고, \( \phi + \psi = 1 \), \( \phi \psi = -1 \)이므로 정확히 일치해요. 이제 부분분수로 \[ F(x) = \frac{x}{(1 - \phi x)(1 - \psi x)} = \frac{A}{1 - \phi x} + \frac{B}{1 - \psi x}. \] 양변에 \( (1 - \phi x)(1 - \psi x) \)를 곱하면 \( x = A(1 - \psi x) + B(1 - \phi x) \). \( x = 1/\phi \) 대입 시 \( 1/\phi = A(1 - \psi/\phi) \), 정리하면 \( A = \dfrac{1}{\phi - \psi} = \dfrac{1}{\sqrt{5}} \). 같은 방식으로 \( B = -\dfrac{1}{\sqrt{5}} \). 그러므로 \[ F(x) = \frac{1}{\sqrt{5}}\left( \frac{1}{1 - \phi x} - \frac{1}{1 - \psi x} \right) = \frac{1}{\sqrt{5}} \sum_{n \ge 0} (\phi^n - \psi^n) x^n, \] \( x^n \)의 계수가 정확히 \( F_n = \tfrac{1}{\sqrt{5}}(\phi^n - \psi^n) \)입니다.
∎
점화식이 무리수와 거듭제곱으로 깔끔히 표현되는 게 신기하지 않나요. \( |\psi| < 1 \)이라 \( n \)이 커질수록 \( \psi^n \)은 0에 가까워지고, 결국 \( F_n \approx \phi^n / \sqrt{5} \)라는 황금비 성장률이 자연스럽게 따라옵니다. 일반적으로 “선형동차 점화식 → GF 분모는 다항식 → 부분분수 → 등비합”이라는 한 줄 파이프라인을 기억해 두면, 어지간한 점화식은 모두 같은 방식으로 닫힌 식이 나옵니다.
여태 계속 “수렴은 신경 안 써도 된다”라는 말을 흘려 왔는데, 이제 그 약속에 책임을 져야 할 때입니다. 핵심은 우리가 다루는 대상이 “함수”가 아니라 “수열에 가방을 씌운 형식적 표현”이라는 점이에요.
정의 16.5.1 (형식 멱급수)
형식 멱급수란 단순히 무한 수열 \( (a_0, a_1, a_2, \dots) \)를 \( \sum a_n x^n \)이라는 표기로 적은 것입니다. 두 형식 멱급수의 덧셈/곱셈은 항별로 정의해요. \[ \sum a_n x^n + \sum b_n x^n = \sum (a_n + b_n)x^n, \] \[ \left(\sum a_n x^n\right)\left(\sum b_n x^n\right) = \sum_{n}\left(\sum_{k=0}^{n} a_k b_{n-k}\right) x^n. \] 이 연산들은 형식적 합/곱이라 어떤 \( x \) 값도 대입할 필요가 없습니다.
이렇게 정의하면 곱셈의 \( x^n \) 계수는 항상 유한 합이라 잘 정의됩니다. 즉 “무한히 더했는데 발산하면 어쩌지” 같은 걱정은 처음부터 발생할 자리가 없어요. \( \sum_{k=0}^n a_k b_{n-k} \)는 유한합이니까요.
그럼 \( \dfrac{1}{1-x} = \sum x^n \) 같은 등식의 의미는 뭘까요. 이건 “\( (1-x) \cdot \sum x^n = 1 \)”이라는 형식 곱 관계로 정의합니다. 좌변을 컨벌루션 정의대로 곱하면 정말 1만 남는다는 걸 손으로 확인할 수 있어요. 그러니까 \( 1/(1-x) \)는 “\( 1-x \)의 형식 곱 역원”이라는 뜻이지, “함수 \( x \mapsto 1/(1-x) \)와 일치한다”는 해석학적 주장이 아닙니다.
정리 16.5.2 (역원의 존재)
형식 멱급수 \( A(x) = \sum a_n x^n \)에 곱셈 역원 \( A(x)^{-1} \)이 존재할 필요충분조건은 \( a_0 \ne 0 \)인 것입니다.
증명 스케치
역원 \( B(x) = \sum b_n x^n \)이 존재한다면 \( A(x)B(x) = 1 \)에서 \( x^0 \) 계수 비교로 \( a_0 b_0 = 1 \), 따라서 \( a_0 \ne 0 \). 역으로 \( a_0 \ne 0 \)이라면 \( b_0 = 1/a_0 \)에서 시작해 \( x^n \)계수가 0이라는 조건 \( \sum_{k=0}^n a_k b_{n-k} = 0 \)을 \( b_n \)에 대해 풀면 \( b_n = -\dfrac{1}{a_0}\sum_{k=1}^n a_k b_{n-k} \)이라는 점화식이 나오고, 이로써 모든 \( b_n \)을 차례로 정의할 수 있습니다.
∎
이 결과 덕분에 \( 1 - x - x^2 \) 같은 다항식도 형식 멱급수의 세계에서 안전하게 “나눌 수” 있고, 16.4에서처럼 \( \dfrac{x}{1-x-x^2} \)을 부담 없이 적을 수 있어요. 분모의 상수항이 0이 아니기 때문입니다.
마지막으로 형식적 미분도 짚고 넘어갑시다. 형식 도함수는 \( \dfrac{d}{dx}\sum a_n x^n = \sum n a_n x^{n-1} \)로 항별로 정의해요. 수렴이 어떻든 신경쓰지 않고요. 이 형식 도함수는 일반 함수 미분이 만족하는 곱 규칙, 합 규칙을 그대로 만족하기 때문에, 16.1의 \( \frac{1}{(1-x)^2} = \sum (n+1) x^n \) 같은 항등식을 “미분으로 유도”했을 때도 결과가 진짜로 옳다고 보장됩니다.
노트 — 컴퓨터과학 시각
형식 멱급수의 마음가짐은 사실 컴퓨터과학자에게 익숙합니다. 무한 스트림(infinite stream)을 머리부터 한 항씩 “지연 평가”로 만들어내는 것과 닮았어요. 곱셈 컨벌루션은 두 스트림의 누적합 합성에 해당하고, 형식적 역원은 “자기 자신의 출력 일부를 입력으로 다시 받는” 피드백 회로로 볼 수 있습니다. 이산수학과 함수형 프로그래밍이 같은 그림을 다른 언어로 그리고 있다는 게 이 단원의 마지막 메시지예요.