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.