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
_____________________________________________

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 
items, then the answer is: 

      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

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