Intro to combinatorics verification

[lus1450]

Homework Statement

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.

Homework Equations

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.

 

[Sunil Simha]

Homework Statement

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.


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

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.

 

[lus1450]

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.

 

[Sunil Simha]

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.

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?

 

[lus1450]

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.

 

[haruspex]

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.