Boletos de lotería en caja, números de rencontres y número de grado- $n$ permutaciones de orden exacto $d$

Question

Esta es una pregunta que me encontré en el trabajo y de la que estoy tratando de obtener una comprensión más profunda.

Vendemos boletos en una lotería en la que se adivina $4$ números fuera del rango de $36$ (el rango es irrelevante para este problema) en una orden. Se extraen cuatro números. Si su primer número adivinado coincide con el primer número sorteado, se considera que ha acertado, al igual que el segundo, tercer y cuarto sorteos. Se obtienen diferentes premios según el número de números que se acierte. Si acierta los cuatro números, obtiene un $S4$ premio, al acertar tres se obtiene un $S3$ premio, etc.

Sin embargo, también ofrecemos un billete "en caja", que equivale a comprar todo $24$ permutaciones de la $4$ números que ha seleccionado. Puede determinar cuántos premios de cada clase ganará por el recuento de números coincidentes de esta tabla: $$\begin{array}{ |c | c | c | c | c | } \hline \text{Matching Numbers} & S4 & S3 & S2 & S1 \\ 4 & 1 & 0 & 6 & 8 \\ 3 & 0 & 1 & 3 & 9 \\ 2 & 0 & 0 & 2 & 8 \\ 1 & 0 & 0 & 0 & 6 \\ \hline \end{array} $$ Ahora, el " $4$ "es el número de permutaciones de $4$ con $4$ , $3$ , $2$ , $1$ puntos fijos, es decir, los números de rencontres $n=4$ . Esto naturalmente se sale de la descripción del problema y lo entiendo.

Utilizando la base de datos de la OEIS he podido averiguar que $3$ La fila de números coincidentes corresponde al número de grados. $n$ permutaciones de orden exacto $2$ . La fila 2 de números coincidentes corresponde al número de grados. $n$ permutaciones de orden exacto $3$ .

No sé si se trata de una correspondencia auténtica o si es una coincidencia. Me pregunto si hay una forma general de generar esta tabla, por ejemplo para una lotería con n números seleccionados.

Answer 1

Basándose en el trabajo de @AlexFrancisco para aclarar la definición del problema definición del problema, estableciendo una recurrencia y proporcionando ejemplos, parece que parece que tenemos la forma cerrada

$$\bbox[5px,border:2px solid #00A000]{ {m\choose k} \sum_{q=0}^{m-k} {m-k\choose q} (-1)^q (n-k-q)!.}$$

Este es el número de premios de la clase $k$ con $m$ partidos de entre $n$ total. Con esta fórmula seleccionamos primero el $k$ partidos de la $m$ disponibles y combinarlos con un trastorno generalizado de el resto, que calculamos por inclusión-exclusión.

Para el argumento PIE tenemos que los nodos $Q$ de la subyacente poset representan subconjuntos $Q\subseteq R$ del conjunto de posibles fijos puntos fijos $R$ de cardinalidad $m-k$ que se requieren para no ser fijados. Las permutaciones representadas en $Q$ tienen los elementos de $Q$ ser fijada además de la $k$ y posiblemente más. Este conjunto tiene cardinalidad $(n-k-|Q|)!.$ Nos preguntamos por el peso total de un permutación de la $n-k$ elementos restantes después del $k$ puntos fijos se han elegido, donde los pesos en $Q$ son $(-1)^{|Q|}$ . Una permutación admisible no tiene ninguno de los elementos de $R$ siendo fijo y por lo que sólo se incluye en $Q=\emptyset$ con peso $(-1)^{|\emptyset|} = 1.$ Una permutación con exactamente $P\subseteq R$ puntos fijos además del $k$ donde $P\ne\emptyset$ y por lo tanto $|P|\ge 1$ se incluye en todos los nodos $Q\subseteq P,$ para un peso total de

$$\sum_{Q\subseteq P} (-1)^{|Q|} = \sum_{q=0}^{|P|} {|P|\choose q} (-1)^q = 0.$$

El peso total de una permutación en la que ninguno de los elementos de $R$ son fijos es uno, y cero en caso contrario. Concluimos que el término de la suma de la fórmula propuesta cuenta exactamente las permutaciones de los restantes $n-k$ donde ninguno de los elementos $m-k$ elementos de $R$ son fijados.

Answer 2

Aquí se dará una fórmula general para la tabla.

Paso 1: Dados distintos $a_1, a_2, \cdots$ y $b_1, b_2, \cdots$ , defina $A_n = \{a_1, \cdots, a_n\}$ y $B_n = \{b_1, \cdots, b_n\}$ para $n \geqslant 0$ y $$ \mathscr{F}_{m, n} = \{: A_m A_m \cup B_n \mid \text{ is injective},\ (x) x,\ \forall x \in A_m\},\\ f(m, n) = |\mathscr{F}_{m, n}|, $$ donde $m, n \geqslant 0$ . Entonces para $n \geqslant 0$ , $$ f(0, n) = 1, \quad f(1, n) = n,\\ f(m, n) = (m + n - 1)f(m - 1, n) + (m - 1)f(m - 2, n). \quad (m \geqslant 2) $$

Prueba: Obviamente $f(0, n) = 1$ . Para $m = 1$ , ya que $(a_1) \in B_n$ entonces $f(1, n) = n$ . Ahora considere $m \geqslant 2$ .

Si $(a_1) \in B_n$ Entonces, intuitivamente $$ |_{A_m \setminus \{a_1\}}: A_m \setminus \{a_1\} \longrightarrow (A_m \setminus \{a_1\}) \cup \bigl( (B_n \setminus \{(a_1)\}) \cup \{a_1\} \bigr) $$ corresponde a un mapeo en $\mathscr{F}_{m - 1, n}$ y por lo tanto $$ |\{ \in \mathscr{F}_{m, n} \mid (a_1) \in B_n\}| = n f(m - 1, n). \tag{1} $$ Si $(a_1) = a_i$ y $(a_i) = a_1$ Entonces, intuitivamente $$ |_{A_m \setminus \{a_1, a_i\}}: A_m \setminus \{a_1, a_i\} \longrightarrow (A_m \setminus \{a_1, a_i\}) \cup B_n $$ corresponde a un mapeo en $\mathscr{F}_{m - 2, n}$ . Si $(a_1) = a_i$ pero $(a_i) a_1$ Entonces, intuitivamente $$ |_{A_m \setminus \{a_1\}}: (A_m \setminus \{a_1, a_i\}) \cup \{a_i\} \longrightarrow \bigl( (A_m \setminus \{a_1, a_i\}) \cup \{a_1\} \bigr) \cup B_n $$ corresponde a un mapeo en $\mathscr{F}_{m - 1, n}$ . Así, $$ |\{ \in \mathscr{F}_{m, n} \mid (a_1) \in A_m\}| = (m - 1) (f(m - 1, n) + f(m - 2, n)). \tag{2} $$ Combinando (1) y (2) se obtiene $$ f(m, n) = (m + n - 1)f(m - 1, n) + (m - 1)f(m - 2, n). $$ El resto de esta demostración se centra en demostrar rigurosamente (1), ya que (2) puede demostrarse de forma análoga.

Por simetría, $$ |\{ \in \mathscr{F}_{m, n} \mid (a_1) \in B_n\}| = n·|\{ \in \mathscr{F}_{m, n} \mid (a_1) = b_1\}|. $$ Por un lado, para $ \in \mathscr{F}_{m, n}$ tal que $(a_1) = b_1$ , defina $: A_{m - 1} A_{m - 1} \cup B_n$ como $$ (x) = \begin{cases} b_1; & x = a_i,\ (a_{i + 1}) = a_1\\ a_j; & x = a_i,\ (a_{i + 1}) = a_{j + 1}\\ b_j; & x = a_i,\ (a_{i + 1}) = b_j \end{cases}, $$ entonces $ \in \mathscr{F}_{m - 1, n}$ . Nótese que esto define un mapeo inyectivo desde $\{ \in \mathscr{F}_{m, n} \mid (a_1) = b_1\}$ a $\mathscr{F}_{m - 1, n}$ Por lo tanto $$ |\{ \in \mathscr{F}_{m, n} \mid (a_1) = b_1\}| \leqslant f(m - 1, n). $$ Por otro lado, para $ \in \mathscr{F}_{m - 1, n}$ , defina $: A_m A_m \cup B_n$ como $$ (x) = \begin{cases} b_1; & x = a_1\\ a_{j + 1}; & x = a_{i + 1},\ (a_i) = a_j\\ a_1; & x = a_{i + 1},\ (a_i) = b_1\\ b_{j + 1}; & x = a_{i + 1},\ (a_i) = b_{j + 1} \end{cases}, $$ entonces $ \in \mathscr{F}_{m, n}$ y $(a_1) = b_1$ . Obsérvese que se trata de un mapeo inyectivo desde $\mathscr{F}_{m - 1, n}$ a $\{ \in \mathscr{F}_{m, n} \mid (a_1) = b_1\}$ Por lo tanto $$ f(m - 1, n) \leqslant |\{ \in \mathscr{F}_{m, n} \mid (a_1) = b_1\}|. $$ Por lo tanto, (1) se mantiene.

Paso 2: Dados distintos $a_1, a_2, \cdots$ , $b_1, b_2, \cdots$ y $c_1, c_2, \cdots$ , defina $A_n = \{a_1, \cdots, a_n\}$ , $B_n = \{b_1, \cdots, b_n\}$ , $C_n = \{c_1, \cdots, c_n\}$ para $n \geqslant 0$ y $$ \mathscr{G}_{k, m, n} = \{: A_m \cup B_{n - m} A_m \cup C_{n - m} \mid \text{ is injective with exactly } k \text{ fixed points}\},\\ g(k, m, n) = |\mathscr{G}_{k, m, n}|, $$ donde $k \leqslant m \leqslant n$ . Entonces $$ g(k, m, n) = (n - m)!\, C(m, k) f(m - k, n - m). $$ (Tenga en cuenta que $g(k, m, n)$ es el número de premios de la clase $k$ si hay $m$ números coincidentes de $n$ en total).

Prueba: Hay $C(m, k)$ formas de seleccionar $k$ puntos fijos de $A_m$ entonces $f(m - k, n - m)$ formas de seleccionar las imágenes del resto $m - k$ elementos de $A_m$ y luego $(n - m)!$ formas de seleccionar las imágenes de los elementos en $B_{n - m}$ . Así, $$ g(k, m, n) = (n - m)!\, C(m, k) f(m - k, n - m). $$