Creating an Organized List of Combinations
Date: 11/25/2008 at 06:58:33 From: Huang Subject: How to derive combinations? How can I derive all possible combinations of 6 numbers drawn from 12 numbers (1 to 12 inclusive)? Most maths teachers only teach how to calculate the number of combinations (not how to derive them). Most people use a trial and error method. (Think of any possible combination and write it down if it is not already listed. The trial and error method is tedious and error prone. And it doesn't guarantee that what is derived includes all possible combinations. Is there a more professional and foolproof method to derive all possible combinations? I've tried using lexicographical order but that creates too many combinations and I'm not sure whether all are valid.
Date: 11/25/2008 at 08:41:48 From: Doctor Ian Subject: Re: How to derive combinations? Hi Huang, Most people focus on the formulas because the whole point of being able to calculate things like 12_C_6 directly is to AVOID enumerating the actual combinations, which as you say is cumbersome, error-prone, and normally useless. Normally you'd write a computer program to do it for you. Here's one way to go about it: Suppose I have the letters A, B, C, D, E, and I want to find all subsets of 3 of those. Think for a moment about how we DERIVE the formula for 5_C_3. We start by using the fundamental counting principle, 5 * 4 * 3 5 Ways to choose the first letter, 4 ways to choose the second, 3 ways to choose the third. 5! = ------ (5-3)! and then we account for the same cases appearing in different orders, 5! = --------- (5-3)! 3! 3! permutations of whatever I've chosen So this suggests a method of generating the subsets. I start by making the first choice, A-- B-- C-- D-- E-- followed by the second choice - but only considering choices where the items are in increasing order (which lets me get, e.g., ACD but not DAC), A-- -> AB- AC- AD- AE- B-- -> BC- BD- BE- C-- -> CD- CE- D-- -> DE- E-- -> none and finally the third choice, again keeping the restriction on order, A-- -> AB- -> ABC ABD ABE AC- -> ACD ACE AD- -> ADE AE- -> none B-- -> BC- -> BCD BCE BD- -> BDE BE- -> none C-- -> CD- -> CDE CE- -> none D-- -> DE- -> none E-- -> none And that's my list: ABC ABD ABE ACD ACE ADE BCD BCE BDE CDE I have 10 items, which is what the formula predicts: 5! --------- = 10 (5-3)! 3! And at least for small cases, I can be confident that fatigue or boredom hasn't prevented me from tracing out the process correctly. Does this help? - Doctor Ian, The Math Forum http://mathforum.org/dr.math/
Date: 11/25/2008 at 19:18:32 From: Huang Subject: Thank you (How to derive combinations?) Thank you, Doctor Ian!
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.