Question

Using the formual (2n-3)! / [2^n-2 x (n-2)!], how many possible rooted trees can you generate using 6 organisma?

Answer 1

Its very easy to calculate the number or rooted and unrooted trees using the double factorial notation !!. Here is how it works. We know 5! = 5*4*3*2*1. But 5!! is defined as the product including only odd numbers. That is,

                       5!! = 5*3*1 = 15. Similarly, 7!! = 7*5*3*1.

Now, For n organisms, the number of rooted trees is given by (2n-3)!!.

Here n = 6. Thus (2n-3)!! = (2*6 - 3)!! = 9!! = 9*7*5*3*1 = 945. Thus number of rooted trees for 6 organisms is 945. The formula for finding number of rooted trees is (2n-3)!! and for unrooted trees is (2n-5)!!.

Thank you.