walker wrote:
You can post here any concepts/examples you think aren't covered by my post. At least everyone who read this thread will see them. I will do my best to include them in the first post.
Here are some notes on choosing subsets, which might serve as a good addition. Hope you find this useful.
Choosing subsets & their applicationsCombinatorial questions almost always deal with counting certain kinds of subsets of a given set in question. For instance, the popular C(n,r) formula is used to count the number of ways to pick up r objects from a set of n objects. This is basically the same as asking the question : "If a set A contains n objects, how many subsets of A contain exactly r objects ?". Notice that we cannot use P(n,r) to count these subsets since that involves counting the ordering as well, which is irrelevant when it comes to sets ({1,2,3} is same as {3,2,1}).
An interesting and useful extension of this way of thinking about counting presents itself when we encounter a group of problems where we need to count all the possible subsets of a set. Consider the following question :
There is a basket with 5 different fruits inside. A child is given the basket and he may pick out none, one or more of the fruits. In how many ways can this choice be made ?In this question if we an count all the possible subsets of the basket of fruits, then each subset represents one way of choosing, and hence the answer to the question.
Solution 1Think of each fruit as a yes/no question that the child is answering. "Will this fruit be picked ?". There are 2 ways to answer that question. There are 5 fruits in all and hence, 5 yes/no questions. Each set of answers [y n y n n], [y y n n n], etc represents a way of picking. In all the number of ways would be 2x2x2x2x2=2^5
Solution 2An alternate method is to consider the cases, that the child picks 0 fruit, picks 1 fruit, ... picks 5 fruits. And sum the possibility
This method will yield the answer to be C(5,0)+C(5,1)+C(5,2)+C(5,3)+C(5,4)+C(5,5). If you calculate this sum, it is exactly equal to 2^5
Lets now look at a special case where, the objects we are picking from are identical to each other. Consider the following question :
There is a basket with 5 identical balls. A child is given the basket and he may pick out none, one or more of the balls. In how many ways can this choice be made ?Notice the subtlety in this question, the objects to be picked out are identical to each other. So unlike the previous case where choosing just fruit#1 is a different choice to choosing just fruit#2, here choosing one ball or the other ball constitutes the same choice as long as only 1 ball is picked because the balls are indistinguishable
SolutionSince the balls are identical, the number of ways to pick them is defined merely by the number of balls you pick. So the different ways are "pick 0 balls", "pick 1 ball", ... "pick 5 balls". The answer therefore is 5+1 (The plus 1 giving the case where you pick 0 balls)
Finally we should consider the special case where we need to pick objects out of a set such that a few of the objects are identical to each other.
There is a basket with 4 blue balls, 3 red balls and 2 yellow balls. The balls of the same color are identical. How many ways can a child pick balls out of this basket ?SolutionWe combine techniques from the 2 cases above. Consider the blue balls as one entity and instead of asking the yes/no question, ask the question how many ways to choose the balls ? This is answered using the second case, and the answer is (4+1). Combining this with the ways to choose red and yellow balls, the overall ways to choose balls would be (4+1)*(3+1)*(2+1).
Formula SummaryNumber of ways to pick 0 or more objects from n non-identical objects = \(2^n\)
Number of ways to pick 1 or more objects from n non-identical objects = \(2^n - 1\)
Number of ways to pick 0 or more objects from n identical objects = \(n+1\)
Number of ways to pick 1 or more objects from n identical objects = \(n\)
Number of ways to pick 0 or more objects from n objects of which n1 are identical, n2 are identical, ... ,nk are identical, such that n is n1+..+nk = \((n1+1)*(n2+1)*...*(nk+1)\)
Number of ways to pick 1 or more objects from n objects of which n1 are identical, n2 are identical, ... ,nk are identical, such that n is n1+..+nk = \((n1+1)*(n2+1)*...*(nk+1) - 1\)
Typical ApplicationsHere are just a couple of questions of this type :
How many factors does a number n have ?Consider the prime factorization of n. Let this be :
\(n=p_1^{a1} p_2^{a2} ... p_n^{an}\)
Any factor of n will be of the form
\(m=p_1^{b1} p_2^{b2} ... p_n^{bn}\) where \(0<=b_i<=a_i\) & \(1<=i<=n\)
To count the number of factors, we need to count all the products of p1,...,pn such that the exponent is less than or equal to ai. This is just case 3. We just count per factor, how many ways to select p1, p2, ....
Answer is (a1+1)*(a2+1)* .... *(an+1)
In a class of 10 students, in how many ways can you form a academic committee, if the committee must contain a minimum of 2 students ?Total number of ways to form committees (case 1) = 2^10
Number of ways to form of size 0 = 1
Number of ways to form of size 1 = 10 (each student picked one at a time)
So no of ways = 1024 -1 -10 = 1013
close
Updated on: 10 Dec 2010, 22:26
