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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.