This post illustrates what Feynman praised as a beautiful facet of mathematics–abstraction from the concrete–as well as the fascinating synergy at one of its crossroads–that of algebra and enumerative geometry.
One day last fall in a class, several curious 12-th graders marvelled at the relationship I showed them between the Pascal triangle (OEIS A007318) and the enumerative geometry of triangles and squares and their -dimensional extensions/abstractions the hypertriangles (HTs) and hypersquares (HSs) (or, equivalently, the tetrahedrons and hypertetrahedrons, and the cubes and hypercubes). By looking at certain physico-geometric ways of generating the -dimensional extensions, we can relate simple algebraic manipulations–multiplication of polynomials and a matrix by itself–to counting the components of these geometric constructs, enumerated by their face-polynomials.
First, let’s tackle the HT beasties. The face-polynom, or f-polynom, of a polytope, such as a HT or HS, has coefficients enumerating the number of -D faces of the polytope. For example, the -D HT is a triangle with the associated f-polynom
enumerating the 3 vertices (-D faces), 3 edges (-D faces), and 1 triangle (-D face) of a triangle. The -D HT is a tetrahedron with f-polynom
corresponding to the 4 vertices, 6 edges, 4 triangles, and 1 tetrahedron comprising its faces. (Note that in the general literature the -D faces of either -D polytope can be referred to as their facets.) The general formula that follows from the forthcoming method of constructing the HTs for the f-polynom of the -D HT is
Now for the recursive physico-geometric construction of an -D HT from an -D HT, consider the -D HT, a line segment. Move from the -D HT in a direction perpendicular to it and place a point some distance from it. Then draw line segments connecting each vertex of the -D HT to the new vertex. We have generated an instance of the -D HT, a triangle.
To obtain the -D HT, the tetrahedron, just iterate on the algorithm for generating the triangle by replacing each ocurrence of -D by -D. That is, move in a direction perpendicular to the plane of the triangle, -D HT, place a point some distance away from it, and connect that new vertex to each old vertex, and you have a -D HT, a tetrahedron. For higher dimensions, repeat the procedure ad nauseum.
Now we are in a position to relate multiplication of by to obtain the formula for , the f-polynom of the -D hypertriangle. Note that the coefficients of the polynomial (the elements of the -th row of the Pascal triangle) alledgely enumerate the number of vertices, (), edges (), triangles (), etc., that comprise the -D HT. From the geometric construction, the new -D HT has one more vertex than the old -D HT. This is reflected in the multiplication in the factors . The new HT has as many edges as the old plus an edge for each old vertex giving Similarly, the new HT has as many triangles as the old plus a new one for each old edge; i.e., . And so on for the higher dimensional faces.
Following this train of physico-geometric intuition mapped to this particularly simple algebraic recursion relation, we have established the general f-polynom is indeed
and in some sense defined what hypertriangles are.
Now we are ready to look at the f-polynoms of the hypersquares (HSs) and show that their coefficients are generated by squaring the Pascal matrix as a lower triangular matrix, i.e., by squaring a triangle. This is equivalent to umbral substitution of into itself; that is, the face-polynomial for the -D HS is . For example,
enumerating the faces of a square (4 vertices, 4 edges, and 1 square). This can be simplified as
The method of physico-geometric construction of a new -D HS from an old -D HS is to drag the old through a dimension perpendicular to it letting the edges fill in new squares. For example, drag a line segment in a direction perpendicular to it and a square is obtained. Drag a square in a direction perpendicular to the plane of the square and a cube is obtained. Check that correctly enumerates the faces of a cube, and develop algebraic arguments analogous to those for the hypertriangles to prove the general formula for Do a numerical check that squaring the Pascal matrix as a lower triangular matrix (i.e., a matrix with zeros above the main diagonal) gives the same result as the umbral substitution (cf. A038207).
From here paths meander through glades of analysis, geometry, and combinatorics, roamed by a hybrid of aspects of the hypertriangles and hypersquares–the Vandermonde matrix–and the ubiquitous Bernoulli polynomials and their elegant escorts, the reciprocal polynomials.
Related stuff and other trails in combinatorics:
1) Counting faces of polytopes by Lee. (The varying definitions and uses of the terms h–vector and h-polynomial–and even f-polynomial–in the vast literature are confusing. If we take the h-polynomial to be algebraically defined as with the f-polynomials, , described above, then for the hypertriangles, we obtain and for the hypercubes, .)
5) OEIS A074909
6) OEIS A135278
7) GeneratingFunctionology by Wilf
8) Analytic Combinatorics by Flajolet and Sedgwick
9) Enumerative Combinatorics Vol. I by Stanley
11) A species approach to Rota’s twelvefold way by Claesson
12) Combinatorial Species–Bergeron
13) Computing the Discrete Continuously by Beck and Robins
14) Trianglations of Point Sets by De Loera, Rambau, Santos
15) Ch. 10: Topology Grows into a Branch of Mathematics in the book Never a Dull Moment: Hassler Whitney–Mathematics Pioneer by Kendig
16) Merging/identifying opposing facets of the -hypercube gives us the -torus, and truncating facets of the hypertriangles or hypercubes gives us permutahedra and associahedra and paths to other important and exciting fields of modern research in math and quantum physics.