A fair die is rolled four times. What is the probability that each of the final three rolls is at least as large as the roll preceding it? 
A fair die is rolled four times. What is the probability that each of the final three rolls is at least as large as the roll preceding it?

This question is from the AIME 2001.
I am looking for a solution that does not use brute-force methods.

Considering a starting point at the number $1$, the problem can be formulated as finding the number of integer tuples $(x_1,x_2,x_3,x_4)$ such that:


*

*$x_1\ge0,x_2\ge0,x_3\ge_0,x_4\ge0$

*$x_1+x_2+x_3+x_4\le5$  


Each element $x_i$ in a tuple represents the increment in throwing the die for the $i-th$ time over what was obtained on the $(i-1)-st$ throw. We consider the $0-th$ throw to be $1$. Hence, there is a one-to-one mapping between all qualifying dice throws and all tuples that meet the stated conditions.
I know the total number of possible dice rolls is $6^4$ but am unsure how to count the number of tuples.
The brute-force method is to simply count the number of distinct solutions to each of $x_1+x_2+x_3+x_4=0,\quad x_1+x_2+x_3+x_4=1,\ldots$ by listing all ways of making up the sums accounting for permutations. For example:
$$\underline{x_1+x_2+x_3+x_4=2} \\
\begin{array}{crl}
(0,0,0,2) & 4 & \text{perms} \\
(0,0,1,1) & 6 & \text{perms} \\
\text{total} & 10 
\end{array}$$
But I think there must be a more elegant way.
 A: We can always integrate:
\begin{eqnarray}
\mathbb{P}(x_1 \le x_2 \le x_3 \le x_4 ) &=& \sum_{x=1}^6 \mathbb{P}(x \le x_2 \le x_3 \le x_4) \mathbb{P}(x_1 = x) \\
&=& \sum_{x=1}^6 \sum_{y = x}^6 \mathbb{P}(y \le x_3 \le x_4) \mathbb{P}(x_2 = y) \mathbb{P}(x_1 = x) \\
&=& \sum_{x=1}^6 \sum_{y = x}^6 \sum_{z=y}^6 \mathbb{P}(z \le x_4) \mathbb{P}(x_3 =z) \mathbb{P}(x_2 = y) \mathbb{P}(x_1 = x) \\
&=&  6^{-4}  \sum_{x=1}^6 \sum_{y = x}^6 \sum_{z=y}^6 7-z \\
&=&6^{-4}  \sum_{x=1}^6 \sum_{y = x}^6 \frac{1}{2} \left( y^2 -15y +56 \right) \\
&=& 6^{-4}  \sum_{x=1}^6 -\frac{x^3}{6}+4x^2- \frac{191x}{6}+84\\
&=& \frac{126}{6^4}
\end{eqnarray}
A: Add a fifth variable, $x_5$, to take up the slack, and count the solutions in non-negative integers to $$x_1+x_2+x_3+x_4+x_5=5\;;$$ by the standard stars and bars argument this is $\binom{5+5-1}{5-1}=\binom94=126$.
A: An alternative approach is to use an absorbing Markov chain with 8 states. This approach is less elegant but easier to understand.
A: A somewhat easier approach (in that it doesn't require quite as much up-front insight as Brian M. Scott's approach) is to combine a bit of thought with a bit of brute force . . .
If we know that two dice are restricted to a range of size $n$, and that the second needs to be at least as large as the first, then there are $1+2+\dots+n$ possible pairs. We can easily tabulate this:


*

*$n = 1$: $1 = 1$

*$n = 2$: $1 + 2 = 3$

*$n = 3$: $1 + 2 + 3 = 6$

*$n = 4$: $1 + 2 + 3 + 4 = 10$

*$n = 5$: $1 + 2 + 3 + 4 + 5 = 15$

*$n = 6$: $1 + 2 + 3 + 4 + 5  + 6 = 21$


(These are the triangle numbers.)
Now, suppose that $x_3$ is known. Then $x_1$ and $x_2$ are restricted to the range $[1, x_3]$, which is of size $x_3$, which we can use the above table for; and $x_4$ is restricted to the range $[x_3, 6]$, which is of size $6 - x_3 + 1$, which is easy to inspect.
So, we can easily tabulate the number of possibilities for each $x_3$:


*

*$x_3 = 1$: $1 \times 6 = 6$

*$x_3 = 2$: $3 \times 5 = 15$

*$x_3 = 3$: $6 \times 4 = 24$

*$x_3 = 4$: $10 \times 3 = 30$

*$x_3 = 5$: $15 \times 2 = 30$

*$x_3 = 6$: $21 \times 1 = 21$


Adding these up, we get a total of $126$ across all values of $x_3$.
