Conteo

robert123
Mensajes: 11
Registrado: Dom 11 Feb, 2018 12:43 pm
Nivel: 3

Conteo

Mensaje sin leer por robert123 »

¿De cuántas formas se pueden escoger ocho enteros $a_{1}, a_{2}, ..., a_{8}$, no necesariamente distintos, tales que $1\leq a_{1} \leq a_{2} \leq ...\leq a_{8} \leq 8$ ?
Avatar de Usuario
Emerson Soriano

OFO - Mención-OFO 2015 OFO - Medalla de Oro-OFO 2016 OFO - Medalla de Plata-OFO 2017 OFO - Medalla de Bronce-OFO 2018 OFO - Mención-OFO 2020
OFO - Medalla de Plata-OFO 2022
Mensajes: 826
Registrado: Mié 23 Jul, 2014 10:39 am
Medallas: 6

Re: Conteo

Mensaje sin leer por Emerson Soriano »

Biyecciones. Mañana cuelgo una solución.
Avatar de Usuario
Emerson Soriano

OFO - Mención-OFO 2015 OFO - Medalla de Oro-OFO 2016 OFO - Medalla de Plata-OFO 2017 OFO - Medalla de Bronce-OFO 2018 OFO - Mención-OFO 2020
OFO - Medalla de Plata-OFO 2022
Mensajes: 826
Registrado: Mié 23 Jul, 2014 10:39 am
Medallas: 6

Re: Conteo

Mensaje sin leer por Emerson Soriano »

Spoiler: mostrar
Lema 1. El número de $n-$uplas ordenadas $(x_1, x_2, ... , x_n)$ de enteros no negativos tales que $x_1+x_2+\cdots +x_n=k$ es $\binom{n+k-1}{n-1}$.

Prueba. Consideramos un tablero de $1\times (n+k-1)$. Pintamos $n-1$ casillas cualesquiera. Notemos que la cantidad de casillas no pintadas es $k$. Sea $y_1$ la cantidad de casillas no pintadas que hay antes de la casilla pintada, sea $y_2$ la cantidad de casillas no pintadas entre la primera y la segunda casilla pintada, así sucesivamente, sea $y_n$ la cantidad de casillas no pintadas que hay después de la última casilla pintada. Entonces, $y_1+y_2+\cdots +y_n=k$. Entonces el número de soluciones que hay en la ecuación original (la del lema) es equivalente al número de formas de pintar $n-1$ casillas del tablero, que es $\binom{n+k-1}{n-1}$, pues claramente hay una biyección.

Con respecto al Problema.

Sea $x_1=a_1-1$, $x_2=a_2-a_1$, $x_3=a_3-a_2$, ... , $x_8=a_8-a_7$ y $x_9=8-a_8$. Notemos que $x_1+x_2+\cdots +x_9=7$, donde los $x_i$ son enteros no negativos. El número de soluciones es $\binom{9+7-1}{9-1}=\binom{15}{8}$, que es precisamente la respuesta, pues cada solución genera una $8-$upla ordenada $(a_1, a_2, ... , a_8)$.
2  
Responder