Wednesday, August 28, 2013

Triplets of Dyck words code the physical configurations completely folded surfaces

In phantom configurations of a completely folded surface, the triangles and hinges can intersect and coincide. In semi-physical configurations of a completely folded surface, triangles do not coincide (they have a physical, stacked order,) but hinges may cross through each other. In physical configurations of a completely folded surface, triangles do not coincide and hinges do not cross. Since a surface in a physical configuration has no self-intersection, such can never be a non-orientable surface without boundary.

A completely folded surface in either a physical or semi-physical configuration has a stack of triangles—and consequently three stacks of edges—hinged together in a particular way. We assume in the following that the surface has no boundary: therefore every triangle edge is connected to one other triangle edge in the same edge stack by a hinge.

If hinges are permitted to cross each other (the semi-physical condition), then the hinge connections in a given edge stack are a perfect matching of those edges.

If hinges are not permitted to cross (the physical condition), then our boundary-less surface must be orientable, and the hinge connections in a given edge stack are a non-crossing partition of those edges. A natural way to code a non-crossing partition is as a parenthesis word, or Dyck word. When written out as a Dyck word, it is easy to imagine the non-crossing arrangement of the hinges in the edge stack by simply connecting the paired parentheses with arcs above the Dyck word, e.g.:

( ) ( ) ( ( ) ).

Since there are three edge stacks, a triplet of Dyck words of the same length can encode a completely folded physical configuration.

The number of Dyck words of length 2n are counted by the nth Catalan number:

1, 1, 2, 5, 14, 42, 132, 429, 1430, ....

and triplets of Dyck words are counted by the cube of the nth Catalan number:

1, 1, 8, 125, 2744, 74088, 2299968, 78953589, 2924207000, ....

For triangle-faced maps that are, as usual, without boundary, but possibly composed of multiple disjoint components, the same daunting integer sequence counts their completely folded configurations when 2n is the number of triangles in the stack. In using the cube of Catalan numbers we are counting as different every possible difference in the completely folded configuration: e.g., simply rotating the stack, flipping it over, enantiomorph-ing the surface or the folded configuration, etc. More significantly, since the map is permitted to have multiple disjoint components, we also count every possible way the multiple components can be arranged in the stack, including the different ways they can enclose each other.

Though it is appealing to think that we can now dial up the phone number of any completely folded configuration that will ever be designed, the combinatorial explosion frustrates "cold-calling" as a technique to discover new designs. Nonetheless, dialing from even the shortest phonebook puts us in touch with shapes that we humans have largely avoided thinking about. A phonebook with n<=2 has 1 + 1 + 8 = 10 entries in it. The configurations that pick up the phone are the empty set; the triangular pillow; a stack of two triangular pillows; a triangular pillow enclosing another triangular pillow; two triangular "ears" that have seamed along a double edge and folded along the seam—in three rotations; and the same "double ear" with one ear tucked inside the other—also in three rotations. 

No comments: