Results 1 to 2 of 2

Math Help - [SOLVED] Graph Theory and Labeled Trees

  1. #1
    Junior Member
    Joined
    Oct 2009
    Posts
    26

    [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!!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Oct 2009
    Posts
    26
    never mind, figured it out
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: March 2nd 2011, 05:39 AM
  2. Graph Theory - Trees and Paths
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 9th 2010, 11:14 PM
  3. Graph Theory question about trees
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 27th 2009, 02:52 AM
  4. Graph theory: Trees
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 3rd 2009, 12:30 PM
  5. [SOLVED] Graph Theory - Trees
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 8th 2007, 12:29 AM

Search Tags


/mathhelpforum @mathhelpforum