Contar el número de secuencias combinatorias.

Question

Dejemos que $n$ sea un número natural positivo. Una secuencia de $n$ enteros positivos (no necesariamente distintos) se llama secuencia de "cuatro grupos" si satisface los siguientes requisitos: para cualquier $k \geq 2$ , si $k$ ocurre en esta secuencia, entonces $k 1$ y la primera posición en la que aparece el número $k 1$ ocurre, es anterior a la última posición en la que el número $k$ se produce. Encuentra el número de secuencias de "cuatro grupos" de longitud $n$ .

Answer 1

Hay $n!$ secuencias de cuatro grupos de longitud $n$ .

Aquí hay una biyección entre los FGS y las permutaciones. Dada una permutación de longitud $n$ , dividirlo en subsecuencias consecutivas decrecientes máximas. Por ejemplo, con $\pi=[\pi_1,\pi_2,\dots,\pi_{n}]$ en notación de una línea, y $n=10$ , $$ [7,5,2,1, 3,10,6,9,8,4]\implies 7,5,2,1\def\div{\;\Big|\;}\div3\div10,6\div9,8,4 $$ Para realizar el FGS correspondiente a esta permutación, colocamos un $1$ en cada índice de la primera subsecuencia (en los puntos $7,5,2$ y $1$ ), colocamos un $2$ en cada índice de la segunda subsecuencia decreciente (en el punto $3$ ), y en general colocar el número $k$ en cada posición que aparece en el $k^{th}$ bloque. El resultado en este ejemplo es $$ 1, 1, 2, 4, 1, 3, 1, 4, 4, 3 $$ Obsérvese que el conjunto de números que aparecen será siempre un intervalo consecutivo de enteros que contiene $1$ . Además, la maximalidad de las sucesiones decrecientes implica que la primera instancia de $k-1$ es antes de la última instancia de $k$ para cada $k$ .

El mapa inverso es el siguiente Dado un FGS, ordenar los índices de las apariciones de $1$ en orden decreciente, y luego añadir los índices de las apariciones de $2$ en orden decreciente, y así sucesivamente. Te dejo que compruebes que estos mapas son inversos entre sí.