Posts Tagged ‘ 생성함수 ’

2009 KMO 겨울학교 모의고사 2차 조합부등식

다음은 2009년 1월에 있었던 KMO 겨울학교의 모의고사 2차에 나온 문제이다.

n>=0인 정수에 대해, \sum_{i+j+k=n} \frac{(3i)!}{i!^3}\frac{(3j)!}{j!^3}\frac{(3k)!}{k!^3} \leq 27^n임을 보여라.

생긴게 참 조합적으로 의미도 있어 보이고, 실제로 작은 n 몇 개 대입하면 갭이 크기 때문에 조합적으로 쉽게 증명이 되리라 생각되어도 잘 안 된다.

풀이는 생성함수를 이용한다. \frac{1}{(1-27x)^{1/3}}\sum_{n \geq 0} \frac{(3n)!}{(n!)^3}x^n을 비교하자. 좌변은 Newton 이항 정리를 이용한다. 그 식은 (1-27x)^{-1/3}이므로
\displaystyle \sum_{n \geq 0} \binom{-1/3}{n}(-27x)^n=\sum_{n \geq 0}\frac{(-\frac{1}{3})(-\frac{4}{3})\cdots(-\frac{3n-2}{3})}{n!}(-27)^nx^n
\displaystyle = \sum_{n\geq 0} \frac{1 \cdot 4 \cdot \cdots \cdot (3n-2)}{n!}9^n x^n
\displaystyle \geq \sum_{n\geq 0} \frac{(3n)!}{n!(3 \cdot 6 \cdot \cdots \cdot 3n)^2}9^nx^n
\displaystyle =\sum_{n\geq 0} \frac{(3n)!}{(n!)^3}x^n이 된다. 즉 \frac{1}{(1-27x)^{1/3}}x^n의 계수를 a_n, \sum_{n \geq 0} \frac{(3n)!}{(n!)^3}x^nx^n의 계수를 b^n이라 하면 a_n \geq b_n이 성립한다.

따라서 \displaystyle \left( \sum_{n \geq 0} \frac{(3n)!}{(n!)^3}x^n \right)^3의 계수는 \displaystyle \sum_{i+j+k=n}a_ia_ja_k이고 \displaystyle \left( \sum_{n \geq 0} \frac{(3n)!}{(n!)^3}x^n \right)^3의 계수는 \displaystyle \sum_{i+j+k=n}b_ib_jb_k이므로 \displaystyle \left( \sum_{n \geq 0} \frac{(3n)!}{(n!)^3}x^n \right)^3의 계수, 즉 주어진 식의 우변이 \displaystyle \sum_{i+j+k=n}a_ia_ja_k의 계수, 즉 주어진 식의 좌변보다 크거나 같다. 이로써 증명이 끝난다.

아직 조합적 풀이는 찾지 못했다.

이 부등식의 갭은 상당히 커서, 사실 \displaystyle \lim_{n \rightarrow \infty}\frac{(LHS)}{(RHS)}=0인 것도 증명이 가능하다. 이는 위의 풀이에서 조금만 더 연구하면 나오는 결과로, 원래 내가 이 문제를 모의고사에 낼 때엔 위의 문제만 냈는데 후배가 이를 개조해서 얻은 결과인 위의 리미트 문제를 part b로 추가해서 냈다. (중등부 모의고사엔 part a만이 나왔다.)

이 문제는 이미 알려진 다음 문제의 analogue이다.

n \geq 0인 정수에 대해, \displaystyle \sum_{i+j=n} \frac{(2i)!}{(i!)^2}\frac{(2j)!}{(j!)^2} = 4^n임을 보여라.

이 문제 역시 위에서 보인 방법과 똑같이 풀린다. 이 때엔 \frac{1}{\sqrt{1-4x}}의 계수를 구하면 그것이 \binom{2n}{n}이 됨을 보이면 된다.

이 등식의 경우 조합적인 풀이가 있다. (찾아내는 것은 다소 힘들긴 하지만, 풀이 자체는 간단하다.) 그 풀이는 다음과 같다. 먼저 (0,0)에서 북동쪽↗과 남동쪽↘으로 2n번 이동하는 경로들을 생각하자. 자유롭게 움직여도 된다. 그러면 매번마다 두 번의 선택이 있으므로 경우의 수는 총 2^{2n}=4^n이다. 한 편, 이 경로가 x축과 마지막으로 만나는 곳을 (2(n-k),0)이라 하자. (x좌표가 짝수임은, 움직일 때마다 y좌표의 기우성이 달라지는데 처음과 마지막이 둘 다 0이면 움직인 횟수가 짝수번이어야하기 때문이다.) 그러면 시작부터 (2(n-k),0)까지 움직이는 횟수는 45도 돌려서 생각하면 (0,0)에서 (n-k,n-k)까지 오른쪽과 위쪽으로 움직이는 경우의 수가 되어 \binom{2(n-k)}{n-k}이다. 그럼 이제 보여야할 사실은 하나다. (2(n-k),0)에서 (혹은 그냥 (0,0)에서) 2k번 움직이되 x축에 닿지 않는 경우의 수가 \binom{2k}{k}임을 보이면 된다.

이를 45도 돌려서 생각하면, (0,0)에서 2k번 움직이되 y=x와 닿지 않게 움직이는 경우의 수가 \binom{2k}{k}임을 보이는 것이 된다. 맨처음에 위로 올라갈 수도 있고 오른쪽으로 갈 수도 있으니 한 경우를 보아 2를 곱한다. 일반성을 잃지 않고 y=x 밑으로 움직이는 경우의 수를 생각하자. 그러면 이 상황을 x축 방향으로 -1만큼 움직이면 y=x 이하로 (이번엔 닿아도 된다) 2k-1번 움직이는 경우의 수가 된다. 그 마지막 점은 (k,k-1),(k+1,k-2),\cdots,(2k-1,0)이 되는데 그 중 하나 잡아 (k-1+i,k-i)로 가는 경우의 수를 세자.

방법은 카탈란 수열을 계산하는 조합적 방법와 동일하다. y=x를 넘는 경우 최초로 넘게 되는 곳을 (a,a+1)라 할 때 그 이후의 결과는 y=x+1에 대해 대칭해버리면 그 결과는 (0,0)에서 (k-i-1,k+i)로 가는 경로가 되며, 임의의 이런 경로는 반드시 y=x를 넘어야 하므로 또 최초로 넘는 순간에 대해 그 이후를 y=x+1에 대해 대칭시키면 원래 조건을 만족시키는 경로가 된다. 따라서 그 경우의 수는 \binom{2k-1}{k+i}가 된다. 곧 원래 조건을 만족시키는 경우의 수는 \binom{2k-1}{k-1+i} -\binom{2k-1}{k+i}이 된다.

따라서 y=x 밑으로 2k-1번 움직이는 총 경우의 수는 \displaystyle \sum_{i=1}^k \left( \binom{2k-1}{k-1+i} -\binom{2k-1}{k+i} \right) = \binom{2k-1}{k}가 된다. (마지막 항의 \binom{2k-1}{2k}는 0으로 친다. 실제로 위의 과정에서 생각해도 0이어야 하고.) 따라서 총 경우의 수는 2\binom{2k-1}{k}=2\binom{2k-1}{k-1}=\binom{2k}{k}이다. 이로써 이 조합등식이 증명된다!

물론 맨 처음의 문제를 만들게 된 계기는 이 문제였다. 매우 단순한 일반화.

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

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?

2010 JMO 예선 #9

2010년에 있었던 일본 수학 올림피아드의 예선 9번 문제. 일본에서는 예선으로 12문제가 나오는데 예전에 일본 학생에게서 들은 기억에는 이 문제를 다 풀어야 하는 것이 아니라 몇 문제를 골라서 푸는 것으로 기억한다. (그런데 그게 몇 문제인지는 또 기억이 안 난다..) 아무튼 문제는 다음과 같다.

흰 돌 2010개와 검은 돌 2010개를 가로 일렬로 늘어놓을 때, 다음 조건을 만족하는 가지수는 몇 가지인가?
– 흰 돌 하나와 검은 돌 하나를 택했을 때 흰 돌이 검은 돌보다 오른쪽에 오는 경우가 홀수 개다.

즉 흰 돌을 X, 검은 돌을 O이라 하면 O하나를 택하고 그 오른쪽에 있는 X를 또 택하는 경우의 수가 총 홀수 개가 되는 나열법이 몇 가지인가를 묻는 것이다. 예컨대 XOOXOX라면 첫 O는 오른쪽의 X가 2개, 두 번째 O는 오른쪽의 X가 2개, 세 번째 O는 오른쪽의 X가 1개므로 총 5개로 홀수 개이다. 이런 것이 몇 개 있는지를 묻는 문제이다.

이 문제를 조금 더 일반화하여, 다음과 같이 다시 쓰자.

흰 돌 n개와 검은 돌 n개를 가로 일렬로 늘어놓되, 흰 돌 하나와 검은 돌 하나를 택했을 때 흰 돌이 검은 돌보다 오른쪽에 오는 경우가 홀수 개가 되도록 하고 싶다.
(1) n이 홀수일 때 그 경우의 수를 구하여라.
(2) n이 짝수일 때 그 경우의 수를 구하여라.

n이 작은 경우 몇 가지를 보다 보면, (1)의 답은 쉽게 추측이 가능하다. (1)의 답은 \frac{1}{2}\binom{2n}{n}이다. 한 편 (2)의 답은 바로 추측이 되지 않는데, 그 답은 \frac{1}{2}(\binom{2n}{n}-\binom{n}{n/2})이다. 이를 몇 가지 방법으로 증명하자.

First Solution 먼저 (1)의 간단한 풀이를 보자. 앞에서처럼 O이 X의 왼쪽에 있는 것이 홀수 개인 경우를 세자. O n개와 X n개를 나열한 것 중 하나를 a라 하고, 그를 거꾸로 나열한 것을 b라 하자. 그러면 a에서 (O,X)의 개수는 b에서 (X,O)의 개수와 같고, 즉 a,b에서의 (O,X)의 개수의 합은 a에서의 (O,X)와 (X,O)의 개수를 세는 것이 된다. 이는 O 중 하나, X 중 하나를 택하기만 하면 되므로 총 n^2개로 홀수이다. 따라서 a에서 (O,X)의 개수가 홀수였다면 b는 짝수이고, a가 짝수였다면 b는 홀수이다. 따라서 이것은 짝수인 것과 홀수인 것의 일대일 대응이 되고 그 개수는 정확히 같아야 한다. (뒤집어서 같게 나오는 것은 없음을 유의하자.) 따라서 그 개수는 전체 \binom{2n}{n}개의 절반인 \frac{1}{2}\binom{2n}{n}이다.

이 풀이는 (2)에선 적용되지 않는다. 왜냐하면 n^2가 짝수이기 때문에, 짝수인 것과 홀수인 것의 일대일 대응인 것을 보일 수가 없기 때문이다.

Second Solution 이제 보일 풀이는 (1)도 (2)도 적용되는 풀이이다. 먼저 (2)의 경우를 본다. (O,X)의 개수가 홀수인 것의 집합을 A라 하고, 짝수인 것의 집합을 B라 하자. 이 때 다음과 같은 대응 f:A \cup B \rightarrow A \cup B을 생각하자. 먼저, A의 임의의 원소 a를 두 자리씩 나눈다. 예를 들어 OO|XX|XX|OX|OO|XO 이런 식으로 두 자리씩 나눈다. 그러면 만약 OX나 XO가 나오지 않으면 f(a)=a로 정의하고, OX나 XO가 하나 이상 나오면 최초로 나오는 OX나 XO를 각각 XO와 OX로 바꾼 것을 f(a)로 정의한다. 그러면 이 경우는 (O,X)의 쌍의 개수가 정확히 하나 바뀌기 때문에 f(a)B에 속한다. 마찬가지로 B의 원소에 대해서도 똑같이 정의한다. 그러면 AB의 원소들 중에서 OX나 XO가 나오지 않는 것들을 제외하곤 AB가 일대일 대응이 된다.
그런데 OX와 XO가 없다는 것은 곧 두 자리로 나눈 결과가 OO과 XX만 나오는 것인데, 이 때 (O,X)의 개수는 반드시 짝수개다. 곧 그런 것들은 전부 B의 원소이다. 이런 것들의 개수는 OO \frac{n}{2}개와 XX \frac{n}{2}개를 배열하는 가지수이므로 \binom{n}{n/2}이다. 즉, A의 원소와 B의 원소 중 \binom{n}{n/2}개를 제외한 것들이 일대일 대응이 되므로 A의 원소의 개수(우리가 구하고자 하는 값)를 x라 하면 |A|=x, |B|=x+\binom{n}{n/2}이다. \binom{2n}{n}=|A|+|B|=2x+\binom{n}{n/2}이므로, 답은 \frac{1}{2}(\binom{2n}{n}-\binom{n}{n/2})이다.

마찬가지 풀이를 n이 홀수일 때에도 적용할 수 있다. 이 경우 OX와 XO가 없는 경우가 없다. 즉 O가 홀수 개, X가 짝수 개 있으므로 반드시 두 개씩 나눌 때 OX나 XO가 등장한다. 따라서 완벽히 AB가 일대일 대응이 되고 그 개수는 전체의 절반이 되어 같은 답이 나온다.

Third Solution 이번엔 생성함수를 이용한 풀이를 보자. 먼저 O m개, X n개인 경우 O이 X의 왼쪽에 있는 것이 홀수 개인 경우의 수를 f(m,n)이라 하자. 이제 f(2n,2n)=\frac{1}{2}(\binom{4n}{2n}-\binom{2n}{n})임을 보이자.

먼저 f(m,n)의 점화식을 찾아내자. 맨 앞의 것이 O인지 X인지를 따짐으로써, n이 짝수이면 f(m,n)=f(m-1,n)+f(m,n-1)이고 n이 홀수이면 f(m,n)=\binom{m+n-1}{m-1}-f(m-1,n)+f(m,n-1)가 됨을 확인할 수 있다. 이를 이용해 생성함수를 만들어낸다. f(0,n)=f(m,0)=0임을 주의하자.

이 점화식을 이용하여 f(2a,2b)=\binom{2a+2b-2}{2a-1}+f(2a-2,2b)+f(2a,2b-2)임을 얻을 수 있다. 따라서 \displaystyle F(x,y)=\sum_{a,b\geq 0}f(2a,2b)x^ay^b라고 두면 이 점화식으로부터 \displaystyle F(x,y)=\sum \binom{2a+2b-2}{2a-1}x^ay^b + (x+y)F(x,y), 즉 \displaystyle F(x,y)=\frac{1}{1-x-y}\sum \binom{2a+2b-2}{2a-1}x^ay^b가 된다.

이제 \sum \binom{2a+2b-2}{2a-1}x^ay^b를 구하자. 이는 \displaystyle \sum_{a \geq 1}x^a\sum_{b \geq 1}\binom{2a+2b-2}{2a-1}y^b이 되는데 \displaystyle \sum_{b \geq 1}\binom{2a+2b-2}{2a-1}y^b = \binom{2a}{2a-1}y+\binom{2a+2}{2a-1}y^2+\cdots의 값은 \displaystyle \frac{1}{2} \left( \frac{1}{(1-y)^{2a}}-\frac{1}{(1+y)^{2a}} \right)=\binom{2a}{2a-1}y+\binom{2a+2}{2a-1}y^3+\cdots에서 양변에 y를 곱하고 y\sqrt{y}를 대입하여 얻을 수 있다. 그 결과 \displaystyle \sum \binom{2a+2b-2}{2a-1}x^ay^b = \sum_{a \geq 1} x^a \frac{\sqrt{y}}{2} \left( \frac{1}{(1-\sqrt{y})^{2a}}-\frac{1}{(1+\sqrt{y})^{2a}} \right)이므로 \displaystyle \sum \binom{2a+2b-2}{2a-1}x^ay^b = \frac{\sqrt{y}}{2} \left( \frac{x}{(1-\sqrt{y})^2}\frac{1}{1-\frac{x}{(1-\sqrt{y})^2}} \right) - \frac{\sqrt{y}}{2} \left( \frac{x}{(1+\sqrt{y})^2}\frac{1}{1-\frac{x}{(1+\sqrt{y})^2}} \right)이다. 이를 정리하면 \displaystyle \frac{2xy}{1+x^2+y^2-2x-2y-2xy}가 된다. 따라서 \displaystyle F(x,y)=\frac{2xy}{(1-x-y)(1+x^2+y^2-2x-2y-2xy)}을 얻는다.

이제 여기서부터 G(t)=f(0,0)+f(2,2)t+f(4,4)t^2+\cdots를 얻고자 한다. 이를 위해 (x,y)(xy,\frac{x}{y})를 대입한 후에 y^0의 계수를 보면 그 결과가 G(x^2)가 되므로 x=\sqrt{t}를 대입하면 된다.

(xy,\frac{x}{y})를 대입하면 그 결과 \displaystyle F(xy,\frac{x}{y})=\frac{2x^2}{(1-x(y+\frac{1}{y}))(1+x^2(y^2+\frac{1}{y^2})-2x(y+\frac{1}{y})-2x^2)}인데 여기서 z=y+\frac{1}{y}를 대입하면 이는 \displaystyle \frac{2x^2}{(1-xz)(1-4x^2-2xz+x^2z^2)}=\frac{2x^2}{(1-xz)(1+2x-xz)(1-2x-xz)}이고, 이를 부분분수로 나누면 그 결과는 \displaystyle -\frac{1}{2}\frac{1}{1-xz}+\frac{1}{4}\frac{1}{1+2x}\frac{1}{1-\frac{x}{1+2x}z}+\frac{1}{4}\frac{1}{1-2x}\frac{1}{1-\frac{x}{1-2x}z}, 즉 \displaystyle -\frac{1}{2}(1+x(y+\frac{1}{y}+\cdots)+\frac{1}{4}\frac{1}{1+2x}(1+\frac{x}{1+2x}(y+\frac{1}{y})+\cdots)+\frac{1}{4}\frac{1}{1-2x}(1+\frac{x}{1-2x}(y+\frac{1}{y})+\cdots)이다. 여기서 y^0의 계수는 \displaystyle -\frac{1}{2}(1+\binom{2}{1}x^2+\binom{4}{2}x^4+\cdots)+\frac{1}{4}\frac{1}{1+2x}(1+\binom{2}{1}(\frac{x}{1+2x})^2+\cdots)+\frac{1}{4}\frac{1}{1-2x}(1+\binom{2}{1}(\frac{x}{1-2x})^2+\cdots)이 된다. 맨 앞 항을 제외한 나머지 두 항은 \displaystyle 1+\binom{2}{1}x+\binom{4}{2}x^2+\cdots=\frac{1}{\sqrt{1-4x}}임을 이용하면 \displaystyle \frac{1}{4}\frac{1}{1+2x}\frac{1}{\sqrt{1-\frac{4x^2}{(1+2x)^2}}}+\frac{1}{4}\frac{1}{1-2x}\frac{1}{\sqrt{1-\frac{4x^2}{(1-2x)^2}}}이 되고 정리하면 \displaystyle \frac{1}{4}\frac{1}{\sqrt{1+4x}}+\frac{1}{4}\frac{1}{\sqrt{1-4x}}=\frac{1}{2}(1+\binom{4}{2}x^2+\binom{8}{4}x^4+\cdots)가 된다. 따라서 G(x^2)x^{2n}의 계수는 \displaystyle \frac{1}{2}\binom{4n}{2n}-\frac{1}{2}\binom{2n}{n}이 되고 이것이 곧 f(2n,2n)이므로 증명이 끝난다.

(1) 역시 마찬가지 방법으로 증명이 되지만, 풀이가 비슷하게 길어서 생략.

내가 이 문제를 풀면서 시도한 방법은.. 먼저 답을 추측하는 것. 그리고 그것을 증명할 때 먼저 일대일 대응을 찾는 것이다. 그를 찾는 과정에서 먼저 First Solution의 방법을 찾아냈으나 그것은 짝수인 경우를 증명할 수 없었다. 그래서 조금 더 시도한 결과 Second Solution을 찾아냈다. 여기서 멈추지 않고 점화식을 찾아내어 생성함수 풀이를 찾아냈다.

다른 풀이는 무엇이 있을까?

조합 삼각 함수

이 글은 서울과학고 수학연구반 MO의 연회지인 ‘셈사랑’ 19호에 졸업생투고로 낸 원고로, 학부 시절에 Richard Stanley 교수님의 수업을 들으며 알게 된 사실을 조금 정리한 글이다. 앞의 서문은 불필요하다고 생각하여 생략하고 나머지 부분을 조금 다듬었다. 이 글의 본문에는 미분 방정식과 관련된 내용이 조금 언급되는데, 관련 배경 지식이 있으면 좋고 없어도 그 부분만 스킵하고 넘어가도 좋을 것 같다.

일단 한 종류의 수열에 대해서 생각하는 것으로 시작하기로 한다.

정의 1. [n]= \{ 1,2,\cdots,n \}이라 한다. 이 때 이 집합에서 자기 자신으로 대응하는 함수 \sigma:[n] \rightarrow [n] 중에 일대일대응인 것을 순열이라고 부른다.

순열을 표현하는 법에는 두 가지 방법이 있다. 하나는 \sigma(1),\sigma(2),\cdots,\sigma(n)을 나열하는 법으로 순열을 w=w_1w_2\cdots w_n으로 표현하는 것이고, 다른 하나는 싸이클을 이용한 것으로, \sigma^k(a)=a인 최소의 자연수 k에 대해, (a,\sigma(a),\cdots,\sigma^{k-1}(a))을 하나의 싸이클이라 하며 이것들을 합성하여 표현하는 것이다. 이 글에서는 첫 번째 방법인 나열식을 쓰기로 한다. [n]에서 정의되는 순열의 집합은 보통 S_n으로 표시하며, symmetric group이라는 이름을 갖는다.

정의 2. S_n의 원소 중에서, w_1>w_2<w_3>\cdots, 즉 모든 자연수 k에 대해 w_{2k-1}>w_{2k},w_{2k}<w_{2k+1}이 성립하는 순열을 교대순열이라고 한다. 반대로, w_1<w_2>w_3<\cdots, 즉 w_{2k-1}<w_{2k},w_{2k}>w_{2k+1}이 성립하는 순열을 역교대순열이라고 한다.

정의 3. S_n의 교대순열의 개수를 오일러 수라고 하며, E_n으로 표기한다.

그러면 여기서 간단한 정리를 하나 얻을 수 있다.

정리 1. S_n의 역교대순열의 개수 역시 E_n이다.
증명) 일대일대응 f:S_n \rightarrow S_n을 생각하여 f(\sigma)(i)=n+1-\sigma(i)로 정의한다. 그러면 f(\sigma)는 한 순열로, n+1에서 각 \sigma(i)를 뺀 것을 나열한 것이 된다. 곧 f는 교대순열을 역교대순열로 대응시키며, 역대응은 바로 자기 자신으로, 역교대순열을 교대순열로 대응시킨다. 따라서 f는 교대순열과 역교대순열 사이의 일대일대응이 되어 둘의 개수는 같다. -증명끝

수열에 대한 더 자세한 것을 알기 위해서 일반적으로 수학자들은 그에 대한 특성을 찾는데, 그 중의 하나가 생성함수이다. 생성함수를 얻기 위해 점화식을 먼저 얻는 경우도 비일비재한데, 여기에서도 오일러 수 E_n의 점화식을 먼저 살펴보기로 한다.

정리 2. \displaystyle 2E_{n+1}=\sum_{k=0}^n \binom{n}{k}E_kE_{n-k}가 성립한다.
증명) [n]의 부분집합 중에서 원소가 k개인 부분집합 S를 택한다. 그 경우의 수는 \binom{n}{k}이다. 이 때, S 내부에서 역교대순열 u를 잡는 방법의 수는 정의에 의해 E_k이고, S^c에서 역교대순열 v를 잡는 방법의 수는 E_{n-k}이다. 이제 u=u_1u_2 \cdots u_k이라 할 때 u^r=u_ku_{k-1}\cdots u_1이라 하자. 그러면 (u^r)(n+1)(v), 즉 u^rn+1의 왼쪽에 쓰고 vn+1의 오른쪽에 써서 얻어지는 길이 n+1인 순열은 [n+1]의 교대순열이거나 역교대순열이다. (k의 기우성에 따라 그 결과가 다르다.) 또한 임의의 교대순열이나 역교대순열의 경우, n+1을 기준으로 양 옆으로 나눈 후 왼쪽에 있는 것을 거꾸로 한 것과 오른쪽에 있는 것은 모두 역교대순열이다. 왜냐하면 n+1 다음에 나오는 것은 반드시 n+1보다 작으므로, 그 다음은 증가부터 시작하기 때문이다.
따라서 \binom{n}{k}E_kE_{n-k}를 전부 합한 우변의 식은 [n+1]의 모든 교대순열과 역교대순열을 세는 식이 된다. 정리 1에 의해 둘 다 그 개수가 E_{n+1}이므로, 이 식은 좌변인 2E_{n+1}와 같게 되어 증명이 끝난다. -증명끝

이제 E_n과 관련된 생성함수를 찾는다. 이 때, 생성함수보다 지수생성함수를 쓰는 것이 더 적합하다는 것을 깨달아야 한다. 왜냐하면 정리 2에서 얻은 식에는 \binom{n}{k}와 같이 계승을 이용한 것이 나오는데, 지수생성함수가 보다 이것을 원활히 처리해줄 수 있기 때문이다. \displaystyle F(x)=\sum_{n\geq 0} E_n \frac{x^n}{n!}이라 하자. 또한 앞으로의 편의를 위해 E_0=E_1=1으로 정의한다. 그러면 이를 미분한 식은
\displaystyle F'(x)=\sum_{n\geq 0}E_{n+1}\frac{x^n}{n!}=\frac{1}{2}\sum_{n\geq 0}\sum_{k=0}^n \binom{n}{k}E_kE_{n-k}\frac{1}{n!}x^n
이 되어 \displaystyle 2F'(x)=\sum_{n\geq 0}\sum_{k=0}^n \frac{E_k}{k!} \frac{E_{n-k}}{(n-k)!}x^n을 얻는다. 이는 곧 F를 제곱한 것에서 얻는 식이므로, 초기조건과 맞물려 이 관계식을 정리하면 2F'=F^2+1F(0)=1이라는 결과를 얻는다.

한 편, 주어진 구간 내에서 연속 함수에 대한 일차미분방정식은 초기조건이 하나 주어지면 그 해는 유일함이 잘 알려져 있다. 이 미분방정식은 F'만이 연루되어 있으므로 일차이며, 초기조건이 하나 주어져 있으므로 그 해는 유일해야 한다. 여기에서 F(x)=\sec{x}+\tan{x}를 대입하면 등식이 성립하므로, 이것이 그 해가 됨을 알 수 있다. 이를 짧게 정리하면 다음과 같다.

정리 3. \displaystyle \sum_{n\geq 0}E_n\frac{x^n}{n!}=\sec{x}+\tan{x}이 성립한다.

\sec 함수는 우함수, \tan 함수는 기함수라는 데에서, 이 함수의 우함수와 기함수를 분리할 수 있다. 그 결과로, \displaystyle \sum_{n\geq 0}E_{2n}\frac{x^{2n}}{(2n)!}=\sec{x}\displaystyle \sum_{n \geq 0}E_{2n+1}\frac{x^{2n+1}}{(2n+1)!}=\tan{x}를 얻을 수 있다. 곧, 삼각함수를 두 가지 조합등식을 이용해서 역으로 얻어낼 수 있다. 이를 이용하면 \cos\sin을 쉽게 얻을 수 있고, 이는 곧 조합적인 언어만을 이용하여 삼각함수를 재구축할 수 있다는 것이다. 그 결과는 삼각함수가 원래 지니고 있어야 할 기하적인 면이나 해석적인 면이 일체 들어있지 않은 순수 조합적인 그것이 된다.

한 예로 다음 문제를 보자.

정리 4. 1+\sec^2{x}=\tan^2{x}가 성립한다.
증명) 상수항은 쉽게 알 수 있다. x^{2n}의 계수를 계산하기로 하자. 좌변의 계수는 \displaystyle \binom{2n}{0}E_{2n}E_0+\cdots+\binom{2n}{2n}E_0E_{2n}이며, 우변의 계수는 \displaystyle \binom{2n}{1}E_{2n-1}E_1+\cdots+\binom{2n}{2n-1}E_1E_{2n-1}이다. 이 둘이 같음을 증명하기 위해, 길이가 2n+1인 교대순열과 역교대순열을 생각하낟. 앞에서 2n+1을 기준으로 생각할 때에 왼쪽과 오른쪽의 개수를 쉽게 셀 수 있었다. 만약 2n+1 양 옆에 각각 짝수 개의 수들이 있다면, 그 결과는 교대순열이 되고, 따라서 좌변의 계수의 값이 바로 그 개수가 되어 E_{2n+1}이다. 한 편, 2n+1 양 옆에 각각 홀수 개의 수들이 있다면, 그 결과는 역교대순열이 되므로 우변의 계수의 값이 바로 그 개수가 되어 역시 E_{2n+1}이 된다. 따라서 두 계수의 값이 같고, 증명은 끝난다. -증명끝

다음 예제들을 통해, 기존의 정리들을 다른 눈으로 바라보면 다른 방법이 생김을 느껴보고, 한 수학적인 결론은 오직 한 맥락에서만 도출되지 않을 수도 있다는 것을 깨달아보자.

예제 1. \tan{x}+\tan{y}=(\tan(x+y))(1-\tan{x}\tan{y})를 조합적으로 증명하여라.
예제 2. \displaystyle \sec{x}(\sum_{n\geq 0} \frac{(-1)^nx^{2n}}{(2n)!})=1를 조합적으로 증명하여라.
예제 3. \displaystyle \tan{x}=(\sum_{n\geq 0} \frac{(-1)^nx^{2n+1}}{(2n+1)!})(\sec{x})를 조합적으로 증명하여라.