Number of arrangements of paths connecting edges of a fixed hexagon

Question

Assume that a path must simply connect one edge to another. Then there could be up to 3 separate paths through a hexagon (they do not merge but they may cross).

I have 15 single paths, 33 non-crossing double paths, 15 crossing double paths, 2 non-crossing triples, and 6+6+1 triples with 1,2,3 crossings. The total is 78, but I'm not at all sure this is a good approach or the answer is correct. Perhaps there is a much simpler way to calculate/enumerate.

---

If rotations and/or reflections are allowed then the number of distinct tiles is much reduced. If paths are allowed to merge when they cross the number is quite a bit higher. Perhaps the question has 3 different answers, but the answer I'm most interested in is the distinct paths on fixed tiles.

[The application is to games like Tantrix, but really a hex maze.]

---

Edit: there are 30 non-crossing double paths, not 33. The total is 75.

Answer 1

Since the hexagon edges are distinct, the question becomes

How many ways are there to pair up some or all of the edges using one to three indistinguishable paths?

Your answer of 78 is wrong and the correct answer is 75; crossings are irrelevant for the answer. The derivation is as follows:

• One path. There are $\binom62=15$ pairs that can be connected (choose two from the six edges available).
• Two paths. As before, there are 15 ways to choose the first pair. After this we have four remaining edges, so $\binom42=6$ ways to choose the second pair. However, since the two paths are indistinguishable, we must divide by $2!$ to count each choice once. So there are $\frac{15\cdot6}2=45$ ways to make two paths in the hexagon.
• Three paths. After inserting two paths, there are only two edges left, so the third path is forced (I like to consider it as $\binom22=1$ way for completeness, though). Now that there are three paths, we must divide by $3!$ instead of $2!$, leading to $\frac{15\cdot6\cdot1}6=15$ ways of making three paths.

Summing up, we get $15+45+15=75$ arrangements of paths on the fixed hexagon. We can generalise this to other polygons; the number of arrangements $a(n)$ on the fixed $n$-gon is given by A001189, which has $a(6)=75$. Based on how I calculated this specific term above, $a(n)$ has the following formula: $$a(n)=\sum_{k=1}^{\lfloor n/2\rfloor}\frac1{k!}\prod_{j=1}^k\binom n{2j}$$

Answer 2

Partly Taxel has provided a good answer counting them. Here I will just show how to enumerate them to check you have them all (or to find which ones you've double counted).

Numbering Number each of the sides of the hexagon from 1 to 6. A line can then be represented by a pair of numbers $(x,y)$. To avoid counting $(x,y)$ and $(y,x)$ as different paths apply the restriction that $x<y$.

One Path - 15 paths

Loop starting from $x=1$ and increase to $x=5$. For each value of $x$ loop for $y$ starting from $y=x+1$ up to $y=6$. This will give:

$$(1,2),(1,3),(1,4),(1,5),(1,6),(2,3),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)$$

Two Path - 45 paths

Take each answer from the one path answer and add a second path using available numbers. To avoid double listing the second path must have its smallest number which is bigger than the smallest number of the first path.

$(1,2)$ gains: $(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)$ - 6 paths

$(1,3)$ gains: $(2,4),(2,5),(2,6),(4,5),(4,6),(5,6)$ - 6 paths

$(1,4)$ gains: $(2,3),(2,5),(2,6),(3,5),(3,6),(5,6)$ - 6 paths

$(1,5)$ gains: $(2,3),(2,4),(2,6),(3,4),(3,6),(4,6)$ - 6 paths

$(1,6)$ gains: $(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)$ - 6 paths

$(2,3)$ gains: $(4,5),(4,6),(5,6)$ - 3 paths

$(2,4)$ gains: $(3,5),(3,6),(5,6)$ - 3 paths

$(2,5)$ gains: $(3,4),(3,6),(4,6)$ - 3 paths

$(2,6)$ gains: $(3,4),(3,5),(4,5)$ - 3 paths

$(3,4)$ gains: $(5,6)$ - 1 path

$(3,5)$ gains: $(4,6)$ - 1 path

$(3,6)$ gains: $(4,5)$ - 1 path

Three Paths - 15 paths

To avoid double counting the third (last remaining) path must have its smallest number bigger than the smallest number of the other two paths.

$(1,2),(3,4)$ gains: $(5,6)$

$(1,2),(3,5)$ gains: $(4,6)$

$(1,2),(3,6)$ gains: $(4,5)$

$(1,3),(2,4)$ gains: $(5,6)$

$(1,3),(2,5)$ gains: $(4,6)$

$(1,3),(2,6)$ gains: $(4,5)$

$(1,4),(2,3)$ gains: $(5,6)$

$(1,4),(2,5)$ gains: $(3,6)$

$(1,4),(2,6)$ gains: $(3,5)$

$(1,5),(2,3)$ gains: $(4,6)$

$(1,5),(2,4)$ gains: $(3,6)$

$(1,5),(2,6)$ gains: $(3,4)$

$(1,6),(2,3)$ gains: $(4,5)$

$(1,6),(2,4)$ gains: $(3,5)$

$(1,6),(2,5)$ gains: $(3,4)$