The math behind Carcassonne tiles
Nareau said:
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[4]^0 = i = [1]o[2]o[3]o[4]
p[4] = [1 2 3 4]
p[4]^2 = [1 3]o[2 4]
p[4]^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.
Hypersmurf
Moderatarrrrh...
Thikket said:
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.)
Similar Threads
