Pascal's triangle: Difference between revisions

Revision as of 06:16, 31 January 2025

Revision as of 09:15, 10 February 2025

Line 336:

==== Number of elements of simplices ====

Let's begin by considering the 3rd line of Pascal's triangle, with values 1, 3, 3, 1. A 2-dimensional triangle has one 2-dimensional element (itself), three 1-dimensional elements (lines, or edges), and three 0-dimensional elements ([[Vertex (graph theory)|vertices]], or corners). The meaning of the final number (1) is more difficult to explain (but see below). Continuing with our example, a [[tetrahedron]] has one 3-dimensional element (itself), four 2-dimensional elements (faces), six 1-dimensional elements (edges), and four 0-dimensional elements (vertices). Adding the final 1 again, these values correspond to the 4th row of the triangle (1, 4, 6, 4, 1). Line 1 corresponds to a point, and Line 2 corresponds to a line segment (dyad).{{citation needed}} This pattern continues to arbitrarily high-dimensioned hyper-tetrahedrons (known as [[simplex|simplices]]).{{citation needed}}

To understand why this pattern exists, one must first understand that the process of building an ''n''-simplex from an {{math|(''n'' − 1)}}-simplex consists of simply adding a new vertex to the latter, positioned such that this new vertex lies outside of the space of the original simplex, and connecting it to all original vertices.{{citation needed}} As an example, consider the case of building a tetrahedron from a triangle, the latter of whose elements are enumerated by row 3 of Pascal's triangle: '''1''' face, '''3''' edges, and '''3''' vertices. To build a tetrahedron from a triangle, position a new vertex above the plane of the triangle and connect this vertex to all three vertices of the original triangle.

The number of a given dimensional element in the tetrahedron is now the sum of two numbers: first the number of that element found in the original triangle, plus the number of new elements, ''each of which is built upon elements of one fewer dimension from the original triangle''.{{citation needed}} Thus, in the tetrahedron, the number of [[cell (mathematics)|cells]] (polyhedral elements) is {{math|1={{define|0|the original triangle possesses none}} + {{define|1|built upon the single face of the original triangle}} = '''1'''}}; the number of faces is {{math|1={{define|1|the original triangle itself}} + {{define|3|the new faces, each built upon an edge of the original triangle}} = '''4''';}} the number of edges is {{math|1={{define|3|from the original triangle}} + {{define|3|the new edges, each built upon a vertex of the original triangle}} = '''6''';}} the number of new vertices is {{math|1={{define|3|from the original triangle}} + {{define|1|the new vertex that was added to create the tetrahedron from the triangle}} = '''4'''}}. This process of summing the number of elements of a given dimension to those of one fewer dimension to arrive at the number of the former found in the next higher simplex is equivalent to the process of summing two adjacent numbers in a row of Pascal's triangle to yield the number below. Thus, the meaning of the final number (1) in a row of Pascal's triangle becomes understood as representing the new vertex that is to be added to the simplex represented by that row to yield the next higher simplex represented by the next row.{{citation needed}} This new vertex is joined to every element in the original simplex to yield a new element of one higher dimension in the new simplex, and this is the origin of the pattern found to be identical to that seen in Pascal's triangle.

==== Number of elements of hypercubes ====

A similar pattern is observed relating to [[square (geometry)|squares]], as opposed to triangles.{{citation needed}} To find the pattern, one must construct an analog to Pascal's triangle, whose entries are the coefficients of {{math|(''x'' + 2)^{row number}}}, instead of {{math|(''x'' + 1)^{row number}}}.{{citation needed}} There are a couple ways to do this. The simpler is to begin with row 0 = 1 and row 1 = 1, 2. Proceed to construct the analog triangles according to the following rule:

:<math> {n \choose k} = 2\times{n-1 \choose k-1} + {n-1 \choose k}.</math>

That is, choose a pair of numbers according to the rules of Pascal's triangle, but double the one on the left before adding. This results in{{citation needed}}:

:<math>\begin{matrix}

\text{ 1} \\

Line 359:

\text{ 1} \quad \text{ 14} \quad \text{ 84} \quad 280 \quad 560 \quad 672 \quad 448 \quad 128

\end{matrix}</math>

The other way of producing this triangle is to start with Pascal's triangle and multiply each entry by 2^k, where k is the position in the row of the given number.{{citation needed}} For example, the 2nd value in row 4 of Pascal's triangle is 6 (the slope of 1s corresponds to the zeroth entry in each row). To get the value that resides in the corresponding position in the analog triangle, multiply 6 by {{math|1=2^{position number} = 6 × 2² = 6 × 4 = 24}}. Now that the analog triangle has been constructed, the number of elements of any dimension that compose an arbitrarily dimensioned [[cube (geometry)|cube]] (called a [[hypercube]]) can be read from the table in a way analogous to Pascal's triangle.{{citation needed}} For example, the number of 2-dimensional elements in a 2-dimensional cube (a square) is one, the number of 1-dimensional elements (sides, or lines) is 4, and the number of 0-dimensional elements (points, or vertices) is 4. This matches the 2nd row of the table (1, 4, 4). A cube has 1 cube, 6 faces, 12 edges, and 8 vertices, which corresponds to the next line of the analog triangle (1, 6, 12, 8). This pattern continues indefinitely.{{citation needed}}

To understand why this pattern exists, first recognize that the construction of an ''n''-cube from an {{math|1=(''n'' − 1)}}-cube is done by simply duplicating the original figure and displacing it some distance (for a regular ''n''-cube, the edge length) [[orthogonal]] to the space of the original figure, then connecting each vertex of the new figure to its corresponding vertex of the original.{{citation needed}} This initial duplication process is the reason why, to enumerate the dimensional elements of an ''n''-cube, one must double the first of a pair of numbers in a row of this analog of Pascal's triangle before summing to yield the number below.{{citation needed}} The initial doubling thus yields the number of "original" elements to be found in the next higher ''n''-cube and, as before, new elements are built upon those of one fewer dimension (edges upon vertices, faces upon edges, etc.).{{citation needed}} Again, the last number of a row represents the number of new vertices to be added to generate the next higher ''n''-cube.

In this triangle, the sum of the elements of row ''m'' is equal to 3^''m''. Again, to use the elements of row 4 as an example: {{math|1=1 + 8 + 24 + 32 + 16 = 81}}, which is equal to <math>3^4 = 81</math>.

==== Counting vertices in a cube by distance ====

Each row of Pascal's triangle gives the number of vertices at each distance from a fixed vertex in an ''n''-dimensional cube.{{citation needed}} For example, in three dimensions, the third row (1 3 3 1) corresponds to the usual three-dimensional [[cube]]: fixing a vertex ''V'', there is one vertex at distance 0 from ''V'' (that is, ''V'' itself), three vertices at distance 1, three vertices at distance {{sqrt|2}} and one vertex at distance {{sqrt|3}} (the vertex opposite ''V''). The second row corresponds to a square, while larger-numbered rows correspond to [[hypercube]]s in each dimension.{{citation needed}}

=== Fourier transform of sin(''x'')^''n''+1/''x'' ===

As stated previously, the coefficients of (''x''&nbsp;+&nbsp;1)^''n'' are the nth row of the triangle. Now the coefficients of (''x''&nbsp;−&nbsp;1)^''n'' are the same, except that the sign alternates from +1 to −1 and back again. After suitable normalization, the same pattern of numbers occurs in the [[Fourier transform]] of sin(''x'')^''n''+1/''x''. More precisely: if ''n'' is even, take the [[real part]] of the transform, and if ''n'' is odd, take the [[imaginary part]].{{citation needed}} Then the result is a [[step function]], whose values (suitably normalized) are given by the ''n''th row of the triangle with alternating signs.<ref>For a similar example, see e.g. {{citation|title=Solvent suppression in Fourier transform nuclear magnetic resonance|first=P. J.|last=Hore|journal=Journal of Magnetic Resonance|year=1983|volume=55|issue=2|pages=283–300|doi=10.1016/0022-2364(83)90240-8|bibcode=1983JMagR..55..283H}}.</ref> For example, the values of the step function that results from:

:<math>\mathfrak{Re}\left(\text{Fourier} \left[ \frac{\sin(x)^5}{x} \right]\right)</math>

Line 380:

is the [[boxcar function]].<ref>{{citation|title=An Introduction to Digital Signal Processing|first=John H.|last=Karl|publisher=Elsevier|year=2012|isbn=9780323139595|page=110|url=https://books.google.com/books?id=9Dv1PClLZWIC&pg=PA110}}.</ref> The corresponding row of the triangle is row 0, which consists of just the number&nbsp;1.

If n is [[congruence relation|congruent]] to 2 or to 3 mod 4, then the signs start with&nbsp;−1. In fact, the sequence of the (normalized) first terms corresponds to the powers of [[imaginary unit|i]], which cycle around the intersection of the axes with the unit circle in the complex plane{{citation needed}}: <math display="block"> +i,-1,-i,+1,+i,\ldots </math>

== Extensions ==