Random Picks Not So Random

Let's consider the general problem, where the kth person picks from $\{ 0, 1, 2, \ldots, k \}$ .

Claim: The number of non-decreasing sequences that can be picked is equal to $C(n+1)$ , the nth catalan number .

Proof: One of the classifications of Catalan numbers, is that they are the number of ways to walk $n$ blocks north and $n$ blocks east, without crossing the diagonal line. This means that the line might touch $(x,x)$ , but would not reach a point $(x,y)$ with $y > x$ .
Given such a walk, we can easily create a set of numbers picked, where the kth number is equal to the maximum y-value when $x = k$ . We then have $y \leq x = k$ which satisfies the constraints of the problem. In this case, we ignore the walk on $x = n+1$ .
Conversely, given any non-decreasing sequence that satisfies the constraints, we can convert it into a walk that doesn't cross the diagonal line, by letting the person walk to the point $(k, f(k)$ , walk east one square and then walk up (if any) to the point $(k+1, f(k+1))$ . After the final person, the walk goes from $n, f(n)$ , walks east one square and then walks north to the point $(n+1, n+1)$ .
We see that these 2 maps are inverses of each other. Thus, this establishes the bijection. $_\square$

Hence, the number of such sequences is $C(6) = 132$ . The probability is thus $\frac{ C(6) } { 6!} = \frac{132}{720} = \frac{ 11}{60}$ .

---

Note: Can you explain why the walk to went for $n+1$ blocks by $n+1$ blocks instead of $n$ blocks by $n$ blocks? Hint: How does the end point affect the count?

There is likely a more elegant solution, but this is what I came up with...

I worked backwards, starting with Dandy and Endy.

Let $D(n) =$ Probaility of non-decreasing numbers if Dandy chooses $n$ .

$D(n) = \frac{6-n}{6}$

Now lets add in Candy.

Let $C(n) =$ Probability of non-decreasing numbers if Candy chooses $n$ .

$C(n) = \sum_{i=n}^{4}\frac{D(n)}{5}$

Now lets add in Brandy.

Let $B(n) =$ Probability of non-decreasing numbers if Brandy chooses $n$ .

$B(n) = \sum_{i=n}^{3}\frac{C(n)}{4}$

Finally lets add in Andy.

Let $A(n) =$ Probability of non-decreasing numbers if Andy chooses $n$ .

$A(n) = \sum_{i=n}^{2}\frac{B(n)}{3}$

This leaves,

$A(0) = \frac{1}{2}$

$A(1) = \frac{7}{60}$

So, the probability of non-decreasing results is:

$P = \frac{A(0) + A(1)}{2} = \boxed{\frac{11}{60}}$