Multinomial Coefficients and Farkle

This is the first in a series of planned articles about Farkle and its strategy. Lately, I’ve been spending alittle too much time playing Farkle on Facebook. In case you’re not familiar, Farkle is a dice game. It used to be pretty well-known before becoming overshadowed by the popularity of its distant cousin Yahtzee.

Like all the old games, there are a certain number of variations, but the Facebook version is pretty mainstream. For the purposes of this article, we’ll use that version of the rules.

The goal is to gain points by rolling scoring combinations with dice. The scoring combinations are as follows: three (or more) of a kind, 1’s and 5’s, three pairs, and a 1-2-3-4-5-6 straight. (For today’s purposes we don’t care how much the various scoring combinations are worth, only what they are.) You start with six dice. After each roll, you set aside one or more scoring combinations (you must score at least some dice after each roll). Then you can either roll the remaining dice, hoping for more points, or save your points and end the turn. If you use up all six dice in scoring combinations, you get a new set of six dice. But if ever you roll and you don’t get any scoring combinations, you “farkle out” and lose all the points you’ve scored this turn. (This is a bad thing.)

Today we’ll start with a fundamental question: if I roll a certain number of dice, how likely am I to farkle out?

Actually, this question is not so hard to answer. We will need just a few concepts from combinatorics to get ourselves going. (If all you want is the answer, there’s a summary at the end of the post.)

Multiplication of Possibilities.

As I type this, it is about lunchtime on a Sunday. Suppose I have four kinds of leftovers which could be my main lunch, seven kinds of fruits/vegetables for a side, and five different beverages. How many ways can I have lunch? The answr is simple: $4\times 7\times 5 = 120$ . (Convince yourself this is right.)

Another example. Suppose that on another day there are five plates of leftovers in the fridge (all different, each a single serving). How many ways can my wife, my daughter, and I have lunch? My wife has five choices. After she has chosen, my daughter has four choices, since there are four plates left. This leaves me with three choices. There are a total of $5 \times 4\times 3 =60$ possibilities. (Note that exactly what my choices are depends on the choices of my family, but, and this is crucial, how many choices I have does not change.)

Now imagine that I have a selection of six-sided dice. To make everything easier to picture, imagine that the dice are all different colors, so that you can tell them apart. If I roll one die (a red one), there are 6 (equally likely) outcomes. If I roll two dice (a red and a blue), there are 6 outcomes for the red die and 6 outcomes for the blue die, for a total of 36 (equally likely) outcomes. (I am considering “red 4, blue 2” and “red 2, blue 4” as two different outcomes, each as likely as “red 3, blue 3”. This turns out to be much less confusing than treating “4-2” as a single outcome which happens to be twice as likely as “3-3”.) If I roll three dice, there are $6^3=216$ possibilities, and so on.

Factorials.

An important sort of counting problem is the permutation. If there are n objects, there are $n!=n\cdot (n-1)\cdots 4\cdot 3\cdot 2\cdot 1$ different ways to put them in order. This is just a special case of the multiplication principle. If there are ten objects, then there are ten choices for which object goes first, nine remaining choices for the next object, eight remaining choices for the next, and so on.

For example, when four people decide to play a game like Sorry, there are twenty-four possible ways to determine turn order (who goes first, who goes second, who goes third, who goes last).

Multinomial coefficients.

What I’ve said so far is part of the standard high-school curriculum; what I’m about to say is not (but maybe it should be). Suppose we have a bunch of objects and we want to divide them into groups of specified sizes. For example, how many ways can I distribute twelve different toys to four children so that each child gets three toys? How many ways can I divide ten people into a two-person group, a three-person group, and a five-person group? As a variation on the second example, how many ways are there for a ten-person committee to form two (nonoverlapping) three-person subcommittees, leaving a group of four people not on a subcommittee?

The answers to questions like this are the multinomial coefficients; these particular multinomial coefficients are written $\left(\begin{array}{c} 12\\3,3.3.3 \end{array}\right)$ , $\left(\begin{array}{c} 10\\2,3,5 \end{array}\right)$ , $\left(\begin{array}{c} 10\\3,3,4 \end{array}\right)$ , respectively.

Note that the top number is the total number of objects and that the bottom numbers are the sizes of the groups; the bottom numbers always add up to the top number.

It turns out that there is a simple formula for computing these coefficients: $\left(\begin{array}{c} n!\\a_1,a_2,\ldots,a_k \end{array}\right)=\frac{n!}{(a_1!)(a_2!)(a_3!)\cdots(a_k!)}$ . So, for example, there are $\frac{10!}{(2!)(3!)(5!)}=2520$ ways for ten people to form groups of size two, three, and five.

You may remember learning about combinations, sometimes written $\left(\begin{array}{c} n\\r \end{array}\right)$ , which are the number of ways to select $r$ things from a pile of $n$ different things. This is just a special case of what we have been discussing: $\left(\begin{array}{c} n\\r \end{array}\right)$ is what we’ve been writing $\left(\begin{array}{c} n \\r,n-r \end{array}\right)$ . Selecting $r$ things is the same as dividing the $n$ things into the group of $r$ things we take and a group of $n-r$ things we don’t want.

Why the term multinomial coefficient? Because, if you were to fully expand $(a+b+c+d)^{123}$ and collect like terms, then the coefficient of $a^{30}b^{12}c^{34}d^{47}$ is $\left(\begin{array}{c} 123\\30,12,34,47 \end{array}\right)$ .

The main question.

Okay, back to rolling dice.

6 dice. First of all, 1’s and 5’s are scoring combinations all by themselves, so the only way to farkle out is to roll only 2’s, 3’s, 4’s, and 6’s. Rolling three-of-a-kind scores, so we can’t throw more than two of any one number. Three pair also scores, so the only way to farkle out with six dice is to roll two pairs and two singletons. But how many ways can this happen? There are two separate multinomials happening here. First, we choose which two numbers are the pairs and which two numbers the singletons — there are $\left(\begin{array}{c} 4\\2,2 \end{array}\right)=6$ possibilities here. Then, we choose which dice are in the first pair, which are in the second pair, which is the first singleton, and which is the second singleton — there are $\left(\begin{array}{c} 6\\2,2,1,1 \end{array}\right)=180$ possibilities here. So there are a grand total of $6\cdot 180 = 1080$ possible losing throws with six dice. There are $6^6$ total throws, so the probability of losing is $\frac{1080}{6^6}=\frac{5}{216}$ . (Between 2 and 3 percent; the odds against are about 42:1.)

5 dice. This is similar to the previous case, except that there are two possible configurations. We might get two pairs and a singleton, or we might get a pair and three singletons. Working as in the previous paragraph, two pairs and a singleton can happen in $\left(\begin{array}{c} 4\\2,1,1 \end{array}\right) \left(\begin{array}{c} 5\\2,2,1 \end{array}\right)=360$ ways while a pair and three singletons can happen in $\left(\begin{array}{c} 4\\1,3 \end{array}\right) \left(\begin{array}{c} 5\\2,1,1,1 \end{array}\right)=240$ ways. This is a total of 600 losing throws, out of the total $6^5$ throws. The probability of losing with five dice is $\frac{600}{6^5}=\frac{25}{324}$ . (This is between 7 and 8 percent, or about 12:1 against.)

4 dice. Now there are three possible configurations. We might get two pairs, or we might get a pair and two singletons, or we might get four singletons. Working as in the previous paragraph, two pairs can happen in $\left(\begin{array}{c} 4\\2,2\end{array}\right) \left(\begin{array}{c} 4\\2,2 \end{array}\right)=36$ ways, a pair and two singletons can happen in $\left(\begin{array}{c} 4\\1,2,1 \end{array}\right) \left(\begin{array}{c} 4\\2,1,1 \end{array}\right)=144$ ways, and four singletons can happen in $\left(\begin{array}{c} 4\\4 \end{array}\right) \left(\begin{array}{c} 4\\1,1,1,1 \end{array}\right)=24$ . This is a total of 204 losing throws, out of the total $6^4$ throws. The probability of losing with five dice is $\frac{204}{6^4}=\frac{17}{108}$ . (This is between 15 and 16 percent, or about 16:3 against.)

3 dice. We could do this as before, but this case is actually simpler another way. There are $4^3=64$ ways to roll only losing numbers, and of these 4 will still score because they are three-of-a-kind throws. So there are 60 losing throws out of 216 total throws. The probability of losing with three dice is $\frac{5}{18}$ . (This is between 27 and 28 percent, or about 5:2 against.)

2 dice. There are $4^2=16$ losing throws out of $6^2=36$ total throws. The probability is $\frac{4}{9}$ . (This is between 44 and 45 percent, or 5:4 odds.)

1 die. Evidently, 4 of the 6 numbers lose. The probability is $\frac{2}{3}$ . (This is between 66 and 67 percent, or 2:1 odds.)

Summary.

#dice prob of Farkle %%%%

  6        5/16       2.3
  5       25/324      7.7
  4       17/108     15.7
  3        5/18      27.8
  2        4/9       44.4
  1        2/3       66.7

This entry was posted on Monday, July 27th, 2009 at 06:00 and is filed under Articles. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

7 Responses to Multinomial Coefficients and Farkle

John says:

16 August 2009 at 20:54

Nice work. The next step would be to determine odds for getting three-of-a-kind on second and subsequent rolls to help the player decide if it is worth risking a Farkle (the odds for which you have expertly provided) in order to score 200+ points on the next roll.

Depending on my situation in a game, I might risk the 16% chance of a Farkle rolling 4 dice if it could earn me 200, 400, 500, 600, or 1000 points. But what are the odds of rolling 3-kind with 5, 4, and 3 dice?

Reply
- Cap Khoury says:
  
  16 August 2009 at 22:04
  
  This is not so hard; actually, we did harder computations in the main post.
  
  With 3 dice, there are 6 possible three-of-a-kinds out of 216 possible throws. The odds are 35:1 against (2.78%).
  
  With 4 dice, there are 6 possible four-of-a-kinds and (4)(6)(5)=120 possible three-of-a kinds out of 1296 possible throws. The odds of three-or-more-of-a-kind are 65:7 against (9.72%).
  
  With 5 dice, there are 6 possible five-of-a-kinds, (5)(6)(5)=150 possible four-of-a kinds, and (10)(6)(5)(5)=1500 possible three-of-a-kinds out of 7776 possible throws. The odds of three-or-more-of-a-kind are 85:23 against (21.30%).
  
  While this is the next “half-step”, I’m not sure I agree that we’ve taken a full step here. The situation is subtle; combinatorics only provide part of the story. With the numbers we already have (and a few more that aren’t much harder to get), we could analyze pretty completely the problem of maximizing the average value of a turn in FARKLE. The catch is, that’s not how you win at FARKLE. Even if we neglect the effects of knowing how your score compares to your opponent’s score at any given time, there remains the fact that the goal is to minimize the number of turns it takes to get to 10000, which is not quite the same as maximize the average score per turn. And we are even further from a solution to what facebook calls “FARKLE simple”, where the goal is to get the highest score in 10 turns. Here we aren’t really trying to maximize our average score. More likely we want to maximize our expected *high* score over a run of games. Or perhaps we want a specific score (in order to outrank a friend, say), and we want to maximize the probability of getting that score or better. These seemingly small differences in goal have big strategic ramifications.
  
  I’ll try to peel back the next layer of the onion in the Thursday post. Stay tuned, and thanks for the comment!
  
  Reply
Farkle Odds « The Solarium says:

2 September 2009 at 13:08

[…] where the “!” denotes the factorial. ( There is a good discussion of these factors at Not About Apples, and it even happens to be in the context of Farkle! ) The table below shows die combinations with […]

Reply
jon ah says:

6 January 2010 at 23:54

how would u go across 3 dice with using multimomials? i am unable to figure it out on my own, and i am very curious.

Reply
- Cap Khoury says:
  
  9 January 2010 at 12:16
  
  As always, all losing throws would have only 2, 3, 4, and 6. A losing throw with three dice would either be a pair and a singleton or else three singletons. A pair and a singleton can happen in $\left(\begin{array}{c} 4\\1,2,1 \end{array}\right) \left(\begin{array}{c} 3\\2,1 \end{array}\right)=36$ . Three singletons can happen in $\left(\begin{array}{c} 4\\3,1 \end{array}\right) \left(\begin{array}{c} 3\\1,1,1 \end{array}\right)=24$ . This a total of 60 losing throws, out of 64 total throws.
  
  (This checks with what I said in the post, that there are 4 winning throughs.)
  
  Reply
Maximizing Expected Scores in the Game of Zilch < Matt's Maniacal Musings says:

29 August 2010 at 16:53

[…] Multinomial Coefficients and Farkle, Cap Khoury, Jul. 2009. […]

Reply
julie king says:

11 February 2011 at 07:43

HAPPY B-DAY !!! YOUR FARKLE PAL

Reply