How many unique outcomes can be made from the 12 river tiles in Carcassonne?

Question

I have been pondering this question for some time now and it's a bit out of my scope to solve it. I am curious to know how many arrangements are possible for the river 1 expansion for Carcassonne.

The rules for playing the river are as follows: The source tile is played first, The lake tile is played last, and If two river bends are drawn in sequence they must have opposing orientation.

I understand the following: The first and last tile played will not factor into the counting so we just look at the $10$ tiles in between. Each tile has $2$ orientations and there are $8$ unique tiles, plus $1$ repeated corner, and one repeated straight. We must also exclude possibilities that become unplayable when the river curves in onto itself.

Here's an image of the $12$ river tiles:

My preliminary guesswork at counting is

$$\frac{(2^8)10!}{2!2!}$$

My rationale $10!/2!2!$ Because order of selection matters and repetition tiles are excluded by dividing by $2!$

$2^8$ because each tile can be placed in $2$ ways (the $2$ straight tiles are not included because they are not unique)

I know this is wrong. It's just my first guess at it, and it has not excluded possibilities where the river curves into itself and creates an unplayable game. Any assistance would be much appreciated, thanks!

Answer 1

The main problem is counting the different selfavoiding layouts that can be produced using the four tiles of the following figure:

An admissible layout begins with $A$, ends with $B$, and contains $4$ $L/R$ tiles. We may assume that the first such tile is an $L$ (and multiply by $2$ at the end). There are $8$ $L/R$ words of length $4$ beginning with $L$, namely $$LLLL, LLLR, LLRL, LLRR,LRLL, LRLR,LRRL,LRRRR\ .$$ These words have to be decorated with $A$, $B$ and six letters $S$, whereby certain $S$ are compulsory. We then obtain the following $8$ patterns, whereby at the dots optional letters $S$ may be filled in: $$\eqalign{p_1:\quad&A\cdot LS\cdot LS\cdot LS\cdot L\cdot B \cr p_2:\quad&A\cdot LS\cdot LS\cdot L\cdot R\cdot B \cr p_3:\quad&A\cdot LS\cdot L\cdot R\cdot L\cdot B \cr p_4:\quad&A\cdot LS\cdot L\cdot RS\cdot R\cdot B \cr p_5:\quad&A\cdot L\cdot R\cdot LS\cdot L\cdot B \cr p_6:\quad&A\cdot L\cdot R\cdot L\cdot R\cdot B \cr p_7:\quad&A\cdot L\cdot RS\cdot R\cdot L\cdot B \cr p_8:\quad&A\cdot L\cdot RS\cdot RS\cdot R\cdot B \cr}$$ These $8$ patterns fall into three types:

(i) The pattern $p_1$ contains four consecutive equal turns, and has to be treated using a case analysis in order to ensure selfavoiding.

(ii) The two patterns $p_2$ and $p_7$ contain three consecutive equal turns, and have to be treated using a case analysis in order to ensure selfavoiding. (Note that $p_7$ is equivalent to $p_2$.)

(iii) The remaining patterns are selfavoiding however we fill in the optional letters $S$. The number of ways to do this is a stars and bars problem for each $p_k$, depending on the number of compulsory letters $S$ in $p_k$.

Assume that the total number $N$ of selfavoiding layouts has been determined. We then have to distribute the picture tiles on these layouts. The number $M$ of possibilities is the same for all layouts. Concerning the two pictures occurring twice assume that they are "secretly" different, and divide by $2\cdot2$ at the end. In this way we obtain $$M={6!\> 2^6\>4!\over2\cdot2}=276\,480\ .$$

Answer 2

You're off to a good start, but I don't know why you used $2^8$ instead of $2^{10}$. You write “the $2$ straight tiles are not included because they are not unique”, but whether they're unique has nothing to do with counting their $2$ different orientations – you've already correctly accounted for the fact that they're not unique by dividing by $2!$ twice.

I'll leave out the factor $2!^2$ until the end because it applies to all configurations and we can apply it once.

Two conditions are left to be taken into account: We can't have self-intersections, and two consecutive bends must turn in opposite directions.

Let's start with the second one. Each pair of consecutive bends reduces the options by a factor of $2$, so we need to count the configurations according to the number of pairs of consecutive bends they contain. This can be done using inclusion–exclusion.

Let's find the numbers $a_k$ of ways in which $k$ pairs of bends can be adjacent (not yet counting orientations).

$a_0$ is just $10!=3628800$.

For $a_1$, we can choose a pair in $\binom42=6$ ways, order it in $2$ ways, and order the resulting $9$ items (one pair, eight unpaired tiles) in $9!=362880$ ways, for a count of $a_1=4354560$.

For $a_2$, there are two options. We can either choose two disjoint pairs in $3$ ways, order each of them in $2$ ways for a factor of $2^2=4$, and order the resulting $8$ items (two pairs, six unpaired tiles) in $8!=40320$ ways; or we can choose two overlapping pairs to form a consecutive triple in $\binom43=4$ ways, order them in $3!=6$ ways and order the resulting $8$ items (one triple, seven unpaired tiles) in $8!=40320$ ways, for a total count of $a_2=(3\cdot4+4\cdot6)\cdot40320=1451520$.

For $a_3$, there's no choice; we have to have all $4$ bends in a row. We can order them in $4!=24$ ways, and then we can order the resulting $7$ items (one quadruple, six unpaired tiles), in $7!=5040$ ways, for a count of $a_3=120960$.

Then by inclusion–exclusion the number $b_j$ of configurations that have exactly $j$ pairs of adjacent bends is

$$ b_j=\sum_{k=j}^3(-1)^{j+k}\binom kja_k\;, $$

so

\begin{eqnarray*} b_0&=&a_0-a_1+a_2-a_3=3628800-4354560+1451520-120960=604800\;,\\ b_1&=&a_1-2a_2+3a_3=4354560-2\cdot1451520+3\cdot120960=1814400\;,\\ b_2&=&a_2-3a_3=1451520-3\cdot120960=1088640\;,\\ b_3&=&a_3=120960\;. \end{eqnarray*}

Each pair of adjacent bends reduces the options by a factor of $2$, so the total number of configurations (now counting orientations) is

$$ \sum_{j=0}^32^{10-j}b_j=1024\cdot604800+512\cdot1814400+256\cdot1088640+128\cdot120960=1842462720\;. $$

That's a bit less than a half (about $49.6\%$) of the count $2^{10}\cdot10!$ that we'd get without taking into account the bend restrictions.

Now we need to take care of the self-intersections. Those can only occur if all bends are separate, as the chain can't intersect itself once we place two adjacent bends in opposite orientations. So we have at least one straight tile between any two bends; and if we also consider the source and lake (which we must to test for self-intersection), we also have at least one tile before the first bend and after the last bend. Thus, we can describe the sequence of bends and straight tiles by a quintuple $(v,w,x,y,z)$ of the numbers of tiles before, between and after the bends, where each entry is at least $1$ and they sum to $8$.

For a self-intersection to occur, the two bends in the middle have to turn the same way. Which of the two outer bends have to also turn the same way depends on the sequence. (At this point, I'd suggest to draw yourself a diagram. :-) If the first bend turns the same way as the inner bends and $y\ge w$ and $v\gt x$, there's an intersection independent of the orientation of the last bend. Likewise, if the last bend turns the same way as the inner bends and $w\ge y$ and $z\gt x$, there's an intersection independent of the orientation of the first bend. Moreover, if $w=y$ and all bends turn the same way, there's an intersection if $v+z\gt x$.

Thus, for $(2,1,1,1,3)$ and its mirror image there are three options for the outer bends (all except the one where they turn away from each other); for $(2,1,2,1,2)$ there is one option for the outer bends (the one where they turn towards each other), and for all other tuples with $y\ge w$ and $v\gt x$ or $w\ge y$ and $z\gt x$ there are two options for the outer bends (one must turn towards the other and the other's orientation is irrelevant). This last case comprises $(4,1,1,1,1)$, $(2,2,1,1,2)$, $(1,3,1,1,2)$, $(1,2,1,2,2)$, $(1,2,1,1,3)$, $(1,1,2,1,3)$, and their mirror images. Altogether, that's a total of $2\cdot3+1\cdot1+2\cdot6\cdot2=31$ cases. Each of these can have $2$ orientations of the bends in the middle, $2^6=64$ orientations of the straight tiles, $4!=24$ permutations of the bends and $6!=720$ permutations of the straight tiles, for a count of $31\cdot2\cdot64\cdot24\cdot720=68567040$ self-intersecting configurations, a small fraction of the total number of configurations. That leaves us with

$$1842462720-68567040=1773895680$$

admissible configurations, still almost half (about $47.7\%$) of the $2^{10}\cdot10!$ we'd get without restrictions.

Now, at the very end, we can divide by $2!^2=4$ to account for the fact that two bends and two straight tiles are exchangeable; the result is

$$ \frac{1773895680}4=443473920\;. $$

Here's Java code that checks this result by enumerating the chains.