# Determine number of directed trees and rooted trees obtainable

I've been doing some exercises about graph theory and I find myself stuck on this one with no idea of to proceed.

Here's the question :

How many different directed trees can be obtained if we assign all possible orientations to edges of an undirected tree having exactly n nodes ? How many of them will be rooted (directed) trees ?

I started by drawing but there's too many structures possible so I searched through the different formulas and equalities we've learned but can't figure out a way to apply any of them for that question.

Thanks in advance for reading my question and trying to help me.

Yvann

[EDIT] So I just figured something out, simple but yet perfectly answering the question. You have $6$ edges in a $7$ nodes tree. Every edge can be placed in $2$ different directions so you can calculate the number of possible trees easily by writing $2^6 = 64$.
Then to figure out the number of rooted tree is pretty easy, you have $7$ nodes so $7$ possible starting points so $7$ rooted trees within those $64$.

I would attack it this way. I'd use the Matrix-Tree Theorem to obtain the number of unrooted spanning trees. You can then apply $n$ orientations to each tree. So by rule of product, multiply your result from the Matrix-Tree Theorem by $n$.
• I know that. But that doesn't give you a count of the number of spanning trees in $G$. If you are orienting a single spanning tree, there are $n$ such ways to do this. I was asking about the number of edges in $G$. Apr 23, 2014 at 14:58