Rioplatense 2009 N3 P3

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Joacoini

OFO - Medalla de Plata FOFO 9 años - Medalla Especial OFO - Medalla de Oro FOFO Pascua 2019 - Medalla
Mensajes: 254
Registrado: Jue 12 Oct, 2017 10:17 pm
Medallas: 5
Nivel: Exolímpico
Ubicación: Ciudad Gotica

Rioplatense 2009 N3 P3

Mensaje sin leer por Joacoini » Mar 17 Dic, 2019 6:45 pm

Una permutación de los números enteros $(1, 2, ..., n)$ se llama $d$-ordenada si no contiene una subsucesión decreciente de longitud $d$.

Demostrar que para todo $d$ tal que $2\leq d\leq n$ el número de permutaciones $d$-ordenadas de $(1, 2, ..., n)$ es a lo sumo $(d-1)^{2n}$.
NO HAY ANÁLISIS.

Avatar de Usuario
Prillo

Colaborador OFO - Jurado
Mensajes: 400
Registrado: Sab 18 Dic, 2010 8:52 pm
Medallas: 2

Re: Rioplatense 2009 N3 P3

Mensaje sin leer por Prillo » Vie 20 Dic, 2019 2:14 am

Spoiler: mostrar
A cada numero de la permutacion $d$-ordenada $A$ le asignamos la maxima longitud de una subsucesion decreciente que termina en ese numero. Asi obtenemos una nueva sucesion $L$ que tiene terminos entre $1$ y $d - 1$ inclusive. Por ejemplo, para la permutacion $A = (1,4,3,5,2)$ obtenemos la sucesion $L = (1,1,2,1,3)$. Hay a lo sumo $(d - 1)^n$ sucesiones $L$ que podemos obtener de esta manera. Por otra parte, dada la sucesion $L$, veamos de cuantas permutaciones $A$ puede provenir. Dada $L$, la permutacion $A$ queda totalmente determinada si decimos para cada numero $1 \le k \le n$ de $A$, el valor de $l$ que va a tener $k$ en $L$, pues en tal caso los numeros con el mismo valor $l$ tienen que ocupar las posiciones de $L$ iguales a $l$ en orden creciente (o se violaria la definicion de $L$). Entonces cada sucesion $L$ proviene de a lo sumo $(d - 1)^n$ permutaciones $A$, y luego hay a lo sumo $(d - 1)^n\times (d - 1)^n = (d - 1)^{2n}$ permutaciones $d$-ordenadas.

Responder