# Combination/permutations question where repetition is allowed

So I guess this is a combination/permutations question where repetition is allowed.

What is the % chance that six six-sided dice will show at least 3 duplicates of the same number or that there will be at least 3 numbers in ascending value?

These questions are sufficiently messy that a brute force calculation seems advisable. Let formal variables $x_1, x_2, \ldots, x_6$ correspond to the six possible outcomes. The probability distribution of the outcomes is represented by the polynomial

$$d_6 = \frac{1}{6}x_1 + \frac{1}{6}x_2 + \cdots + \frac{1}{6}x_6$$

and so the probability distributions of combinations of outcomes observable among $n$ of these dice, thrown independently, can be represented by expanding $d_6^n$ into monomials. For example,

$$d_6^2 = \left(x_1^2+x_2^2+x_3^2+x_4^2+x_5^2+x_6^2+2 x_2 x_1+2 x_3 x_1+2 x_4 x_1+2 x_5 x_1+2 x_6 x_1+2 x_2 x_3+2 x_2 x_4+2 x_3 x_4+2 x_2 x_5+2 x_3 x_5+2 x_4 x_5+2 x_2 x_6+2 x_3 x_6+2 x_4 x_6+2 x_5 x_6\right)/36$$

shows that individual duplicates (represented by $x_1^2, x_2^2, \ldots$) each have $1/36$ chance of occurring in two dice, and therefore some duplicate has a $1/36+1/36+\cdots+1/36=1/6$ chance of occurring. This summation is readily done by replacing all the $x_i$ by some common variable, say $y$.

To compute the chance that $n$ dice will not exhibit three of the same number, nor three numbers in a row (which is what I take "ascending value" to mean), construct the ideal

\eqalign{ \mathbb{Q}(x_1, x_2, \ldots, x_6) \supset \mathcal{I} = \langle &x_1^3-1, x_2^3-1, \ldots, x_6^3-1; \\ &x_1x_2x_3-1, x_2x_3x_4-1, x_3x_4x_5-1, x_4x_5x_6-1 \rangle }

and compute $d_6^n \mod \mathcal{I}$ using the lowest possible total degrees. Anything of degree $n$ that remains represents a combination where such an event does not occur. From this the desired probability can be read off. This computation is done efficiently by repeatedly multiplying by $d_6$ and reducing modulo $\mathcal I$.

For instance, suppose we wanted to find the chance of throwing two of a kind with two dice. We would compute $d_6^2$ modulo the ideal generated by $\mathcal{J} = \{x_1^2-1, x_2^2-1, \ldots, x_6^2-1\}$ and then replace all the $x_i$ by $y$, giving

$$d_6^2 = \frac{1}{6} + \frac{5}{6}y^2\mod \mathcal{J},$$

from which the chance $\frac{5}{6}$ of not doing this is found in the coefficient of $y^2$, once again giving $1 - \frac{5}{6} = \frac{1}{6}$ as the answer.

Here is a tabulation of the chances asked for in the question as a function of $n$, followed by the Mathematica 9 code that generated it.

  n     Chance
---  ---------
2          0
3       5/36
4        3/8
5      17/27
6    269/324
7    613/648
8  3853/3888
9          1


(Indeed, there is no way to avoid getting a triple or a sequence of three in a row with nine dice, as one can check.)

die = Sum[Subscript[x, i], {i, 1, 6}]/6;
relations = Join[Table[Subscript[x, i]^3 - 1, {i, 1, 6}],
Table[Subscript[x, i] Subscript[x, i + 1] Subscript[x, i + 2] - 1, {i, 1, 4}]];
MatrixForm@Table[{n, 1 - Coefficient[Nest[PolynomialMod[# die, relations] &, die, n - 1]
//. {Subscript[x, _] -> y}, y, n]}, {n, 2, 9}]

• (The calculations can be made more efficient by removing all lower-degree polynomials that are produced at any step.) In effect, all that's going on here is to exploit the sophisticated algorithms of a computer algebra system to keep track of all the possible combinations as each additional die is introduced. – whuber Nov 19 '14 at 22:54