If $4$ distinct integers $a, b, c, d$ are randomly selected from $n$ distinct integers, what is the probability that $a \lt b \lt c \lt d$?

Question

a. If $i$ distinct integers $r_1, r_2, \ldots,r_i$, i $\leq n$, are randomly selected (one after other) from n distinct integers, what is the probability that $r_1 < r_2 < \cdots < r_i$?

b. Does the probability you got in part a of the question change if < is replaced with $\leq$?

I know that a question similar to part 'a' of this question can be solved using the concept of Decision tree that orders the elements of the list, an application of which is to analyse the complexity of comparison-based sorting algorithm.

I came across a solution to part 'a' of the question that says the required probability is $C(n, i)/P(n,i)$, which is nothing but equal to the solution of the Decision tree based approach, which is $1/i!$.

What I don't understand is this - how $C(n,i)$ is equal to favourable number of outcomes and $P(n,i)$ is equal to total number of outcomes?

---

Figure: A decision tree for sorting three distinct elements.

Image taken from Discreet Mathematics and its Applications by Kenneth Rosen

Answer 1

$C(n,i)$ chooses $i$ integers from $n$ integers without giving importance to their order. Given such a set of $i$ integers, we can first order them in ascending order, and then assign the corresponding values to $r_1,r_2\dots r_i$ so that $r_1 \lt r_2 \lt \dots \lt r_i $.

$P(n,i)$ counts the total ways. Why? The number of choices for $r_1$ is $n$, for $r_2$ is $n-1$ and so on. That gives $$n(n-1)(n-2)\dots (n-i+1)=\frac{n!}{(n-i)!} = P(n,i) $$

Answer 2

For any given choice of $i$ integers from among the $n$ possible integers, only one permutation of these $i$ integers produces a valid result, because the $n$ integers are distinct.

There are $C(n,i)$ such choices of $i$ integers from among $n$ integers, and $P(n,i)$ permutations of $i$ integers from among $n$ integers.

Answer 3

Approach 1:

If you take letters $a, b, c, d$, there are $4!$ orders possible.
$a \lt b \lt c \lt d$ is one of them.

Hence the desired probability $\displaystyle = \frac{1}{4!}$

Approach 2: Place ( $ \ $ a $ \ $ b $ \ $ c $ \ $ d $ \ $) first, and now start placing other $(n-4)$ letters in between. The first letter of $(n-4)$ has $5$ places available. Once you place the first letter, you now have $6$ places for the next letter and so on.

Total number of favorable arrangements $ = 5 \times 6 \times 7 ... \times n$. Divide this by $n!$ which is total number of unrestricted arrangements.

Approach 3 (same as approach 2): As the order is fixed, you cannot permute (a b c d) so the number of arrangements are $\frac{n!}{4!}$. Divide this by $n!$

Answer 4

The probability does change if you replace $<$ with $\leq$ and you're sampling from your set of $n$ distinct integers with replacement.

In this situation, the number of unordered samples of size $i$ becomes ${n+i-1 \choose i}$ while the number of ordered samples of size $i$ is $n^i$.

So the probability that $r_1\leq \ldots \leq r_i$ equals $\frac{{n+i-1 \choose i}}{n^i}$

Answer 5

Another approach for solving $a)$ and $b)$ is the following:

$a)$ (I assume the numbers are selected without replacement): Each sequence of $i$ numbers can be represented as a vector in $\{0,1\}^n$ with exactly $i$ coordinates being equal to $1$. For example, let $n=9$ and $i=4$, then $$1< 4< 5<8 \longleftrightarrow \{1,0,0,1,1,0,0,1,0\}\\ 2<3<7<9 \longleftrightarrow \{0,1,1,0,0,0,1,1,0\}\\ 5<6<7<8\longleftrightarrow \{0,0,0,0,1,1,1,1,0\}$$ This way, in order to create any feasible sequence we only have to choose the $i$ coordinates where the $1$s will be placed. This lead us to a probability of $$\dfrac{\dbinom{n}{i}}{n!/(n-i-1)!}.$$

$b)$ (I assume the numbers are selected with replacement): In order to solve $b)$ all we have to do is to represent each sequence as a vector in $\{0,\ldots,n\}^i$ and count how many of these vectors have the sum of their coordinates equal to $i$. For example, let $n=9$ and $i=4$, then $$1\leq 2\leq 2\leq 6 \longleftrightarrow \{1,2, 0,0,0,1,0,0,0\}\\3\leq 3\leq 3\leq 3 \longleftrightarrow \{0,0,4,0,0,0,0,0,0\}\\ 1\leq 4\leq 8\leq 9 \longleftrightarrow \{1,0,0,1,0,0,0,1,1\}$$ By using stars and bars we get that the probability of having a favourable sequence is $$\dfrac{\dbinom{n+i-1}{i}}{n^i}.$$