[SOLVED] Graph Theory and Labeled Trees
A saturated hydrocarbon is a connected graph where each vertex has degree 1 (“hydrogen atom”) or degree 4 (“carbon atom”) and the number of hydrogen
atoms is two more than twice the number of carbon atoms. Prove the following statement:
The number of labeled saturated hydrocarbons with k carbon atoms is:
(3k+2 choose k)((3k)!/(3!)^k)
Alright this is what I got so far:
if we are assuming there are k carbon atoms, that means that there are (2k+2) hydrogen atoms, totaling 3k+2 atoms.
so the (3k+2 choose k) is just out of all the atoms we are choosing k of them to be carbon atoms. Then I really don't understand where the (3k)!/(3!)^k comes from. I know that there is a theorem stating:
Let T be a labeled tree of order n >= 2. Then there exists a code (a1, . . . , an−2) of vertices such that each vertex v appears in the sequence deg(v) − 1 times and two different labeled trees of order n have different codes.
wouldn't that mean that k appears 3 times? I don't know, I'm lost, any help would be great!!