4 ms·
>"For each item of a set, you will either include it or exclude it in one of the results." I found this interesting. This may be a silly question(my combinator
by bogomipz 10y ago
>"For each item of a set, you will either include it or exclude it in one of the results."
I found this interesting. This may be a silly question(my combinatorics knowledge is limited) but what exactly is the relationship between power sets and "N choose K"?
- cpchen 10y agoThe 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 10y agoThanks for the good explanations. Cheers.
- daenz 10y 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)
- bmm6o 10y agoThe combinations (n choose k) tell you how many ways there are to take k things from n, and so count that subset of the power set. And since the sets of k things are obviously distinct from the sets of j != k things, there is no overlap. This gives the well-known result that 2^n = Sum n choose k.
- mlpinit 10y agoAn example can be helpful: Given Set A = {1, 2, 3} This is the power Set of A P(A) = {{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}} (All the subsets of A including the empty set and A itself) 3 choose 2 = 3 (If you look in the power set, you'll see that there are only 3 ways to choose 2 items out of 3) Note that order does not matter.