Number of Combinations for Connecting N Villages with One-Way Roads

[Pzi]

Homework Statement

There are N villages which have to be connected using one-way roads in a manner that for every two villages there exists at least one route to travel from one to another.
How many different solutions are there?

Homework Equations

This fits pretty well not only into combinatorics but also in a graph theory.

The Attempt at a Solution

For N=2 there is only 1 trivial solution.
For N=3 there seems to be 15 solutions, but it's done by writing out the combinations and does not lead to general solution.

 

[LCKurtz]

I'm not proposing an answer, but I don't think you have well stated the question. Can there be more than one route that works for two cities? Is there some limit on how many roads can enter/leave a city? What are the restrictions?

 

[Whovian]

Perhaps you should start out by trying to find some recursive solution, and then using mathematical induction to make it non-recursive. A lot of solutions to problems such as this in Graph Theory involve recursivity. (Is that a word?)

 

[voko]

I'm not proposing an answer, but I don't think you have well stated the question. Can there be more than one route that works for two cities? Is there some limit on how many roads can enter/leave a city? What are the restrictions?

I am guessing it should be no more than 1 route from any A to any B.

 

[voko]

recursivity. (Is that a word?)

The word is "recursion" :)