Probabilidad de elegir $n$ números de $\{1, \dots, 2n\}$ para que $n$ es el tercero en tamaño

Question

Elegimos uniformemente al azar $n$ números de $2n$ números del grupo $\{1, \dots, 2n\}$ de modo que el orden importa y se permiten las repeticiones. ¿Cuál es la probabilidad de que $n$ es el $3^{\text{rd}}$ número en tamaño en la serie elegida? (= sólo hay dos mayores que $n$ )
Tenga en cuenta que si un número que es mayor que $n$ fue elegido más de una vez, seguimos contando como un número mayor que $n$ .

Ejemplo: $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$ - no está bien, 5 es $2^{\text{nd}}$ en tamaño

Mi pista fue elegir primero 2 números que son mayores que $n$ de los n números que son mayores que $n$ en el grupo $\{1, \dots, 2n\}$ . A continuación, para completar una serie de $n$ números que tengo que elegir $n-3$ más de los números que son iguales o menores que $n$ pero luego pensé que esto no es correcto ya que se podría formar una serie a partir de los 2 números mayores que $n$ y $n$ sin ningún número adicional. En este momento no tengo ninguna pista adicional y me vendría muy bien su ayuda y orientación.

Answer 1

Puede utilizar el principio de inclusión-exclusión.

Dejemos que $S:=$ El evento de obtener una secuencia válida de números ( $n$ números $\le n$ y 2 números $\gt n$ )

$A_1 :=$ El evento que $n$ no aparece en la secuencia

$A_2 :=$ El caso de que uno de los números más grandes que $n$ no aparece en la secuencia

$A_3 :=$ El caso de que el segundo número que sea mayor que $n$ no aparece en la secuencia

Ahora bien, la probabilidad que buscamos es la probabilidad de que ocurra S pero la unión de $A_1,\, A_2,\, A_3$ no se produce.

Tenemos la fórmula

$$ \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 ] $$

Calculemos las probabilidades de los eventos definidos anteriormente.

En primer lugar, nuestro espacio muestral $\Omega$ son todas las secuencias de $n$ números del grupo $\{1, 2, \ldots, 2n\}$ .

Así que $\left| \Omega \right| = \left( 2n \right)^n $ .

Ahora, $ \Pr \left[S \right] = \frac{\left ( n+2 \right )^n}{\left ( 2n \right )^n} $ (tenemos $n$ números $\le n$ y 2 números mayores que $n$ )

De la misma manera, $ \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} $

También tenemos que calcular las intersecciones.

$ \Pr\left [ A_i\cap A_j \right ] = \frac{n^n}{\left ( 2n \right )^n} \; ($ para $ 1\leq i<j\leq 3 )$ - Obsérvese que hay 3 intersecciones de este tipo. Y también está la intersección de las tres:

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

Una última cosa: hay $ \binom{n}{2} $ maneras de elegir esos 2 números que son mayores que $n$ .

Ahora, introduciremos todo en la fórmula de inclusión-exclusión y multiplicaremos por $ \binom{n}{2} $ y nosotros lo conseguiremos:

$$ \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

Elija los dos valores de $[n+1,2n]$ por encima de $n$ para conseguir

$${n\choose 2}.$$

Dejemos que $q$ sean los valores adicionales de abajo $n$ que están presentes (además de los tres que hemos seleccionado). Entonces tenemos $0\le q\le n-1.$

Contando estas configuraciones obtenemos

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

Recordemos la especie de las particiones de conjuntos que es $$\mathfrak{P}(\mathcal{U}\mathfrak{P}_{\ge 1}(\mathcal{Z}))$$ para que la función generadora bivariante sea $$G(z, u) = \exp(u(\exp(z)-1))$$

que finalmente da como resultado $${n\brace q} = n! [z^n] \frac{(\exp(z)-1)^q}{q!}.$$

Esto da como resultado para nuestra suma

$${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)).$$

Extrayendo los coeficientes tenemos

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

para una probabilidad de

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

Answer 3

En un resultado favorable, $2$ de la $n$ números de $n+1$ a $2n$ que se puede elegir en $\binom n2$ formas, y $k$ de la $n-1$ números de $1$ a $n-1$ que se puede elegir en $\binom{n-1}k$ maneras con $0\le k\le n-3$ . Junto con $n$ que también debe ocurrir, es decir $k+3$ números. El número de maneras de dividir el $n$ se convierte en $k+3$ subconjuntos no vacíos viene dado por el número de Stirling del segundo tipo $\def\stir#1#2{\left\{{#1\atop #2}\right\}}\stir n{k+3}$ . El $k+3$ Los números se pueden asignar a estos subconjuntos en $(k+3)!$ diferentes maneras. La probabilidad deseada es el número de resultados favorables dividido por el número total $(2n)^n$ de resultados equiprobables:

\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}

donde la línea marcada con $(*)$ se obtiene mediante una suma Vandermondesca como la derivada en esta página tan útil . Desembolsar la suma sobre $j$ lleva a estar de acuerdo con las otras dos respuestas.