5
$\begingroup$

enter image description here

Rules:
1. Start from point A reach back to point A.
2. Each path needs to be visited at least once and only once in each journey.
3. never turning off at crossroads.

to make it more understandable

path = AB, BC etc
journey = ABCDEBDACE or AECADBEDCBA

How many different journeys exist?

$\endgroup$
5
  • $\begingroup$ If ABCDEBDACEA is a path, is AECADBEDCBA also counted? $\endgroup$
    – JMP
    Oct 9, 2019 at 8:40
  • $\begingroup$ Can you precise what are "Path" and "Journey" in the context of this question ? $\endgroup$
    – Evargalo
    Oct 9, 2019 at 9:10
  • 1
    $\begingroup$ "Each path needs to be visited at least once and only once in each journey" - Do you mean each edge needs to be used exactly once? So are you really asking how many Eulerian circuits this graph has? $\endgroup$ Oct 9, 2019 at 9:20
  • $\begingroup$ Oh, so you are asking for Hamiltonian circuits? But then the title doesn't seem to fit the question anymore? $\endgroup$
    – Evargalo
    Oct 9, 2019 at 10:07
  • 2
    $\begingroup$ @Evargalo Not Hamiltonian, Eulerian. Every edge has to be used exactly once, not every vertex. But yes, the title makes no sense given that in the question "path" was used to mean an edge. $\endgroup$ Oct 9, 2019 at 10:09

2 Answers 2

5
$\begingroup$

Each node has 4 edges, so is visited twice. We start and end on node A, but it must be visited some time in between as well.

Let's split this up into cases depending on how many other nodes are visited before we come back to A the first time.

A node cannot be travelled back to immediately because that reuses the same edge, so between two visits to a node at least two other nodes are visited.

1. Node A is visited after 4 other nodes, i.e. $A....A....A$. There can be no repeats in the two halves (they must be at least 2 apart, so it would have to be $AX..XA$, but that repeats edge $AX$). So all four other nodes are visited in some order in the first half. There are $4!=24$ such orderings. The second half of the route is then fixed, apart from the direction. This gives $48$ such routes.

2. Node A is visited after 5 other nodes, i.e. $A.....A...A$. There must be exactly one repeat in that first section, so $AX..X.A$ or its reverse. Any more repeats or putting the repeat further apart will cause edges to be used twice. The blanks are then the other 3 nodes in any order. This means there are $4!*2=48$ choices for this section. The second half is again fixed apart from direction, so we have $96$ such routes.

3. Node A is visited after 6 other nodes, i.e. $A......A..A$. There must be exactly two repeats in that first section. The only patterns that work without repeating any edges are $AXY.X.YA$, its reverse, and $AX.YX.YA$. The blanks are then the other 2 nodes. This means there are $4!*3=72$ choices for this section. The second half is again fixed apart from direction, so we have $144$ such routes.

4. Node A is visited after 3 other nodes. This is case 2 in reverse, so also $96$ routes.

5. Node A is visited after 2 other nodes. This is case 3 in reverse, so also $144$ routes.

This gives a total of:

$48+2*96+2*144 = 528$ routes.

More explicitly, the routes are:

Using the digits $1$-$4$ to stand for the letters $B$-$E$ in any order:
1. $A1234A2413A$, $A1234A3142A$
2. $A12314A243A$, $A12314A342A$, $A21341A423A$, $A21341A324A$
3. $A123142A34A$, $A123142A43A$, $A132412A34A$, $A132412A43A$, $A132142A34A$, $A132142A43A$
4. $A243A12314A$, $A342A12314A$, $A423A21341A$, $A324A21341A$
5. $A34A123142A$, $A43A123142A$, $A34A132412A$, $A43A132412A$, $A34A132142A$, $A43A132142A$

$\endgroup$
2
  • $\begingroup$ @JMP I don't think so. I count ABCDEACEBDA and ABCDEADBECA (only the second half reversed), and then times the 4! permutations of the labels BCDE. $\endgroup$ Oct 9, 2019 at 11:29
  • $\begingroup$ @JMP All circuits in this question have a direction. If you want undirected circuits, the final answer has to be divided by two. Note that the cases 2 and 4 are reverses of each other, as are 3 and 5. Case 1 is reverse of itself, so there are only 24 undirected circuits for that case, but I am counting them with direction here. $\endgroup$ Oct 9, 2019 at 11:36
0
$\begingroup$

Edit : This is an answer to the question:

How many different paths exist from A to A that go through each other point exactly once ?

However, per the comments, it seems the OP is looking for something else. I cannot figure out what exactly yet.


There are

24

paths that qualify.

Indeed,

Each path must be of the type A????A where each ? stands for either B,C,D, or E.
The number of arrangements of {B,C,D,E} into the four positions marked with ?s is 4!=24

$\endgroup$
1
  • $\begingroup$ @SayedMohdAli Maybe I need more clarification. I'll comment under the question. $\endgroup$
    – Evargalo
    Oct 9, 2019 at 9:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.