How many combinations?

  • Thread starter Pzi
  • Start date
  • #1
Pzi
26
0

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

  • #2
LCKurtz
Science Advisor
Homework Helper
Insights Author
Gold Member
9,568
774
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?
 
  • #3
Whovian
653
3
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?)
 
  • #4
voko
6,054
391
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.
 
  • #5
voko
6,054
391
recursivity. (Is that a word?)

The word is "recursion" :)
 

Suggested for: How many combinations?

Replies
5
Views
406
Replies
19
Views
522
Replies
12
Views
397
Replies
16
Views
671
  • Last Post
Replies
4
Views
2K
Replies
1
Views
599
Replies
3
Views
672
  • Last Post
Replies
22
Views
2K
Top