I love counting problems and here is one of my favourites. How many triangles can be made using the vertices and edges of the diagram below such that it is orientated the same way as ABC?
If you counted exactly 35, that's right! Counting them all by hand can get a bit messy so maybe you found an easier way. Here are a couple of my favourites that we can summarise non-rigorously now.
This means that the number of valid triangles that have a vertex on the the horizontal line is given by the number of vertices in that line, multiplied the number of valid triangles that use a given vertex as its top. This gives triangles that have a vertex on the the horizontal line. Now this gives the formula for the number of valid triangles .
These counting arguments gave us two different formulas for how to count the triangles which were connected to two different ways of counting the triangles. Since they are counting the same thing this gives us a cute combinatoric identity that = .
With a little effort and algebraic manipulation, we can use some more identities to prove that both of these formulas are also equal to the expression . Before we started with a method of counting things and derived a mathematical formula. In this case, we are given a formula for counting the number of triangles, , but we did not get it explicitly from counting triangles... spooky!
So the question is, does there exist a way of counting the triangles connected to this formula? Is there a way of having n+2 objects such that when we choose any 3 of them it determines a unique valid triangle? I strongly encourage you to try to think about this before reading on.
We'll show a way of counting the triangles inspired by the formula . We won't go into the rigour of why it works but I think that's a fun exercise in itself! First of all, we are going to need to decide on some objects for which choosing 3 of them will determine a valid triangle. For this, we will use the vertices of the bottom row along with some newly created vertex to the left of these. We will label these vertices with the numbers 1,2,...,n+2 starting from left to right as shown below. We will also assume that all the edges between adjacent vertices in our diagram are of unit length.
Now we will select 3 of these labelled vertices and determine a triangle from it. We will call the vertices chosen L, M, R for the left most, the middle one and the right most labelled vertex selected. We let the values or L, M, R be their labels to make it easier to explain ideas.
We will use the label of L to determine the length of the triangle we will determine. We will use M and R to determine the position of the valid triangle of length L we are interested in. Here's how it works in detail.
First, we define the point H of a valid triangle to be the point, on the edge between "the bottom right vertex" of the valid triangle and "the top vertex", that is distant 1 from the bottom right vertex. Here is an animation to try make this clear. The orange triangles are valid triangles and the highlighted blue vertex is its corresponding H point.
Ok, now we have some terminology we can describe the algorithm for corresponding a valid triangle to 3 of our n+2 labelled points.
Let's see what this looks like!
Ok, so now we should prove that this actually works! So what do we need to do? We need to check that this process is reversible and works for all n. I am feeling extremely lazy and will not fill in the details here now but a lot of it can be seen by using induction.