Probability of choosing $n$ numbers from $\{1, \dots, 2n\}$ so that $n$ is 3rd in size

Question

We uniformly randomly choose $n$ numbers out of $2n$ numbers from the group $\{1, \dots, 2n\}$ so that order matters and repetitions are allowed. What is the probability that $n$ is the $3^{\text{rd}}$ number in size in the chosen series? (= there are only two bigger than $n$)
Note that if a number that is bigger than $n$ was chosen more than once, we still count it as one number bigger than $n$.

Example: $n = 5, \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$
$7, 1, 5, 9, 9$ - ok
$2, 2, 10, 5, 7$ - ok
$6, 6, 3, 5, 5$ - not ok, 5 is $2^{\text{nd}}$ in size

My lead was to first choose 2 numbers that are bigger than $n$ out of the n numbers that are bigger than $n$ in the group $\{1, \dots, 2n\}$. Then in order to complete a series of $n$ numbers I need to choose $n-3$ more from the numbers that are equal or smaller than $n$, but then I figured this is not right as a series could be formed from the 2 numbers bigger than $n$ and $n$ itself without any additional numbers. At this point I have no additional leads and could very much use your assistance and guidance.

Answer 1

You can use the inclusion-exclusion principle.

Let $S:=$ The event of getting a valid sequence of numbers ($n$ numbers $\le n$ and 2 numbers $\gt n$)

$A_1 :=$ The event that $n$ does not appear in the sequence

$A_2 :=$ The event that one of the larger numbers than $n$ does not appear in the sequence

$A_3 :=$ The event that the second number that is larger than $n$ does not appear in the sequence

Now, the probability we are looking for is the probability that S occurs but the union of $A_1,\, A_2,\, A_3$ does not occur.

We have the formula

$$ \Pr \left[S\setminus \bigcup_{i=1}^{3}A_i \right] = \Pr \left[ S \right] - \sum_{i=1}^{3} \Pr\left [ A_i \right ] + \sum_{1\leq i< j\leq 3} \Pr\left [ A_i\cap A_j \right ] - \sum_{1\leq i<j<k\leq 3} \Pr\left [ A_i\cap A_j\cap A_k \right ] $$

Let's calculate the probabilities of the events defined above.

First of all, our sample space $\Omega$ is all sequences of $n$ numbers from the group $\{1, 2, \ldots, 2n\}$.

So $\left| \Omega \right| = \left( 2n \right)^n $.

Now, $ \Pr \left[S \right] = \frac{\left ( n+2 \right )^n}{\left ( 2n \right )^n} $ (we have $n$ numbers $\le n$ and 2 numbers greater than $n$)

Similarly, $ \Pr \left[A_1 \right] = \Pr \left[A_2 \right] = \Pr \left[A_3 \right] = \frac{\left ( n+1 \right )^n}{\left ( 2n \right )^n} $

We also have to calculate the intersections.

$ \Pr\left [ A_i\cap A_j \right ] = \frac{n^n}{\left ( 2n \right )^n} \; ($for $ 1\leq i<j\leq 3 )$ - notice there are 3 such intersections. And also there is the intersection of all three:

$ \Pr\left [ A_1\cap A_2\cap A_3 \right ] = \frac{\left ( n-1 \right )^n}{\left ( 2n \right )^n} $

One last thing - there are $ \binom{n}{2} $ ways to choose those 2 numbers that are greater than $n$.

Now, we'll plug everything in the inclusion-exclusion formula and multiply by $ \binom{n}{2} $, and we'll get:

$$ \Pr \left[S\setminus \bigcup_{i=1}^{3}A_i \right] = \binom{n}{2} \left( \frac{\left ( n+2 \right )^n}{\left ( 2n \right )^n} - 3\frac{\left ( n+1 \right )^n}{\left ( 2n \right )^n} +3\frac{n^n}{\left ( 2n \right )^n} - \frac{\left ( n-1 \right )^n}{\left ( 2n \right )^n} \right) = \binom{n}{2} \frac{\left ( n+2 \right )^n - 3\left ( n+1 \right )^n + 3n^n - \left ( n-1 \right )^n}{\left ( 2n \right )^n} $$

Answer 2

In a favourable result, $2$ of the $n$ numbers from $n+1$ to $2n$ occur, which can be chosen in $\binom n2$ ways, and $k$ of the $n-1$ numbers from $1$ to $n-1$, which can be chosen in $\binom{n-1}k$ ways with $0\le k\le n-3$. Together with $n$, which must also occur, that's $k+3$ numbers. The number of ways to partition the $n$ draws into $k+3$ non-empty subsets is given by the Stirling number of the second kind $\def\stir#1#2{\left\{{#1\atop #2}\right\}}\stir n{k+3}$. The $k+3$ numbers can be assigned to these subsets in $(k+3)!$ different ways. The desired probability is the number of favourable results divided by the total number $(2n)^n$ of equiprobable results:

\begin{align} &(2n)^{-n}\binom n2\sum_{k=0}^{n-3}\binom{n-1}k(k+3)!\stir n{k+3} \\ ={}&(2n)^{-n}\binom n2\sum_{k=0}^\infty\binom{n-1}k(k+3)!\stir n{k+3} \\ ={}&(2n)^{-n}\binom n2\sum_{k=0}^\infty\binom{n-1}k\sum_{j=0}^{k+3}(-1)^{k+3-j}\binom{k+3}jj^n \\ ={}&(2n)^{-n}\binom n2\sum_{k=0}^\infty\binom{n-1}k\sum_{j=0}^\infty(-1)^{k+3-j}\binom{k+3}jj^n \\ ={}&(2n)^{-n}\binom n2\sum_{j=0}^\infty(-1)^{j+1}j^n\sum_{k=0}^\infty(-1)^k\binom{n-1}k\binom{k+3}j \\ ={}&(2n)^{-n}\binom n2\sum_{j=0}^\infty(-1)^{j+n}j^n\binom3{j-n+1}\tag{*} \\ ={}&(2n)^{-n}\binom n2\sum_{j=0}^3(-1)^{j+1}\binom3j(n+j-1)^n\;, \end{align}

where the line marked with $(*)$ is obtained by a Vandermondesque summation as derived on this very useful page. Unpacking the sum over $j$ leads to agreement with the other two answers.

Answer 3

Choose the two values from $[n+1,2n]$ above $n$ to get

$${n\choose 2}.$$

Let $q$ be the additional values from below $n$ that are present (other than the three we have selected). We then have $0\le q\le n-1.$

Counting these configurations we obtain

$${n\choose 2} \sum_{q=0}^{n-1} {n-1\choose q} \times {n\brace q+3} \times (q+3)!$$

Recall the species of set partitions which is $$\mathfrak{P}(\mathcal{U}\mathfrak{P}_{\ge 1}(\mathcal{Z}))$$ so that the bivariate generating function is $$G(z, u) = \exp(u(\exp(z)-1))$$

which finally yields $${n\brace q} = n! [z^n] \frac{(\exp(z)-1)^q}{q!}.$$

This yields for our sum

$${n\choose 2} n! [z^n] \sum_{q=0}^{n-1} {n-1\choose q} \times \frac{(\exp(z)-1)^{q+3}}{(q+3)!} \times (q+3)! \\ = {n\choose 2} n! [z^n] \sum_{q=0}^{n-1} {n-1\choose q} \times (\exp(z)-1)^{q+3} \\ = {n\choose 2} n! [z^n] (\exp(z)-1)^3 \exp((n-1)z) \\ = {n\choose 2} n! [z^n] (\exp((n+2)z)-3\exp((n+1)z)+3\exp(nz)-\exp((n-1)z)).$$

Extracting coefficients we have

$${n\choose 2} \left((n+2)^n - 3(n+1)^n + 3n^n - (n-1)^n\right)$$

for a probability of

$$\frac{1}{(2n)^n} {n\choose 2} \left((n+2)^n - 3(n+1)^n + 3n^n - (n-1)^n\right).$$