| > Can anybody show an aesthetic mapping from n-gon dissections to triangle
> paths?
> -- edp
Here's a mapping from the triangle paths to the n-gon dissections.
Judge its aesthetic worth for yourself. Details are in the next reply.
-------------------------------------------------------------------------------
We are given a path through the Cartesian grid, from (0,0) to (n-2,n-2)
comprising unit steps *up* or *rightwards*. The path does not enter the region
y>x.
Define a *shaft* to be a line segment:
(i) parallel to the main diagonal of the grid
(ii) joining exactly two vertices on the path
(iii) never running *below* the path
For example: if n=5, then the following path from (0,0) to (3,3):
*
|
*
|
*-*-*
|
*-*
has the following shafts:
*
/| (0,0) -> (1,1)
/ * (1,1) -> (3,3)
/ /| (2,1) -> (3,2)
*-*-*
/|
*-*
Draw all the shafts. There are always n-2 of them. All we're
interested in are the y coordinates, so label the shafts by those. In the
above example, that gives us shafts labelled:
[0,1]
[1,3]
[1,2]
Arrange n > 1 vertices in a circle, and label them consecutively
0,1,...,n-1. Draw edges to connect these vertices, according to the following
recipe:
(i) Draw an edge from 0 to n-1.
(ii) For each shaft [a,b], draw an edge from a to b.
(iii) For each shaft [a,b], draw an edge from b to b', where [a',b'] is
the shaft immediately *above* [a,b]. (If [a,b] has no shaft above it, then
b' = n-1.)
And that's it!
Continuing with our example, we get the following edges:
(i) 0-4
(ii) 0-1 1-3 1-2
(iii) 1-4 3-4 2-3
yielding the following triangulated pentagon:
0-1-2
|/ \|
4---3
Try experimenting with the other four possible triangle paths, for
n = 5.
Regards,
Andrew.
|
| (1) How many triangle paths are there?
How many paths, f(m,n), are there from (0,0) to (m,n) which comprise
unit steps *up* or *rightwards*, and do not enter the "Forbidden Zone",
{(x,y)|x<y}? Answer:
(m+n) (m+n)
( ) - ( )
( m ) (m+1)
Why is this so? Call the two combinatorial terms above A & B
respectively. A is just the number of paths from (0,0) to (m,n), some of
which enter the Forbidden Zone (F.Z.). B is the number of paths from (-1,1)
to (m,n).
There is a 1-1 correspondence between:
(i) set of paths from (-1,1) to (m,n)
(ii) set of paths from (0,0) to (m,n) which enter the F.Z.
For each path, P, in set (i), determine the first point where it
enters the diagonal y=x+1. This point separates P into two subpaths Q & R.
Reflect Q in the diagonal y=x+1 to get Q'. Then Q' followed by R is a path
in set (ii). It's clear that this mapping gives us a 1-1 correspondence
between the two sets, which therefore have the same cardinality. Here's a
picture to show an example:
/
/ * The path runs from (0,0) to (3,3) via the F.Z.
/ | Point (1,2). Reflect the first component of the path in
@=@=o-*-* the diagonal line (which *doesn't* represent a shaft in this
" /| picture) and you get a path from (-1,0) to (3,3).
@ / *
/ | I find this construction pretty.
/ *-*
Hence, in any event, f(m,n) = A-B. In the case m=n, this gives the
same answer as edp's base note suggested:
f(m,m) = (2m)!/((m+1)!m!)
(2) How many n-gon triangulations are there?
Let g(n) denote the number of triangulations of an n-gon. [Note
that we are assuming that the vertices of the n-gon are labelled, say as
0,1,...,n. Rotating a triangulation thus *can* give rise to a different
triangulation.]
edp's base note gave a recursive expression for g(n) as
g(n) = (n/(2n-6)) * sum (i=3..n-1) g(i)*g(n-i+2).
This is based on selecting a random chord, C, of the n-gon, N. C
bisects N, and by counting the number of triangulations of each of the two
components of N, we know how many triangulations of N contain C.
Alternatively, consider removing from N the triangle, T, incident with
the edge 0-(n-1). N\T again contains two components, and hence we derive:
g(n) = sum (i=2..n-1) g(i)*g(n-i+1). (*)
The two recursions are not equivalent, and indeed by comparing them
we get immediately:
g(n) = ((4n-10)/(n-1)) * g(n-1).
Which together with the knowledge that g(2)=1 gives us:
g(n) = (2n-4)!/((n-1)!(n-2)!)
(3) So numerically we've proved that...
g(n) = f(n-2,n-2)
ie: the number of triangulations of an n-gon is just the same as
the number of suitable paths through the triangle with n-1 vertices on a side.
Now, can we map the one set to the other?
(4) Triangle path <-> n-gon triangulation
One feature of the T-recursion is there is no normalizing constant.
(Contrast the C-recursion, where the constant n/(2n-6) is required.) The
T-recursion thus permits a direct recursive construction of all the possible
n-gon triangulations.
First we can interpret i, the summation variable in equation (*)
above, in the context of the triangle paths problem. Given any path from
(0,0) to (n-2,n-2), it's easy to see that (i-1,i-1) is just the earliest
point after (0,0) that the path visits the line x=y again.
Thus each shaft, in the sense of the previous reply, corresponds to
one of the triangles of the n-gon. If you start dealing with the shafts from
the top left, and work downwards and to the right, you will find that each time
you consider a shaft, you draw in the n-gon two sides of a triangle, and that
the third side has already been drawn. The triangulation thus corresponds to
a binary tree.
The proof of the correctness of the algorithm is by recursion. Draw
the the edge 0-(n-1) on the n-gon. Consider the first time the path revisits
the line x=y, at P say. P defines a shaft, which defines a triangle. The
path is cut into two components by P, just as the triangle separates the n-gon
into two components. Consider each component separately. All you have to
do then is check that the labelling of the vertices is handled consistently.
Similarly, any n-gon triangulation gives a unique triangle path.
(5) Another nice equation, complementary to (*):
f(m,m) = sum(i=0...floor(m/2)) f(i,m-1)^2
Regards,
Andrew.
|