Choosing the vertices of a regular hexagon, how many ways are there to form four triangles such that any two triangles share exactly one vertex?

449 Views Asked by At

In other words, how many ways are there to choose four $3$-combinations of a $6$-set, such that each two combinations contain exactly one common element, modulo dihedral group $D_6$?

For example, $\{1,2,3\}, \{1,4,5\},\{2,4,6\}, \{3,5,6\}$ and $\{2,3,4\}, \{2,5,6\},\{3,5,1\}, \{4,6,1\}$ belong to the same class, but $\{1,2,3\}, \{1,4,5\},\{2,5,6\}, \{3,4,6\}$ does not.

Context: I am considering partitions of a $4$-set and partially ordering them by refinement. The result is a lattice which I am trying to visualize by a $3$D graph. The most interesting part of the graph involves a square and a regular hexagon. For example: $\{1,2,3\}, \{1,4,5\},\{2,4,6\}, \{3,5,6\}$ leads to this visualization.

Edit: I have categorized all $30$ possibilities into $5$ orbits:

  1. (three edges of the hexagon missing, $4$ elements) $124.135.256.346, 125.134.246.356, 135.146.236.245, 136.145.235.246.$
  2. (two edges, one long diagonal missing, $6$ elements) $123.145.246.356, 124.135.236.456, 125.136.246.345, 126.135.245.346, 134.156.235.246, 135.146.234.256.$

  3. (one edge, two short diagonals missing, $12$ elements) $123.145.256.346, 123.146.245.356, 124.136.235.456, 124.136.256.345, 124.156.235.346, 125.134.236.456, 125.146.234.356, 125.146.236.345, 126.134.245.356, 126.145.235.346, 134.156.236.245, 136.145.234.256.$

  4. (two short and one long diagonal missing, $6$ elements) $123.146.256.345, 123.156.245.346, 124.156.236.345, 125.136.234.456, 126.134.235.456, 126.145.234.356.$

  5. (three long diagonals missing, $2$ elements) $123.156.246.345, 126.135.234.456.$

2

There are 2 best solutions below

1
On BEST ANSWER

Four triangles means twelve slots to fill. There are six vertices to place in those slots. No vertex can occur three times, because it can't occur twice in a single triangle, and if there are three triangles which share that vertex and no other then there must be six other distinct vertices. In short: by two applications of the pigeonhole principle, each vertex is in precisely two of the triangles.

Therefore each vertex has four neighbours, so is missing precisely one neighbour, and they pair up: the overall graph is $K_6$ from which three non-adjacent edges have been removed.

The possibilities for the missing edges modulo the dihedral group are:

  1. Three edges of the hexagon (e.g. $0-1, 2-3, 4-5$)
  2. Two edges of the hexagon and one long diagonal (e.g. $0-1, 2-5, 3-4$)
  3. One edge of the hexagon and two short diagonals (e.g. $0-1, 2-4, 3-5$)
  4. Two short diagonals and one long diagonal (e.g. $0-2, 1-4, 3-5$)
  5. Three long diagonals (e.g. $0-3, 1-4, 2-5$)
2
On

First, I'll define group equivalency such that$$\{2,3,4\},\{2,5,6\},\{3,5,1\},\{4,6,1\}\equiv\{1,3,5\},\{1,4,6\},\{2,3,4\},\{2,5,6\}$$ so that we only need to consider combinations where $1$ is in each of the first two groups.

With that restriction there are $\binom{5}{2}=10$ ways to fill the first group and $\binom{3}{2}=3$ ways to fill the second. Dividing by $2$ because each is counted twice gives $\frac{10*3}{2}=15$ ways to fill the first two groups. Each will have the form $\{a,b,c\},\{a,d,e\}$ and there are $2$ ways to fill the other two groups: $\{b,d,f\},\{c,e,f\}$ and $\{b,e,f\},\{c,d,f\}$. That gives a total of $30$ distinct combinations.