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!

Intro to combinatorics verification

  1. Apr 3, 2013 #1
    1. The problem statement, all variables and given/known data
    There are 7 different routes from A to B, 4 different routes from B to C, and two different routes from C to A. What are the possible routes from A to C and back, allowing any route to be traversed once in each direction.


    2. Relevant equations



    3. The attempt at a solution
    So I think I have it, but I just need some verification since we've only had one lecture and my high school combinatoric lessons (if you could call them that) weren't very "in depth" and several years ago.

    So I figure these are the possibilities:
    A to B to C to A gives 7*4*2 = 56 possible routes
    A to B to C to B to A gives 7*4*4*7 = 784 possible routes
    A to C to A gives 2*2 = 4 possible routes
    Altogether that makes 844 possibilities.

    However, I'm wondering if this one "counts" as well:
    A to B to A to C to A gives 7*4*7*2*2 = 784, however I'm not sure if that double counts some of the routes from above. Any help would be greatly appreciated.

    Edit: I also just thought of A to C to B to A, but that one I think double counts. Thanks again.
     
  2. jcsd
  3. Apr 3, 2013 #2
    Since one route can be traversed only in one direction A→B 7 ways, B→C 4 ways but C→B? Only 3 ways there right? Because one of the 4 routes has already been assigned direction form B→C and hence you cannot go on that from C→B. Similar arguments hold for the rest.
     
  4. Apr 3, 2013 #3
    The way I read it is that it can be used once TO C and then once BACK from C, so I wouldn't need to discount it. One of the next parts limits the routes to those roads not used twice, so that's why I believe my interpretation is correct, but I do understand what you're getting at.
     
  5. Apr 3, 2013 #4
    Sorry about my first post. I misinterpreted the question.

    I guess since direction matters, the above routes also count. Also there is the possibility of A→B→A→B→A→B→A or similar things. But I don't know whether you are allowed to go to A more than once after starting (i.e. you start at A and end at A but don't visit A in between). What does the source say about the answer?
     
  6. Apr 3, 2013 #5
    No worries, and thanks for the replies. I guess in a sense that's also part of my question. I think by virtue of the "road only once in each direction," that the endless ABABABABA...probably isn't allowed but it's kind of ambiguous in that sense. I have a feeling I might just be thinking about this too hard haha. As for the answer, this question doesn't appear in the solutions in the back since it's an even numbered question, so it doesn't give too much in the way of what it should look like. My thinking is that as long as you start at A and hit C, and end at A using no road more than once before hitting C the first time and then no road more than once from C to A it should work.
     
  7. Apr 3, 2013 #6

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    This strikes me as quite a hard problem. Even if you start with the simple case of not using any direct AC routes it is nontrivial. As you allow up to 2 direct routes in each direction (9 cases in total), it gets progressively tougher.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Intro to combinatorics verification
  1. Logarithm verification (Replies: 4)

  2. Combinatorics Question (Replies: 4)

  3. Combinatorics question (Replies: 2)

Loading...