[BOJ 12797] 연금술

굉장히 오랜만에 올리는 포스팅~ 방학동안 버클리에 가 있어서 백준을 못한게 크다 ㅜㅜ. 본론으로 들어가자.

문제는 $m$개의 재료 중에서 $n$개를 선택해서 그 값들의 곱을 모두 더하는 것이다!! 간단히 주어진 예제로 생각해보면 값이 각각 $x, y, z$라고 할 때

$$x^{3}+y^{3}+z^{3}+x^{2}(y+z)+y^{2}(z+x)+z^{2}(x+y)+xyx$$

를 구하는 것이다. 우리가 생각할 수 있는 것은 이 식을 어떻게 좀 간단하게 할 수 있냐는 것이다. 놀랍게도 위의 식은 다음과 같이 간단하게 표현된다!

$$\frac{x^{5}}{(x-y)(x-z)}+\frac{y^{5}}{(y-x)(y-z)}+\frac{z^{5}}{(z-x)(z-y)}$$

값이 서로 다른 $m$개의 재료 중에서 $n$개를 선택해서 값을 모두 구하는 함수를 $f(n,m)$이라 정의하자. 

$$\mathbf{Claim.}\ \ f(n,m)=\sum_{i=1}^{m} \frac{a_{i}^{n+m-1}}{\prod_{j=1,\ j\ne i}^{m} (a_{i}-a_{j})}$$

우리는 $f(n,m)$를 더 작은 꼴로 나눠서 생각해 볼 수 있다. $m$번째 재료를 반드시 사용한다고 하자. 그럼 $a_{m}f(n-1,m)$이 되겠다. 반대로 $m$번째 재료는 사용하지 않는다고 하면 $f(n,m-1)$이 된다. 따라서 다음을 얻는다.

$$f(n,m)=a_{m}f(n-1,m)+f(n,m-1)$$

이때 우리가 $f(n-1,m),\ f(n,m-1)$의 값이 Claim의 값과 같다고 가정하자. 그럼

$$f(n,m)=a_{m}\sum_{i=1}^{m} \frac{a_{i}^{n+m-2}}{\prod_{j=1,\ j\ne i}^{m} (a_{i}-a_{j})} + \sum_{i=1}^{m-1} \frac{a_{i}^{n+m-2}}{\prod_{j=1,\ j\ne i}^{m-1} (a_{i}-a_{j})}$$

각 항에 있는 $i$를 $t<m$로 고정해서 생각해보자. 그럼

$$a_{m} \frac{a_{t}^{n+m-2}}{\prod_{j=1,\ j\ne t}^{m} (a_{t}-a_{j})} + \frac{a_{t}^{n+m-2}}{\prod_{j=1,\ j\ne t}^{m-1} (a_{t}-a_{j})}=a_{t}^{n+m-2}\frac{a_{m}+(a_{t}-a_{m})}{\prod_{j=1,\ j\ne t}^{m} (a_{t}-a_{j})}=\frac{a_{t}^{n+m-1}}{\prod_{j=1,\ j\ne t}^{m} (a_{t}-a_{j})}$$

반면 $f(n,0)=0,\ f(0,n)=1$임이 자명하므로 귀납법에 의해 증명 되었다.