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:
Number of points: | 1 | 2 | 3 | 4 | 5 | 6 | |||||
Number of edges: | 0 | 1 | 3 | 6 | 10 | 15 | |||||
Number of triangles: | 0 | 0 | 1 | 4 | 10 | ? |
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
| |
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:
(a + b) | = | a + b |
(a + b)^{2} | = | a^{2} + 2ab + b^{2} |
(a + b)^{3} | = | a^{3} + 3ab^{2} + 3a^{2}b + b^{3} |
(a + b)^{4} | = | a^{4} + 4ab^{3} + 6a^{2}b^{2} + 4a^{3}b + b^{4} |
(a + b)^{5} | = | a^{5} + 5ab^{4} + 10a^{3}b^{2} + 10a^{2}b^{3} + 5a^{4}b + b^{5} |
(a + b)^{6} | = | a^{6} + 6ab^{5} + 15a^{4}b^{2} + 20a^{3}b^{3} + 15a^{2}b^{4} + 6a^{5}b + b^{6} |
Removing the literal factors leaves a shifted version of Pascal's triangle:
1 | 1 | ||||||||||
1 | 2 | 1 | |||||||||
1 | 3 | 3 | 1 | ||||||||
1 | 4 | 6 | 4 | 1 | |||||||
1 | 5 | 10 | 10 | 5 | 1 | ||||||
1 | 6 | 15 | 20 | 15 | 6 | 1 |
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
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^{n}+1. This same relationship can be observed by setting
both