Cayley formula에 대한 George Polya의 아이디어

저번 언젠가 T_n을 number of trees on [n]이라 할때 다음 항등식이 성립한다고 햇다.

 

증명은 두 트리를 붙이는 가짓수를 셈으로써 증명한다. 저 summand index k가 1부터 n-1까지만 딱 돌아가는걸 봐서 abel formula로 induction을 완성시킬 수 잇다는 것이 저번 포스팅이엇다.

Cayley formula를 증명할 때 algorithmic한 bijection을 증명도 여럿 잇다.(Cayley 본인도 그렇게 햇고 ㅇㅇ) Prufer code가 가장 대표적인 예시이고 이걸 이용하면 좀 더 general한 항등식도 여럿 이끌어낼수 잇다. 그 외에도 rooted forest의 recursive structure를 이용하는 것도 잇고 다른 방법도 잇다. 저번 포스팅한 parking function도 algorithmic한 bijection을 찾은 후 Pollak의 확률론적 방법을 인용하면 하나의 증명이 되긴 하지만 확률론에서 algorithm을 잃어버린다.

여기서 포스팅하려고 하는 것은 약간의 complex analysis를 이용한 George Polya의 증명이다. 증명이 다른 증명들과 그림이 너무 달라서 인상이 깊엇기에 포스팅한다. (참 이런 것들을 대가의 아이디어에 감탄하는 것도 공부하는 사람으로서 얻는 즐거움 중 하나임은 분명한 듯하다.)

어떤 수열을 공부할때 흔히 recursion relation이나 ordinary(exponential) generating function을 조사하고 또, recursion relation을 통해 generating function을 구체적으로 구해서 수열의 정보를 알아내는 것도 전형적인 방법 중 하나이다. generating function에서 convergence를 구체적으로 묻지 않고 그저 formal power series로 취급하는 것이 일반적이다.

복소함수론에서도 power series를 중요하게 생각하는데 가 한 점 a에서 local하게 power series로 표현이 가능하면 f is holomorphic at a 또는 analytic at a라 말한다. 전자는 주로 복소함수론에서 쓰는 말이고 후자는 real case에서 쓰는 말이다. f가 점 a에서 holomorphic하면 

가 성립하고 이를 Cauchy formula라 한다. 적분 contour C는 a를 감싸는 simple closed contour. 이 식은 holomorphic function을 연구하는데 초석이 되고 아주 강력하다. rough하게 말해서 저 식의 양변을 a에 대해 n번 미분하고 다시 a를 대입하면

                                                                

이 된다. 이는 holomorphic function은 미분과 적분이 아주 긴밀한 관계에 잇음을 말해주는데 여기서부터 신기한 성질들이 많이 나온다(리우빌 정리 같은...).

자 이제 Cayley formula를 증명해보자. 우선 라 해보자. 기존 exponential generating function에서 살짝 modified되엇다(다 Polya의 깊은 생각에서 나왓겟지... 전체 증명에서 함수 t(x)를 이렇게 잡아야 좋다는걸 알아내는게 가장 힘들듯 하다).

Claim.

증명.

 

 

두 함수를 곱해보자. 

이 되므로,  이고 x=0를 대입해서 상수 A=1을 얻는다.

여기까지는 점화식을 가지고 generating function을 알아내는, 자주 하는 계산이다. 이제 복소함수론을 쓸 차례다. C를 원점을 감싸는 simple closed contour(in counterclockwise)라 하자. Cauchy formula에 의해 다음이 성립한다.

   

평소 보던 공식과는 조금 다른데 그 이유는 물론 t(x)를 조금 다르게 잡앗기 때문이다. 저 T_n이 정확히 저렇게 된다는 것은 계산으로 알 수 잇다. 흐름에 크게 중요하지 않으므로 체크하지 않겟다.

이제 curve C를 도는 z를 치환적분할 것이다. 라 하면, (...!)

따라서

  

                     

짜잔. 저 적분이 최종적으로 사라지는 부분은 저 위의 general Cauchy formula로부터 나온다.

증명이라고 이리 햇지만, 정당화가 필요한 부분이 좀 잇다. 멱급수를 잡긴 잡앗지만 복소함수론의 지식을 쓰려면 수렴성을 확인해야되고 또한 저 역함수 치환이 타당한 지도 검토해봐야 한다. 여튼 여기서는 아이디어 위주로 설명햇고, 자세한 계산은 스스로 해보면 도움될 것이다.