Exploring the Combinatorial Nature of Subsets in a Finite Set

[Townsend]

How many 4 element subsets can you get from a 21 element set. I know the combination formula C(21,4)=5985. I was trying to see how this is working out though. I know there are 2^21 subsets of a 21 element set, I want to know how I can find the number of all the 4 element subsets without using the formula C(n,r).

The way to get 2^21 is to just go down the line for each element in the set. for each element there are 2 choices. Yes or no, so by the multiplication principle you have 2^21 choices. How can I then eliminate all the subsets that have a cardinality other than 4?

Or if there is a better way to than the total minus the bad method that will work I would like to hear that way too.

Thanks for helping...

Jeremy

 

[e(ho0n3]

What's wrong with using the formula C(n,r)? The other method you're proposing will also end up using C(n,r).

 

[Townsend]

Some practice counting problems. I just need to make sure I know what I am doing on these problems.

1) There are ten people in a club. They are going to elect the club officers of President, Vice President and a Treasurer. Bill and Jed are two of the ten people. Bill said he will only be an officer if Jed is an officer too. How many ways can they elect their officers?

Ok, I see this as a bad minus the good kind of problem. There are 720 ways to elect 3 people from 10 if order counts. The bad is whenever Jed is not an officer and Bill is an officer. Without Jed being an officer there are 504 possibilites. Of these I need to know how many have Bill as an officer. There are three cases for this, Bill as P, Bill as VP or Bill as T. For each one there are 8*7 possibilites for the other two offices. So there are 8*7*3 cases where Bill is an officer but Jed is not. So we have 720-8*7*3=552. Is that right?

2) Same club and same ten people. Alice is one of the ten and so is Ben. This time Alice will not be an officer if Ben is an officer. Now how many ways can they elect a President, VP and Treasurer?

For this problem there are two situations. Case one has Ben as an officer and Case 2 has Ben not as an officer. In case 1 we are assuming Ben is an officer and so Alice is not. Ben can be anyone of the 3 officers and for each of the three positions he there are 8*7 possibilities for the remaining two positions. So for Ben as an officer there are 8*7*3=168 possibilites. For case two Ben cannot be an officer at all and so he is removed from the list of ten people. Now of the remaining 9 people there are 9*8*7=504 possibilites for the three officer positions. Since case 1 is disjoint from case 2 we can add these together to find that there are 672 ways to elect the three officers in this situation. Is that correct?

Thanks for the help

 

[Townsend]

What's wrong with using the formula C(n,r)? The other method you're proposing will also end up using C(n,r).

Nothing is wrong with it at all, I just wanted to see if there is a way to count the subsets without using that formula at all. I realize it is more or less the same thing but I think I will see how the formula is doing the counting if I can see it worked out without using the formula. The purpose for that is so that when some really strange, mixed up question comes up I will hopefully see how to apply this formula where as if I just spend all day answering questions using this formula I don't think I will be able gain that kind of intuition.

Thanks...

 

[SGT]

There are n ways to choose the first element of the group, n-1 ways to choose the second and so on. So there are n.(n-1).(n-2)...(n-r+1) ways to choose r elements from a set of n elements.
Since the sets {1,2,3,4}, {3,2,1,4}, ... are all the same, you must divide the total number of arrangements by the number of permutations of r elements.
But this is only the way to arrive at the formula C(n,r), so I don't know if it helps.