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$.
Best Answer
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$.