Archive for the ‘ 조합 ’ Category

2010 JMO #3

3. 2010개의 섬이 있고, 그 섬들을 연결하는 2009개의 다리가 있다. 어떤 두 개의 섬에 대해서도 1개의 다리가 둘을 연결하거나 다리가 없거나 둘 중의 하나라 하고, 다리의 양 끝은 서로 다른 두 개의 섬이라 하자. 또한, 임의의 두 섬을 골라도 한 섬에서 다른 섬으로 다리를 몇 번 건넘으로써 갈 수 있다고 한다.
이제, 모든 섬이 한 통의 편지를 임의의 섬에 보낸다고 한다. (단, 자기 자신에게 편지를 보내는 것도 가능하다.) 이 때, 다음 사실이 판명되었다.
“섬 A와 섬 B가 다리로 연결되어 있으면, 섬 A의 편지의 목적지와 섬 B의 편지의 목적지는 서로 다리로 연결된 두 섬이거나, 같은 섬이다.
이 때, 다음 (1)과 (2) 중 적어도 하나가 성립함을 보여라.
(1) 자기 자신에게 편지를 보낸 섬이 존재한다.
(2) 서로 편지를 교환하고, 다리로 연결되어 있는 두 섬이 존재한다.

그래프로 바꾸면 단순그래프인데 2010개의 점, 2009개의 변을 갖고 있고 연결그래프가 되어야 한다. 곧 이 그래프는 수형도로 회로가 없다. 편의상 도시 X가 편지를 보낸 도시를 f(X)라 하자. 그러면 보여야할 것은 f(X)=XX가 존재함을 보이거나 f(X)=Y,f(Y)=XX,Y가 존재함을 보이면 된다. 귀류법으로 그런 경우가 없음을 가정하자. 그리고 수형도이기 때문에 X에서 f(X)로 가는 경로는 유일하게 존재하는데 그 길이를 d(X)라고 하자.

먼저 임의의 도시 X_0을 택한다. 그리고 d(X_0) \geq 2임을 가정하자. 그러면 X_0에서 f(X_0)으로 가는 경로가 있는데 그 경로에서 X_0 바로 다음 점을 X_1이라 한다. 마찬가지로 X_1에서 f(X_1)으로 가는 경로에서 X_1의 다음 점을 X_2라 하고, 계속 정의한다. 그러면 0 \leq d(X_{i+1})-d(X_i) \leq 2임을 보일 수 있다. 그런데 d(X_{i+1})=d(X_i)인 경우는 X_i에서 f(X_i)까지 이어진 경로 위에 f(X_{i+1})이 없음을 의미한다. 즉 새로운 점이 하나 필요하게 된다. 따라서 d(X_{i+1})=d(X_i)인 경우는 무수히 많이 나올 수 없어서 d(X_i)는 계속 감소해야만 한다. 그러면서도 0이 되어선 안 된다. (d(X_i)=0이면 X_i=f(X_i), 모순) 그러면 언젠가 d(X_n)=1n이 존재하게 된다. (만약 d(X_0)=1이었다면 바로 n=0인 경우로 보면 된다.)

이제 m \geq n인 경우 X_{m+1}=f(X_m)이 되어야 한다. 이 때 앞에서와 비슷한 논의로 계속 새로운 점이 나올 수 없어서 언젠가 f(X_m)=X_m이거나 f(X_m)=X_{m-1}이 되어야 한다. 이는 모순. 끝

풀기 전에 좀 브레인스토밍하다보면 문제가 어떤 의미인지 또 어떤 풀이인지 감은 잡히는데 그걸 표현하는게 다소 짜증나는 문제

2010 KMO #7

7. 정보기관에서 테러리스트 용의자 2000명 사이에 휴대전화 통화가 있었는지 여부를 조사하였다. 그런데 서로 겹치지 않는 3명씩의 두 모임 A,B를 뽑아보면 AB 사이에는 반드시 통화하지 않았던 쌍이 있었다. 이 때, 통화한 적이 있는 쌍의 개수는 201000보다 작음을 보여라.

더블 카운팅!

그래프로 바꾼 후 각각의 차수를 d_i라 하고 전체 변의 개수 (=통화한 적이 있는 쌍의 개수)를 e=\frac{1}{2} \sum d_i라 한다. 집합 {(A,(B_1,B_2,B_3)): i=1,2,3에 대해 AB_i는 아는 사이}을 생각한다.
(1) 임의의 A에 대해 그가 아는 세 사람을 택하면 되므로 전부 \sum \binom{d_i}{3}가지.
(2) 그런데 B_1,B_2,B_3을 미리 택하고 나면 그들과 전부 통화한 사람은 최대 두 명이다. 세 명이면 조건에 모순. 따라서 저 집합의 원소의 개수는 최대 2 \binom{2000}{3}.
따라서 \displaystyle 2 \binom{2000}{3} \geq \sum \binom{d_i}{3} \geq 2000 \binom{\frac{2e}{2000}}{3}가 젠센 부등식으로 성립. 이를 정리하면 2 \cdot 1999 \cdot 1998 \geq x(x-1)(x-2)가 성립한다. (x=\frac{1000}{e}) 우변을 f(x)라 하면 f는 증가함수이고 f(201)=200^3-200 > (LHS)이므로 f(x) \leq 2 \cdot 1999 \cdot 1998 < f(201), 즉 e < 201000를 의미한다.

더블 카운팅 중에서도 Iran NMO #2와 비슷하다. 통강은 KMO의 예고? ㅋㅋ

2010 KMO #4

4. 총 n명(n \geq 4)의 외교관들이 모여 있다. 임의의 네 외교관 A,B,C,D에 대하여, AB가 악수를 했고 BC가 악수를 했으며 CD가 악수를 했다면, 세 쌍 AC, AD, BD 중 악수를 했던 쌍이 반드시 존재한다. 이 때 다음을 증명하여라.
(a) 전체 외교관을 다음 성질이 만족하도록 공집합이 아닌 두 집합 X,Y로 나눌 수 있다. X에 속한 모든 외교관이 Y에 속한 어떤 외교관과도 악수를 하지 않았거나, X에 속한 모든 외교관이 Y에 속한 모든 외교관과 악수를 하였다.
(b) 어떤 두 외교관 A,B가 있어서 A,B 이외의 외교관 중에 A와 악수한 사람들의 모임과 B와 악수한 사람들의 모임이 같다.

약간 까다롭지만 어떻게 되긴 되네..

먼저 편의상 두 무리가 서로 악수를 안 했으면 적대관계, 전부 악수를 했으면 우호관계라 하자.

(a) 수학적 귀납법으로 보인다. 먼저 사람이 세 명 이하면 거의 트리비알.. 케바케. 네 명인 경우 선이 두 개 이하면 not connected이기 때문에 한 component vs 나머지로 만들면 적대관계로 만들 수 있음. 선이 세 개라면 가능한 경우는 삼각형이거나 한 명에게 세 명이 연결된 경우. 삼각형은 삼각형 vs 나머지 한 점으로 놓으면 적대관계이고, 후자의 경우 중심 한 명 vs 나머지 세 명으로 놓으면 우호관계가 된다. 선이 네 개 이상이라면 차수가 3 이상인 점이 존재하게 되어 그 점 vs 나머지 세 점으로 하면 우호관계가 되는데 예외가 딱 하나. 4-cycle. 그런데 이 경우 1-2-3-4-1이라면 1,3 vs 2,4가 우호관계.

이제 n명일 때 성립함을 가정한다. 그리고 n+1명일 때를 본다. 한 점 아무거나 택하고 그걸 제외한 것들을 보면 귀납법 가정에 의해 둘로 나눠 서로 연결되거나 서로 연결되지 않게 할 수 있다. 이 한 점을 x라 하고 이 두 집합을 A,B라 하자. 만약 A,B가 적대관계라면 이 그래프에서 선이 있는 것을 없애고 선이 없었던 곳엔 선을 만든다. 그래도 문제의 조건이 그대로 성립한다! (왜냐면 문제의 조건이 의미하는건 어떤 네 점을 택했을 때 A-B-C-D이고 B-/D-/-A-/-C가 된다는 건데, 위의 시행을 해도 똑같은 상황이 되기 때문이다.) 따라서 A,B가 우호관계일 때만 체크하면 된다. (편의상 x-/-yx,y 사이에 선이 없음을 뜻하기로.)

이제 a \in A, b \in B가 있어 a-x-/-b이거나 a-/-x-b가 성립함을 보이자. 만약 그렇지 않다면 A vs \{ x \}B vs \{ x \}가 전부 우호관계이거나 전부 적대관계이다. 어떤 경우든 A \cup \{ x \} vs B로 하면 해결됨. 이제 일반성을 잃지 않고 a -/- x-b라 하자.

B에서 x와 연결된 것들의 집합을 B_1, 나머지를 B_2라 하자. 앞에서 얻은 결과는 B_1이 공집합이 아니라는 것이다. 그러면 임의의 b_1 \in B_1, b_2 \in B_2에 대해 x-b_1-a-b_2인데 x-/-a,x-/-b_2이므로 b_1-b_2여야 한다. 따라서 B_1,B_2는 우호관계. 그러면 A \cup B_2 \cup \{ x \} vs B_1로 하면 된다.

따라서 수학적 귀납법으로 된다.

(b) 조금 서술이 까다로운데.. 디테일은 생략하기로 한다.

주요 키 포인트는, 주어진 조건을 만족하는 그래프에서 subgraph, 즉 점 집합의 부분집합을 잡고 원래 변 집합에서 이 점의 부분집합에 점을 갖는 것만 남긴 그래프를 보면 이것도 원래 조건을 만족한다는 것이다. (원래 조건 자체가 임의의 4-subgraph에 대해서 보는 intrinsic (?)한 조건이었기 때문에..) 그러면 (a)에 의해 우호나 적대 관계의 AB로 나눌 수 있다. 이를 A-B로 쓰자. 그러면 A,B 각각이 또 조건을 만족시키기 때문에 AA_1-A_2로, BB_1-B_2로 나눌 수 있다. 이를 (A_1-A_2)-(B_1-B_2)로 쓴다. 또 B_1을 두 개로 나누어 B_{11},B_{12}로 나누면 (A_1-A_2)-((B_{11}-B_{12})-B_2)로 쓰고, … 계속 하면 등장하는 모든 집합이 원소가 1개인 것들로 바꿀 수 있다. 이 과정에서 마지막 과정에 주목한다. 마지막에는 어떤 집합 XX_1-X_2로 나눴을텐데, 지금까지 오면서 X_1,X_2는 둘 다 X에 속하면서 다른 집합들과의 연결상태가 전부 동일했다. 따라서 X_1,X_2는 자신들끼리를 제외하면 다른 것들과의 연결상태가 동일하게 됨. 끝.

아마 원래 문제를 내고픈건 (b)였을텐데, (b) 하나만 내면 문제가 너무 어려워지니 그 과정인 (a)를 추가한 것이 아닐지?

2010 KMO 여름학교 모의고사 2차 #2

더블 카운팅하니 한 문제 더. 얼마 전에 있었던 여름학교 모의고사의 2차 2번. 2차 1번과 마찬가지로 이번에 출제한 문제.

48명의 학생이 7개의 문제가 주어지는 경시대회에 참가한다. 시험이 끝난 후, 다음과 같은 사실이 알려졌다.
– 임의의 5문제에 대해 그들을 전부 푼 학생은 없었다.
– 임의의 3문제에 대해 그들을 전부 푼 학생은 정확히 5명이었다.
– 임의의 1문제에 대해 그를 푼 학생 수는 짝수였다.
이 때 한 문제만 푼 학생은 정확히 한 명임을 보여라.

문제에서 더블 카운팅을 써달라고 애원하는 것이나 마찬가지. 첫 조건에 의해 학생이 푼 문제 수는 4개 이하다. 4,3,2,1,0개의 문제를 푼 학생 수를 a,b,c,d,e라 하자. 그러면 d=1을 보이면 된다.
{(문제 A,B,C, 학생 X): X가 A,B,C를 풂}을 생각한다.
(1) 두 번째 조건에 의해, 원소의 개수는 5\binom{7}{3}=175.
(2) 한 편, 이 원소의 개수는 \binom{4}{3}a+\binom{3}{3}b=4a+b이다.
따라서 이 두 조건에 의해 4a+b=175가 된다. 여기서 음 아닌 정수 k에 대해 a=43-k,b=3+4k라 할 수 있다. 한 편, a+b+c+d+e=48이므로 48=a+b+c+d+e \geq a+b=46+3k가 되어 k=0이 된다. 곧 a=43,b=3,c+d+e=2가 된다.
한 편, 이번엔 {(문제 A, 학생 X): X가 A를 풂}을 보면 세 번째 조건에 의해 그 원소의 개수 4a+3b+2c+d는 짝수가 되어 bd는 기우성이 같다. 즉 d는 홀수가 되는데 d \leq c+d+e=2이므로, d=1이고 문제가 증명된다.

나중에 들은 이야기지만 이 문제가 2차 시험 중에서 가장 평균이 높았다고. 이제 더블 카운팅도 많이 정립된건가..

2010 Iran NMO #2, #6

2010 Iran NMO의 조합 문제 2번과 6번. 놀랍게도 둘 다 기초적인 더블 카운팅 문제였다. 이 중 2번은 올 봄에 있었던 통신강좌 (수행평가라고 이름이 바뀌었던데) 금주의 문제로 나오기도 했다.

2. 평면 위에 n개의 점이 있어 어떤 세 개도 일직선 위에 있진 않다고 한다. 이 때 이 점들 중 세 개를 택하여 만드는 삼각형 중 넓이가 1인 것의 개수는 \frac{2}{3}(n^2-n) 이하임을 보여라.

간단한 더블 카운팅. 집합 {(점 A, (점 B,C)): 삼각형 ABC의 넓이는 1}을 생각한다. 이 집합의 원소의 개수를 센다.
(1) 두 점 B,C를 미리 택하면 삼각형 ABC의 넓이가 1이 되게 하는 A의 자취는 BC에 평행한 직선 두 개이다. 따라서 어떤 세 점도 한 직선 위에 있지 않음에서 그러한 A는 최대 네 개이므로 원소의 개수는 최대 4\binom{n}{2}이다.
(2) 한 편 임의의 넓이가 1인 삼각형 하나에 대해, 그 삼각형이 이 집합에 나오는 가지수는 꼭지점 세 개 중에서 어느 것을 맨 앞에 쓰느냐의 문제이므로 세 번 나온다. 곧, 구하고자 하는 개수를 N이라 하면 원소의 개수는 3N이다.
따라서 이를 연립하면 3N \leq 4\binom{n}{2}이므로 N \leq \frac{2}{3}(n^2-n)이 성립한다.

6. n명의 학생이 있는 한 학교에 몇 가지 특별반이 있다. 각 학생은 자신이 원하는 어떤 특별반에도 개수에 제한 없이 들어갈 수 있다. 모든 특별반은 적어도 2명의 학생이 듣고 있다. 만약 두 개의 서로 다른 특별반이 두 명 이상의 공통 학생을 가지면, 두 특별반의 학생 수는 서로 다르다고 한다. 이 때 특별반의 개수는 (n-1)^2 이하임을 보여라.

약간 어렵지만 그래도 더블 카운팅. 학생 수가 k명인 특별반이 x_k개 있다고 하자. 이 특별반들에 대해 {(특별반, (학생 두 명 A, B)): 특별반에 학생 A,B가 속해 있음}의 원소의 개수를 센다.
(1) 각 특별반은 k명을 가지므로 그 중 두 명을 택하는 가지수는 \binom{k}{2}이다. 곧, 원소의 개수는 x_k\binom{k}{2}이다.
(2) 학생 두 명에 대해 그 둘을 동시에 포함하는 특별반들은 전부 학생 수가 달라야 한다. 곧, 학생 수가 k명이면서 이 둘을 포함하는 특별반은 최대 한 개이므로 원소 개수는 \binom{n}{2}이하이다.
따라서, x_k\binom{k}{2} \leq \binom{n}{2}, 곧 x_k \leq \frac{n(n-1)}{k(k-1)}이다. 따라서 특별반의 개수는 x_2+\cdots+x_n \leq n(n-1) \left( \frac{1}{1 \cdot 2} + \cdots + \frac{1}{(n-1)n} \right) = n(n-1)\left(1-\frac{1}{n} \right) = (n-1)^2이다.

나중에 조합론 2판 쓰게 된다면 추가할 문제.

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}이다. 이로써 이 조합등식이 증명된다!

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

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?