combinatorias descensos encontrar el número de permutaciones con criterios

Question

Necesito ayuda con lo siguiente:

Definir un descenso de una permutación a ser $j$ al $p_{j+1} < p_j$. A continuación, el descenso conjunto de una permutación es el conjunto de todos los descensos. Por ejemplo, el $5$-permutación: \begin{equation} 4, 3, 1, 5, 2 \end{equation}

tiene ascendencia set $D=\{1, 2, 4\}$

Cuántas $9$-permutaciones han descenso conjuntos de $D$ tal que $D$ es un subconjunto de a $\{1,4,7\}$?

No puedo pensar en ninguna forma de enumerar un resultado así que empecé a pensar en la inclusión de la exclusión, sin embargo me siento como este enfoque es el mismo, en términos de complejidad debido a la búsqueda de la bajada de los conjuntos que no son subconjuntos es tan duro. Por la complejidad me refiero a averiguar lo que ocurría.

EDITAR Estoy en busca de una respuesta concreta ahora. Por ejemplo, digamos que tenemos $2$-descensos entre los elementos $1$ $2$ y elementos $5$$6$. Una solución que he visto dice que la cantidad dada por ${8 \choose 1}\cdot{7\choose 4}\cdot {3\choose 3}$ nos dice el número de subconjuntos con el descenso conjunto de $=\{1 5\}$. Que es el dos descensos se producen entre los índices de $1$$2$$5$$6$.

¿Qué significa la cantidad significa? Veo que somos de "escoger" los números entre los índices de los descensos, pero aún no puedo pieza lo suficientemente razonamiento juntos para convencerme de que esto es correcto. Ahora estoy multiplicar estos números juntos porque me hace ver que estos pasos son independientes.

Gracias, y toda la ayuda es muy apreciada!

Answer 1

Es lo mismo que preguntar por el número de permutaciones con $$p_2\lt p_3\lt p_4,\quad p_5\lt p_6\lt p_7,\quad{\rm and}\quad p_8\lt p_9$$ So, given a random permutation, what is the probability of $p_2\lt p_3\lt p_4$? Is it independent of the probability of $p_5\lt p_6\lt p_7$? y así sucesivamente....

EDIT: Hay $9!$ permutaciones de $1,\dots,9$. Elija cualquiera de uno de estos, llamado Joe. Cómo muchas de las $9!$ está de acuerdo con Joe, excepto, posiblemente, en las posiciones 2, 3 y 4? Bien, ese es el número de permutaciones de los números en los $3$ posiciones, por lo que es $3!$. De los$3!$, ¿cuántos no tienen ningún descenso en las posiciones 2, 3 y 4? Sólo uno, el uno que ha $p_2\lt p_3\lt p_4$. Así, tenemos que dividir el $9!$ total de permutaciones por $3!$ para obtener el número con el no descenso a los 2, 3, y 4. Del mismo modo, tenemos que dividir de nuevo por $3!$ para obtener el número con el no descenso en 5, 6, y 7, y por $2!$ conseguir sin descenso a las 8 o 9. Así llegamos hasta con $${9!\over3!3!2!}$$ Esto es, básicamente, el mismo razonamiento que en la de Michael respuesta, sin usar el vocabulario de la teoría de grupos.

No veo la manera de obtener el resultado en el comentario de $9$-permutaciones con el descenso conjunto de $\{{1,5\}}$. Llego $9!/(4!4!)=630$, donde su fórmula da $280$.

Answer 2

He aquí una sugerencia si conoces algún grupo de teoría:

Considerar el subgrupo $H = S_1 \times S_3 \times S_3 \times S_2$ que permutes los conjuntos $\{1\}$, $\{2,3,4\}$, $\{5,6,7\}$ y $\{8,9\}$ individualmente (pero los elementos de $H$ no se permite el envío de los números de uno de estos conjuntos a otro). A continuación, $H$ actúa en $S_9$ a la derecha y cada coset en $S_9 / H$ tiene un único representante, cuya ascendencia conjunto está contenido en $D = \{1, 4, 7\}$. (¿Por qué? Recuerde que al multiplicar una permutación por otra permutación de la derecha tiene el efecto de mezclar las posiciones de la original de permutación.)

Por lo tanto, el número de permutaciones que buscamos es igual al número de cosets en $S_9 / H$, por lo que es igual a $|S_9| / |H| = 9! / (3! 3! 2!) = 5040$.