Proof for the vertical sums relation in A046816 and similar sequences Eitan Y. Levine 2023-05-21 (In case this text will be copied elsewhere: The drawings of the triangular number grids below are best viewed using a monospaced font, on a display with at least 62 columns to avoid the lines from breaking and mixing.) Introduction ------------- The Pascal triangle, A007318, lists the binomial expansion coefficients, where each C(n,k) is the coefficient of x^k in the expansion of (1+x)^n, or alternately it is the coefficient of x^k * y^(n-k) in the expansion of (x+y)^n. These two representations, (1+x) and (x+y), give the same coefficients. However, when we want to generalize by adding more terms to the parentheses, there is more than one way to do it, leading to different possible sets of coefficients. First, let's rewrite these two expressions using a slightly different notation, which will make the generalization options discussed below more clear: (x^0+x^1)^n (x_0+x_1)^n So for example, generalizing to three terms, we can talk about: (x^0+x^1+x^2)^n, or (x_0+x_1+x_2)^n. In the first option, back in the "original" notation, we ask what is the coefficient of x^k in the expansion of (1+x+x^2)^n. The answer is a function of (n,k), just like in Pascal's triangle. In the second option, again in an extension to the "original" notation, the question is now what is the coefficient of x^a*y^b*z^c, for 0<=a,b,c<=n, and a+b+c=n. The answer now has three degrees of freedom (n,a,b,c with one constraint about the sum) instead of two in the first option (n,k). These two types of generalizations are of course related, and this text discusses some of the relations between them. In the OEIS they are both present, and the following table summarizes their sequence numbers. Dim stands for dimensionality, which is the number of terms in the parentheses, and the two other titles describe the expansion type on which the sequence is based. Dim (sum(x^i))^n (sum(x_i))^n Comments --- ------------ ------------ ----------------- 2D A007318 A007318 Pascal's triangle 3D A027907 A046816 4D A008287 A189225 5D A035343 ... ... kD A273975 A191358 General dimensionality As far as I could find, there is no sequence for the 5D version of the (sum(x_i))^n generalization (and I assume that none exist for higher dimensions). I didn't list all sequences of the (sum(x^i))^n; more exist. The kD versions are going over antidiagonals in a table of general-dimension constant-n Pascal simplex slices, so they contain (although interleaved) all of the other sequences. (A273975 links to more sequences which should go instead of the "..." in the table above). In this text, I will first describe the vertical-sum relation between the two 3D generalizations, A027907 and A046816, and then demonstrate how this relation generalizes to higher dimensionality. Vertical sum relation between the 3D generalizations ---------------------------------------------------- The numbers in the tetrahedron A046816 are the coefficients of (x_0+x_1+x_2)^n, whereas the numbers in the triangle A027907 are the coefficients of (x^0+x^1+x^2)^n. (Both are termed "trinomial coefficients" in different contexts, and similarly there are multiple definitions for "quadrinomial coefficients" and the general "multinomial coefficients".) If we take n=3 for example, we can see that while in A046816, the coefficient of e.g. x_0*x_1*x_2 is separate from that of x_1^3, in A027907 the corresponding coefficients - those of x^0*x^1*x^2 and (x^1)^3 - are grouped to one coefficient, since both terms are x^3. Similarly the terms for x_0^2*x_2 and x_0*x_1^2 are separate here but are grouped there (as the coefficient of x^2), and similarly for x_0*x_2^2 and x_1^2*x_2 (which together form the coefficient of x^4 in the line n=3 of A027907). All of this was an example with n=3, to demonstrate the grouping and summing of the A046816 tetrahedron coefficients to obtain the A027907 coefficients. In general, if the powers of x_0, x_1, x_2 are respectively a_0, a_1, a_2 in the expansion of (x_0+x_1+x_2)^n (meaning that a_0+a_1+a_2=n), then the corresponding power of x in A027907 is 0*a_0+1*a_1+2*a_2 = sum_i=0..k-1 (i*a_i) := S, where k is the number of summands in the parentheses and also the dimensionality of the generalized triangle, 3 in our case. Therefore, different terms in the same n slice in the tetrahedron are grouped to the same element in A027907 if they have the same S value. The only way to maintain S for a given n (for k=3) is by changing the value of a_2 by some b, and changing the value of a_1 by -2b (a_0 will need to change by b as well, to maintain the value of n which is the sum of the three a_i's, but a_0 doesn't affect the sum S, so in that sense it acts as a regulator, adapting to the changes in the other coefficients for maintaining the same n). In each slice of the tetrahedron, the numbers are arranged in a triangular grid (see the example slice drawing below). If we name the three vertices x_0, x_1 and x_2, then for any natural a_0,a_1,a_2 that sum up to n we can see that the coefficient of x_0^a_0*x_1^a_1*x_2^a_2 (in the expansion of (x_0+x_1+x_2)^n) is located in the n-th slice, on the intersection of the grid lines which are at distances a_i from the edges opposite to vertices x_i, respectively (for every i). For convenience, we can also label the opposite edges like the corresponding vertices, and rephrase the last sentence: the location of the coefficient in the n-th slice is on the intersection of the grid lines which are at distances a_i from the edges x_i, repectively. Let's explicitly name them and then consider an example: the bottom left vertex of each slice will be named x_0, the top vertex will be named x_1, and the bottom right vertex will be x_2. The edge labeling mentioned above means that we also identify the bottom (horizontal) edge with x_1, etc. So for example: for n=3 and a_0=a_1=a_2=1, the coefficient is the central 6, which is located on the horizontal line which is at a distance of 1 from the horizonral edge of the n=3 slice, and similarly at distances 1 from each of the two diagonal edges. As another example, for a_1=3 and a_0=a_2=0, the corresponding coefficient is the 1 at the top vertex, which is at a distance of 3 horizontal grid lines from the x_1 (bottom) edge, and which also lies on the other two edges, so its distances from them are both 0, corresponding to a_0 and a_2. Now, we notice that motion along a vertical line to the next number in this grid, for example from top to bottom, is getting us two grid lines closer to the x_1 edge, thereby decreasing a_1 by 2, and one grid line farther from the x_2 edge, thereby increasing a_2 by 1, thereby maintaining S, and staying in the same group of terms that add up to one A027907 term. As an example, we draw the n=3 slice of the tetrahedron, and beneath it the n=3 line of A027907. It is easy to see that the vertical lines sum up to the corresponding terms. ...1... ..3.3.. .3.6.3. 1.3.3.1 1367631 Due to the freedom of choice of the order for naming the vertices x_0, x_1, x_2, or alternatively due to the symmetries of the triangular slices, we can sum along lines normal to any of the three edges (not just the horizontal edge as was shown above) and obtain the same result. Generalizing the relation to higher dimensions ---------------------------------------------- For higher dimensions, similar relations can be found. For example, in the 4D version A189225, the terms that correspond to the same term in A008287 (and sum up to it) are lying on planes within each tetrahedral layer of a given n. In general, in the k-dimensional version of Pascal's triangle A191358, the summation over the correctly chosen (k-2)-dimensional hyperplanes within the (k-1)-dimensional slice of constant n, gives the corresponding elements T(k,n,h) from A273975. To find the grid vectors that span these hyperplanes, we do the following (if something is hard to follow, think about the k=3 case discussed above as a refrence): For a k-dimensional Pascal simplex, a constant-n slice is a (k-1)-dimensional simplex. As before, we denote its vertices as x_0,...,x_{k-1}, where in each grid position the value of each a_i is the distance from the (k-2)-dimensional facet opposite of the x_i vertex. Now, looking at the 1D edges (x_i,x_j), we define e_ij to be the grid-unit vector oriented along this edge, pointing from x_i towards x_j. For every 2<=i<=k-1, we define v_i = i*e_10 + e_0i. This vector decreases a_i by 1 while increasing a_1 by i (and also changing a_0), thereby maintaining a fixed value for S. The hyperplane spanned by {v_i}_i=2..k-1 and its parallels are those that group the desired terms, and summing along them we can get A273975 from A191358 etc. For example, we take the example slice (n=4) from A189225. In this sequence k=4 so the slice is a 3D tetrahedron. For this example we denote the topmost vertex, containing the first 1 in the tetrahedron, as x_3, and the bottom triangle's vertices as x_0, x_1, x_2 (from left to right). With this notation, v_2 is the vector taking us from x_1 (the 1 at the top of the bottom triangle) to the 12 that is directly two lines below it (or from that 12 to the 6 at the bottom edge), and v_3 is the vector taking us from x_1 to the 12 located to the left of the 24. 1 . 4 4 4 . 6 12 12 6 12 6 . 4 12 12 12 24 12 4 12 12 4 . 1 4 4 6 12 6 4 12 12 4 1 4 6 4 1 Conveniently, with proper indentation, summing over these planes can again become summation over vertical lines; we can think about it as a linear skew applied to the grid, making the summation plane vertical: :::::::::::::::::::::::: 1 . :::::::::::::::::: 4 :::::::::::::::::: 4 4 . :::::::::::: 6 :::::::::::: 12 12 :::::::::::: 6 12 6 . :::::: 4 :::::: 12 12 :::::: 12 24 12 :::::: 4 12 12 4 . 1 4 4 6 12 6 4 12 12 4 1 4 6 4 1 ----------------------------------------- 1 4 10 20 31 40 44 40 31 20 10 4 1 which is the n=4 line in A008287. As another example, we can take the example slice from A191358 (in A191358 the notation is (s,r), but I'll stick to (k,n)); this slice is again for k=4 (same dimensionality) but now for n=5, so these are in fact also the next elements in A189225 (right after the previous example ended). I'm already displaying it here with the same indentation rules as above (same v_2, which is already vertical, and same v_3, which determines the relative indentation required between the 2D slices so that the summation planes will be vertical also between the triangles). :::::::::::::::::::::::::::::::::::::::: 1 :::::::::::::::::::::::::::::::: 5 :::::::::::::::::::::::::::::::: 5 5 :::::::::::::::::::::::: 10 :::::::::::::::::::::::: 20 20 :::::::::::::::::::::::: 10 20 10 :::::::::::::::: 10 :::::::::::::::: 30 30 :::::::::::::::: 30 60 30 :::::::::::::::: 10 30 30 10 :::::::: 5 :::::::: 20 20 :::::::: 30 60 30 :::::::: 20 60 60 20 :::::::: 5 20 30 20 5 1 5 5 10 20 10 10 30 30 10 5 20 30 20 5 1 5 10 10 5 1 ------------------------------------------------------------- 1 5 15 35 65 101 135 155 155 135 101 65 35 15 5 1 which are the next elements (line n=5) in A008287, and also the line T(4,5,h) in A273975. As a last example, we take a higher dimensional simplex: we take the n=4 slice from the 5D Pascal's simplex. To my knowledge, at the time of writing this explanation, there is no dedicated sequence for the 5D Pascal's simplex; however it is contained in the general k-dimensional simplex sequence A191358, where the slice of any constant n is denoted there as P(s=5,r=n), as part of the P(s,r) sequence. P(5,4) itself is a 4D simplex, and every 3D slice of it is layed out like the 3D tetrahedra above (with the 2D triangular layers below each other). The 3D slices appear next to each other horizontally. 1 4 4 4 4 6 12 12 12 6 12 6 12 12 6 4 12 12 12 12 24 12 24 24 12 4 12 12 4 12 24 12 12 12 4 1 4 4 4 6 12 6 12 12 6 4 12 12 4 12 24 12 12 12 4 1 4 6 4 1 4 12 12 4 6 12 6 4 4 1 The vertices x_0, x_1, x_2 will be as before the left, top and right vertices of the bottom-left triangle; x_3 as before is the top 1; and x_4 will be the bottom-right 1. The vectors v_2 and v_3 are be the same as before, and v_4 is the vector taking us from x_1 to the bottom-left corner of the second triangle (from the left) at the bottom row. This shows us how to align the 3D slices with respect to each other, so the summation will still be along vertical lines. Indentation aligning the 2D slices will be marked as before by ":", and indentation aligning the 3D slices will be marked by ";". Also, one example summation line (the one passing through the top vertex x_3) was marked by "|" marks to ease tracking of such lines. :::::::::::::::::::::::: 1 . :::::::::::::::::: 4 :::::::::::::::::: 4 4 | . :::::::::::: 6 | :::::::::::: 12 12 :::::::::::: 6 12 6 | . :::::: 4 | :::::: 12 12 :::::: 12 24 12 | :::::: 4 12 12 4 . | 1 4 4 | 6 12 6 4 12 12 4 | 1 4 6 4 1 | ;;;;;;;;;;;;:::::::::::::::::: 4 | ;;;;;;;;;;;;:::::::::::: 12 ;;;;;;;;;;;;:::::::::::: 12 12 ;;;;;;;;;;;;:::::: 12 | ;;;;;;;;;;;;:::::: 24 24 ;;;;;;;;;;;;:::::: 12 24 12 | ;;;;;;;;;;;; 4 | ;;;;;;;;;;;; 12 12 ;;;;;;;;;;;; 12 24 12 | ;;;;;;;;;;;; 4 12 12 4 | ;;;;;;;;;;;;;;;;;;;;;;;;:::::::::::: 6 ;;;;;;;;;;;;;;;;;;;;;;;;:::::: 12 ;;;;;;;;;;;;;;;;;;;;;;;;:::::: 12 12 | ;;;;;;;;;;;;;;;;;;;;;;;; 6 ;;;;;;;;;;;;;;;;;;;;;;;; 12 12 ;;;;;;;;;;;;;;;;;;;;;;;; 6 12 6 | ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;:::::: 4 | ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; 4 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; 4 4 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; 1 ------------------------------------------------------ 1 4 10 20 35 52 68 80 85 80 68 52 35 20 10 4 1 Which is the n=4 line of A035343, and the values of T(5,4,h) in A273975, appearing between positions 201 and 217.