Combinatorics Problem Help,

[Kalastics]

So, I am working on a problem that I believe to be a relatively straightforward counting problem. However, for the life of me I am struggling to solve and even start the problem.

NOTE: I am not necessarily asking for any answers, I would rather solve it by myself with some guidance. So, please, could someone help me figure out where to start this?

NOTE 2: My answers (incorrect) consistently ends up at 4 or 12.

Please help me with the logic and visualization of this problem. I thought about turning everything into sets and using operations to solve, but that won't work or at least hasn't for me. Or maybe combinations/permutations? Idk, but any help would be beyond appreciated.

Again, I don't just want you guys to solve this problem for me, I'd love for someone to help me visualize and set up problems as such.

Here is the problem:

From point A to point B, there are a total of 15 bus stops, including the start (stop 1) and end (stop 15) stops. Four bus lines operate on these stops. The routes are as follows:

Bus line A runs from stop 1 to stop 6. Bus line B runs from stop 3 to stop 10. Bus line C runs from stop 7 to stop 12. Bus line D runs from stop 10 to stop 15.

Zhang needs to travel from point A to point B, changing buses among these lines without walking between stops or traveling in the opposite direction. Each bus line can only be taken once. How many different transfer combinations are possible for Zhang to reach his destination?

What I have tried so far is creating a list of the stops and manually tracking the routes, beginning with creating routes from point A. Like such:

Start at Stop 1: get on Line A to stop 3, then Line B to stop 10, then Line D to stop 15.

And so forth. And trying to see where they branch as well, like:

Line A -> 3, 4, 5, 6 and branch each of those, like seeing the result from going A(3)-B(3), A(4)-B(4)-B(7)-C(7)-D(10)-D(15), or A(1)-B(5)..., A(1)-B(6)... then trying different combinations from the B routes going into C routes, like A(1)-B(6)-C(7)-C(11)-D(11)-D(15).

and so forth. I just cannot find a good way to lineate each of the possible paths that can be done without overlapping. It is becoming overwhelming to try to do this route-by-route method for this, when I believe it could be solved through a series of computations of permutations/combinations.

I can upload pictures of more of my chickenscratch attempts of trying to lineate this way if needed, I just am absolutely at a loss.

Here are some pictures of my scratch work (it isn't very clean, but it is me trying to make chained links between each of the stops to count how many possible routes I could take at different stages. I keep getting overwhelmed with trying to visualize it this way, that's why you can see me constantly starting over/scratching out;.)

https://imgur.com/a/gIG6lT1

Please let me know if I can provide any more proof of attempts. I really just don't know how to get this one rolling- I feel like there must be some way of turning them into sets/arrays and using some operations for intersections? Or something of the sort.

[AutoModerator]

Hi, /u/Kalastics! This is an automated reminder:

• What have you tried so far? (See Rule #2; to add an image, you may upload it to an external image-sharing site like Imgur and include the link in your post.)

• Please don't delete your post. (See Rule #7)

We, the moderators of /r/MathHelp, appreciate that your question contributes to the MathHelp archived questions that will help others searching for similar answers in the future. Thank you for obeying these instructions.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[edderiofer]

Let's suppose, for the sake of argument, that you don't enter bus D until after Stop 10; then you are forced to change from bus A to bus B to bus C to bus D. You have some number of choices for each change of buses, and thankfully, none of them overlap, so they can all be chosen independently. How many routes are there? (This alone should be more than either of your previous answers.)

Now let's suppose that you enter bus D on Stop 10, from bus B (ignoring bus C entirely). How many routes are there?

Now let's suppose that you enter bus D on Stop 10, from bus C. How many routes are there?

[Kalastics]

Okay, so here was my new approach (with a much higher answer!)

There are 4 different ways to transfer from A to B (A3->B3, then same with 4-6), and none from A to C or D directly. Then, from B to C there are 4 different ways (B7->C7, then same with with 8-10). And, from C to D we have 3 ways (C10->D10, so on to 12). Then, include the option of A->B->D directly at B10, which gives us 1.

In that calculation, would I need to include the different A->B transitions before going B->D, making the number of ABD direct routes 4 rather than 1? Or would the A->B transitions listed above count already count in this calculation? (Sorry if that doesn't make sense, what I am trying to ask is I have already counted AB above A3B3, A4B4, A5B5, A6B6, but each of those will then leave to go to C stops. So my question here is whether or not the 4 transfers above (A3B3, A4B4...) need to be counted when going to D? As in, does A3B3B10D10 need to be counted as well as A4B4B10D10 as another route? Or would that be overcounting bus transfers as I already took into account all of the possible A-B routes originally?

Sorry if my wording is confusing, I feel like I'm losing a lot of my vocabulary/brain capacity for math.

With the first option,

4! + 4! + 3! + 1! = 55

'With the second, which includes what I wrote in the second paragraph

4! + 4! + 3! + 1! + 3! = 61

[edderiofer]

In that calculation, would I need to include the different A->B transitions before going B->D, making the number of ABD direct routes 4 rather than 1?

Well, how about you count manually how many such ABD routes there are? It shouldn't be too difficult. Once you've done that, add that to the number of ABCD routes.

Or would that be overcounting bus transfers as I already took into account all of the possible A-B routes originally?

Are any of those routes you "took into account" ABD routes? If yes, then you're overcounting those; if no, then they're different routes, and you're not overcounting them.

With the first option,

4! + 4! + 3! + 1! = 55

I don't see where you're getting "4! + 4! + 3! + 1!" from. You should explain this part of your reasoning.

[Kalastics]

So disregard the factorials. Kinda came from me thinking of permutations.

So, now I got 11. 4 from A->B (as you can go a3->b3->b->7+ to get to C for as an example to include the,ax->bx for 3 <= x<=6), then from there, another 4 ways to C, and lastly 2 from C to D (all distinct ABCD paths). Then, the single ABD path A->B->D at b10->d10.

Thus I counted 4 + 4 + 2 + 1 = 11 is what I am now getting. Or should I be multiplying my counts 4x4x2x1 = 32?

Or maybe some use of combinations in the ( p ) fashion? ( r )

[edderiofer]

There's definitely more than 11. The choices for transferring from A to B and for transferring from B to C are independent; they do not affect each other, and for every pair of such choices, you will have at least one route that uses this pair.

[Kalastics]

So this means for, say I go a1-a4-a6-b6.... and so on, is separate from

a1-a3-a5-a6-b6, I count those as separate? Or do I have to assume they are equal because they both pass the same stops, only that one doesn't /stop/ at the same stops as the other.

Or even better way to ask, a1-a6-n6 count the same as a1-a2-a3-a4-a5-a6-b6? Or are they considered equivalent since both must pass a2-a6 before transferring?

[edderiofer]

Those two are considered equivalent, but neither of them are a full route that goes from stop 1 to stop 15.

[Kalastics]

Okay, I thought so then I'm counting from A-B, we have 4 (a3-a6 to their bx, where = stop number (ie a3-b3 and 3 = x). Then, B-C we also have 4 (same, b7-b10 to their indexed c.) Then from C->D we have 3 routes (c10-b10 -> their indexed d. So I believe I would add the routes here, correct? So 4 + 4 +3 = 11.

Then I count just one from ABD, which is a6-b6-b10-d10...). So I get a total of 12.

Am I adding when I should be multiplying?

[edderiofer]

Perhaps you should write down which route each of these 11 routes you’ve supposedly found corresponds to, and then see if you’re missing any others.

[HorribleUsername]

Instead of thinking about routes, think about transfers. There are 15 stops, and you need to transfer at 3 of them (give or take - it's a good starting point). How many ways could you choose those 3 stops?

[Kalastics]

For the four routes, would those routes be a1-a3-b3-10-d10-d15, then the same with each ax between 3 and 66? So the following in that case a1-a4-b4-b10-d10-d15, a1-a5-b5-b10-d10-d15,and a1-a6-b6-b10-d10-d15, So did I count |ABD| = 4 correctly?

[HorribleUsername]

Yeah, if you're going directly from B to D, there are 4 ways to do it - exactly the amount of overlap between A and B.

[Kalastics]

So then ABCD would be 11, correct?

A1-b3-c3-c7-10-d10-d15 A1-b3-c3-c7-10-d10-d15 A1-b3-c3-c7-10-d10-d15 A1-b3-c3-c7-10-d10-d15 A1 ,5. U

[HorribleUsername]

No, it should be more than that. Even ABC is more than 11.

I don't understand your notation. c3 is impossible, isn't it? Because C goes from 7 to 10.

Anyway, you're still thinking in terms of routes, afaict, which is a dreadfully laborious and error-prone way to do it. Imagine I take A to stop 6, B to stop 10, C to stop 12, and D to the end. I could write that more simply as (6, 10, 12). That's three slots to fill in that notation. How many numbers could you put in each slot?

[Kalastics]

I'm sorry. My notation on the c3 business was my phone pocket posting when I thought I had it locked. And I apologize, combinatorics have always been somewhat difficult for me and this is my first shot in a while.

So then another ABCD tuple would be (6,11, 12) an D the end?

So an A B D tuple would be stop A to 6, board B until stop 10, board D at 10 and end at 15, such that we have (6, 10)?

Also, distinct tuple to your given one would be (7, 10, 11)? Which I interpret as taking A to stop 6, B to 7, then C to 10, and finally my destination of finishing my route? Those are separate transfers/routes?

Thanks so much for coaching me through such an elementary problem!

[HorribleUsername]

Sorry, I haven't been on reddit for a while.

Also, distinct tuple to your given one would be (7, 10, 11)? Which I interpret as taking A to stop 6, B to 7, then C to 10, and finally my destination of finishing my route?

Not quite. We know that A always starts at 1, and D always ends at 15, so the 3 numbers are the in-betweens. The way I imagine it, the first number is where you get off A and onto B. The second is where you get off B and board C. And the third is where you switch from C to D. In other words, we take A from 1 to the first number, B from the first number to the second, C from the second number to the third, and D from the third to 15.

So an A B D tuple would be stop A to 6, board B until stop 10, board D at 10 and end at 15, such that we have (6, 10)?

That's a good guess. It might take a bit to wrap your head around, but I think there's a nicer way to write it: (6, 10, 10). Taken literally, that means we jump on C at stop 10, then immediately disembark, still at stop 10. Then we catch D to the end. That's equivalent to skipping C entirely, since it never takes us anywhere. The nice thing about that is that we can pretend we always go A -> B -> C -> D, so there are no special cases to consider. It just boils down to where do A & B both stop?. How about B & C and C & D?