## Counting Trees March 1, 2009

Posted by keithkchan in fun stuffs, Philosophy.
Let me illustrate it using some examples. For N=2, there is only 1 topologically distinct configuration. For N=3, there are 3. For N=4, there are 16. Obviously it increases rapidly wiht N, for N=5, I did not even try. The claim is that there are $N^{N-2}$ for N points. I tried to show this formula. I thought it would not be very difficult, but after thinking for 1 hour, I still had no clue, and decided to give up. I later found that this is the Cayley’s theorem in graph theory. In one of the proof one maps the problem to something easier to count by means of the Prufer sequence. Any theorem has a name is unlikely to be very easy to prove, so I don’t bother to describe it here, interested reader can read this note.