Autor Tema: principio inclusión-exclusión

0 Usuarios y 1 Visitante están viendo este tema.

18 Octubre, 2018, 07:05 pm
Leído 949 veces

atayap

  • Nuevo Usuario
  • Mensajes: 4
  • Karma: +0/-0
  • Sexo: Femenino
Hola ¿cómo puedo probar \( \displaystyle\binom{n-k}{n-r}=\displaystyle\sum_{j=0}^k{}(-1)^j\displaystyle\binom{k}{j}\displaystyle\binom{n-j}{r} \) con \( k\leq{r}\leq{n} \) utilizando el principio de inclusión-exclusión?
Muchas gracias.

18 Octubre, 2018, 08:02 pm
Respuesta #1

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 46,534
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

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

Equivale a:

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

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

Son todos los subconjuntos de \( n-r \) elementos del conjunto de los números del \( 1 \) al \( n \): \( \displaystyle\binom{n-0}{n-r-0} \)

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

Y así sucesivamente...

Saludos.

CORREGIDO

20 Octubre, 2018, 12:01 pm
Respuesta #2

atayap

  • Nuevo Usuario
  • Mensajes: 4
  • Karma: +0/-0
  • Sexo: Femenino
Hola, no entiendo esta parte
Son todos los conjuntos de \( n−r \) elementos de los números del \( 1 \) al \( n \):\(  \displaystyle\binom{n-0}{n-r-0} \)
Muchas gracias,
Un saludo.

20 Octubre, 2018, 09:40 pm
Respuesta #3

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 46,534
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

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

Corregí un poco la redacción.

Me refiero a que comenzamos contando todos los subconjuntos de \( n-r \) elementos del conjunto de números de \( 1 \) a \( n \).

Luego retiraremos los que contienen al menos una de los \( k \) primeros; pero así quitamos dos veces los que contiene al menos dos y hay que sumárselos; y así sucesivamente...

Saludos.