Matemática => Matemática Discreta y Algoritmos => Mensaje iniciado por: atayap en 18/10/2018, 02:05:39 pm



Título: principio inclusión-exclusión
Publicado por: atayap en 18/10/2018, 02:05:39 pm
Hola ¿cómo puedo probar [texx]\displaystyle\binom{n-k}{n-r}=\displaystyle\sum_{j=0}^k{}(-1)^j\displaystyle\binom{k}{j}\displaystyle\binom{n-j}{r}[/texx] con [texx]k\leq{r}\leq{n}[/texx] utilizando el principio de inclusión-exclusión?
Muchas gracias.


Título: Re: Principio inclusión-exclusión
Publicado por: Luis Fuentes en 18/10/2018, 03:02:13 pm
Hola

Hola ¿cómo puedo probar [texx]\displaystyle\binom{n-k}{n-r}=\displaystyle\sum_{j=0}^k{}(-1)^j\displaystyle\binom{k}{j}\displaystyle\binom{n-j}{r}[/texx] con [texx]k\leq{r}\leq{n}[/texx] utilizando el principio de inclusión-exclusión?
Muchas gracias.

Equivale a:

 [texx]\displaystyle\binom{n-k}{n-r}=\displaystyle\sum_{j=0}^k{}(-1)^j\displaystyle\binom{k}{j}\displaystyle\binom{n-j}{n-j-r}[/texx]

Entonces el término de la izquierda se puede interpretar como subconjuntos de los números del [texx]1[/texx] al [texx]n[/texx] formados por [texx]n-r[/texx] elementos y sin contener a los [texx]k[/texx] primeros.

Son todos los subconjuntos de [texx]n-r[/texx] elementos del conjunto de los números del [texx]1[/texx] al [texx]n[/texx]: [texx]\displaystyle\binom{n-0}{n-r-0}[/texx]

Restamos los que contienen a algún número de [texx]1[/texx] a [texx]k[/texx]: [texx]\displaystyle\binom{k}{1}[/texx] opciones para elegir el número entre [texx]1[/texx] y [texx]k[/texx] y [texx]\displaystyle\binom{n-1}{n-r-1}[/texx] posibilidades para los restantes.
 
Pero así hemos restado dos veces los que contienen simultáneamente a dos números de [texx]1[/texx] a [texx]k[/texx]; los sumamos.  [texx]\displaystyle\binom{k}{2}[/texx] opciones para elegir los dos números entre [texx]1[/texx] y [texx]k[/texx] y [texx]\displaystyle\binom{n-2}{n-r-2}[/texx] posibilidades para los restantes.

Y así sucesivamente...

Saludos.

CORREGIDO


Título: Re: principio inclusión-exclusión
Publicado por: atayap en 20/10/2018, 07:01:51 am
Hola, no entiendo esta parte
Son todos los conjuntos de [texx]n−r[/texx] elementos de los números del [texx]1[/texx] al [texx]n[/texx]:[texx] \displaystyle\binom{n-0}{n-r-0}[/texx]
Muchas gracias,
Un saludo.


Título: Re: principio inclusión-exclusión
Publicado por: Luis Fuentes en 20/10/2018, 04:40:45 pm
Hola

Hola, no entiendo esta parte
Son todos los conjuntos de [texx]n−r[/texx] elementos de los números del [texx]1[/texx] al [texx]n[/texx]:[texx] \displaystyle\binom{n-0}{n-r-0}[/texx]
Muchas gracias,
Un saludo.

Corregí un poco la redacción.

Me refiero a que comenzamos contando todos los subconjuntos de [texx]n-r[/texx] elementos del conjunto de números de [texx]1[/texx] a [texx]n[/texx].

Luego retiraremos los que contienen al menos una de los [texx]k[/texx] primeros; pero así quitamos dos veces los que contiene al menos dos y hay que sumárselos; y así sucesivamente...

Saludos.