What is the probability of getting a Yahtzee within $n$ rolls? Say there is the standard situation in Yahtzee with $5$ $6$-sided dice. The player tries from the outset to get a Yahtzee. The player is given the conventional liberty of choosing which dice to re-roll in the next roll, as well as the new liberty of having as many rolls as necessary to achieve a Yahtzee, instead of the normal $3$ rolls. Obviously the probability of getting a Yahtzee within $1$ roll is $\frac{1}{1296}$, and the probability of getting a Yahtzee within $n$ rolls approaches $1$ as $n\to \infty$. But what happens in between, as $n$ goes from $2$ to $\infty$?    
 A: First we have to describe the optimal strategy for getting a Yahtzee. It's not hard to see that it's given by:


*

*If none of the current dice match, reroll all $5$ dice

*If $2$ match, reroll the other $3$. (If there are two twos-of-a-kind, choose one arbitrarily -- say, the higher one -- to keep.)

*If $3$ match, reroll the other $2$.

*If $4$ match, reroll the other $1$.

*If $5$ match, you're done. 


So it makes sense to describe the game as being in one of the above $5$ states. You'll need to compute the probabilities of moving from any state to any other state. Let $P$ be the matrix where $P_{ij}$ ($i$th row, $j$th column) is the probability of moving from state $j$ to state $i$. (Note that the matrix must be lower triangular -- can you see why?) The game starts in state $1$ (no matches if you haven't rolled any dice yet), so let $v$ be the column vector with a $1$ in the first entry and the others $0$. Then $P^nv$ gives the probabilities of the game being in each state after $n$ rolls. In particular, you're interested in the fifth entry of $P^nv$.
