MAM2000 (Essays/Dimension)

Counting Triangles

Spatial perception tests often ask students to extract a simple figure from a complicated one. Counting edges is one of the simplest of such tasks. Next in difficulty would be counting the number of distinct angles (Figure 42). By marking each triangle we can extend our table to include the new information:

To fill in the missing value we can reason from patterns, many which are just like those that relate edges to points. Since there are many triangles as there are distinct triples of vertices, the total number of triangles is just the combinations of a certain number of objects taken three at a time. Alternatively, as before, we can use a recursive relationship: the number of triangles at any stage is the sum of the previous number of triangles and the previous number of edges. The latter is the easiest to calculate: it shows that the number of triangles that can be formed from 6 points is 20. [In general the number for n points is n(n - 1)(n - 2) / 6.]

Figure 42. A display of different triangles determined by complete graphs shows that every subset of three vertices determines a triangle. Hence counting triangles is equivalent to counting triples of vertices.

Students who have studied some algebra will be able to relate these numbers to the binomial coefficients:

Removing the literal factors leaves a shifted version of Pascal's triangle:

The fourth row, for example, gives in succession for n = 0, 1, 2, 3, and 4 the numbers of objects with n vertices formed from the four points: dots, lines, triangles in the middle, with the empty set and the whole set at the ends (where n = 0 and n = 4).

Observant students may see another important pattern — that the sum of any row is a power of 2. There is a sophisticated way of stating this observation: the sum of the numbers of simplices of different dimensions in an n-simplex — including the whole object and the empty simplex — is 2ⁿ+1. This same relationship can be observed by setting both a = 1 and b = 1 in the table of binomial expansions or by relating the binomial coefficients to the combinations of n + 1 elements taken k + 1 at a time. The total number of possible combinations is then 2ⁿ⁺¹, the total number of subsets chosen from among n + 1 elements. This basic counting argument can motivate many topics in elementary probability.