• Support PF! Buy your school textbooks, materials and every day products Here!

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,535
751
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
647
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
6,054
390
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
6,054
390
recursivity. (Is that a word?)
The word is "recursion" :)
 

Related Threads on How many combinations?

Replies
2
Views
4K
Replies
5
Views
2K
  • Last Post
Replies
0
Views
821
Replies
1
Views
1K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
22
Views
1K
  • Last Post
Replies
6
Views
3K
Replies
17
Views
2K
Top