# The math behind Carcassonne tiles

#### Nareau

##### Explorer
If you haven't played Carcassonne, it's a little like dominoes in that you lay down tiles that have to match up edge-to-edge.

Each tile has 4 sides, and each side can have 3 different "features": A road, city, or meadow (R, C, or M).

I think this is a pretty simple permutation problem, but there's a twist in it. If you read the sides of the tile in a clockwise fashion, you might get: Road, Road, Road, City.

RRRC is the same as RRCR, RCRR, CRRR because the sides wrap around.

But a tile that is CCRR is not the same as CRCR.

Am I overthinking (or underthinking) this? Can someone help me figure out how many possible different tiles there could be?

Nareau

#### prosfilaes

At most, there's 3^4=81 possibilities. At worst, you can always write them all down.
One colored: 3
Two colors: any two tiles with one side one color and the rest of the sides another are the same, so there's 3*2 = 6 possibilities. If we have two sides one color, two sides the other, a color can either be across from itself or next to itself, so 2 * 3 * 2 = 12.
Three colors are more complex. If we label them starting with the duplicate color, then I think there's 3*3*2*1 = 18 possibilities, though some of them might be equivalent. So there should be at most 39 different tiles.

#### Hypersmurf

##### Moderatarrrrh...
As far as I can tell, it's 24:
RRRR
RRRC
RRRM
RRCC
RRCM
RRMC
RRMM
RCRC
RCRM
RCCC
RCCM
RCMC
RCMM
RMRM
RMCC
RMCM
RMMC
RMMM
CCCC
CCCM
CCMM
CMCM
CMMM
MMMM

-Hyp.

#### Pseudopsyche

##### First Post
Nareau said:
If you haven't played Carcassonne, it's a little like dominoes in that you lay down tiles that have to match up edge-to-edge.

Each tile has 4 sides, and each side can have 3 different "features": A road, city, or meadow (R, C, or M).
I just wanted to point out that the feature space you gave is not sufficient to discriminate among actual Carcasonne tiles. Consider that the game has two different tiles that have the MCMC feature, one in which the two city edges belong to the same city and one in which the two city edges belong to separate cities.

That said, I don't know the answer to the question you posed regardless.

#### Nareau

##### Explorer
Philomath said:
I just wanted to point out that the feature space you gave is not sufficient to discriminate among actual Carcasonne tiles. Consider that the game has two different tiles that have the MCMC feature, one in which the two city edges belong to the same city and one in which the two city edges belong to separate cities.

That said, I don't know the answer to the question you posed regardless.
I know. I also neglected to include internal features (such as cloisters). For the purpose of this exercise, I'm just looking for edge combinations.

I'm interested because I'd like to catalog all the tiles we've got, and be able to keep a list of "how many of what tiles" exist. I think that will help newcomers to the game predict what areas they'll be able to complete. Kind of like how Scrabble has a list of how many of each letter tiles are in the game.

Nareau

#### orsal

##### LEW Judge
Let's work with the problem as you framed it for simplicity, ignoring philomath's comments. Start with 81, which is the number of *oriented* tiles (considering e.g. RCRR different from RRRC). Now, 9 of these have 2-fold symmetry (i.e. both pairs of opposite sides are identical), so there are 72 without any rotational symmetry. 3 of those 9 have 4-fold symmetry (all sides identical); the other 6 have only 2-fold symmetry.

Now, let's stop specifying orientation, so that we won't distinguish RCRR from RRRC. Each tile with no rotational symmetry can be oriented in 4 distinct ways, so the 72 such oriented tiles correspond to 72/4=18 oriented tiles. (Rationale for division: when we first counted oriented tiles, we counted each unoriented tile 4 times, so we got 4 times the number we want.)

Tiles with 2-fold symmetry can each be oriented in 2 distinct ways: 6/2=3.
Tiles with 4-fold symmetry can only be oriented in 1 way: 3/1=3.
Altogether: 18+3+3=24, confirming Hypersmurf's count.

#### meomwt

##### First Post
I think there is a file on BoardGameGeek which lists all the tiles (and numbers thereof) for the main set and all the expansions.

I just don't have time to look for it right now. #### Doug Sundseth

##### First Post
While I'd not thought of it before, this is similar to cis-trans isomerism problems in organic chemistry, but with roads, cities, and meadows instead of OH, CH3, and NH2 radicals. This doesn't especially help to answer the OPs question, but I found it interesting, nonetheless.

#### Crothian

##### First Post
Nareau said:
I'm interested because I'd like to catalog all the tiles we've got, and be able to keep a list of "how many of what tiles" exist. I think that will help newcomers to the game predict what areas they'll be able to complete.
Your game didn't come with a picture list of all the tiles in it? Mine does.

#### Mark

##### CreativeMountainGames.com
Crothian said:
Your game didn't come with a picture list of all the tiles in it? Mine does.

"Forget it, he's rolling." - Boon from Animal House.

#### Thikket

##### First Post
Nareau said:
I know. I also neglected to include internal features (such as cloisters). For the purpose of this exercise, I'm just looking for edge combinations.
I can confirm what others have reported here: the number for the simple edge combination is 24. Everyone did great in figuring that out, and this is completely sufficient for your purposes... However, you seem to be the kind of person who might be curious about the mathematics behind these solutions, so I thought I'd chime in. The problem you're asking is actually not a simple permutation problem; it involves some sophisticated combinatorics. For high numbers of edges (say the board pieces were octagons instead of squares), none of the methods here would be an efficient answer to the problem. orsal's answer is correct, but relies on his knowledge of rotational symmetry in edges of squares (or points on circles). Hypersmurf likewise got the right answer, but going by exhaustion never works for high order cases, unless you plan to write a good computer program to do it for you.

The real situation here comes from recognizing that permutations along rotations form a group (math term!), and that each permutation can be written as a function (another one!) composed with a coloring (there's a third one!). There's a theorem that neatly wraps this information into a succinct formula, though the formula still requires some summation effort to come to a numerical answer. Beware that you may need Wikipedia (or better yet, Wolfram Mathworld) for some of the language. Enter, if you dare:

[sblock]
Let f be a permutation function in a group G.

(Burnside's Theorem) Let G be a group of permutations of X and let C be a set of colorings of X such that f * c is in C for all f in G and all c in C. Then the number N(G,C) of nonequivalent colorings in C is given by:

N(G,C) = 1/|G| * sum(|C(f)|,for f in G)

That is, the number of nonequivalent colorings in C equals the average of the number of colorings fixed by the permutations in G.

Some clarifying notes:
Note 1.

That "*" operator is operating across a function and a coloring, so it's not your usual multiplication (don't imagine multiplying functions). It's defined like this:

(f * c)(i[k]) = c(k)

where i[k] is the final position of some label (in this example, the "Edge" of the square) after being permuted by the permutation function f.

In words, we say that f moves the label "k" to position "i[k]", and therefore the color of "k" (called "c(k)") moves to f(k) = i[k] and thus becomes the color of i[k].

Note 2.
In this theorem, the word "fixed" (a synonym of "stablized") refers to a permutation that holds the particular coloring constant -- so, if your square is labeled RMRM, one permutation that "fixes" the coloring would be the function that moves position 1 to position 3 and position 2 to position 4 (this would entail physically reflecting the square along a diagonal, which is not one of the permutations you're considering here).

Note 3.
|G| refers to the number of permutation functions in the group G, including the identity function (where no labels move at all).
|C(f)| is the number of colorings of C that are fixed by f, which is k^(#(f)), where k is the number of different colors (R M C = 3 in your case), and #(f) is the number of cycles in a cycle factorization of a permutation of f.
[/sblock]

Okay, so, now we have a formula. All we need to do is fill in the corresponding values to get an answer:

N(G,C) = (81 + 3 + 9 + 3) / (4) = 24.

Here's how I got those values:
[sblock]
G contains four rotational functions, with the cycle factorizations of:
p^0 = i = ooo
p = [1 2 3 4]
p^2 = [1 3]o[2 4]
p^3 = [1 4 3 2]

The number of cycles for each of these functions is, respectively,
4
1
2
1

And thus the corresponding |C(f)| values for each permutation function is (since k=3):
3^4 = 81
3^1 = 3
3^2 = 9
3^1 = 3

Recalling that |G| = 4, we have:

N(G,C) = 1/|G| * sum(|C(f)|,for f in G)
N(G,C) = 1/|4| * sum(81 + 3 + 9 + 3)
N(G,C) = 1/4 * 96
N(G,C) = 24
<>
[/sblock]

If you want to complicate the problem further by adding the "internal features (such as cloisters)" or changing how a City edge is defined like you mentioned in one of your posts, I'd be happy to crunch out any numbers you need. Just post your revised problem here, and I (or anyone else here who can read this theorem and understands elementary combinatorics) can very quickly bring you a solution. It only takes maybe 60 seconds to get an answer, if you don't bother writing a freaking essay-length post explaining that answer like I just did . I like combinatorics a lot, obviously. Heh.

#### MerricB

##### Eternal Optimist
Crothian said:
Your game didn't come with a picture list of all the tiles in it? Mine does.
I guess you got the "big box" with several expansions in it, Crothian?

My Carcassonne set dates back quite a while before that... they didn't even include the River expansion in the basic box when I got mine. Cheers!

#### Hypersmurf

##### Moderatarrrrh...
Thikket said:
Hypersmurf likewise got the right answer, but going by exhaustion never works for high order cases, unless you plan to write a good computer program to do it for you.
Yeah - I handled it with a few sorts in Excel, but if there had been ten thousand possibilities instead of 81, I'd have done it programmatically.

My combinatorics is mostly intuitive rather than learned, so I suspect I'd end up reinventing a whole lot of wheels to eventually get there -Hyp.

#### Vocenoctum

##### First Post
MerricB said:
I guess you got the "big box" with several expansions in it, Crothian?

My Carcassonne set dates back quite a while before that... they didn't even include the River expansion in the basic box when I got mine. Cheers!

I just play on Live, so haven't bought the expansions, the game can be quite addictive though. (Plus the music gets stuck in my head.)