How many trees are there on vertex set $[n]$ that contain a given edge $uv$? [duplicate]












1















This question already has an answer here:




  • How many different spanning trees of $K_n setminus e$ are there?

    3 answers





How many trees are there on vertex set $[n]$ that contain a given edge $uv$?




If we glue the vertex $u$ and $v$ with an edge then there are $n-1$ vertices and using the Cayley's formula there are total $(n-1)^{(n-3)}$ trees with vertex set $[n-1]$ and a given edge $uv$.



Is this correct?










share|cite|improve this question















marked as duplicate by Trevor Gunn, Community Nov 26 at 17:05


This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.















  • Also see math.stackexchange.com/questions/2204160 and math.stackexchange.com/questions/1832958 and math.stackexchange.com/questions/575163 (These were found using the Approach0 search engine)
    – Trevor Gunn
    Nov 26 at 16:54
















1















This question already has an answer here:




  • How many different spanning trees of $K_n setminus e$ are there?

    3 answers





How many trees are there on vertex set $[n]$ that contain a given edge $uv$?




If we glue the vertex $u$ and $v$ with an edge then there are $n-1$ vertices and using the Cayley's formula there are total $(n-1)^{(n-3)}$ trees with vertex set $[n-1]$ and a given edge $uv$.



Is this correct?










share|cite|improve this question















marked as duplicate by Trevor Gunn, Community Nov 26 at 17:05


This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.















  • Also see math.stackexchange.com/questions/2204160 and math.stackexchange.com/questions/1832958 and math.stackexchange.com/questions/575163 (These were found using the Approach0 search engine)
    – Trevor Gunn
    Nov 26 at 16:54














1












1








1








This question already has an answer here:




  • How many different spanning trees of $K_n setminus e$ are there?

    3 answers





How many trees are there on vertex set $[n]$ that contain a given edge $uv$?




If we glue the vertex $u$ and $v$ with an edge then there are $n-1$ vertices and using the Cayley's formula there are total $(n-1)^{(n-3)}$ trees with vertex set $[n-1]$ and a given edge $uv$.



Is this correct?










share|cite|improve this question
















This question already has an answer here:




  • How many different spanning trees of $K_n setminus e$ are there?

    3 answers





How many trees are there on vertex set $[n]$ that contain a given edge $uv$?




If we glue the vertex $u$ and $v$ with an edge then there are $n-1$ vertices and using the Cayley's formula there are total $(n-1)^{(n-3)}$ trees with vertex set $[n-1]$ and a given edge $uv$.



Is this correct?





This question already has an answer here:




  • How many different spanning trees of $K_n setminus e$ are there?

    3 answers








combinatorics graph-theory trees






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Nov 26 at 16:38









Shaun

8,507113580




8,507113580










asked Nov 26 at 16:30









thetraveller

1515




1515




marked as duplicate by Trevor Gunn, Community Nov 26 at 17:05


This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.






marked as duplicate by Trevor Gunn, Community Nov 26 at 17:05


This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.














  • Also see math.stackexchange.com/questions/2204160 and math.stackexchange.com/questions/1832958 and math.stackexchange.com/questions/575163 (These were found using the Approach0 search engine)
    – Trevor Gunn
    Nov 26 at 16:54


















  • Also see math.stackexchange.com/questions/2204160 and math.stackexchange.com/questions/1832958 and math.stackexchange.com/questions/575163 (These were found using the Approach0 search engine)
    – Trevor Gunn
    Nov 26 at 16:54
















Also see math.stackexchange.com/questions/2204160 and math.stackexchange.com/questions/1832958 and math.stackexchange.com/questions/575163 (These were found using the Approach0 search engine)
– Trevor Gunn
Nov 26 at 16:54




Also see math.stackexchange.com/questions/2204160 and math.stackexchange.com/questions/1832958 and math.stackexchange.com/questions/575163 (These were found using the Approach0 search engine)
– Trevor Gunn
Nov 26 at 16:54










1 Answer
1






active

oldest

votes


















1














A nice way to perform the count is to count trees with a distinguished edge. As there are $n^{n-2}$ trees and each has $n-1$ edges, there are
$n^{n-2}cdot(n-1)$ such trees.
By symmetry, each of the $nchoose 2$ potential edges is distinguished the same number of times. Thus we arrive at
$$ frac{n^{n-2}cdot(n-1)}{nchoose 2}=2n^{n-3}$$
trees where $uv$ happens to be the distinguished edge.






share|cite|improve this answer




























    1 Answer
    1






    active

    oldest

    votes








    1 Answer
    1






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    1














    A nice way to perform the count is to count trees with a distinguished edge. As there are $n^{n-2}$ trees and each has $n-1$ edges, there are
    $n^{n-2}cdot(n-1)$ such trees.
    By symmetry, each of the $nchoose 2$ potential edges is distinguished the same number of times. Thus we arrive at
    $$ frac{n^{n-2}cdot(n-1)}{nchoose 2}=2n^{n-3}$$
    trees where $uv$ happens to be the distinguished edge.






    share|cite|improve this answer


























      1














      A nice way to perform the count is to count trees with a distinguished edge. As there are $n^{n-2}$ trees and each has $n-1$ edges, there are
      $n^{n-2}cdot(n-1)$ such trees.
      By symmetry, each of the $nchoose 2$ potential edges is distinguished the same number of times. Thus we arrive at
      $$ frac{n^{n-2}cdot(n-1)}{nchoose 2}=2n^{n-3}$$
      trees where $uv$ happens to be the distinguished edge.






      share|cite|improve this answer
























        1












        1








        1






        A nice way to perform the count is to count trees with a distinguished edge. As there are $n^{n-2}$ trees and each has $n-1$ edges, there are
        $n^{n-2}cdot(n-1)$ such trees.
        By symmetry, each of the $nchoose 2$ potential edges is distinguished the same number of times. Thus we arrive at
        $$ frac{n^{n-2}cdot(n-1)}{nchoose 2}=2n^{n-3}$$
        trees where $uv$ happens to be the distinguished edge.






        share|cite|improve this answer












        A nice way to perform the count is to count trees with a distinguished edge. As there are $n^{n-2}$ trees and each has $n-1$ edges, there are
        $n^{n-2}cdot(n-1)$ such trees.
        By symmetry, each of the $nchoose 2$ potential edges is distinguished the same number of times. Thus we arrive at
        $$ frac{n^{n-2}cdot(n-1)}{nchoose 2}=2n^{n-3}$$
        trees where $uv$ happens to be the distinguished edge.







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered Nov 26 at 16:37









        Hagen von Eitzen

        276k21268495




        276k21268495















            Popular posts from this blog

            Probability when a professor distributes a quiz and homework assignment to a class of n students.

            Aardman Animations

            Are they similar matrix