codingfarm

$$\sum_{y=0}^x ( {}_a C_y ~{}_b C_{x-y} ) = {}_{a+b} C_x$$ 위 등식이 성립합을 확인해보자. 우선 $(t+1)^a(t+b)^b = (t+1)^{a+b}$ 위 식의 양변에서 임의의 항의 계수는 같음을 보여보자 가령 $t^n$의 계수를 구해보자 우변의 경우 $t^n$의 계수는 ${}_{a+b} C_n$이다 $(n \leq a+b)$ 좌변의 경우를 구하기 위해 식을 전개해보면 $$[{}_a C_{a} t^{a} + {}_a C_{a-1} t^{a-1} + \cdots + {}_a C_{1} t^{1} + {}_a C_{0} t^{0} ]\cdot [{}_b C_{b} t^{b} + {}_b C_{b-1} t^{b-1} + \cdots + {}_b C_{1} t^{1..