3 ms·
The classic recurrence is if you're choosing K elements out of N, it either has the first element (in which case you choose K-1 elements out of the remaining N-
by cpchen 9y ago
The classic recurrence is if you're choosing K elements out of N, it either has the first element (in which case you choose K-1 elements out of the remaining N-1) or it doesn't (in which case you choose K elements out of the remaining N-1), so:
N choose K = (N-1 choose K-1) + (N-1 choose K).
Also, if you sum (N choose K) for all values of K you get 2^N.
- bogomipz 9y agoThanks for the good explanations. Cheers.
- daenz 9y agoI came at this from the perspective of the Binomial theorem: (x + y)^n = sum{k=0,n} (n choose k) x^(n-k) y^k And since a powerset is: sum{k=0,n} (n choose k) The way we can turn the first equation into a powerset is by setting x=1 and y=1, hence: 2^n = sum{k=0,n} (n choose k)