Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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!
Associated Topics:
High School Permutations and Combinations

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/