Posts Tagged ‘ 지수생성함수 ’

생성함수의 종류와 poset

얼마전에 다른 게시판에 쓴 글을 다시 옮김과 정리.

생성함수에는 두 종류가 있다는 것을 수학경시 했던 사람이라면 다들 알 것이다. 일반적인 생성함수 (Ordinary generating function) 그리고 지수 생성함수 (Exponential generating function) 이들이 그것이다. 이들은 쉽게 말하자면 \sum f(n)x^n\sum f(n)\frac{x^n}{n!}의 꼴을 갖고 있다. 그리고 우리가 접해온 수많은 조합적인 개체들은 이들과 연관되는 경우가 많았다.

하지만 사실은 이게 생성함수의 전부가 아니다. 적어도 이런 종류로 알려진 것이 세 종류는 더 있다. (그 중 하나는 엄밀히 종류가 무한개라고 할 수도 있겠다만..) 첫 번째로, q-analogue version이기도 한 \sum f(n)\frac{x^n}{(n)!}. 여기서 (n)!(1+q)(1+q+q^2)...(1+q+...+q^{n-1}), 즉 n!의 q-analogue이다. 이는 Eulerian generating function이라 불리우며, 주로 \mathbb{F}_q 위의 벡터 스페이스에서 무언가를 세는 문제와 관련이 깊다. 예를 들면, f(n)이 dimension이 n인 한 vector space over \mathbb{F}_q의 subspace 개수라고 할 때 \sum f(n)\frac{x^n}{(n)!} = (\sum \frac{x^n}{(n)!})^2가 된다.

두 번째로 Doubly-exponential generating function. \sum f(n)\frac{x^n}{n!^2}이다. 즉 분모만 n!^2로 바꿨다. 대충 예상했겠지만 이 경우 특수한 행렬들과 관련되는 경우가 많다. (약간의 어폐가 있긴 하다.) 예를 들어 f(n)n\times n 행렬 중 각 요소가 음 아닌 정수이며 행과 열의 원소의 합들이 각각 2일 경우의 수라 하면 \sum f(n)\frac{x^n}{n!^2} = \frac{e^{x/2}}{\sqrt(1-x)} 임을 얻는다. ㄷㄷ 그리고 이 경우 일반화가 가능하여 r-exponential generating function \sum f(n)\frac{x^n}{n!^r}을 생각하는 경우가 많다.

세 번째로 Chromatic generating function. \sum f(n)\frac{x^n}{q^{\binom{n}{2}}n!} 꼴이다. 이것은 n개의 점을 갖는 그래프와 연관이 깊다. (주로 거기서 q-1개의 색을 칠하는 경우) 예컨대 f(n)n개의 점을 가지며 acyclic한 (cycle이 없는) 유향 그래프의 개수라 하면 \sum f(n)\frac{x^n}{q^{\binom{n}{2}}n!} = (\sum (-1)^n \frac{x^n}{q^{\binom{n}{2}}n!})^{-1}을 얻는다.

정리하면, 약간 단순화시켜서 ordinary는 음아닌 정수와 관련되고, exponential은 set에, Eulerian은 vector space, doubly exponential은 서로 잘 연결되어진 두 set의 pair (그래서 특수 행렬과 연관됨), 그리고 chromatic은 그래프와 관련이 된다.

자.. 이쯤 되면 과연 생성함수의 형태는 이것들로만 제한되는지는 당연히 의심된다. 그리고 당연히 답은 부정적이다. 부정적(negative)이자 부정적(a number of solutions)이다. 그러면 이들을 한데 묶어 설명할 순 없을까? 이들은 너무 따로따로 논다. 그리고 각각이 특색이 있기에 이들을 unify할 이론은 없어보인다.

그런데 그게 실제로 일어났습니다.

이야기는 poset, 즉 partially ordered set의 이야기로 올라간다. 아마 수학을 전공하는 사람들이면 Zorn’s lemma 배우면서 한 번은 거칠 개념이다. 즉 집합의 원소들 중 일부 쌍에만 순서를 주는 개념인데, 조합론에서는 이에 관련된 이론이 하나의 branch를 이룰 정도로 연구가 많이 이루어져 있다. 그 중 다음과 같은 특징을 갖는 poset P를 binomial poset이라 부른다.

a. P는 locally finite이고 (interval만 보면 finite) \hat{0}을 가지며 (unique minimum element라 보면 됨) infinite chain을 갖는다.
b. 임의의 interval [x,y]=\{z:x \leq z \leq y \}은 graded이다. (즉 rank function을 줄 수 있다) 또한 interval [x,y]의 길이가 n이면 [x,y]n-interval이라 부르자.
c. 임의의 음 아닌 정수 n에 대해, 임의의 두 n-interval은 maximal chain의 개수가 B(n)으로 똑같다.
이 때 B(n)P의 factorial function이라 하자.

아 아까 전까진 알기 쉽게 풀어쓰는 것을 목표로 했는데 이 문단으로 모든게 틀어져버렸어….

아무튼 factorial function의 이름에서 예감할 수 있듯 이 B(n)은 일반적인 의미의 factorial, 즉 n!의 연장선에 있다. 그리고 binomial poset은.. 한 마디로 말하면, 이 poset의 임의의 같은 크기의 부분을 잡아도 (부분 = interval, 크기 = length) 그 부분에서의 특정 동등한 개체의 ‘개수’ (즉 maximal chain의 개수) 가 항상 일정하게 나타나는 존재란 뜻이다.

그러면 binomial poset의 직접적인 예를 들자.

(1) P=\mathbb{N} (음아닌 정수 집합) 그리고 일반적인 perfect order를 주면 B(n)=1
(2) P\mathbb{N}의 유한 부분집합의 poset으로 잡으면 (order는 inclusion) B(n)=n!
(3) P\mathbb{F}_q 위의 무한차원 벡터공간의 subspace들의 poset으로 잡으면 B(n)=(n)!
(4) P= \{(S,T):S,T \subset \mathbb{N}, |S|=|T| \}으로 잡고 (S,T) \leq (S',T') \Leftrightarrow S \subset S', T \subset T'으로 잡으면 B(n)=n!^2
(5) 귀찮아서 복잡해서 생략.. 아무튼 잘 잡으면 q^{\binom{n}{2}}n!

그러면 이 다섯 개의 예가 바로 앞에서 잡은 다섯 종류의 생성함수와 관련된다. 즉 적당한 binomial poset 하나만 잡으면, 그에 관련된 한 종류의 생성함수를 만들 수 있고, 만약 그 binomial poset이 조합적으로 해석 가능하다면 의미 있는 생성함수 한 종류가 탄생되는 것이다!

더불어, \binom{n}{i}와 비슷하게 \frac{B(n)}{B(i)B(n-i)}를 생각할 수 있고 이는 사실 n-interval [x,y]에서 rank가 i인 원소의 개수와도 같다. 이 때 A(n)=\binom{n}{1}로 잡으면 B(n)=A(n)A(n-1)\cdots A(1)이 된다. 즉 factorial function의 이름이 생각보다 훨씬 본질과 가깝단 이야기.

이에 관련되어 incidence algebra와 합쳐지면 재미있는 사실들이 정말 많은데.. incidence algebra를 언급하는 것은 또 한 세월이 걸리고. Mobius algebra도 한 세월이 걸리고. 아쉽지만 이쯤에서 접도록 한다. 궁금한 사람들은 한 번 (\sum \frac{x^n}{B(n)})^2 = \sum f(n)\frac{x^n}{B(n)}이라 할 때 f(n)이 무엇인지 생각해보라. 참고로 ordinary이면 f(n)=n+1이고 exponential이면 f(n)=2^n이다. (답을 이야기하자면 interval의 길이가 n일 때 그 interval의 원소의 개수이다. ordinary는 [0,n]의 원소 개수가 n+1이고, exponential은 [\emptyset,[n]]의 원소의 개수는 곧 [n]의 부분집합의 개수이니까 2^n이고, …)

그리고, 방금 잡은 예에선 sum x^n/B(n)에 2제곱을 한 것인데 k제곱하면 어떻게 될까? (set이라면 무려 제2종 스털링 수가 등장한다!) doubly-exponential case는? 흥미진진하지 않을 수 없다.

REFERENCE
R. Stanley, Enumerative Combinatorics, Ch.3