Results 1 to 2 of 2
Like Tree1Thanks
  • 1 Post By romsek

Thread: Caley's formula

  1. #1
    Newbie
    Joined
    Nov 2017
    From
    UK
    Posts
    1

    Caley's formula

    Caley's formula-pic.png

    Hope someone can help with the above please? There are three non-isomorphic trees available on 5 vertices as shown in the graphic. The first tree in the picture can be labelled in 5 ways - which I can see using (n!/(k!(n-k)!)

    I am told the second and third can be labelled in 60 ways. Could someone explain how the figure of 60 is arrived at?

    Many Thnaks

    Blobfish
    Attached Thumbnails Attached Thumbnails Caley's formula-pic.png  
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    5,879
    Thanks
    2473

    Re: Caley's formula

    For #2

    $5 \text{ ways to select the level 0 vertice. Then }\dbinom{4}{3}\text{ ways to select the 3 level 1 vertices. Then }\dbinom{3}{1}\text{ ways to select which vertice takes the level 2 child.}$

    $5 \cdot 4 \cdot 3 = 60$

    For #3

    $5 \text{ ways to select the level 0 vertice. Then }\dbinom{4}{2}\text{ ways to select the 2 level 1 vertices. Then }\dbinom{2}{1}\text{ ways to arrange the level 2 children.}$

    $5 \cdot 6 \cdot 2 = 60$
    Thanks from Blobfish
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: Nov 14th 2012, 05:54 PM
  2. Replies: 4
    Last Post: Jul 15th 2011, 02:30 PM
  3. Replies: 8
    Last Post: Sep 5th 2010, 01:11 PM
  4. Replies: 1
    Last Post: Apr 26th 2010, 08:16 PM
  5. How to find matrix A power 5 using caley hamilton theorem?
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: Dec 3rd 2009, 07:38 AM

/mathhelpforum @mathhelpforum