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-
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

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
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search