Note: there are errors contained in this post as described in the comments below. See errata here.
So let us instead answer the question of how many initial states there are in Onitama.
In every game of Onitama, 5 out of the total 16 unique cards are used. I emphasize that the cards are unique, because it matters whether or not we can distinguish between them. Suppose we draw the 5 cards one at a time. For the first card, there are 16 possibilities. When selecting the second card there is one less card, so there are 15 remaining possibilities. This continues until the the fifth card, for which there are $16-4=12$ possibilities. Putting this together, the number of ways in which to draw 5 cards out of 16 unique cards, $n_0$, is given by the following equation.
\begin{align}
n_0 &= 16 \cdot 15 \cdot 14 \cdot 13 \cdot 12 \\
&= 524160
\end{align}
That is a lot of ways. But if we're interesting in the number of sets of 5 cards then we've over counted. For example, we've counted drawing Ox, Elephant, Tiger, Rabbit, then Cobra as distinct from Cobra, Rabbit, Elephant, Tiger, then Ox. To look at the number of combinations we have to divide our previous result by the number of ways we can order the selected 5 cards. Similar to selecting the cards above, we can select the 5 cards one at a time to determine the number of ways to order them. This works out to be the following.
\begin{align}
5! &= 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 \\
&= \prod_{i=1}^5 i
\end{align}
We say this as "five factorial" and it is equal to the product of all whole numbers from 1 to 5, or in general,
\begin{align}
n! &= \prod_{i=1}^n i .
\end{align}
Thus, the number of ways to select a set of 5 cards out of 16 unique cards is,
\begin{align}
n_1 &= \frac{16 \cdot 15 \cdot 14 \cdot 13 \cdot 12}{5!} \\
&= 4368.
\end{align}
This number of combinations is often said as "16 choose 5'', and can be written as follows, depending on the type of notation used.
\begin{align}
n_1 = \,_{16} C_5 = \binom{16}{5} = \frac{16!}{(16-5)! \cdot 5!}
\end{align}
While this is the number of ways to select a set of 5 cards out of 16, it is not the number of initial states in Onitama. This is because the location of the 5 cards matters, but in a particular way such that $n_0$ is not the number we're looking for. Each player starts with a hand of two cards, but whether those two cards are Ox and Cobra or Cobra and Ox doesn't matter. That means we have three distinct locations that these five cards go, two of which each hold two cards.
What about the two players? Are they interchangeable as well? In some sense yes, in some sense no (people are, of course, not interchangeable). We aren't going to count the number of starting states based on who is playing the game, as it doesn't seem to make sense that the number of states would depend on the world population. On the other hand, it does matter as to whether blue or red has a given pair of cards, since either blue or red makes the first move, as determined by the fifth card. Thus, swapping the cards in the blue and red players' hands gives a different starting state, as the first player has different options.
Given these constraints, we can find the number of ways to assign the 5 selected cards to the two hands and the extra move card. We can do this by taking the existing $5!$ orderings, but then divide by 2 in consideration of the fact that the order of drawing the blue player's hand doesn't matter, and then divide by 2 again because the order of drawing the red player's hand doesn't matter. This works out to,
\begin{align}
\frac{5!}{2 \cdot 2} &= 5\cdot 3 \cdot 2 = 30,
\end{align}
ways to meaningfully arrange the 5 selected cards. For each set of 5 cards, we have 30 ways to arrange them. Thus, to get the total number of initial configurations we multiple the number of ways to select 5 cards by the number of ways to arrange 5 cards into the two hands and extra card.
\begin{align}
n_2 &= \binom{16}{5} \cdot \frac{5!}{2 \cdot 2} \\
&= \frac{16!}{(16-5)! \cdot \require{cancel}\cancel{5!}} \cdot \frac{\require{cancel}\cancel{5!}}{2 \cdot 2} \\
&= \frac{16 \cdot 15 \cdot 14 \cdot 13 \cdot 12}{2 \cdot 2} \\
&= 131040
\end{align}
However, there's one more wrinkle left. To see it, we have to look at the cards themselves. You can see a picture of them here. Half of the cards are symmetric (Tiger, Crab, etc.) while the other half are asymmetric and come in pairs. Frog is the mirror of Rabbit. A game with four symmetric cards and an asymmetric card is essentially the same as a game with those same four symmetric cards and the mirror of the asymmetric card. They're isomorphs of each other. Actually, there's a little wrinkle to that fact, which is that the mirrored cards all have opposite starting colors. This doesn't affect the number of unique starting positions, just which ones are isomorphs of each other. For example, if blue has Tiger and Crab, red has Monkey and Crane, and the extra card is Frog (red starts), then the isomorphic game is blue has Monkey and Crane, red has Tiger and Crab, and the extra card is Rabbit (blue starts). We've just swapped red and blue, left and right, otherwise it's the same.
Next, we need to determine how many initial positions have isomorphs. Expanding from the specific example, above, we're looking for cases where there's at least one asymmetric card, but not its mirror image. Let's count the number of sets of 5 cards that fulfill this condition. We'll first select one of the 8 asymmetric cards randomly. The rest of the cards can be anything except the mirror to the first selected card. That means we are choosing 4 cards out of 14 options, as there are fifteen cards left but one is off limits. The number of ways to do this is,
\begin{align}
n_3 &= 8 \cdot \binom{14}{4} \\
&= 8 \cdot \frac{14!}{(14-4)! \cdot 4!}\\
&= 8008 .\\
\end{align}
We only want to keep half of these, so the number of ways to select 5 cards, excluding isomoprhs is as follows.
\begin{align}
n_4 &= n_1 - \frac{n_3}{2} \\
&= \binom{16}{5} - \frac{8}{2} \cdot \binom{14}{4} \\
&= \frac{16!}{(16-5)! \cdot 5!} - 4 \cdot \frac{14!}{(14-4)! \cdot 4!}\\
&= \frac{16!}{11! \cdot 5!} - 4 \cdot \frac{14!}{10! \cdot 4!}\\
&= \frac{16!}{11! \cdot 5!} - 4 \cdot \frac{11 \cdot 5 \cdot 14!}{11! \cdot 5!}\\
&= (16 \cdot 15 - 4 \cdot 11 \cdot 5 ) \cdot \left ( \frac{14!}{11! \cdot 5!} \right )\\
&= (240 - 220) \cdot \left (18.2 \right )\\
&= 364
\end{align}
To get the number of initial positions with isomorphs, we need to multiply by $\frac{5!}{2 \cdot 2}$ as before.
\begin{align}
n_5 &= n_4 \cdot \frac{5!}{2 \cdot 2} \\
&= \left (\binom{16}{5} - \frac{8}{2} \cdot \binom{14}{4} \right ) \cdot \frac{5!}{2 \cdot 2} \\
&= 364 \cdot 30 \\
&= 10920
\end{align}
While I like your idea, there is an error in the calculations.
ReplyDeleteClearly, as n_3 is the number of sets of 5 cards satisfying a certain condition while n_1 is the number of sets of 5 cards, we should have that n_3 is at most n_1, yet according to your calculations n_3>n_1.
The problem is that you're counting sets with multiple unpaired asymmetric cards multiple times: once for each unpaired asymmetric card, as any of them can be the initial card you pick.
In fact, I'd count the entire thing differently. The initial positions of any set of cards are exactly the set of isomorphs of the initial positions of any other set of cards that can be obtained by just flipping unpaired asymmetric cards to the other card in the pair. That means that it literally doesn't matter which exact unpaired asymmetric cards are in a set; you just need to know which pair it comes from.
Hence the number of starting positions modulo isomorphisms is actually $\frac{5!}{2\cdot 2}\cdot \sum_{k=0}^4\sum_{p=0}^{\lfloor \frac{5-k}{2}\rfloor}\binom{4}{k}\binom{4-k}{p}\binom{8}{5-k-2p} = 45360$.
As to where my summation comes from: I'm counting sets with unpaired asymmetric cards from $k$ pairs, (as we're counting modulo isomorphism, it doesn't matter which cards) and $p$ pairs of asymmetric cards. There are $\binom{4}{k}$ ways of choosing the pairs for the unpaired asymmetric cards, $\binom{4-k}{p}$ ways of choosing the pairs of asymmetric cards, and $\binom{8}{5-k-2p}$ ways of choosing the remaining symmetric cards.
DeleteBob, I see what you mean about over counting and especially like your $n_3 > n_1$ check.
ReplyDeleteI think I follow your equation but need time to digest and update my post.
Thank you!
Upon further review, the equation above is incomplete. Specifically, $\binom{4}{k}$ does not specify the number of ways to choose unpaired asymmetric cards when $k > 1$. This is because we must not only select the pair, but which card inside the pair. When $k=1$ this cancels out because you're looking at the unique cases. Consider $k=2$, though. If we consider each pair to have a left and right version, then we could pick left left, right right, left right, or right left. The first and second two sets are isomorphs of each other, but left left is not an isomorph of left right. Thus we have an additional factor of $2^k$ to select each card inside the pairs, and $1/2$ to remove isomorphs. In my errata, now linked above, I use this approach integrated into my own, and check it against $n_1$ to make sure I'm not over or under counting.
ReplyDelete