How many subsets are there of a set consisting of n elements?

[lesdavies123]

Hi,

So I understand this problem a little, I just can't understand the ending! So saying that we have n elements, we want all the subsets consisting of r elements where r goes from 0 to n.

So we want (n choose 0) + (n choose 1) + ... + (n choose n) which is the summation of n choose r for values of r going from 0 to n. (sorry I don't know how to do the summation symbols). I'm fine so far, but then my teacher said this was equal to = summation of ( n choose r for values of r going from 0 to n ) x (1 exp r) x (1 exp(n-r)). So obviously the 1 exp r and 1 exp(n-r) will always be equal to 1. But this is where I really don't get it, she goes from this great big equation to (1+1)exp n which equals 2 exp n. Can someone please help me with this I know it's something I don't get from the summation, it's the transition I'm missing! Thank you hope the question is comprehensible!

 

[gopher_p]

http://en.wikipedia.org/wiki/Binomial_theorem with ##x=y=1##

 

[FactChecker]

1) A short answer is 2ⁿ + 1. The reason is that every number from 0 to 2ⁿ has a unique binomial representation of the string of n 0s and 1s, like 01000101110...0. Each number matches one string and each string matches a subset where 1 in place j means that the j'th element is in the set and 0 means that the j'th element is not in the set. So the number of subsets are matched to all the numbers 0, 1, 2, ... , 2ⁿ. That is 2ⁿ+1 numbers so there are that many subsets. This is counting both the empty set and the entire set.

2) I don't understand why you say that selecting r out of n gives (r)exp n subsets. Did I read that right? The number of possible combinations of n things taken r at a time is n! / (r! * (n-r)!).

 

[da_nang]

1) A short answer is 2ⁿ + 1. The reason is that every number from 0 to 2ⁿ has a unique binomial representation of the string of n 0s and 1s, like 01000101110...0. Each number matches one string and each string matches a subset where 1 in place j means that the j'th element is in the set and 0 means that the j'th element is not in the set. So the number of subsets are matched to all the numbers 0, 1, 2, ... , 2ⁿ. That is 2ⁿ+1 numbers so there are that many subsets. This is counting both the empty set and the entire set.

Isn't it [itex]2^n[/itex] since the number of subsets is the cardinality of the power set?

 

[FactChecker]

Isn't it [itex]2^n[/itex] since the number of subsets is the cardinality of the power set?

Oh, I think you are right. Without thinking, I added one for the null set. But that was already counted, wasn't it. Thanks.

 

[HallsofIvy]

It is fairly easy to prove that a set with n members has [itex]2^n[/itex] subsets by induction:

1) The empty set, with 0 members has only [itex]2^0= 1[/itex] subset, the empty set itself.

2) Suppose that, for some fixed number, k, any set with k members has [itex]2^k[/itex] subsets.
If a set, A, has k+ 1 members, then it has at least one member. We can choose anyone of its members, call it "x", and observe that all subsets pf A can be divided into two classes- those that contain "x" and those that don't. Every subset that does not contain "x" is a subset of A\ {x} which has k members so there are [itex]2^k[/itex] such subsets. Every subset that does contain "x" is equal to a set which does not contain "x" union {x} and so there are also [itex]2^n[/itex] such subsets. A has [itex]2^k+ 2^k= 2(2^k)= 2^{k+1}[/itex] subsets.

 

[caveman1917]

Another way to do it would be to consider a bijection between the set of subsets of a finite set and the set of binary strings of length equal to the cardinality of the set (every subset is defined by whether each element is either in or not in the subset). The cardinality of the set of binary strings of length n is directly [itex]2^n[/itex].

 

[mathwonk]

given any subset define a function that equals 1 on that subset and zero on the complement. conversely given any such function define a subset as the subset of points where the function equals 1. hence the number of subsets equals the number of functions to the 2 - point set {0,1}, which is 2^n.

 

[caveman1917]

given any subset define a function that equals 1 on that subset and zero on the complement. conversely given any such function define a subset as the subset of points where the function equals 1. hence the number of subsets equals the number of functions to the 2 - point set {0,1}, which is 2^n.

I think you can make that more minimal by doing away with the necessity of defining those functions. Subset membership of a set is defined in terms of predicates over the elements of that set. Depending on how exactly we define things we can either take the set of such possible predicates or the set of equivalence classes of those predicates where two predicates are equivalent iff they define the same set. We can then consider binary strings of length n as a notational system for that set of equivalence classes of predicates over the set, rather than having to define these as functions from the set to {0,1}.

 

[lesdavies123]

Thank you for all the answers and different perspectives guys I get it now!