Associated Topics || Dr. Math Home || Search Dr. Math

### Combinations of Pegs

```
Date: 02/04/97 at 11:19:42
From: Jamie Parnell
Subject: Combinations

On a square peg board there are sixteen pegs, four pegs to a side.
If you connect any three pegs, how many triangles can you form?
The answer in the book is 516, and the explanation is that you figure
all possible combinations and then subtract those which result in a
straight line.  The closest I have gotten to the answer is 626 and I
don't know any more combinations to take out.
```

```
Date: 02/04/97 at 15:14:25
From: Doctor Ken
Subject: Re: Combinations

Hi Jamie -

I think your problem is not in finding how many combinations to take
out, but in finding the first figure: all possible combinations of
three pegs.

There's a formula called the "choose" formula, and it says that if you
want to find out how many ways you can choose 3 items from a set of 16

16!        16*15*14
----------  = ----------  =  8*5*14 = 560
3!(16-3)!      3*2*1
N!
In general, N choose P is:   ---------
P!(N-P)!

So since you're coming up with the number 626 after throwing out
straight line combinations, that must be the part that's wrong.

Let's look at why the "choose" formula works.  If you're trying to
choose three points from 16 points, how many ways can you choose the
first point?  You have 16 choices.  How many ways for choosing the
second point?  There are 15 points left, so the number of ways of
choosing the first two points is 16*15.  For the third point, there
are 14 choices left, so the number of different ways of choosing three
points is 16*15*14.

But wait a minute, we actually chose some triangles more than once!
We have to throw away those duplicates.  How many times did we count
each triangle?  Well, if the vertices of the triangle are A, B, and C,
then we counted it in the following ways:

ABC  ACB  BAC  BCA  CAB  CBA

That's 6 ways, and since we counted EVERY triangle 6 times, we can
divide by 6.  So we get 16*15*14/6, which is 16 choose 3.

If you're interested in learning more about the choose formula and
related things, you can look through our archives for topics like
"combinations" and "permutations."  I'll let you figure out the part
where you have to throw away the combinations of three points that
give you a straight line, since that's a little more visual.  Good
luck!

-Doctor Ken,  The Math Forum
Check out our web site!  http://mathforum.org/dr.math/
```
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