Results 1 to 2 of 2

Math Help - proof of cayley's theorem; graph theory

  1. #1
    Senior Member abhishekkgp's Avatar
    Joined
    Jan 2011
    From
    India
    Posts
    495
    Thanks
    1

    proof of cayley's theorem; graph theory

    Consider the recursion:
    f(n)=\sum_{k=1}^{n-1} (-1)^{k+1} {n \choose k} (n-k)^k f(n-k)
    Where n \geq 3, f(1)=f(2)=1.

    I got this recursion when i tried to prove the cayley's theorem which says that there are n^{n-2} distinct labelled trees on n vertices.
    I have checked that f(n)=n^{n-2} satisfies the equation for n=3,4,5,6. Any idea how to prove that the solution to this recursion is f(n)=n^{n-2}.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member Traveller's Avatar
    Joined
    Sep 2010
    Posts
    162

    Re: proof of cayley's theorem; graph theory

    I don't have a solution but could you please explain how you got that recursion?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. a theorem in graph theory.. please help
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: May 8th 2011, 11:22 AM
  2. Replies: 1
    Last Post: September 26th 2010, 10:53 AM
  3. graph theory proof
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: May 20th 2010, 03:27 AM
  4. graph theory proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 12th 2010, 12:00 AM
  5. Graph Theory [Menger's Theorem]
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 27th 2008, 02:29 PM

Search Tags


/mathhelpforum @mathhelpforum