Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

So I am given $n$ points in the plane and I want to create a planar graph such that every face is bounded by $3$ edges (even the "outside" face). Hence if I have say $4$ vertices, then there is a unique way to triangulize it, make all edges adjacent to each other.

Let $L_n$ denote the number of triangulations on $n$ points. I was thinking a way to count $L_n$. To go from $L_4$ to $L_5$ we have an extra vertice that is placed in one of the faces, then in order to triangulize it we can match that point with the vertices of the triangule that points lives in. Since there are $4$ ways of picking which face to place the new vertex we have $L_5=4$. Note that the number of faces goes up by $2$ since we are destroying one face and adding $3$ new ones. Hence $L_6=6L_5$, and in general I would have that $L_n=2^{n-4}(n-3)!$.

I was wondering what is wrong with the above argument since my homework says "Prove $\lim \log L_n$ as $n\rightarrow \infty$ exists" (Since this is homework please only give me hints towards the correct solution, thanks)

share|improve this question
1  
For the limit of $\log L_n$ to exist, the limit of $L_n$ would have to exist. If you can prove that the number of triangulations is unbounded, you have busted the problem. Or copied it down wrong. –  Gerry Myerson Oct 15 '12 at 4:30
2  
Since one would typically expect this sort of thing to grow exponentially and the growth rate can be defined via $\lim_{n\to\infty}\frac1n\log L_n$, it seems likely that a factor $\frac1n$ went missing. Regardless of that, I think you're overcounting because you can reach the same result by adding points in different orders. –  joriki Oct 15 '12 at 5:17
    
Yes, Daniel, I am pretty sure this was a typo as joriki says. Compare your count with oeis.org/A000256 –  Igor Pak Oct 15 '12 at 7:25
    
@IgorPak Yes, the above count is bad, but I still dont quite know exactly what we are counting. For instance say we are given $5$ points $A,B,C,D,E$ in the plane. Then a triangulation must have score $(4,4,4,3,3)$ so as long as we specify which vertices are the ones with degree $3$ then we are done, so the count ought to be $\binom{5}{2}=10$, which does not appear on the oeis that you linked. –  Daniel Montealegre Oct 16 '12 at 4:37
    
In fact it says that the number of triangulations of the plane with $n=5$ is zero, so I am sort of confused. –  Daniel Montealegre Oct 16 '12 at 4:48
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.