jump to navigation

Counting Trees March 1, 2009

Posted by keithkchan in fun stuffs, Philosophy.

Today I tried to count the number of labelled trees. Let me make it clear what kind of trees I am interested in. Suppose there are are N points, and we want to connect these N points together using N-1 lines, which are called edges, only, so that there is a continuous path between any two points. Furthermore we have labelled the points with numbers. The question is that how many topologically different trees for N point. Actually, this problem arises in some tree level perturbative expansion, but that is not the point of the post.

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.

In fact I now remember that I learned this before in my undergraduate graph theory course. At that time I took it just for fun and thought that it would not be of any use in physics. This is the first theorem in graph theory that I find useful in physics, unfortunate I forgot about it. In fact I took quite a lot of math courses, such as group theory, differential geometry, in undergraduate, but I could not appreciate their importance to physics at that time, and were not well motivated. Another point is that the level of difficulty of the combinatorics problem may not be easy to estimate.



No comments yet — be the first.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: