Probability Challenge: Find Interval of Integers Drawn from Urn

[lfdahl]

An urn contains $n$ balls numbered $1, 2, . . . , n$. They are drawn one at a time at random until the urn is empty.
Find the probability that throughout this process the numbers on the balls which have been drawn is an interval of integers.
(That is, for $1 \leq k \leq n$, after the $k$th draw the smallest number drawn equals the largest drawn minus $k − 1$.)

 

[Opalg]

An urn contains $n$ balls numbered $1, 2, . . . , n$. They are drawn one at a time at random until the urn is empty.
Find the probability that throughout this process the numbers on the balls which have been drawn is an interval of integers.
(That is, for $1 \leq k \leq n$, after the $k$th draw the smallest number drawn equals the largest drawn minus $k − 1$.)

[sp]Call the process "allowable" if it satisfies that condition.

Suppose that the first ball drawn is numbered $r$. If the process is to be allowable then the number on each subsequent ball drawn must be next to either the lower end ($L$) or the upper end ($U$) of the existing consecutive run of integers. There are $n-1$ more balls to be drawn, so the process is completely specified by a string of $n-1$ letters $L$ and $U$. Also, there are exactly $r-1$ numbers less than $r$, so the string must contain $r-1$ $L$s (and $n-r$ $U$s). The number of such strings is $$n-1\choose r-1$$. Therefore there are $$n-1\choose r-1$$ allowable processes starting with $r$. So the total number of allowable processes is $$\sum_{r=1}^n{n-1\choose r-1} = 2^{n-1}.$$ The number of all ways of drawing the balls from the urn is $n!$. Therefore the probability of a process being allowable is $\dfrac{2^{n-1}}{n!}.$

[/sp]

 

[lfdahl]

[sp]Call the process "allowable" if it satisfies that condition.

Suppose that the first ball drawn is numbered $r$. If the process is to be allowable then the number on each subsequent ball drawn must be next to either the lower end ($L$) or the upper end ($U$) of the existing consecutive run of integers. There are $n-1$ more balls to be drawn, so the process is completely specified by a string of $n-1$ letters $L$ and $U$. Also, there are exactly $r-1$ numbers less than $r$, so the string must contain $r-1$ $L$s (and $n-r$ $U$s). The number of such strings is $$n-1\choose r-1$$. Therefore there are $$n-1\choose r-1$$ allowable processes starting with $r$. So the total number of allowable processes is $$\sum_{r=1}^n{n-1\choose r-1} = 2^{n-1}.$$ The number of all ways of drawing the balls from the urn is $n!$. Therefore the probability of a process being allowable is $\dfrac{2^{n-1}}{n!}.$

[/sp]

Awesome - thankyou for your participation, Opalg!