¿Cuántas permutaciones casi perfectas hay?

una permutación ( a 1 , a 2 , a 3 , , a norte ) de los numeros ( 1 , 2 , 3 , , norte ) se llama casi perfecto si existe exactamente uno i { 1 , 2 , 3 , , norte 1 } tal que a i > a i + 1 . ¿Cuál es el número de permutaciones casi perfectas de los números ( 1 , 2 , 3 , . . . , 11 ) ?

El problema es de un concurso simulado. Aquí está mi intento de resolver el problema:

Empecé tomando pequeños valores de i y busqué un patrón. Aquí i es un número para el cual a i > a i + 1 . Para i = 1 , los dos primeros números serán de la forma ( k , 1 ) dónde k { 2 , 3 , , norte } . De lo contrario, habrá más de un par. ( a i , a i + 1 ) para cual a i > a i + 1 . Entonces tenemos norte 1 tales permutaciones en este caso.
Para i = 2 , los primeros tres números serán de la forma ( 1 , k , 2 ) o de la forma ( 2 , k , 1 ) dónde k { 3 , 4 , , norte } . Entonces tenemos 2 ( norte 2 ) permutaciones casi perfectas en este caso.
Para i = 3 , los primeros cuatro números serán de la forma ( 1 , 2 , k , 3 ) o ( 1 , 3 , k , 2 ) o ( 2 , 3 , k , 1 ) dónde k { 4 , 5 , , norte } . Entonces tenemos 3 ( norte 3 ) permutaciones casi perfectas en este caso.
Por lo tanto, afirmo que hay i ( norte i ) permutaciones casi perfectas para cada i . Así, por norte = 11 tenemos un total de 1 ( 11 1 ) + 2 ( 11 2 ) + + 10 ( 11 10 ) = 220 permutaciones casi perfectas .

No estoy seguro de si la solución anterior es correcta o no. Pero creo que esta no es la mejor manera de resolver el problema. Entonces, estoy buscando una mejor solución.

Porqué por i = 3 ) no pueden estar en la forma ( 1 , 4 , k , 2 ) ?
¿No sería el conjunto de números ( 1 , 2 , 3 , , norte ) ser casi perfecto si solo elegimos uno de estos norte números ( norte formas) y extravíelo de su posición inicial ( norte 1 ) maneras que se pueden hacer en total norte ( norte 1 ) maneras. Como tal, habrá 110 permutaciones casi perfectas para el conjunto de la primera 11 números naturales.

Respuestas (1)

Asumimos i es el término tal que a i > a i + 1 .

Dejar A Sea el conjunto de números a 1 , , a i . Tenga en cuenta que A determina completamente la permutación, como debe ser a 1 < a 2 < < a i y luego a i + 1 , , a norte deben ser los elementos que no están en A en orden creciente.

Lo único que A necesita satisfacer es que su tamaño esté en el rango [ 1 , norte 1 ] y que su elemento más grande es más grande que el elemento más pequeño que no está en A , en otras palabras, requerimos que A no es uno de los norte 1 intervalos de la forma { 1 , , i }

Por lo tanto, hay 2 norte 2 ( norte 1 ) opciones para A .