GROVES AND THE CUBE RECURRENCE This is a preliminary write-up by Gabriel Carroll and David Speyer, with some editing and additional explanatory passages by Jim Propp; it is based on emails sent out by Gabriel and David, dated 5/5 through 5/12. 1. Overview The following memo is a summary of work done in May 2002. This work concerns multivariate rational functions f(i,j,k) given by the initial conditions f(i,j,k) = x(i,j,k) (for i+j+k = -1, 0, or 1) (where the x(i,j,k)'s are formal indeterminates) and by the recurrence relation f(i,j,k) = [f(i-1,j,k)f(i,j-1,k-1) + f(i,j-1,k)f(i-1,j,k-1) + f(i,j,k-1)f(i-1,j-1,k)] / f(i-1,j-1,k-1) (for i+j+k > 1). This is called the cube recurrence, since it gives an algebraic relation between the values taken by the function f(.,.,.) at eight lattice sites that form the vertices of a cube. (Motivation for the study of this recurrence comes from the analogous but simpler relation that is obtained when the cube is replaced by an octahedron; the resulting recurrence relation, called the discrete Hirota equation, arises in many combinatorial contexts, though frequently disguised.) It was shown by Fomin and Zelevinsky that the rational functions f(i,j,k) are actually Laurent polynomials in the variables x(i,j,k) (|i+j+k| < 2). Here we show (as conjectured by Propp) that all coefficients in these Laurent polynomials are equal to +1. We do this by establishing a bijection between the Laurent monomials that occur in f(i,j,k) and combinatorial objects that we call groves; specifically, the terms of f(i,j,k) correspond to the groves of order i+j+k. By replacing all the variables x(i,j,k) by 1, we can conclude that G(n), the number of groves of order n, satisfies the recurrence relation G(n) = 3 G(n-1) G(n-2) / G(n-3) , which (combined with the initial conditions G(-1) = G(0) = G(1) = 1) implies G(n) = 3^{floor(n^2/4)}. It is easily seen that for any pair of triples (i,j,k), (i',j',k') with i+j+k = i'+j'+k', the rational function f(i',j',k') can be obtained from the rational function f(i,j,k) by a simple substitution in which each variable x(r,s,t) gets replaced by the variable x(r+i'-i,s+j'-j,t+k'-k), so without loss of generality, we will focus henceforth on the case f(n,0,0). We intend to defer writing a completely formal treatment until we have at least a picture of how the same recurrence works with general initial conditions (e.g., slabs of the form 0 <= pi+qj+rk < p+q+r for positive constants p, q, r). In the meantime, if anyone finds mistakes or unclear statements in the following proofs, please inform Gabriel (FAS username: gcarroll). 2. Defining groves Groves of order n are defined as follows: Begin with a triangular lattice with n+1 vertices on a side, and label the boundary vertices so that two vertices receive the same label iff they are exchanged by a reflection through a median of the triangle passing through the vertex of the triangle closest to either of them: a / \ b---b / \ / \ c---*---e / \ / \ / \ d---c---e---f When n is even, the central vertices of the three sides all receive the same label: a / \ b---b / \ / \ c---*---c / \ / \ / \ d---*---*---e / \ / \ / \ / \ f---d---c---e---g Groves are forests contained in this graph such that each tree contains precisely the lettered vertices of one letter, and every tree contains at least one lettered vertex. For example, a b---b c---* c \ / d---* * e \ / / f d c e g is a grove of order 4. (This example shows that lettered vertices need not be leaves, and that leaves need not be lettered vertices.) The number of distinct letters used is (3n+2)/2 when n is even and (3n+3)/2 when n is odd. Hence the number of trees in a grove of order n (including three trivial trees with no edges, whose sole respective vertices are the three corner vertices) is floor((3n+3)/2). Fix some grove of order n. If we take the number of vertices in each tree, and sum over all the trees, we get the total number of vertices, which is (n+1)(n+2)/2. If we take the number of edges in each tree, and sum over all the trees, on the one hand we get (n+1)(n+2)/2 - floor((3n+3)/2) (because each tree now contributes 1 less to the sum, and the number of trees is floor((3n+3)/2)), and on the other hand we get the number of edges in the grove. Hence the number of edges in a grove of order n is (n^2+3n+2)/2 - floor((3n+3)/2) = ceiling((n^2-1)/2) = floor(n^2/2). 3. From groves to Laurent monomials Groves can be identified with Laurent monomials in the variables x(i,j,k) as follows. To get the exponents of the variables x(i,j,k) with i+j+k=0, draw them in the trangular grid in the natural way. (0, 0, 0) (1,-1, 0)---(1, 0,-1) (2,-2, 0)---(2,-1,-1) (2, 0,-2) \ / \ / \ / (3,-3, 0)---(3,-2,-1) (3,-1,-2) (3, 0,-3) \ / / \ / / \ / / (4,-4, 0) (4,-3,-1) (4,-2,-2) (4,-1,-3) (4, 0,-4) For the nonlettered vertices, the exponent is (# of incident edges)-2, which in general can be anything between 1-2 = -1 and 6-2 = 4. For the lettered vertices other than the three corners (that is, for b, c, d and e), the exponent is (# of incident edges)-1, which is always either 1-1 = 0 or 2-1 = 1. For the corners (that is, for a, f and g), the exponent can be written as (# of incident edges)-0 but is always just 0. Thus, we get the exponents 0 0 ----- 0 0 ----- 0 0 \ / \ / \ / 1 ----- -1 1 0 \ / / \ / / \ / / 0 0 0 0 0 So the contribution from the x(i,j,k)'s with i+j+k=0 is 1 -1 1 x(3,-3, 0) x(3,-2,-1) x(3,-1,-2) . Now, we have to get the exponents of the f(i,j,k) with i+j+k=+/- 1. These we write in the faces of the triangular grid. There is no way we can do ASCII art large enough to show this really well, but we'll draw the two types of triangles that occur and the labels they receive. (i-1,j,k) (i,j,k+1)------(i,j+1,k) / \ \ / / \ \ (i,j,k) / / \ \ / / (i,j,k) \ \ / / \ \ / (i,j-1,k)------(i,j,k-1) (i+1,j,k) (Note that the coordinate-triple assigned to an upward-pointing triangle is the componentwise maximum of the coordinate-triples assigned to the three vertices of the triangle; likewise, the coordinate-triple assigned to a downward-pointing triangle is the componentwise minimum of the coordinate-triples assigned to the three vertices. In both cases, the x-coordinate of the center of a triangle is equal to the x-coordinates of two of its three vertices, and likewise for the y- and z-coordinates.) The exponent of a triangle is 1-(# of adjacent edges used) (even if it is on the boundary). Thus, our example gives rise to the exponent-array * 0 *-----* 0 0 1 *-----* * 0 \-1 / 0 0 \ / 0 *-----* * * \-1 0 / 0 / 0 \ 1 / 0 / 0 * * * * * yielding a contribution of 1 -1 -1 x(2,0,-1) x(2,-1,-2) x(3,-3,-1) x(4,-2,-1) from these variables. Putting it all together, we can associate with the grove the array 0 0 0 0 0 0 1 0 0 0 0 -1 0 0 0 1 -1 1 0 -1 0 0 0 1 0 0 0 0 0 0 0 and represent this array by the monomial 1 -1 1 x(3,-3, 0) x(3,-2,-1) x(3,-1,-2) times 1 -1 -1 x(2,0,-1) x(2,-1,-2) x(3,-3,-1) x(4,-2,-1) which, sure enough, occurs in f(4,0,0). We will show that the grove can be reconstructed from its monomial, and that each cube-recurrence Laurent polynomial f(i,j,k) is the sum of all monomials corresponding to groves of order i+j+k. 4. From Laurent monomials to groves To convert back from a monomial to a grove, write the exponents of the monomial inside the "star of David" graph, shown below. This graph is the mediant graph of the triangular lattice in which our groves embed (modulo some extra vertices on the boundary); its vertices correspond to edges of groves, its hexagonal faces correspond to vertices of groves, and its triangular faces correspond to triangles in the grove lattice. We illustrate the conversion with our previous example, here using "-" to signify -1, "+" to signify +1, and " " to signify 0. *---* / \ * * \ / *---*---*---* / \ / \ * * * \ / \ / *---*---*---*---*---* / \ / \+/ \ * * * * \ / \ /-\ / *---*---*---*---*---*---*---* / \ / \ / \ / \ * + * - * + * * \ /-\ / \ / \ / *---*---*---*---*---*---*---*---*---* / \ / \+/ \ / \ / \ * * * * * * \ / \ / \ / \ / \ / *---* *---*---*---*---*---* *---* For any vertex of the star of David graph, draw the four rays extending from it, as shown in the two pictures below. The sums of the numbers in the four wedges will either be 1, -1, 1 and 0 in cyclic order (as in the first picture) or 0, 0, 0 and 1 (as in the second picture). In the former case we draw the edge corresponding to this vertex; in the latter case we do not. * * * * \ * * * * \ * * * \ * * * * * * \1 * * * * -1\ *---*---*---*---*---*---*---* \ * 1 * -1 * 1 * * -1 \ * * * * * * * * * * 1 \ * * * * * * \ * * * * * * * * * * * * * * * * * * * * * \ * * * * * * \ 1 * * * * \ -1 *---*---*---*---*---*---*---* \ * 1 * -1 * 1 * * -1 \ * * * * * * * * * * 1 \ * * * * * * \ * * * * * * * * * * 5. Shuffling groves Shuffling is an operation that turns order-n groves into order-(n+1) groves. The basic idea is that we turn upward-pointing triangles in an order-n grove into downward-pointing triangles in an order-(n+1) grove. To see how this happens, let's first superimpose the vertex grids of the two groves: + * + + * * + + + * * * + + + + * * * * + + + + + * * * * * + + + + + + Here the *'s are vertices of the smaller grid, and the +'s are vertices of the larger grid. We can see that the upward-pointing triangles of *'s are concentric with the downward-pointing triangles of +'s. Now suppose we have a grove on the * grid. For ASCIIgraphic purposes, we will mark edges according to the grid they come from; hopefully this won't be confusing. + * + + ********* + + + * * * * * * + * + * + * + * * * * ********* * * * * + * + * + + * + * * * * * * * * + + + + + + The algorithm is as follows: First we mark each up-pointing * triangle with 0, 1, or 2, according to the number of edges it has. + * + 1 + ********* + 0 + 0 + * * * * * * + 1 * + 2 * + * 1 + * * * * ********* * * * * + 1 * + 1 * + 0 + * 1 + * * * * * * * * + + + + + + Next we "switch" the up-pointing * triangles: If an up * triangle has 2 edges, remove both of them; if it has 1 edge, leave it alone; if it has 0 edges, add two edges arbitrarily. + * + 1 + ********* * * + 0 * + 0 * + * * ***************** * * + 1 * + 2 + * 1 + * * * * * * * * * * + 1 * + 1 * + * 0 + * 1 + * * * * * * ********* * + + + + + + Finally, we "shift" every horizontal edge up, shift every \-shaped edge down and left, and shift every /-shaped edge down and right. Thus, each edge of an up * triangle is turned into a parallel edge of the corresponding down + triangle. If the following drawing is unclear, the reader is encouraged to work through the example on paper. + * +++++++++ * * +++++++++++++++++ + + * + * + * + + + + + + + + * + * * + * + + + + +++++++++ + + + + + * + * + * + * + * + + + + + + + + + + We obtain in this fashion a grove of order n+1. Note that this is not a bijection, and indeed not even a function; a grove of order n can be shuffled into any of 3^m different groves of order n+1, where m is the number of up * triangles with no edges present in the grove. A different way to conceptualize the shuffling procedure is to swap the two steps, so that shifting occurs first and switching occurs after (this time using down + triangles instead of up * triangles). The order of the two steps does not matter, since each star of David is completely self-contained in both of the two steps and has no interaction with other stars of David. It is also possible to apply shuffling in reverse, starting from a grove of order n+1 and producing from it a (usually non-unique) grove of order n, either by doing a shift followed by a switch on the up * triangles, or by doing a switch on the down + triangles followed by a shift. One need not worry about situations like + + + \ + + + + + + + + + + + + + + + + + + (in which an edge does not belong to a star of David in the superimposed graph) because the rules governing groves do not permit such edges in the first place. 6. Why shuffling works The claim is if we appy shuffling to a grove of order n (on the * grid), we obtain a grove of order n+1 (on the + grid). In proving this, we will also study the relationship between the monomial associated with the two groves, since this will play a role in later sections. If an initial * (upward) triangle has one edge, the corresponding + triangle will have one edge, in the same orientation, produced by shifting the given * edge. If our * triangle has two edges, the corresponding + triangle will have no edges. If our * triangle has no edges, the corresponding + triangle will have two edges (randomly assigned). Translating this into exponent terms, this tells us that each up-triangle exponents in the * graph is the negative of the corresponding down-triangle exponent in the + graph, since a triangle's exponent is 1 minus (# of edges used). This actually has two important consequences: (a) The * edges and + edges _never intersect_. In fact, from looking at the graphs, we can see that any possible intersection would have to involve a * edge and a + edge on corresponding triangles. The nature of the shuffling algorithm guarantees that this won't happen: for any two corresponding triangles, either the * triangle has two edges and the + triangle has none, or vice versa, or each triangle has one edge; but in the last case, the two edges used are parallel and so don't intersect. Here for instance is what we get when we superimpose the pre-shuffle and post-shuffle edges from our example: + * +++++++++ ********* +++++++++++++++++ + + * + * + * * + * + * + * + * + * + + * * * + * + ********* + * * + * + * + * + * +++++++++ * + + * + * + * + * + * + * + * + * + + + + + + + + + + (b) The total number of + edges used is forced. The number of edges in the grove of order n can be written as 0a+1b+2c, where a, b, c denote the number of up * triangles with 0, 1, or 2 edges present, respectively. Then the number of + edges present after shuffling must be 2a+1b+0c. But 2a+1b+0c = 2(a+b+c) - (0a+1b+2c), where a+b+c (the total number of up * triangles) is forced, and 0a+1b+2c (the total number of edges in the * grove) is forced. Indeed, we have a+b+c = n(n+1)/2 and 0a+1b+2c = floor(n^2/2), so 2a+1b+0c = 2n(n+1)/2 - floor(n^2/2) = ceiling(2n(n+1)/2 - n^2/2) = ceiling((n^2+2n)/2) = floor((n^2+2n+1)/2) = floor((n+1)^2/2), which is the number of edges in a grove of order n+1. The number of trees in a forest equals the number of vertices minus the number of edges, so if we can show that the + graph is acyclic (i.e., a forest), then the fact that it has the correct number of trees will follow directly from the fact that it has the correct number of vertices and the correct number of edges. However, observation (a) shows that the + graph is acyclic. Indeed, we can check that any possible cycle (except for the trivial cycle made of a single downward-pointing triangle, which can never occur) would have to contain at least one * vertex in its interior. Because + edges never cross * edges, the + cycle would then contain an entire * component. But each * component touches two of the three boundary-components of the * grid, so the + cycle cannot contain such a component without using boundary edges of the + grid. Since our algorithm never uses these boundary edges, acyclicity follows. The number of + components then follows as well. Now for the coup de grace: Let's draw rays coming out of the boundary vertices of the * grid. *** + *** *** *** *** *** *** *** + + *** *** *** ** ** *** *** *** + + + *** *** *** ** * ** *** + + + + *** *** *** ** * * ** + + + + + *** *** ** * * * ** * * * * * + * + * + * + * + * + * * * * * * * * * * * * * * * When we insert the * grove graph, the plane is divided into "sectors" by virtue of the way that the boundary * vertices are connected by the trees. *** + *** *** *** *** *** *** *** + + *** *** *** *********** *** *** *** + + + *** *** *** ** * ** * * * *** + * + * + * + *** *** * * * *** ** ********* ** * * * + * + * + + * + *** * * * *** ** * * * ** * * * * * + * + * + * + * + * + * * * * * * * * * * * * * * * By lemma (a) and the fact that the + boundary edges are never used, we conclude that each + component is contained inside one sector. However, it is not hard to check that we have floor((3n+6)/2) sectors - exactly the number of components of the + graph. Therefore, each sector contains precisely the vertices of one component of the + graph. It is now a straightforward induction to show that the boundary vertices are matched up in the desired manner: if the order-n grove has the property that two boundary vertices are in the same tree iff they have the same label, then it follows that two boundary vertices of the order-(n+1) grid lie in the same sector iff they have the same label, and we just saw that being in the same sector is equivalent to being in the same + tree. (The induction step actually has two cases, depending on the parity of n, but both are straightforward). At this point, we've shown that the + graph is acyclic, that it has the correct number of components, and that the boundary vertices are properly matched - in other words, it is a grove. Reverse shuffling works much the same way. So we can conclude that every order-n grove shuffles into order-(n+1) groves and, conversely, every order-(n+1) grove is obtained by a shuffle from order-n groves. In other words, the set of objects produced by the shuffling algorithm is the same as the set of groves, for any given order. 7. Extension to the plane Given any grove of order n, we can extend it to a forest on the entire plane by adding some edges. Here we have the edges to be added: * * * * * *---*---*---* \ \ \ \ \ * * * * *---*---*---*---* \ \ \ \ * * * * *---*---*---*---* \ \ \ \ * * * * *---*---*---*---* \ \ \ * * * * * *---*---*---* \ \ \ * * * * * *---*---*---* \ \ * * * * * * *---*---* \ \ * * * * * * *---*---* / / / / / / / * * * * * * * *---* / / / / / / / * * * * * * * *---* / / / / / / / / * * * * * * * * * Of course, this pattern continues outward to infinity. In case it's not clear from the picture, the procedure is simply to extend each side of the triangle to a ray in one direction, thus dividing the exterior of the triangle into three regions, and then to fill each region with edges that are all of the same orientation. The central triangle is where you fill in the edges of your grove (in the example above, of order 5). It's straightforward to check that we can now set the exponent of any triangle to be 1 - (# of surrounding edges) and the exponent of any * to be (# of edges) - 2. We get the same values as before for all the exponents (and those that lie outside the triangle are all zero). It's also straightforward to check that if we shuffle an extended order-n grove, the result is an extended order-(n+1) grove. This extension will make subsequent computations a bit easier, since we don't have to worry about special stuff happening on the boundary. It's analogous to a procedure used in EKLP: to shuffle a domino tiling of the Aztec diamond, we first extend the tiling to the entire plane by using horizontals. 8. Shuffling and monomials So now let's show how shuffling groves is equivalent to a change of variables in the grove-counting polynomials. From here on we will assume that groves are extended to the whole plane as described in the previous section, so we don't need to worry about boundaries, and we're still assured that only finitely many exponents are nonzero for any given grove. To keep the initial conditions typographically distinct in a helpful way, we'll write the initial conditions as x(i,j,k) for i + j + k = 1 (the up-pointing triangles) y(i,j,k) for i + j + k = 0 (the vertices of the grove) z(i,j,k) for i + j + k = -1 (the down-pointing triangles) So we denote the grove-counting polynomial at (I,J,K), which is a Laurent polynomial in infinitely many variables (although only finitely many of them actually appear), as f(I,J,K) = P_I,J,K ({x(i,j,k)},{y(i,j,k)},{z(i,j,k)}) Notice that lowercase letters index all the formal variables, and uppercase letters index the particular polynomial in question. We want to show that f(I+1,J,K) = P_I,J,K ( { ( x(i,j,k)y(i+1,j-1,k-1) + x(i+1,j-1,k)y(i,j,k-1) + x(i+1,j,k-1)y(i,j-1,k) ) / z(i,j-1,k-1) }, {x(i+1,j,k)}, {y(i+1,j,k)} ). Because the cube-recurrence polynomials satisfy this same recurrence (you get this by treating the planes i+j+k = 0, 1, 2 as your initial conditions instead of -1, 0, 1), and it's straightforward to check that they agree for the initial cases, this will prove that the cube-recurrence polynomials and the grove-counting polynomials coincide. So let's look at the process of shuffling groves. Recall that it operates as follows: - First "switch" the up triangles: if an up triangle has two edges, remove them; if it has no edges, add two arbitrarily. - Then, "shift" every edge of every up triangle to the parallel edge of the corresponding down triangle, e.g. * * + \ + + + \ --> \ * * * \ * + + (*'s are the vertices of the order-n grove, and +'s are the vertices of the order-(n+1) grove, as before.) Let's see what each of these steps does to the grove polynomial. In the process, we'll work through an example. Pretend that the following groves have been extended to the entire plane as described in the previous section. * 0 0 *-----* 0 0 0 1 0 * *-----* 0 -1 1 \ / 0 -1 \ / 0 1 0 * * * * 0 0 0 0 Switching can produce the following (or any of eight other possibilities): * 0 0 0 0 *-----* 1 0 / -1 0 0 / -1 0 *-----*-----* 2 1 1 \ \ / 0 -1 -2 0 \ \ / 0 -1 0 * *-----* * 0 1 2 0 0 -1 0 Notice that we are using the same rules as before to turn a graph into a monomial, even though the graph is not a grove at this stage. Also notice that we may temporarily have a nonzero exponent outside of our triangular grid, but since we're actually working with infinite grids, this isn't a problem. (The -1's outside the triangle come in part from the edges of the extension, which are not shown here.) When we do the shift, we get: + 0 0 +-----+ 0 0 0 0 0 +-----+-----+ 0 1 0 / -1 0 / 1 -1 1 + +-----+ + 0 1 -1 0 \ \ / 0 -1 0 \ \ / 0 0 1 0 + + + + + 0 0 0 0 0 It should be noted that there is a somewhat arbitrary choice in the correspondence between the vertices of the order-n grid and those of the order-(n+1) grid; we have effectively made this choice by choosing to compare P_I,J,K with P_I+1,J,K (as opposed to, say, P_I,J+1,K). How do we express the new exponents in terms of the old ones? First, let's deal with the switching step. If an up triangle has exponent 1 (no edges), we can replace it by any of the following three configurations: * * * / / \ \ / / \ \ *-----* * * *-----* These correspond to changing the 1 to a -1 and performing the following net changes on the six neighboring exponents: 1 2 1 -1 / 0 -1 / \-1 0 \-1 / / \ \ 2-----1 1 1 1-----2 -1 0 -1 It can be checked in the example above that the switched order-3 grove monomial is obtained from the original by two operations of this sort. So if a monomial in P_I,J,K has a variable x(i,j,k) with exponent 1, it gets effectively replaced by the trinomial B(i,j,k) = y(i-1,j,k)^2 y(i,j-1,k) y(i,j,k-1) / z(i-1,j-1,k) z(i-1,j,k-1) x(i,j,k) + y(i-1,j,k) y(i,j-1,k)^2 y(i,j,k-1) / z(i-1,j-1,k) z(i,j-1,k-1) x(i,j,k) + y(i-1,j,k) y(i,j-1,k) y(i,j,k-1)^2 / z(i,j-1,k-1) z(i-1,j,k-1) x(i,j,k). We claim that the same substitution describes the effect of a switch on up triangles with exponent -1. Indeed, if a up triangle has exponent -1 in P_I,J,K, then we have one of the three two-edge configurations above. We claim that the monomials obtained by replacing this configuration with either of the other two also occur in P_I,J,K. To see this, notice that the claim is equivalent to the assertion if an up triangle has two edges used, we may replace them by either other pair of edges and still obtain a valid grove. But this is easy to see. Therefore, the polynomial consisting of those monomials in P_I,J,K where x(i,j,k) has exponent -1 is actually divisible (in the Laurent polynomial ring) by the same trinomial B(i,j,k) as above. Moreover, we can write B(i,j,k) = C(i,j,k)/x(i,j,k), where C(i,j,k) is a trinomial independent of the variable x(i,j,k). In particular, the substitution x(i,j,k) <- B(i,j,k) is an involution, so applying the switch move to a triangle of exponent -1 (which should entail dividing by B(i,j,k) and multiplying by x(i,j,k)) is represented by this substitution. Finally, if an up-triangle has exponent 0 (one edge used), it will not be affected by the substitution, which is exactly what we want from the switching step. Thus, if we let Q_I,J,K({x(i,j,k)},{y(i,j,k)},{z(i,j,k)}) denote the polynomial which counts switched (but not yet shifted) groves, we have shown that Q_I,J,K is equal to P_I,J,K({B(i,j,k)},{y(i,j,k)},{z(i,j,k)}). Now let's deal with the shifting step. The new down triangles have the same exponents as the corresponding up triangles. For the + vertices we have the following picture: * a f + + a f f a * * f a b e ----> +ccccc+ddddd+ b e b e *ccccc*ddddd* b e + + where each distinct lowercase letter denotes an edge that may be present or absent. If we denote the exponents in the picture on the left (order n) by uppercase letters as follows: * A * * X B C * * * then the number of edges used from {a,b,c,d,e,f} is (1-A) + (1-B) + (1-C) - (1-X) = X - (A+B+C) + 2. Therefore, the exponent of the central * (in order n+1) is X-(A+B+C). For the up triangles, we have the following picture: * * a c + a c a c * * * ----> a c +bbbbb+ *bbbbb* If we again label the three up triangles' and the central vertex's exponents by uppercase letters: * * A C * X * B * * then the number of edges used from among {a,b,c} is (1-A)+(1-B)+(1-C)-(X+2) = 1-(A+B+C+X). Therefore, the exponent of the resulting up triangle (in order n+1) is A+B+C+X. Now, for each exponent in the order-n picture, let's see which order-(n+1) exponents it contributes to. If an old up triangle had exponent X, then it contributes X to the corresponding new down triangle exponent and the three neighboring up triangle exponents, and -X to the three neighboring vertices (in the order-(n+1) picture). The other order-n exponents contribute only to the corresponding order-(n+1) exponents. That is, a down triangle of exponent X in order n contributes X to the exponent of the corresponding vertex in order n+1 (and it doesn't contribute to any other exponents), and a vertex of exponent X in order n contributes X to the exponent of the corresponding up triangle in order n+1 (and it doesn't contribute to anything else). All of this can be verified in the example shown above - if we take each nonzero exponent in the post-switch order-3 grove, record its contributions to the nearby exponents in the order-4 graph according to the rules just stated, and add, we do get the same values that were observed above. Let's write these rules down algebraically. After performing the shift move on the already-switched order-n groves, we get the order-(n+1) groves, which are counted by P_I+1,J,K. Therefore, P_I+1,J,K ({x(i,j,k)},{y(i,j,k)},{z(i,j,k)}) = Q_I,J,K ({ z(i,j-1,k-1)x(i,j,k)x(i+1,j-1,k)x(i+1,j,k-1) / y(i+1,j-1,k-1)y(i,j-1,k)y(i,j,k-1) }, { x(i+1,j,k) }, { y(i+1,j,k) } ) = P_I,J,K ({ ( x(i,j,k)y(i+1,j-1,k-1) + x(i+1,j-1,k)y(i,j,k-1) + x(i+1,j,k-1)y(i,j-1,k) ) / z(i,j-1,k-1) }, {x(i+1,j,k)}, {y(i+1,j,k)} ) where the second equality comes from our earlier expression for Q_I,J,K. And we're done.