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

### 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/
```
Associated Topics:
High School Permutations and Combinations
High School Triangles and Other Polygons

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