Connecting the Dots

Date: 03/14/99 at 17:55:29
From: Tim Ferry
Subject: Permutation and Combination

I want to know if the formula I used for a maths problem is the right 
one. The question is: if you have a few dots on a page, how many lines 
does it take to connect them all to each other? If you have three dots 
you can connect them by three lines. I worked out that you can work 
the answer out by halving the amount of lines, taking away 0.5 and 
then multiplying it by the amount of lines. The formula works and I 
wanted to know what is it called if someone has already thought of it.

Date: 03/15/99 at 09:16:30
From: Doctor Peterson
Subject: Re: Permutation and Combination

Yes, your method does work, and it has been thought of (though usually 
by older people!). There are some interesting things to say about it.

One thing mathematicians like to do is to look at a problem in 
different ways and see if those other ways of thinking help to solve 
it. In this case, what you are doing is really the same as finding how 
many pairs you can make from a set of objects, since each pair of dots 
will define a line. So for instance, if I have three dots named A, B, 
and C, the three lines correspond to the three possible pairs AB, AC, 
and BC. Now we do not need to draw dots and lines to think about the 
problem, but can just make lists of letters!

How can I count the number of pairs? If I try to make a "word" by 
choosing two different letters out of A, B, and C, I can choose any of 
the three for the first letter, and I will have two choices left for 
the second letter:

    AB    AC
    BA    BC
    CA    CB

That gives 3 x 2 possibilities: two for each of the three first 
letters. (Do you see the rectangle in my list? The number of objects 
in a rectangle is the number of rows times the number of columns.) But 
that includes every pair exactly twice, since I can have either AB or 
BA, for instance, but they are the same pair. So the number of pairs 
is half of this, or 3.

Now if we do this for any number of objects, call it N, rather than for 
3, what we have done is to multiply N by N-1 (since there are N choices 
for the first, and N-1 choices for the second), and then divide by 2 
(to eliminate duplicates). So the formula is

            N x (N-1)
    Pairs = ---------
                2

You formula would be written like this:

              N     1
    Pairs = (--- - ---) x N
              2     2

That is really just the same, since N/2 - 1/2 = (N-1)/2. That is, we 
can subtract one before dividing by two, and it is the same as first 
dividing both the N and the 1 by two and then subtracting them.

This is called "the number of combinations of N objects taken 2 at a 
time", and there is even a special symbol for it. It can be written as

                   N
      C    or as (   )
     N 2           2

You might like to think about what it would mean to replace the 2 with 
a three in this symbol - what would it mean to find the number of 
combinations of N taken 3 at a time? It is only a little more 
complicated.

After you have done some thinking yourself, you can look at our 
Frequently Asked Questions page on this subject:

   http://mathforum.org/dr.math/faq/faq.comb.perm.html   

One other thing that is interesting is that this really is not 
necessarily the number of lines formed by N dots - only the largest 
possible number. If the three dots are in a row, there is only one 
line! But usually none will be "collinear" (the fancy word for being 
in a line), so your formula will work.

- Doctor Peterson, The Math Forum
  http://mathforum.org/dr.math/