用递归函数计算从n个人中选择k个人组成一个委员会的不同组合数答案就是由n个人里选k个人的组合数＝由(n-1)个人里选k个人的组合数＋由(n-1)个人里选(k-1)个人的组合数.为什么是这个样啊

Question

用递归函数计算从n个人中选择k个人组成一个委员会的不同组合数
答案就是由n个人里选k个人的组合数＝由(n-1)个人里选k个人的组合数＋由(n-1)个人里选(k-1)个人的组合数.为什么是这个样啊

Answer 1

n个人里选k个人的组合数 = nCk = n!/[(n-k)!k!]
由(n-1)个人里选k个人的组合数＋由(n-1)个人里选(k-1)个人的组合数
= (n-1)Ck + (n-1)C(k-1)
= (n-1)!/[(n-1-k)!k!]+ (n-1)!/[(n-k)!(k-1)!]
= [ (n-1)!* (n-k) + (n-1)!*k] /(n!k!)
= [(n-1)!(n-k+k)] /(n!k!)
= n!/(n!k!) = nCk