Recently I played Settlers of Catan and, as you do, got into a discussion about combinatorics. We were debating how to answer this question:

How many distinct starting Catan board configurations are there using the default setup rules?

We tried to resolve our debate with Google. It turns out there's a whole lot of answers, most of which must be wrong or (to be more charitable) answering a slightly different question. Without a clear consensus, I decided to wade into the fray.

My Solution

The basic solution is just a simple combinatorics exercise.

  • There are \(19!/(4!4!4!3!3!) = 244432188000\) ways to place the tiles.
  • There are \(6\) ways to arrange the number tokens assuming the normal setup where you start in a corner and expand in a spiral pattern.
  • There are \(9!/4! = 15120\) ways to place the ports.

Thus in total there are \(244432188000 * 15120 * 6 = 22174888095360000\) ways to set up the board disregarding symmetries.

To account for the symmetries we can use a theorem from group theory: Burnside's lemma. Burnside's lemma states that the number of orbits of a set \(X\) under the symmetry group \(G\) is the average of the number of invariant elements \(X^{g}\) for each element \(g\). In equation form,

\begin{equation*} \left|X/G\right| = \frac{1}{\left|G\right|} \sum_{g \in G} \left|X^{g}\right| \end{equation*}

The proof is more or less straightforward; the Wikipedia version is a bit of a mess, so check out this version if you want the details.

To use this formula we first need to figure out the size of \(X\). This is simply the result from the first part: \(22174888095360000\).

Now that we have \(\left|X\right|\) we need to figure out what our group \(G\) is. We need to be careful here; most of the approaches I've seen only consider symmetries of the tiles and conclude that Catan has the symmetry group of a regular hexagon. However, the ports also restrict the set of symmetries. For example, rotation by angle \(\pi/3\) moves ports onto previously empty coastline thus clearly ruling this out as a symmetry. Adding in this constraint results in only permitting reflections about 3 axes (denoted \(F_{1}\), \(F_{2}\), and \(F_{3}\) respectively) and rotations by angle \(\pi/3\) (\(R_{1}\) and \(R_{2}\) respectively). Thus our group is

\begin{equation*} G = \left\{ I, R_{1}, R_{2}, F_{1}, F_{2}, F_{3} \right\} \end{equation*}

Now we calculate the number of invariants.

  • For the identity element \(I\) everything is invariant so we have \(22174888095360000\) invariants.
  • For \(R_{1}\) we have no invariants. Firstly, consider the desert tile. For a board to be invariant the Desert tile must be in the center of the board otherwise it would be rotated onto a previously different tile. But now consider the Wool and Wheat tiles which both have 4 tiles. At most three of these tiles can be invariant while the fourth must be rotated onto a previously different tile (since the center is already taken). Thus there are no boards invariant under \(R_{1}\). The same goes for \(R_{2}\).
  • For \(F_{1}\) we again have no invariants. This is due to the ports again. We have 4 2:1 ports which being unique must be reflected onto a previously different port. Thus no boards are invariant under \(F_{1}\). The same goes for \(F_{2}\) and \(F_{3}\).

Plugging this into the formula for Burnside's lemma we get

\begin{equation*} \left|X/G\right| = \frac{1}{6}(22174888095360000 + 0 + 0 + 0 + 0 + 0) = 3695814682560000 \end{equation*}

Thus there are 3,695,814,682,560,000 distinct Catan board setups using the default setup rules.