Triangle Vertices But Not Sides

Date: 02/22/2003 at 14:28:07
From: Jessica
Subject: Combinatorics

If P is a regular n-gon, what is the number of triangles whose 
vertices are the vertices of P but whose sides are NOT the sides of P?

Date: 02/24/2003 at 14:53:47
From: Doctor Greenie
Subject: Re: Combinatorics

Hello, Jessica -

Thanks for sending us your question.  I got a lot of good (and 
enjoyable) mental exercise pondering this one.

The title of your message is "combinatorics." When I first started 
working on your problem, I was doubtful that a nice combinatoric 
formula could be found, so I developed a laborious method for counting 
the number of triangles. Then I went to sleep thinking about the 
problem, and I woke up the next morning thinking about the problem, 
and by the time I got out of bed I had formulated a plan for 
developing a combinatoric formula. Happily, the two processes yield 
identical results.

I will give you just a bit of my analytical approach to the problem 
and then show you my neat and simple combinatoric approach.

For both approaches, my methods count all the triangles that include 
any particular vertex of the n-gon and then divide the result by 
three, since each distinct triangle uses three vertices and thus will 
get counted three times.

For the analytical approach, I think of starting at a particular 
vertex and moving around the polygon from vertex to vertex, arriving 
back at my starting point in three moves - each of the three moves 
tracing one side of a triangle. Because the sides of the triangle 
cannot be sides of the polygon, the only rule I have is that the 
number of consecutive vertices I move in any one of the three moves 
must be greater than 1.

So for an n-gon, the number of triangles I can form using any 
particular vertex is the number of different ways I can add three 
positive integers greater than 1 to get a total of n.

Let's look at this method for a couple of relatively simple cases and 
one more complex case.

For n = 6, I have only one set of three positive integers greater than 
1 whose total is 6:

  (2,2,2)

From any particular vertex, then, I only have one way to construct a 
triangle with the required properties - the number of consecutive 
vertices I need to move from my starting vertex is 2, then 2, then 2.

So from each of the 6 vertices I can only construct one triangle of 
the required type. Therefore I can count 6*1 = 6 such triangles; 
however, each distinct triangle gets counted 3 times, so the number 
of distinct triangles of the required type is 6/3 = 2.

For n = 7, there is again only one set of three positive integers 
greater than 1 whose total is 7:

  (2,2,3)

However, in this case, I get different triangles depending on the 
order in which I use these three numbers.  I get one triangle if the 
consecutive numbers of vertices I move are 2, 2, and 3; I get a 
different one if those numbers are 2, 3, and 2; and I get yet a 
different one if those numbers are 3, 2, and 2.

So in this case, for each of the 7 vertices I can construct 3 
different triangles of the required type.  Therefore the total number 
of such triangles is 7*3 = 21; however, as always, each distinct 
triangle gets counted 3 times, so the number of distinct triangles of 
the required type is 21/3 = 7.

Now let's tackle the case n = 12.  Here is a table of the different 
sets of three positive integers whose sum is 12, along with the 
number of distinctly different orders in which the elements of each 
such set can be used:

   set of   number of 
  integers   orders
  -------------------
    2,2,8       3
    2,3,7       6
    2,4,6       6
    2,5,5       3
    3,3,6       3
    3,4,5       6
    4,4,4       1
  -------------------
       total   28

So from each vertex of a 12-gon I can construct 28 different triangles 
of the required type. This gives a total of 12*28 = 336 triangles, of 
which each distinct triangle is counted 3 times, so the number of 
triangles of the required type for n = 12 is 336/3 = 112.


Now let's find the combinatoric formula and compare the results we 
get using that formula to the results we obtained above.

For the first vertex of a triangle of the required type, you can 
choose any of the n vertices of the n-gon. In combinatorical terms, 
the number of ways you can choose the first vertex is "n choose 1":

  C(n,1)

The task remaining is to choose two more vertices. How many vertices 
do you have to choose from? You can't choose the vertex you have 
already used; and you can't choose either neighboring vertex, so 
there are 3 vertices you can't choose, leaving (n-3) vertices that 
you can choose from. So the total number of possible choices for the 
remaining two vertices is "(n-3) choose 2":

  C(n-3,2)

However, some of those selections of the remaining two vertices are 
not allowed - specifically, any selection of two adjacent vertices.  
With (n-3) vertices to choose from, the number of adjacent pairs of 
vertices is (n-4).

So the number of ways of choosing the remaining two vertices is

  C(n-3,2)-(n-4)

The total number of triangles formed starting at any one of the n 
vertices is then the product of the number of ways of choosing the 
first vertex and the number of ways of choosing the remaining two:

  [C(n,1)]*[C(n-3,2)-(n-4)]

But again this total counts each distinct triangle 3 times, so we 
finally have

  number of triangles of the required type in an n-gon =

  [C(n,1)]*[C(n-3,2)-(n-4)]
  -------------------------
               3

Using this formula for n = 6, n = 7, and n = 12 to compare our answers 
with the answers we got above, we have:

For n = 6,

  [C(6,1)]*[C(3,2)-(6-4)]/3 = [6][3-2]/3 = 2

For n = 7,

  [C(7,1)]*[C(4,2)-(7-4)]/3 = [7][6-3]/3 = 7

And for n = 12,

  [C(12,1)]*[C(9,2)-(12-4)]/3 = [12][36-8]/3 = 112

I hope all this helps. Please write back if you have any questions 
about any of this. And thanks again for sending us a very interesting 
problem!

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