Hacker News Reader

Comment by bogomipz | Hacker News Reader

>"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"?

View on HN

An 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.

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.

Thanks for the good explanations. Cheers.

I 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)

The 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.

Reply on news.ycombinator.com