Combinations of Combinations?
Date: 12/15/2003 at 17:31:32 From: Charles Subject: Combinations of combinations! I understand the formula n!/((n-r)!*r!) to compute the number of combinations of r objects selected from n objects. My question is this--having determined nCr, how do I calculate M, the number of resulting sets which contain, say, t items? For example, I have 4 items A, B, C, and D. Selecting any 3 gives 4 combinations; ABC, ABD, BCD, and ACD. These 4 sets contain 2 occurrences of AB. In this simple example t = 2 and the result M is 2. Similarly, if t=1 then M = 3. My question is how do I compute M in the general case? None of the standard texts seem to deal with this problem. I am 57 and studying A-Level maths.
Date: 12/15/2003 at 19:07:42 From: Doctor Schwa Subject: Re: Combinations of combinations! Hi Charles - Nice question! Here's how I see it. Out of the combinations (4 of them in your example) with 3 letters out of 4 total, the first letter (A) has a 3/4 chance of being in the combination you list. Then, once that letter is used up, the second letter (B) has a 2/3 chance of being in the combination (since the combination has 2 letters left unused, out of a total of 3 letters left after using A). So, the answer is (4 choose 3) * (3/4) * (2/3). In the general case, you'll have (n choose r) * (r/n) * (r-1)/(n-1) * ..., where the "..." goes on for t factors (ending with (r-t+1)/(n-t+1), I guess). Then that product can be rewritten with factorials, since r*(r-1)*... with t terms in it is r!/(r-t)! (n choose r) * (r!/(r-t)!) * ((n-t)!/n!), or overall n! * r! * (n-t)! -------------------- (n-r)! r! (r-t)! n! which reduces a whole lot, to (n-t)! ---------------- (n-r)! * (r-t)! and then since the two numbers in the bottom add up to n-t, it miraculously turns into (n-t choose r-t). Wow! So there must be a simpler reason why (n-t) choose (r-t) is the right answer. And now that I get to this point, I see it: To make a choice of r things from n, which contains a certain specified t symbols, you first choose the specified t symbols (only 1 way to do that!) and then choose the other (r-t) from the remaining (n-t). So it really is only a combination problem, after all! Thanks for the fun problem, - Doctor Schwa, The Math Forum http://mathforum.org/dr.math/
Date: 12/17/2003 at 18:24:07 From: Charles Subject: Thank you (Combinations of combinations!) Thanks, that's a neat solution. It has helped me very much consolidate my thinking on the subject.
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.