Problem2B

Problem2B: How many trees {T} are there on the set of vertices {\left\{ 1,2,3,4,5,6,7\right\} } in which the vertices {2 } and {3} have degree {3}, vertex {5} has degree {2}, and hence all others have degree {1}? Do not just draw pictures but consider the possible Prufer codes of these trees.

Solution: There is a one-to-one correspondence from the labeled trees on {n} vertices and the {(n-2)}-dimensional vectors over {\{1,\ldots ,n\}}. It is called Prufer code. The number of times that a vertex {k} appears in the Prufer code, is the degree of vertex {k} in the labeled tree minus one. So vertices {2} and {3} will appear twice, and vertex {5} appears once in the code. There are {\left( \begin{array}{c} 5 \\ 2 \end{array} \right) \left( \begin{array}{c} 3 \\ 2 \end{array} \right) =30} such codes, so that there are {30} labeled trees of this type.

Note: It is not easy to obtain a one-to-one mapping from the objects we study to some other objects easier to study. If there is sth. like this, it will be a big step up with great pleasure. Well, usually, we try building up some mappings for easier research, analyze the properties of the images, and check how much information and how it is revealed from the images. Some other examples?

 

Advertisements

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: