The vaxmaple program (a successor to Greg Kuperberg's dommaple program)
was written by Jim Propp and David Wilson, based on ideas by David Wilson.
vaxmaple outputs a matrix whose determinant is the number of domino
tilings of the input region, with certain constraints on allowed
placements. The matrix should be fed to Maple, via the command
vaxmaple < region | maple -q
The input format allows for computing the number of matchings of any
bipartite planar graph, although some will be easier to put into the
format than others.
The region to be tiled should be given as a pattern of V's, A's, X's,
<'s, and >'s. All characters after a percent are ignored. Currently,
the input must fit in a rectangle with 500 rows and 200 columns.
The five main symbols and their meanings are as follows:
X: A cell occupied by an X can be covered by a domino in any of the
four cardinal directions (rightward, leftward, upward, downward).
V: A cell occupied by a V can be covered by a domino any way but DOWN.
A: A cell occupied by an A can be covered by a domino any way but UP.
<: A cell occupied by a < can be covered by a domino any way but LEFT.
>: A cell occupied by a > can be covered by a domino any way but RIGHT.
(Note: A good mnemonic for these conventions comes from the fact that
if one has a region tiled by equilateral triangles
____
/\ /\
/__\/__\
\ /\ /
\/__\/
and one wishes to pair up the triangles to form a rhombus-tiling, the
triangles that look like V's are the ones that can pair (sort of) leftward,
(sort of) rightward, or upward. Etc.)
There can be holes in the array of non-blank characters, and in the new
version, these holes can be arbitrary. For instance, the graphs
o--o--o
| |
o o
| |
o--o--o
and
o--o--o--o
| |
o--o--o--o
and now both acceptable; the former can be represented as
XXX
X X
XXX
while the latter can be represented as
AVVA
VAAV
Note that in order to be matchable, two vertices must EACH be
compatible with the other; thus for example
V
X
has no perfect matchings.