4.1 생성함수

셈하는 기법을 개발하는 것이 조합론에서 중요한 목표 중의 하나였다는 사실을 되새기자. 제4장에서는 셈하기에서 자주 이용되는 가장 강력한 도구 중에 하나인 '생성함수'에 대해 알아본다. 이 장의 내용은 일반 독자에게 생소하고 굉장히 신기할 수도 있다. 

 

생성함수 수열 $a(r)$을 생각한다. 여기서$ r=0, 1, 2, 3, \cdots$이다. 이 수열에 대한 '생성함수'는 다음 급수로 정의된다. 

 

   $A(x) = a(0) +a(1)x^1 +a(2)x^2 +a(3)x^3 +\cdots$

 

위의 식은 $x$에 관한 다항식이고 $a(r)$은 그에 대한 계수이다. 나중에 확실히 알게되겠지만, 이 계수는 어떤 셈하기 문제에 대해 의미있는 수가 된다.

쉬운 예로 이항정리

   $B(1,x) = C(n,0)x^0 + C(n,1)x^1 + C(n,2)x^2 + \cdots$

에서의 이항계수 $a(r) = C(n,r)$는 어떤 셈하기 문제에서 의미있는 수일까? 우리는 (이미 알고 있으므로) 이 물음에 대해 쉽게 답할 수 있다. 서로 다른 $n$개의 대상에서 $r$개를 선택하는 조합의 수이다. 

 

생성함수에 대한 결론부터 얘기하면, 명칭이 이미 말해주듯이 무언가를 생성한다는 것이다. 무엇을 생성할까? 우리가 셈하기를 원하는 대상의 개수를 계수로 생성시켜주는 함수라는 얘기다. 굴비 엮듯이 주어진 문제에 대한 '경우의 수'를 줄줄이 엮어줄 함수라는 얘기다.

---

우리는 이미 그 결과를 알고 있는 $n$개의 숫자 $1, 2, \cdots, n$에서 $r$개를 선택하는 경우에 대한 생성함수를 살펴보자. 여기서 $r=0,1,2,\cdots,n$이다.

 

우리의 논의를 좀 더 간편하게 하기 위해서 숫자 $1, 2, 3$인 경우에 대하여 생각한다. 이때 $r=0,1,2,3$이다. 이것은 집합

   $S=\left\{a, b, c \right\}$

에서  원소를 선택하는 방법의 수를 생각해도 된다. 사실 대상을 숫자로 두기보다 문자로 두는 것이 좋을 때가 있다. S로부터터 한 개의 원소를 고르는 경우는

   $\left\{a\right\}, \left\{b\right\}, \left\{c\right\}$

이고, 두 개의 원소를 고르는 경우는 

   $\left\{a, b\right\}, \left\{b, c\right\}, \left\{c, a\right\}$
이며, 세 개의 원소를 고르는 경우는 

   $\left\{a, b, c\right\}$

이다. 이것을 다음과 같이 표기할 것이다. 
   $\left\{a\right\}, \left\{b\right\}, \left\{c\right\} ; a+b+c$

   $\left\{a, b\right\}, \left\{b, c\right\}, \left\{c, a\right\} ; ab+bc+ca$

   $\left\{a, b, c\right\} ; abc$

이렇게 표기하고 나면 이 표기들은 다음과 같은 식에서도 발견 되어진다. 

 

   $(1+ax)(1+bx)(1+cx)= 1x^0 + (a+b+c)x^1 + (ab+bc+ca)x^2 + (abc)x^3$

 

신기한 일이다! 이러한 관찰을 어떻게 해석하는 것이 좋을까?

 

여기서 $(1+ax) = (x^0 + ax^1)$으로 쓸 수 있고, 이것을 우리는 다음과 같이 읽도록 하자. 

"a가 선택되지 않거나 a가 한번 선택된다." 

$(1+bx)$와 $(1+cx)$도 동일한 방식으로 해석된다. 따라서 결국 식 

   $(1+ax)(1+bx)(1+cx)$

은 $a$가 선택되지 않거나 또는 선택되는 사건, $b$가 선택되지 않거나 또는 선택되는 사건, $c$가 선택되거나 또는 선택되는 사건의 '곱의 법칙'을 의미한다. 

 

우변의 전개식에서 각 항의 x의 지수는 선택되는 원소의 개수를 나타내고, 그 항의 계수는 선택가능한 모든 경우를 나타냄을 알 수 있다. 우리는 선택 방법의 수에만 관심이 있으므로

   $a=b=c=1$

로 놓으면 다음의 결과를 얻는다. 

   $(1+x)(1+x)(1+x) = 1 + 3x^1 + 3x^2 + 1x^3$

이것은 수열 $(1, 3, 3, 1)$의 생성함수이다. 그러므로 3개의 서로 다른 원소들 중에 $r(=0,1,2,3)$개를 고르는 방법의 수에 대한 생성함수는 

   $(1+x)(1+x)(1+x)$

이다. 

따라서 숫자 $1, 2, \cdots, n$에서 $r$개를 선택하는 경우의 수를 구하는 문제는 바로 다음 식의 계수를 구하는 문제로 생각할 수 있다. 
   $B(1,x) = (1+x)(1+x)\cdots(1+x) = (1+x)^n$
바로 이 이항식의 이항계수 $C(n,r)$가 우리가 구하고자 하는 경우의 수이다. 다시 말해, 이항식 
   $B(1,x)$
의 계수를 구하는 문제가 결국 서로 다른 $n$개의 대상에서 $r$개를 선택하는 조합의 수를 구하는 문제를 의미한다. 

---

'생성함수'에 대한 이해를 돕기 위해 또 하나의 다른 예를 생각해 본다. 

$a, b$로 부터 중복을 허용하여 $2$개를 선택하는 경우의 수를 생각하자. 단, $a$는 $2$개까지만 중복 선택이 가능하고, $b$는 $1$개끼지만 가능할 경우로 제한한다. 이것을 중복집합 $S={2a, 1b}$로 부터 원소를 선택하는 경우로 생각할 수 있다. 만약 중복 선택이 무한히 허용될 경우 
   ${\infty\cdot a, \infty\cdot b}$
로 표기한다. 

$S$로부터 하나의 원소를 고르는 경우, 
   $\left\{a\right\}, \left\{b\right\} ; a+b$
이고, 두 개의 원소를 고르는 경우, a는 2번까지 선택 가능하므로 
   $\left\{a, a\right\}, \left\{a, b\right\} ; a^2+ab$
이고, 세 개의 원소를 고르는 경우, 
   $\left\{a, a, b\right\} ; a^2b$
이다. 이제, $r=0,1,2,3$일 때, 각각 경우의 수를 구할 수 있는 생성함수를 찾는다. 
"a는 선택되지 않거나 한 번 선택되거나 두 번 선택되고, b는 선택되지 않거나 한 번 선택된다." 

이것을 앞에서와 마찬가지 방법으로 다항식으로 나타내면 다음과 같다. 
   $(1+ax+a^2 x^2)(1+bx) = 1x^0 + (a+b) x^1 + (a^2 +ab) x^2 + (a^2 b) x^3$
여기서도 우리는 선택 방법의 수에만 관심이 있기 때문에 a=b=1로 놓으면 다음과 같은 결과를 얻는다. 

   $(1+x+x^2)(1+x) = 1 + 2x + 2x^2 + 1x^3$

 

이것은 수열 $(1, 2, 2, 1)$의 생성함수이다. 그러므로 중복집합 $\left\{2a, 1b\right\}$로 부터 $r(=0,1,2,3)$개의 원소를 선택하는 방법의 수에 대한 생성함수는

   $(1+x+x^2)(1+x)$

이다. 우리의 문제에서 $r=2$일 경우였으므로 구하고자 하는 값은 생성함수의 전개식으로부터 $x^2$항의 계수 $2$이다. 이것은 실제 결과와 일치한다.