Posts Tagged ‘ 조합등식 ’

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

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

챕터 미리보기!

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

파일: 조합등식 강의록

Advertisements

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임을 보여라.

한 조합등식과 그 별해들

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?

2010 USA TST #8

다음은 앞에서 올린 2010 USA TST의 한 문제이다.

8. m \geq n이 자연수이며 Sa_1+a_2+\cdots+a_n=m인 양의 정수쌍 (a_1,a_2,\cdots,a_n)의 집합이라 하자. 이 때, 다음 등식이 성립함을 보여라.

\displaystyle \sum_{S}1^{a_1}2^{a_2}\cdots n^{a_n}=\binom{n}{n}n^m-\binom{n}{n-1}(n-1)^m+\cdots+(-1)^{n-2}\binom{n}{2}2^m+(-1)^{n-1}\binom{n}{1}

이 식은 간단히 써서 \displaystyle \sum_{a_1+\cdots+a_n=m}1^{a_1}2^{a_2}\cdots n^{a_n}=\sum_{i=0}^{n} \binom{n}{i}(-1)^i (n-i)^m이라 할 수 있다.

First Solution. 순수하게 생성함수만을 이용하여 문제를 풀어보자.
좌변에 대한 생성함수인 \displaystyle \sum_{m=1}^{\infty}\sum_{a_1+\cdots+a_n=m}1^{a_1}2^{a_2}\cdots n^{a_n} x^m을 표현하자. 이는 \displaystyle \sum_{m \geq 1} \sum_{a_i} (1x)^{a_1}(2x)^{a_2} \cdots (nx)^{a_n}, 즉 \frac{x}{1-x}\frac{2x}{1-2x} \cdots \frac{nx}{1-nx}=\frac{n!x^n}{(1-x)(1-2x)\cdots (1-nx)}가 된다.

한 편, 우변의 생성함수는
\displaystyle \sum_{m=1}^{\infty}\sum_{i=0}^{n-1} \binom{n}{i} (-1)^i (n-i)^m x^m =\sum_{i=0}^{n-1}\sum_{m=1}^{\infty} \binom{n}{i} (-1)^i (n-i)^m x^m
\displaystyle =\sum_{i=0}^{n-1}\binom{n}{i}(-1)^i \sum_{m=1}^{\infty} ((n-i)x)^m =\sum_{i=0}^{n-1}\binom{n}{i}(-1)^i \frac{(n-i)x}{1-(n-i)x}
\displaystyle =\sum_{i=0}^{n-1}\binom{n}{n-i}(-1)^i \frac{(n-i)x}{1-(n-i)x} =\sum_{i=0}^{n-1}n \binom{n-1}{n-i-1}(-1)^i \frac{x}{1-(n-i)x}
\displaystyle =nx\sum_{i=0}^{n-1}\binom{n-1}{i}(-1)^i \frac{1}{1-(n-i)x}가 되므로,
\displaystyle \frac{(n-1)!x^{n-1}}{(1-x)(1-2x)\cdots (1-nx)} = \sum_{i=0}^{n-1} \binom{n-1}{i}(-1)^i \frac{1}{1-(n-i)x}
임을 확인하면 된다. 이는 곧
\displaystyle (n-1)!x^{n-1} = \sum_{i=0}^{n-1} \binom{n-1}{i}(-1)^i \frac{(1-x)(1-2x)\cdots(1-nx)}{1-(n-i)x}
임을 확인하는 것인데, 양변이 둘 다 차수가 n-1차인 다항식이므로 n개의 x의 값에 대해 양변이 일치하면 된다. 이제 1 \leq k \leq n에 대해 x=\frac{1}{k}를 대입하자. 그러면 좌변은 \frac{(n-1)!}{k^{n-1}}이고 우변은 i=n-k에 해당하는 항을 제외하곤 전부 소거되고 n-k번째 항인 \displaystyle \binom{n-1}{n-k}(-1)^{n-k}(1-\frac{1}{k})(1-\frac{2}{k}\cdots(1-\frac{k-1}{k})(1-\frac{k+1}{k})\cdots(1-\frac{n}{k})만 남는다. 이는 정리하면 \displaystyle \frac{(n-1)!}{(n-k)!(k-1)!}(-1)^{n-k}\frac{(k-1)(k-2) \cdots 1 (-1)(-2) \cdots (-(n-k))}{k^{n-1}} = \frac{(n-1)!}{k^{n-1}}이 된다. 따라서 문제가 증명된다.

사실 가장 먼저 발견한 풀이는 다음 semi-combinatorial한 풀이였다. 우변을 보자마자 전사함수 개수를 떠올려버려서, 거의 10분만에 풀었다. -_-;; 위의 생성함수 풀이는 그 후에 발견한 풀이.

Second Solution. 이번엔 조합적으로 식을 해석한다. 먼저 우변은 포함과 배제의 원리를 이용하여 원소의 개수가 m개인 집합에서 n개인 집합으로 가는 전사함수의 개수임을 확인할 수 있다. 한 편 좌변의 생성함수는 \displaystyle \frac{n!x^n}{(1-x)(1-2x)\cdots (1-nx)}임을 앞 풀이에서 이미 확인했다. 그런데 이것의 x^m의 계수는 바로 n!(S(m,n)), 즉 제2스털링 수이다. 이것은 m개짜리 집합을 n개의 공집합 아닌 집합들로 나누는 분할의 가지수에 n!을 곱한 것이다. 이는 이렇게 해석해볼 수 있다. 먼저 정의역의 m개의 원소들을 n개의 부분집합들로 분할한 후, 각각의 부분집합이 치역의 어느 원소로 대응될지를 결정하는 것이다. 앞의 경우의 수가 S(m,n)이고 뒤의 경우의 수가 n!이므로 문제는 증명된다.

그런데 제2스털링수가 나오니, 예전에 Enumerative Combinatorics Vol. 1을 공부하다가 제2스털링수와 관련된 일대일대응을 배운 것이 기억나서 순수 조합적인 풀이를 찾으려 노력했고 그 결과는 다음과 같다.

Third Solution. 앞에서 해결한 바와 같이 우변은 원소가 m개인 집합에서 n개인 집합으로 가는 전사함수의 개수이고, 이는 곧 원소가 m개인 집합을 n개의 부분집합으로 분할한 후 n!을 곱한 값과 같다. 이런 분할마다 다음과 같이 m의 분합(composition)으로 대응하자. a_n+\cdots+a_{n-i+1}집합의 분할에서 1,2,\cdots,r을 없앴을 때 남은 부분집합의 개수가 (공집합 제외) n-i개가 되도록 하는 최소의 r 정의한다. 예컨대, m=4,n=2의 한 예인 \{ 1,3 \}, \{ 2,4 \}의 경우 1,2,3을 지워야 비로소 한 개의 부분집합만 남게 되므로 a_2=3, a_1+a_2=4(a_1,a_2)=(1,3)을 얻는다. 이 때 m의 한 분합 (a_1,\cdots,a_n)에 대해 이것으로 대응되는 분할의 개수를 생각한다. 이는 다음과 같이 생각하자. 먼저 n부터 차례대로 써 넣는다. n을 쓰고 나서 n-1부터는 어느 부분집합으로 갈지 결정해야 한다. 이 때 n-a에서 n-a_1+1까지는 한 부분집합만을 쓰므로 그 가지수는 1^{a_1-1}이다. 한 편 n-a_1은 반드시 새로운 부분집합을 만들어야 한다. 그리고 n-a_1-1부터 n-a_1-a_2+1까지는 두 부분집합에서 결정해야 하므로 가지수는 2^{a_2-1}이다. 마찬가지로 계속 하다보면 한 분합 (a_1,\cdots,a_n)으로 대응되는 분할의 개수가 1^{a_1-1}\cdots n^{a_n-1}이 된다. 즉 전사함수의 개수는 \displaystyle n! \sum_{a_1+\cdots+a_n=m} a^{a_1-1}\cdots n^{a_n-1}=\sum_{a_1+\cdots+a_n=m} a^{a_1}\cdots n^{a_n}, 즉 좌변이 되어 증명이 끝난다.

약간 우회한 감이 없지 않다. 밑의 풀이는 오피셜 솔루션이라 하는데, 본질은 결국 위의 세 번째 풀이랑 똑같지만 서술하는 과정이 훨씬 깔끔하다.

Fourth Solution. 역시 우변은 전사함수의 개수이다. 이는 곧 1,2,\cdots,n을 이용하여 길이가 m인 수열을 만들되 1,2,\cdots,n이 한 번 이상 들어가도록 하는 개수와 같다. 이제 맨 처음부터 봤을 때 새로운 숫자가 나올 때마다 표시를 해준다. 예컨대, m=10,n=5일 때에 2,2,3,2,3,1,4,3,4,4란 수열이 있으면 (2),2,(3),2,3,(1),(4),3,4,4와 같이 표시를 한다. 이 때 i번째 새로운 수가 나오는 위치를 a_1+a_2+\cdots+a_{i-1}+1이라 한다. 그리고 a_n=m-(a_1+\cdots+a_{n-1})로 정의한다. (이 예의 경우 a_1=2,a_2=3,a_3=1,a_4=4이다.) 그러면 표시한 곳들에는 1,2,\cdots,n이 들어가야 하므로 그 순서를 택하는 가지수가 n!이다. 그리고 첫 번째 표시에서 두 번째 표시 사이에는 한 가지 숫자만 들어가므로 가지수는 1^{a_1-1}가지이고, 두 번째 표시에서 세 번째 표시 사이에는 두 가지 숫자만 들어가므로 가지수는 2^{a_2-1}가지이고, …, 이런 식으로 계속 하면 결국 우변의 값은 \displaystyle n! \sum_{a_1+\cdots+a_n=m} a^{a_1-1}\cdots n^{a_n-1}=\sum_{a_1+\cdots+a_n=m} a^{a_1}\cdots n^{a_n}, 즉 좌변이 되어 증명이 끝난다.

Any other solutions?