[확률과 통계] binomial theorem proof (이항 계수 증명) (x+y)n = ∑k=0n(nk)xkyn−k 해당 수식을 귀납법을 통해 증명할 수 있습니다. 1. n = 1 일 때 (x+y)1=(10)x1y0+(01)x0y1이므로 n = 1 일 때는 수식이 맞음을 알 수 있습니다. 2. 증명 n - 1 일 때 맞다고 가정하고, n을 증명합니다. (x+y)n = (x+y)(x+y)n−1입니다. 이때 n - 1 일 때는 맞다고 가정했으므로, 위의 수식은 (x+y)∑k=0n−1(n−1k)xky(n−1)−k입니다. 앞의 x + y가 거슬리므로 뒤에 곱해서 식을 전개해봅니다. \(\.. 수학/확률과 통계 2022.09.18
[알고리즘] 동적 계획법 - 최적화된 이항 계수 구하기 (Dynamic Programming - Optimal Binomial Coefficient) 문제) Computer Science/알고리즘 2022.04.13
[알고리즘] 동적 계획법 - 이항 계수 (Dynamic Programmin - Binomial Coefficient) 다들 이항 계수 아시죠? (nk)=n!k!(n−k)!입니다. 이때 n!를 계산하기 매우 힘드므로, 재귀 관계식을 이용하여 다음과 같이 정리할 수 있습니다. \(\binom{n}{k}=\left\{\begin{matrix} \binom{n-1}{k-1}+\binom{n-1}{k} & 0 Computer Science/알고리즘 2022.04.13