Archive for the ‘ 수학 칼럼 ’ Category

2010 KMO 여름학교 “조합등식” 강의록

저번 8월의 여름학교에 조합론 강의를 했다. 많은 토픽 중에서 조합 등식에 대해 강의를 하였는데 그 때 나누어주었던 강의록을 올린다. 사실 중등부의 프린트는 아주 약간 다른 버젼이긴 한데, 차이래봤자 중등부엔 이항계수에 대한 개념적 설명이 더 추가됐고 맨 마지막 J 챕터를 없앤 것에 불과하니 고등부 버젼을 올린다. 조합등식이 올림피아드에 반드시 나오리란 보장도 없지만 증명하면서 많은 테크닉을 익힐 수 있어 더 없이 좋은 연습문제가 되리라 생각. 게다가 2010 USA TST #8로 조합등식 문제가 하나 나오기도 했지..

챕터 미리보기!

A. 조합등식이란
B. 생성함수
C. 생성함수의 이용 리뷰
D. 기초 조합등식
E. 포함과 배제의 원리
F. 차분법
G. 부호가 붙은 조합등식
H. 응용 조합등식
I. 심화 조합등식
J. 도전 조합등식

파일: 조합등식 강의록

Hensel’s Lemma

Hensel’s Lemma, 헨젤의 보조정리(혹은 Lifting Lemma)라는 것이 잘 알려져 있다. 그 내용은 다음과 같다.

다항식 f(x)와 소수 p에 대해, 어떤 정수 a가 있어 만약 f(a) \equiv 0\text{ (mod }p\text{)}이고 f'(a) \not\equiv 0\text{ (mod }p\text{)}이면 임의의 양의 정수 n에 대해 f(x) \equiv 0\text{ (mod }p^n\text{)}x\text{mod }p^n에서 유일하게 찾을 수 있다.

Proof. 증명 자체는 간단하다. 수학적 귀납법으로, 그런 x가 존재하며 동시에 x \equiv a\text{ (mod }p\text{)}임을 증명한다. n=1인 경우는 자명하고, n일 때의 성립을 가정하자. 즉 f(b) \equiv 0\text{ (mod }p^{n}\text{)}b가 유일하게 존재함을 가정한다. 그러면 f(b+kp^n)을 계산하자. 그를 위해 f(x)=c_nx^n+\cdots+c_1x+c_0이라 하자. 그러면 f(b+kp)-f(b) \equiv p^n f'(b)\text{ (mod }kp^{n+1}\text{)}임을 쉽게 알 수 있다. f'(b) \equiv f'(a)\text{ (mod }p\text{)}는 0이 아니므로 이 값은 k가 변함에 따라 p개의 서로 다른 값을 내놓는다. 그 중 하나는 반드시 \text{(mod }p^{n+1}\text{)}로 0이어야 하므로, 증명이 끝난다.

p^n에서 p^{n+1}로 ‘올린’다는 의미로 ‘Lifting’ Lemma로 불린다. 참고로 lifting은 여기에서뿐만이 아닌 Algebraic Number Theory에서도 나오는데 (사실 거의 똑같은 의미) 아마 이 개념의 일반화가 아닐지. (아니면 원래 저 개념이 있은 뒤에 간단한 경우로 specialization한 것일수도 있겠는데.. 자세한 이야기는 잘 모르겠다.)

이것을 직접적으로 이용하는 문제들도 있지만, 아이디어만을 이용해서 간접적으로 쓰는 문제들도 많다. 다음은 그런 문제들 중 (극히) 일부.

1. (2010 USA TST #1) 정수계수 다항식 P(x)P(0)=0\gcd(P(0),P(1),P(2),\cdots)=1을 만족한다고 하자. 이 때 다음을 만족시키는 양의 정수 n이 무수히 많음을 보여라.

\gcd(P(n)-P(0),P(n+1)-P(1),P(n+2)-P(2),\cdots)=n

2. (2008 Putnam) p는 소수이며, h(x)는 정계수 다항식으로 h(0),h(1),\cdots,h(p^2-1)\text{(mod }p^2\text{)}으로 서로 다르다고 한다. 이 때 h(0),h(1),\cdots,h(p^3-1) 역시 \text{(mod }p^3\text{)}으로 서로 다름을 보여라.

Finite Difference Method

미분 가능한 함수에서 미분이란 함수값의 변화량을 수치화한 것이다. 그렇다면 연속도 아닌 이산적인 함수에서 (즉, 정의역이 구간이 아니라 띄엄띄엄 떨어진 수들의 집합인 경우) 미분에 해당하는 것은 무엇일까? 논의는 여기에서 시작한다.

f\mathbb{Z}에서 정의되는 경우를 보자. 이 때 답은 단순하다. f(x+1)-f(x)f의 변화량을 나타낸다. 이제 Df(x)f(x+1)-f(x)로 정의하자. 즉 Df(x)라는 함수를 f(x+1)-f(x)로 바꾸는 함수의 변환이라 볼 수 있겠다. (마치 미분이 f(x)f'(x)로 바꾸듯)

그러면 D^nf(x)=\sum_{i=0}^n (-1)^{n-i} \binom{n}{i} f(x+i)가 성립한다. 증명이야 뭐.. 수학적 귀납법말곤 딱히.. 아무튼 이를 finite difference라 하고, 한국어로 어떻게 번역해야할지 고민한 끝에 차분법으로 명하기로 했다. (미분과 대조되는 개념으로, 차로 나눈다는 뜻의 差分) 그래서 차분법이란 이름으로 내가 쓴 책 “올림피아드 조합론”에도 실어버렸는데, 놀랍게도 일본어에서 똑같은 한자의 단어로 번역하고 있었다!

이제 특수한 경우, 즉 f가 다항수인 경우를 보자. 만약 f의 차수가 d이고 최고차항이 c_dx^d라 하자. 그러면 Df=c_d((x+1)^d-x^d)+\cdots인데 여기서 x^d는 전부 없어지고 x^{d-1}은 맨 첫 항에서만 나타나며 그 항은 dc_d x^{d-1}으로 계수가 0이 아니다. 따라서 차수는 정확히 1 줄어든다. 곧 D^nf(x)의 차수는 d-n이 된다. 곧 n=d이면 상수함수가 되고, n>d이면 0이 된다. 이를 다시 정리하면 다음과 같다.

n>d이면 \displaystyle \sum_{k=0}^n (-1)^k \binom{n}{k} f(k)=0이 성립한다.

실제론 f(k)가 아니라 f(x+k)인데, x만큼 옮기면 어차피 같은 함수니까 x=0인 경우만 state해줘도 상관이 없다.

사실 위의 정리는 다른 풀이가 많다. 다음은 그들을 간략히 설명한 것들.

First Solution. 앞의 풀이대로, D를 적용하면 차수가 하나씩 줄어들어서 성립.

Second Solution. 라그랑주 보간법. n=d+1일 때만 하면 그 이후는 자명한데, 그 때는 d+1개의 함수값이 주어지면 f를 결정할 수 있으므로 x=0,1,\cdots,d일 때를 대입한 결과들로 f를 구한 후 그에 x=d+1를 대입하면 얻을 수 있다. 방법만 알면 그 이후는 그저 계산일 뿐..

Third Solution. \binom{x}{i}i차 다항식으로, \binom{x}{0},\cdots,\binom{x}{n}n차 이하의 다항식들의 vector space over \mathbb{C}의 한 basis가 된다. 위 식에서 D^n(af+bg)=aD^nf+bD^ng이므로 \binom{x}{i}들에 대해서만 보이면 된다. 이는 \binom{n}{k}\binom{k}{i}=\binom{n}{i}\binom{n-i}{k-i}란 유명한 등식을 이용하면 증명이 된다.

Fourth Solution. 서인석 형님의 증명이다. 위와 같은 이유로 x^i에 대해서만 성립함을 보이면 되는데, \displaystyle \sum_{k=0}^n (-1)^k \binom{n}{k}k^ii개의 원소를 가진 집합에서 n개의 원소를 가진 집합으로 대응되는 전사함수의 개수와 같음을 포함과 배제의 원리로 보일 수 있다. 그러나 i \leq d <n이므로 그런 함수는 없으므로 이 값은 0이 된다.

저 정리를 이용하면 많은 문제들을 쉽게 증명하는 것이 가능하다. 먼저 조합등식들 중에 일부 문제들은 위의 내용을 응용하면 한 방에 증명이 된다. 그 예로 다음 문제를 본다.

p_1+p_2+\cdots+p_r<n을 만족하는 자연수 p_1,p_2,\cdots,p_r,n에 대하여 \displaystyle \sum_{k=0}^n (-1)^k \binom{n}{k} \binom{p_1+k}{k}\cdots \binom{p_r+k}{k}=0임을 보여라.

2003년 KMO 여름학교의 연습문제 중의 하나로 나온 문제. (출처가 더 있을 법한데 잘 모르겠다.) 책에는 모의고사라고 썼는데 오타..라기보다 헷갈렸다. 여튼, f(x)=\binom{p_1+x}{p_1} \cdots \binom{p_r+x}{p_r}로 잡으면 이 다항식의 차수가 p_1+\cdots+p_r<n이 되어 바로 대입하면 증명이 끝난다. 와우

이 문제의 별해도 있어 생성함수를 이용하여 증명할 수도 있고, 조합적인 해석을 할 수도 있다. 그러나 지금 너무 졸려져서 왠지 귀찮고.. 궁금하신 분들은 책을 참조하시길… (후에 귀차니즘에서 회복하면 다시 쓸 수도)

남은 문제들의 일부를 옮겨 적으면 다음과 같다.

1. (4th Mathlinks Contest) m \geq n일 때 \displaystyle \sum_{k=0}^n (-1)^k \binom{n}{k}\binom{m-k}{n}의 값을 구하여라.

2. (2008 Putnam) n \geq 3인 정수가 있다. 실계수 다항식 f,g가 있어 좌표평면에서 (f(1),g(1)),(f(2),g(2)),\cdots,(f(n),g(n))이 정n각형의 점들을 반시계방향으로 나열한 것이 되게 한다. 이 때 f,g중 적어도 하나는 차수가 n-1 이상임을 보여라.

3. (1983 IMO Short-list) F_1=F_2=1인 피보나치 수열 F_n이 있다. k=992,993,\cdots,1982일 때 P(k)=F_k를 만족하는 차수 990인 다항식 P에 대해 P(1983)=F_{1983}-1임을 보여라.

생성함수의 종류와 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

한 조합등식과 그 별해들

jackal_anu님의 블로그에서 퍼온 문제와 그 원형이 되는 문제 (sos440님의 블로그에서 퍼옴).

먼저 sos440님 블로그에 올라온 문제는 다음과 같다.

n이 음 아닌 정수이면 \displaystyle \sum_{k=0}^n \binom{n+k}{n}\frac{1}{2^{n+k}}=1이 성립한다.

이 문제도 여러 가지의 풀이를 발견하였다. 사실 예전에 봤던 문제인데 어디에서 봤는지는 기억이 잘 안 난다.

First Solution. 문제를 조금 바꾸어 \displaystyle \sum_{k=0}^n \frac{1}{2^k}\binom{n+k}{n}=2^n임을 증명하자. 이것의 생성함수는 \displaystyle \sum_{n=0}^{\infty}\sum_{k=0}^n\binom{n+k}{n}2^{-k}x^n=\sum_{k=0}^{\infty}\sum_{n=k}^{\infty}\binom{n+k}{n}2^{-k}x^n, 즉 \displaystyle \sum_{k=0}^{\infty}2^{-k} \left(\binom{2k}{k}x^k+\binom{2k+1}{k}x^{k+1}+\cdots \right)가 된다.

여기서 잠시 다른 길로 빠진다. 다음 Lemma를 보자.
Lemma. \displaystyle P_c(x)=\sum_{n=0}^{\infty}\binom{2n+c}{n}x^n이라 하자. 그러면 \displaystyle P_c(x)=\frac{1}{\sqrt{1-4x}} \left( \frac{1-\sqrt{1-4x}}{2x} \right)^n가 성립한다.
Proof of Lemma. P_c(x)=xP_{c+1}(x)+P_{c-1}(x)임을 쉽게 얻을 수 있다. (주세걸의 항등식 혹은 반데르몬드의 항등식) P_0(x)=\frac{1}{\sqrt{1-4x}}임과 P_1(x)=\sum \binom{2n+1}{n}x^n = \sum \frac{1}{2} \binom{2n+2}{n+1}x^n = \frac{P_0-1}{2x}임에서 점화식을 풀면 원하는 결과를 얻는다. QED

따라서 다시 원래 식으로 돌아가면 그 식은 \displaystyle \sum_{k=0}^{\infty} \left( \binom{2k}{k}( \frac{x}{2})^k + \binom{2k+1}{k} (\frac{x}{2})^k x + \cdots \right)
\displaystyle =\frac{1}{\sqrt{1-2x}} \left( 1+(1-\sqrt{1-2x})+(1-\sqrt{1-2x})^2+\cdots \right)
\displaystyle =\frac{1}{\sqrt{1-2x}} \frac{1}{1-(1-\sqrt{1-2x})}
\displaystyle =\frac{1}{\sqrt{1-2x}} \frac{1}{\sqrt{1-2x}} = \frac{1}{1-2x}가 된다. 따라서 그 x^n의 계수는 2^n이 되므로 증명이 끝난다.

다음은 조합적인 풀이. 아쉽게도 내가 발견한 것은 아니고, 이 문제가 올라왔을 때 같이 있었던 풀이이다. 누구 것인지마저 가물..

Second Solution. 문제를 바꾸어 \displaystyle \sum_{k=0}^n \binom{n+k}{n}2^{n+1-k}=2^{2n+1}임을 증명한다. O와 X를 적당히 택해 길이 2n+1인 것들을 본다. 전체 개수는 2^{2n+1}이다. 이제 O와 X가 홀수개이므로 어느 하나는 반드시 다른 하나보다 개수가 커야 한다. 이제 O가 X보다 많은 경우를 보자. 이 경우 O의 개수는 n+1개 이상이어야 한다. 이 때 n+1번째 O의 위치를 선택한 후 개수를 세어보자. 그 O는 n+1,n+2,\cdots,2n+1번째 위치에 올 수 있다. 이것이 오는 위치를 n+1+k번째 위치라 하자. 그러면 그 앞에는 O가 n개, X가 k개 있어야 하므로 그 개수는 \binom{n+k}{n}이다. 그리고 n+1번째 O의 오른쪽에는 O,X가 아무렇게나 배열될 수 있으므로 그 개수는 2^{n-k}이다. 따라서 이러한 가지수는 \displaystyle \sum_{k=0}^n \binom{n+k}{n}2^{n-k}이다. X가 O보다 많은 경우도 마찬가지로 같은 값이므로, 이 식에 2를 곱한 값인 좌변은 2^{2n+1}이 되어 증명이 끝난다.

다음은 아마 수학 올림피아드를 공부하는 학생들 중 대다수가 발견할 법한 수학적 귀납법 풀이.

Third Solution n=0인 경우는… 자명하다. n인 경우 성립을 가정하고 n+1인 경우를 본다. 그러면 \displaystyle \binom{2n+1}{n+1}\frac{1}{2^{2n+1}}+\binom{2n+2}{n+1}\frac{1}{2^{2n+2}} = \binom{2n+1}{n+1}\frac{1}{2^{2n+1}}+\binom{2n+1}{n}\frac{1}{2^{2n+1}}=\binom{2n+1}{n+1}\frac{1}{2^{2n}}이므로 n+1일 때의 식에서 n일 때의 식을 빼주면
\displaystyle \binom{n+1}{n+1}\frac{1}{2^{n+1}}+\cdots+\binom{2n}{n+1}\frac{1}{2^{2n}}+\binom{2n+1}{n+1}\frac{1}{2^{2n+1}}+\binom{2n+2}{n+1}\frac{1}{2^{2n+2}}-\binom{n}{n}\frac{1}{2^n}-\cdots-\binom{2n}{n}\frac{1}{2^{2n}}
\displaystyle =\binom{n+1}{n+1}\frac{1}{2^{n+1}}+\cdots+\binom{2n}{n+1}\frac{1}{2^{2n}}+\binom{2n+1}{n+1}\frac{1}{2^{2n}}-\binom{n}{n}\frac{1}{2^n}-\cdots-\binom{2n}{n}\frac{1}{2^{2n}}
\displaystyle =\binom{n+1}{n+1}\frac{1}{2^{n+1}}+\cdots+\binom{2n}{n+1}\frac{1}{2^{2n}}+\binom{2n}{n+1}\frac{1}{2^{2n}}-\binom{n}{n}\frac{1}{2^n}-\cdots-\binom{2n-1}{n}\frac{1}{2^{2n-1}}
\displaystyle = \binom{n+1}{n+1}\frac{1}{2^{n+1}}+\cdots+\binom{2n-1}{n+1}\frac{1}{2^{2n-1}}+\binom{2n}{n+1}\frac{1}{2^{2n-1}}-\binom{n}{n}\frac{1}{2^n}-\cdots-\binom{2n-1}{n}\frac{1}{2^{2n-1}}
이 된다. 여기서 잘 보면, 두 번째 식의 2n2n-1로 바꾼 식이 네 번째 식이다. 즉 위의 과정은 항을 두 개씩 줄이는 과정이 되고 이를 계속 하면 그 결과는 \displaystyle \binom{n+1}{n+1}\frac{1}{2^{n+1}}+\binom{n+2}{n+1}\frac{1}{2^{n+1}}-\binom{n}{n}\frac{1}{2^n}-\binom{n+1}{n}\frac{1}{2^{n+1}}이 되고 이것이 0임은… 또 자명하다. 끝.

위의 증명에서 중간에 얻은 사실을 (수학적 귀납법의 step) 정리하면 다음과 같이 쓸 수 있다.
Lemma. \displaystyle \sum_{k=n+1}^m \binom{k}{n+1}\frac{1}{2^k}+\binom{m+1}{n+1}\frac{1}{2^m} = \sum_{k=n}^{m} \binom{k}{n}\frac{1}{2^k}

이제 다음 풀이를 보자. 이번엔 생성함수를 다른 방법으로 응용하였다. 후에 보게 되겠지만, 이 방법은 일반화에서도 유효하다.

Fourth Solution. \displaystyle \sum_{k=0}^n 2^{n-k}\binom{n+k}{n}=2^{2n}임을 보이자. 좌변은 \displaystyle \frac{1}{1-2x} \frac{1}{(1-x)^{n+1}}x^n의 계수가 됨을 알 수 있다. 그런데 \displaystyle \frac{1}{1-2x} \frac{1}{(1-x)^{n+1}}을 partial fractions로 나타내면 그 결과는 \displaystyle \frac{2^{n+1}}{1-2x}-\frac{2^n}{1-x}-\frac{2^{n-1}}{(1-x)^2}-\cdots-\frac{2^0}{(1-x)^{n+1}}이다. 따라서 이 식의 x^n의 계수는 \displaystyle 2^{n+1}2^n - 2^n \binom{n}{n}-2^{n-1}\binom{n+1}{n}-\cdots-2^0\binom{2n}{n}이 되는데, 잘 보면, \displaystyle 2^n \binom{n}{n}+2^{n-1}\binom{n+1}{n}+\cdots+2^0\binom{2n}{n}이 바로 우리가 구하는 값이다. (!) 따라서 이 값을 S라 하면 S=2^{2n+1}-S가 되어 S=2^{2n}이 되어 증명이 끝난다.

이제 이것의 일반화인 jackal_anu 님의 조합등식을 보자.

p,q가 음 아닌 정수이면 \displaystyle \sum_{k=0}^q \frac{1}{2^{p+k}}\binom{p+k}{k}+\sum_{k=0}^p \frac{1}{2^{q+k}}\binom{q+k}{k}=2가 성립한다.

p=q를 대입하면 처음에 소개한 조합등식을 얻을 수 있다.

First Solution. 위 문제의 Third Solution에서 쓴 방법을 그대로 이용한다. p는 그대로 놔두고 q에 대한 수학적 귀납법을 쓴다. q=0이면 \displaystyle \frac{1}{2^p}\binom{p}{0}+\binom{0}{0}+\frac{1}{2}\binom{1}{1}+\cdots+\frac{1}{2^p}\binom{p}{p}=2를 얻는다. 이제 q일 때 성립함을 가정하고 q+1일 때의 식에서 q일 때의 식을 빼면 그 값은
\displaystyle \frac{1}{2^{p+q+1}}\binom{p+q+1}{q+1} + \sum_{k=q+1}^{p+q+1}\frac{1}{2^k}\binom{k}{k-q-1} - \sum_{k=q}^{p+q} \frac{1}{2^k} \binom{k}{k-q}인데 이 식 정리하면 위의 Lemma에서 n=q,m=p+q를 대입한 것이 되어 0이다. 끝. (원래 문제의 Third Solution의 analogue)

Second Solution. 문제를 바꿔 \displaystyle 2^{p+q+1}=\sum_{k=0}^q 2^{q-k}\binom{p+k}{p} + \sum_{k=0}^p 2^{p-k}\binom{q+k}{q}임을 보이자. 앞 문제의 Fourth Solution과 비슷하게 생각하면, 앞의 summation은 \displaystyle [x^q]\frac{1}{1-2x}\frac{1}{(1-x)^{p+1}}이고 뒤의 summation은 \displaystyle [x^p]\frac{1}{1-2x}\frac{1}{(1-x)^{q+1}}이다. 앞에서 구한 결과를 이용하면 앞의 summation은 \displaystyle [x^q]( \frac{2^{p+1}}{1-2x}-\frac{2^p}{1-x}-\cdots-\frac{2^0}{(1-x)^{p+1}}이므로 \displaystyle 2^{p+q+1}-2^p\binom{q}{q}-2^{p-1}\binom{q+1}{q}-\cdots-2^0\binom{q+p}{q}가 된다. 마찬가지로 두 번째 summation의 값은 \displaystyle 2^{q+p+1}-2^q\binom{p}{p}-2^{q-1}\binom{p+1}{p}-\cdots-2^0\binom{p+q}{p}이다. 그런데 이번에도, 두 summation의 결과의 첫항을 제외한 것들은 원래 값과 같다! 그래서 그 합을 S라 하면 S=2^{p+q+2}-S가 되어 원하는 결과를 얻는다. (원래 문제의 Fourth Solution의 analogue)

Third Solution. 역시 \displaystyle 2^{p+q+1}=\sum_{k=0}^q 2^{q-k}\binom{p+k}{p} + \sum_{k=0}^p 2^{p-k}\binom{q+k}{q}를 보이자. 이번엔 앞의 문제의 Second Solution을 응용하자. O과 X를 p+q+1개를 늘어놓는다. 그러면 O가 p+1개 이상 나오거나 X가 q+1개 나오거나 둘 중 하나이며, 두 event가 동시에 일어날 수 없다. 앞의 경우 p+1번째 O가 나오는 곳이 p+k+1이라 하면 그 가지수는 \binom{p+k}{p}2^{q-k}가 된다. 이들을 모든 k에 대해 더하면 첫 번째 summation. 마찬가지로, 두 번째 event의 경우의 수가 두 번째 summation이 되어 증명이 끝난다.

여기서 부가적으로 \displaystyle \sum_{k=0}^q 2^{q-k}\binom{p+k}{p} = \sum_{k=0}^q \binom{p+q+1}{k}가 됨을 확인할 수 있다. 이는 앞의 문제의 refinement가 되겠다.

A Weak Generalization. \displaystyle \sum_{k=0}^q 2^{q-k}\binom{p+k}{p} = \sum_{k=0}^q \binom{p+q+1}{k}

jackal_anu 님의 마지막 일반화를 보자. 다음 등식 역시 sos440님의 등식이다.

p,q가 음 아닌 정수이면 \displaystyle (1-x)^{p+1}\sum_{k=0}^q\binom{p+k}{p}x^k+x^{q+1}\sum_{k=0}^p\binom{q+k}{q}(1-x)^k=1이 성립한다.

x=\frac{1}{2}를 대입하면 위의 문제가 됨을 확인할 수 있다.

First Solution. jackal_anu 님의 풀이. 이 풀이는 앞의 문제의 Third Solution과 관련이 깊다. 간략히 설명하자면, O,X를 p+q+1개 쓰되 O가 나올 확률을 1-x, X가 나올 확률을 x로 두고 O가 p+1개 이상 나오는 확률과 X가 q+1개 이상 나오는 확률의 합이 1임을 이용한다.

Second Solution. sos440님의 풀이. 또 간략히 설명하자면
\displaystyle \sum_{k=1}^{q} \binom{p+1+k}{k} x^k=\sum_{k=1}^{q} \sum_{j=0}^{k} \binom{p+j}{j} x^k
\displaystyle =\sum_{j=0}^{q} \sum_{k=j}^{q} \binom{p+j}{j} x^k=\sum_{j=0}^{q} \binom{p+j}{j} \frac{x^j - x^{q+1}}{1-x}
\displaystyle =\sum_{k=0}^{q} \binom{p+k}{k} \frac{x^k-x^{q+1}}{1-x}=\frac{1}{1-x} \left( \sum_{k=0}^{q} \binom{p+k}{k} x^k - \binom{p+q+1}{q} x^{q+1} \right)
임을 이용한다.

It’s my turn!

Third Solution. 설마 수학적 귀납법이 또 통할줄이야… 원래 문제의 Third Solution, 두 번째 문제의 First Solution의 뜻을 계승한다. 대략적인 설명만 하자면 q에 대한 수학적 귀납법으로 q=0인 경우는 또 자명하고 q+1일 때의 식에서 q일 때의 식을 빼면 그 결과가 정리하면 \displaystyle \sum_{k=0}^{p-1}\binom{q+1+k}{q+1}x(1-x)^{k}+\binom{q+p+1}{q+1}(1-x)^p - \sum_{k=0}^{p}\binom{q+k}{q}(1-x)^k가 되는데, 이번에도 맨 끝에서 장난을 쳐서 두 항을 없애는 식으로 계속 해나가면 0이 되어 원하는 결과를 얻는다.

Fourth Solution. 설마 생성함수 방법도 또 통할줄이야…… 원래 문제의 Fourth Solution, 두 번째 문제의 Second Solution과 뜻을 같이한다. 식을 변형하여 \displaystyle (1-x)\sum_{k=0}^q\binom{p+k}{p}\frac{1}{x^{q-k}}+x\sum_{k=0}^p\binom{q+k}{q}\frac{1}{(1-x)^{p-k}}=\frac{1}{x^q(1-x)^p}임을 보인다. 첫 번째 summation을 보자. 이것은 앞에서와 마찬가지로 생각하면 \displaystyle [z^q](1-x)\frac{1}{1-\frac{z}{x}}\frac{1}{(1-z)^{p+1}}인데, \displaystyle (1-x)\frac{1}{1-\frac{z}{x}}\frac{1}{(1-z)^{p+1}}을 partial fractions로 표현하면 그 결과 \displaystyle \frac{1}{(1-x)^p}\frac{1}{1-\frac{z}{x}}-\frac{x}{(1-x)^p}\frac{1}{1-z}-\cdots-\frac{x}{(1-x)^0}\frac{1}{(1-z)^{p+1}}이 된다. 이것의 z^q의 계수는 \frac{1}{(1-x)^p}\frac{1}{x^q}-\frac{x}{(1-x)^p}\binom{q}{q}-\cdots-\frac{x}{(1-x)^0}\binom{q+p}{q}가 되는데, 여기서 첫 항을 제외한 뒤의 항들의 합은 원래 식에서의 두 번째 summation이 되어 바로 증명이 끝난다. (합해서 2 \frac{1}{(1-x)^p}\frac{1}{x^q}-S=S이므로 어쩌구 이런 식의 논의로 해도 상관은 없다.)

Fifth Solution. 먼저 위 문제의 Third Solution에서 refine하듯 여기서도 First Solution에 의거하여 refine할 수 있다. 그 식이란 \displaystyle (1-x)^{p+1}\sum_{k=0}^q \binom{p+k}{k}x^k= \sum_{k=0}^q \binom{p+q+1}{k}x^k(1-x)^{q-k}이다. 여기서 1-x=y라 하고 x+y=1임을 이용하여 homogenization하면 다음과 같은 이쁜 식을 얻는다.
A Bit Stronger Generalization. \displaystyle \sum_{k=0}^q\binom{p+k}{k}x^k(x+y)^{q-k}=\sum_{k=0}^q\binom{p+q+1}{k}x^ky^{q-k}
이 일반화는 앞에서의 A Weak Generalization의 일반화도 된다. x=y=1을 대입하면..
이제 이 일반화를 증명하자. 0 \leq n \leq q에 대해 x^ny^{q-n}의 계수를 비교하면, \displaystyle \binom{p}{0}\binom{q}{n}+\binom{p+1}{1}\binom{q-1}{n-1}+\cdots+\binom{p+n}{n}\binom{q-n}{0}=\binom{p+q+1}{n}임을 보이면 된다. (거의 다른 문제로 바뀌었다!) 이 식의 좌변은 \displaystyle \left( \binom{p}{0}+\binom{p+1}{1}x+\cdots \right) \left( \binom{q-n}{0}+\binom{q-n+1}{1}x+\cdots \right), 즉 \displaystyle \frac{1}{(1-x)^{p+q-n+2}}x^n의 계수이다. 따라서 그 값은 \displaystyle \binom{(p+q-n+1)+n}{p+q-n+1}=\binom{p+q+1}{n}이 되어 증명이 끝난다.

Sixth Solution. 이 풀이로 별해 개수를 늘리는게 큰 의미가 있을까도 싶다만.. 앞의 A Bit Stronger Generalization을 다른 방법으로 증명한다. 먼저 위 식에 q 대신 q+n을 대입해 대칭꼴인 \displaystyle \sum_{k=0}^n \binom{p+k}{p}\binom{q+n-k}{q}=\binom{p+q+n+1}{n}으로 바꾼다. 이제 1,2,\cdots,p+q+n+1에서 p+q+1개의 수를 택하는 경우를 보자. 그 경우의 수는 물론 \binom{p+q+n+1}{p+q+1}, 즉 우변이다. 한 편 크기순으로 p+1번째 수가 무엇인지를 주목하자. 그것은 p+1,p+2,\cdots,p+n+1가 후보인데 p+1+k라 하면 그보다 작은 수들에선 p개를 뽑아야 해 경우의 수가 \binom{p+k}{p}가 되고 그보다 큰 수들에선 q개를 뽑아야 해 경우의 수가 \binom{q+k}{q}가 된다. 따라서 이들을 곱해 전부 합하면 그 값은 좌변이 되어 문제가 증명된다.

Any other solutions?

직선 OI 위의 점들

2007년에 썼던 글을 조금 다듬어서 다시 올린다.

그동안 몇 가지 세 쌍의 직선들이 한 점에서 만나는 사실을 관찰했는데, 그 점들 대부분이 직선 OI에 놓이게 되는 사실이 있었기에 그 점들을 소개하고자 한다.

(1) 삼각형 ABC와 닮음이며 ABC의 내접원에 내접하는 삼각형 중 대응변이 평행인 삼각형은 두 개 있다. 그 중 대응되는 점의 거리가 더 가까운 것을 생각하고, 그 닮음의 중심을 C_1이라 한다. 이 때 이 삼각형에서 ABC에의 닮음변환을 생각하면 내접원이 외접원이 되므로 C_1, O, I는 한 직선 위에 있으며, \frac{IP}{OI} = \frac{r}{R-r}가 성립한다.

(2) 이번엔 두 삼각형 중 나머지, 즉 대응되는 점의 거리가 더 먼 것의 닮음의 중심을 C_2라 한다. 그러면 역시 마찬가지 이유로 C_2, O, I가 한 직선 위에 있으며, \frac{IC_2}{OI} = \frac{-r}{R+r}가 된다. (-의 의미는 반직선 OI와 IQ의 방향이 다름을 의미한다.)

(3) ABC의 내접원과의 접점으로 이루어진 삼각형의 구점원의 중심을 X라 하면, O, I, X가 한 직선 위에 있게 된다. 이는 반전에 의한 풀이 혹은 벡터에 의한 풀이로 구할 수 있다. 이 때 벡터에 의한 풀이를 연장하면 \frac{IX}{OI} = \frac{r}{2R}을 얻는다.

(4) 삼각형 ABC의 내접원이 각 변에 접하는 점을 P,Q,R이라 한다. 외접원에 내접하고 내접원과는 P, Q, R에서 외접하는 원들을 잡고 그들과 외접원의 접점을 P', Q', R'이라 한다. 이 때 P'P, Q'Q, R'R는 한 점에서 만나는데 이는 바로 (2)의 C_2가 된다.

(5) 위와 같은 상황에서, AP', BQ', CR'는 한 점에서 만나는데, 그를 K라 하면 \frac{IK}{OI} = \frac{2r}{2R-r}가 된다.

(6) 삼각형 ABC의 외접원과는 A,B,C에서 내접하고 내접원과는 외접하는 원들이 내접원과 접하는 점을 P, Q, R이라 한다. 그러면 AP, BQ, CR은 한 점에서 만나는데 그것은 역시 (2)의 C_2가 된다.

(7) 이번엔 A,B,C에 내접하고 내접원과는 내접하는 원들의 접점을 P, Q, R이라 하면 AP, BQ, CR은 한 점에서 만나며 그것은 이번엔 (1)의 C_1가 된다.

즉 결론적으로 OI 위에 C_1, C_2, X, K를 잡을 수 있는 것이 된다. 증명은 간단한 경우가 많으니 한 번 직접 시도해보길.

Ehrhart 다항식과 Pick의 정리

2009년 가을 학기에 역시 Richard Stanley 교수님 수업을 듣다가 배운 것 중 가장 흥미로웠던 Ehrhart polynomial을 혼자 재정리했던 내용이다. 천년바위라는 다른 곳의 게시판에 남긴 내용을 조금 다듬어 옮긴다.

Pick의 정리에 대해 들어본 적이 있을 것이다. 간략히 설명하자면, 좌표평면에서 두 좌표가 정수인 것을 격자점이라 할 때 꼭지점이 격자점인 도형의 넓이는 흥미롭게도 (도형 내부의 점의 개수) + (테두리 위의 점의 개수)/2 – 1이 된다. 만약 도형이 무지 큰 경우를 생각하면, 각 점을 중심으로 하는 단위정사각형들이랑 넓이가 얼추 비슷해질 것이다. 대충 그런 의미.

이것이 신기한 이유는 도형의 넓이를 계산하는 것은 복잡할 것 같은데 점의 개수만 세면 되기 때문이다. (비록 격자점 case에만 해당되지만) 곧 소개하겠지만, 점의 개수를 센다는 것이 사실은 생각보다 엄청난 행위이다.

이제 이를 3차원으로 확장해보자. 만약 어떤 다면체의 꼭지점들이 전부 격자점이면 그 부피는 무엇과 연관이 있을까? 내부의 점과 면 위의 점들 개수란 두 정보만으로 표현이 될까? 약간 아쉽지만 답은 부정적이다. 하지만 뭔가 한 요소를 더하면 표현이 가능하다! 왜 둘만으로는 부족할까. “왜냐하면 3차원이기 때문이다. 2차원에선 두 가지 요소로 표현이 되지만 3차원에선 세 가지 요소가 필요하다.”란 설명은 뭔가 상당히 석연찮은 설명이다. 하지만 결과론적으로 저 설명이 맞다. 왜냐하면 n차원 내에서의 볼록 격자 도형은 차수가 n인 다항식이 붙고 그 최고차항계수가 부피와 연관되기 때문이다.

그럼 본격적으로 어떤 다항식인지 알아보자. Ehrhart polynomial이란 이름이 붙은 다항식은 m차원 공간 \mathbb{R}^m에서 \mathbb{Z}^m의 원소들을 꼭지점으로 갖는 볼록도형 P에 대해, i(P,n) = \#\{nP \cap \mathbb{Z}^m\}으로 정의된다. 즉, Pn배 확대시킨 것의 내부의 (경계 포함) 격자점 개수로 정의한다. 아주 쉬운 예로, 2차원 공간에서 (0,0), (1,0), (1,1), (0,1)을 꼭지점으로 갖는 정사각형을 생각한다면 i(P,n)=(n+1)^2이 된다. 이와 쌍대적인 개념으로 (dual) \bar{i}(P,n)을 생각할 수 있는데, 이것은 Pn배 확대시킨 것의 내부 (경계 포함하지 않음) 격자점의 개수이다. 즉 위의 예시에서 \bar{i}(P,n)=(n-1)^2이다.

위와 같이 정사각형처럼 변들이 착착 맞아떨어지는 경우라면 저 식이 n에 대한 다항식이 되리란건 알겠는데, 만약 좀 더 복잡하게 생긴 도형이라면? 그 때도 저렇게 일이 잘 풀린다면 얼마나 좋을까. 그런데 그게 실제로 일어났습니다. 바로 i(P,n)n에 대한 유리계수 다항식임이 증명된 것이다. 또한 그 차수는 P의 차수 d가 되고, (꼭 d=m일 필요는 없다. 삼차원에서 평면 도형인 정사각형을 잡을 수 있듯이) 그 최고차항의 계수는 P의 volume이 되며, i(P,0)=1임을 보인 것이다. (이들의 증명은 positive monoid에 대한 언급을 하지 않을 수 없는데 너무 길어지므로 생략한다.) 또한 충격적이게도, 내부의 점의 개수를 세는 \bar{i}i와 밀접한 관계가 있음도 보여졌다. 바로 \bar{i}(P,n) = (-1)^d i(P,-n)이 되는 것이다. 즉, i(P,n)이란 다항식은 기본적으로 n이 양수라면 n배했을 때의 도형 안의 점의 개수인데 n이 음수라면 그것을 n배했을 때 경계를 제외한 내부의 점의 개수 (에 적당히 부호가 붙은) 가 되는 것이다.

이제 연결고리가 보인다. 2차원의 경우 그 Ehrhart polynomial은 P의 넓이가 A일 때 i(P,n)=An^2 + an + 1로 주어져야 한다. 이 때, i(P,1)=I+B, i(P,-1)=I가 되니까 이 결과들을 종합하면 우리가 원하는 결과인 Pick의 정리를 얻는 것이다. 2차원이니까 식이 2차, 따라서 세 점에 의해 다항식 결정, 그런데 최고차항 계수가 바로 넓이 => 넓이와 몇 가지 “점들의 개수” 간의 관계 도출. 이것이 주요 flow이다.

따라서, 도형이 주어지면 그것을 적당히 확대하여 점을 세는 것만으로 그 도형의 일종의 특성식(=Ehrhart polynomial)을 얻어낼 수 있다는 것이다! 앞에서 점을 세는 행위가 왜 중요한 행위가 되었는지에 대해 짤막히 언급했는데 그 이유가 여기에 있다.

그리하여 Pick의 정리와 똑같은 짓을 Reeve란 사람이 3차원으로 확장했고, Macdonald란 사람이 햄버거 세트를 4차원 이상으로 확장했다. 즉 앞에서 말한 특성식이 구체적으로 어떤 결과를 가져다 주는지를 밝혔다. 정확한 식은 구글링하면 나올텐데 별로 중요치 않고, 중요한 사실은 i(P,2), i(P,1), i(P,0), i(P,-1)의 값을 기하적으로 표현할 수 있고, 최고차항의 계수가 P의 부피임을 이용하여 부피, 도형 내부의 점의 개수, 도형 경계의 점의 개수, 그리고 도형을 2배 확대했을 때의 내부의 점의 개수들의 관계식을 얻어낼 수 있다는 것이다.

예제 1. 음수 계수를 갖는 Ehrhart polynomial이 존재하는가?
예제 2. \mathbb{R}^d에서 2d개의 벡터 \pm e_i들의 볼록포로 이루어진 도형의 Ehrhart polynomial을 i(P_d,n)이라 하면 \displaystyle (1-x)^{d+1} \sum_{n \geq 0} i(P_d,n) x^n은 어떤 다항식이 된다. 그 값을 구하여라.
예제 3. \displaystyle \sum_{n\geq 0}i(P,n)x^n=\frac{1+x^3}{(1-x)^4}, 즉 i(P,n)=\binom{n+3}{3}+\binom{n}{3}인 격자점 볼록 다양체 P는 존재하지 않음을 보여라.

Reference.
M. Beck and S. Robins, Computing the Continuous Discretely, Ch. 3
R. Stanley, Enumerative Combinatorics, Ch. 4