Triangle Vertices But Not SidesDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/