Re: combinations (choosing objects from "same set".. product rule)


Proginoskes wrote:
G Patel wrote:
Concerning this question (well, this is just the simplest
representative example of the type of question I am having some
struggles with):

"There are 12 students in a class. In how many ways can the 12 students
take 3 different test if four students are to take each test?"

What first comes to mind is: C(12,4) * C(8,4) * C(4,4)

Choosing elements 4 at a time from what's left in the set.

But the conflict arises (in my brain) when I remember the other type of
example I was having trouble with (see
http://groups.google.ca/group/sci.stat.math/browse_thread/thread/a9d5ae1ae28f270b/0d50eae8ecb694a4?lnk=gst&q=Gaya&rnum=4#0d50eae8ecb694a4
)

The problem with my solution there was that I was basically dealing
with combinations (unordered selections) from sets that were not
disjoint (the set of 4 aces was not disjoint from the set of "51 other
things").

But back to the above example, aren't we breaking a rule here too? The
first selection takes from the whole set of 12 students, the second
takes from a subset of this, and the third takes from a subset of both.
How does this not break any rules (especially the product rule,which
we use implicity when multiplying the 3 terms)?

Because all conditions are met. Remember that the official version of
the product rule is:

----------------------------------
PRODUCT RULE. Suppose there are n_1 ways to do task 1, n_2 ways to do
task 2, ..., n_k ways to do task n, AND every combination is admissible
AND no combination is inadmissible AND every combination is generated
exactly once (by choosing particular ways to do the tasks). Then the
number of ways to do the overall task is
n_1 * n_2 * ... n_k.
----------------------------------

The difference is that here, you're not counting possibilities more
than once. If you look at hands consisting only of 2 cards (as opposed
to 13 cards), you get the hand {AH,AD} by choosing AH as an ace and
then AD as your second card, and also by choosing the AD as an ace and
then AH as the second card. In other words, the ordered choices (AH,AD)
and (AD,AH) give the same end result, and so the product rule doesn't
apply here: One particular outcome can be obtained by making two sets
of choices.

If you want to get technical for the student/test question, you can
order the students from 1 to 12. Then you want to choose 4 of these
numbers to put into set A.

Now, to choose the next 4 numbers, what you do to make sure you're not
counting things more than once is to set up a function f from
{1,2,3,...,8} to
{1,2,...,12} - A. (The latter set is the numbers which haven't been
chosen.) You can always do this so that f is increasing; f(1) < f(2) <
... < f(8), and this can only be done in one way.

Then you're choosing 4 elements a,b,c,d, of {1,2,3,...,8} and letting B
= {f(a), f(b), f(c), f(d)}. Finally, you assign the leftover elements
to C.

Because the tests are different, there is no way to end up with the
same assignment of tests by choosing (A, {a,b,c,d}) in two different
ways; and every distribution of the 3 tests can be obtained by finding
a particular A and {a,b,c,d}; and you're not counting anything you're
not interested in. Hence the product rule works.



Yes. I get it now. The main difference is that the selections are
going into 3 sepearate sets (for the 3 tests), so there is no way for
duplicate outcomes to occur because we are not considering all the
selections as one thing (like choosing from non-disjoint sets to be
placed in a common output/result set in the aces problem).

Example:

Along the lines of your AH, AD aces example above, had the 2 selections
been going into 2 separate sets (which we are considering separate in
terms of outcome), then ({AH}, {AD}) would be considering DIFFERENT
from ({AD}, {AH}) - say the first term in ordered pair is pile 1, and
second is pile 2.

But if we consider selections (from non-disjoing sets) as going into a
common set (or "hand"), a duplication occurs because {AH, AD} is the
same as {AD, AH} - as you've pointed out.


Slowly but surely I'm getting it. I'm trying to learn this stuff
purely from first principles and a "lot of thinking/questioning"
instead of doing 1000 problems and looking at the solutions, and thus
knowing which method to use with each type of problem. It's a huge
risk.... hope it's worth the trouble.

Thanks Proginoskes

.

Relevant Pages