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?

Advertisements
    • pedantry
    • July 18th, 2010

    풀이 잘 봤습니다.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: