1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: How many combinations?

  1. Sep 12, 2012 #1


    User Avatar

    1. The problem statement, all variables and given/known data
    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?

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

    3. 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.
  2. jcsd
  3. Sep 12, 2012 #2


    User Avatar
    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?
  4. Sep 12, 2012 #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?)
  5. Sep 12, 2012 #4
    I am guessing it should be no more than 1 route from any A to any B.
  6. Sep 12, 2012 #5
    The word is "recursion" :)
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook