Posts Tagged ‘ 조합적해석 ’

한 조합등식과 그 별해들

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?

Advertisements

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을 찾아냈다. 여기서 멈추지 않고 점화식을 찾아내어 생성함수 풀이를 찾아냈다.

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