# How many combinations?

## 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.

## Answers and Replies

LCKurtz
Science Advisor
Homework Helper
Gold Member
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?

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?)

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.

recursivity. (Is that a word?)

The word is "recursion" :)