Estoy tratando de entender este principio , pero lo que me sale en la
red habla en un lenguaje demasiado matematico para mi

Me lo podrian explicar con palabras sencillas ojala acompañado con un
ejemplo simple


se agradece

tymy escribió:
> Estoy tratando de entender este principio , pero lo que me sale en la
> red habla en un lenguaje demasiado matematico para mi
>
> Me lo podrian explicar con palabras sencillas ojala acompañado con un
> ejemplo simple
>

El ejemplo más sencillo es el de los desórdenes ("derangements")

http://en.wikipedia.org/wiki/Derangement

Sea un conjunto de 5 elementos {A,B,C,D,E}. Se realiza una permutación
aleatoria. ¿Cuál es la probabilidad de que ninguno de los cinco
elementos coincida con su lugar original?

Vamos a contar los casos favorables. Luego dividiremos por los posibles.

1) Primero la inclusión: Una primera aproximación nos dice que tenemos
5! casos.

N = 5!

2) Exclusión. El cálculo anterior es claramente incorrecto pues cuenta
los casos en que uno de los elementos esté en su sitio. Por ejemplo,
supongamos que B no cambia de lugar,

· B · · ·

¿cuántos casos supone esto? Pues tenemos 4! permutaciones de los
elementos restantes. Como tenemos 5 elementos que pueden permanecer
fijos, debemos restar 5*4!

N = 5! - 5·4!

3) Inclusión de nuevo. Al restar antes nos hemos pasado (¡y tanto, nos
hemos quedado sin nada!). La razón es que hay casos que hemos descontado
dos veces. Por ejemplo, los casos de la forma

· B · · E

los hemos descontado como ·B··· y como ····E, así que hay volver a
incluirlos una vez. ¿Cuantos son? Tenemos 5*4/2 pares posibles y por
cada uno 3! permutaciones del resto, lo que nos da

N = 5! - 5·4! + (5·4)/2 3!

o, usando el lenguaje de los números combinatorios

N = C(5,0)5! - C(5,1)4! + C(5,2)3!

4) Exclusión de nuevo. Al meter los casos anteriores de nuevo nos hemos
vuelto a pasar, ya que los casos de la forma AB··E los hemos re-incluido
con los AB···, los ·B··E y los A···E, así que descontamos de nuevo.
Tenemos C(5,3) tríos y 2! permutaciones de los elementos restantes, lo
que nos da

N = C(5,0)5! - C(5,1)4! + C(5,2)3! - C(5,3)2!

5) Otra inclusión. Ahora toca incluir los elementos tales que hay cuatro
fijos

N = C(5,0)5! - C(5,1)4! + C(5,2)3! - C(5,3)2! + C(5,4)1!

6) Exclusión final. Por último debemos descontar el caso en que todos
están quietos

N = C(5,0)5! - C(5,1)4! + C(5,2)3! - C(5,2)2! + C(5,4)1! - C(5,5)0!

La probabilidad de que ninguno coincida será

P = N/5! = 1/0! - 1/1! + 1/2! - 1/3! + 1/4! - 1/5!

(que obviamente tiende a 1/e cuando el número de elementos tiende a
infinito).

La idea de entonces del principio de inclusión-exclusión es primero
contar los casos aparentemente favorables, luego descontar los
repetidos, luego re-incluir los que hemos quitado más de la cuenta,
luego volver a incluir los que hemos quitado de más y así sucesivamente.






--

Antonio

tymy escribió:
> Estoy tratando de entender este principio , pero lo que me sale en la
> red habla en un lenguaje demasiado matematico para mi
>
> Me lo podrian explicar con palabras sencillas ojala acompañado con un
> ejemplo simple
>

El ejemplo más sencillo es el de los desórdenes ("derangements")

http://en.wikipedia.org/wiki/Derangement

Sea un conjunto de 5 elementos {A,B,C,D,E}. Se realiza una permutación
aleatoria. ¿Cuál es la probabilidad de que ninguno de los cinco
elementos coincida con su lugar original?

Vamos a contar los casos favorables. Luego dividiremos por los posibles.

1) Primero la inclusión: Una primera aproximación nos dice que tenemos
5! casos.

N = 5!

2) Exclusión. El cálculo anterior es claramente incorrecto pues cuenta
los casos en que uno de los elementos esté en su sitio. Por ejemplo,
supongamos que B no cambia de lugar,

· B · · ·

¿cuántos casos supone esto? Pues tenemos 4! permutaciones de los
elementos restantes. Como tenemos 5 elementos que pueden permanecer
fijos, debemos restar 5*4!

N = 5! - 5·4!

3) Inclusión de nuevo. Al restar antes nos hemos pasado (¡y tanto, nos
hemos quedado sin nada!). La razón es que hay casos que hemos descontado
dos veces. Por ejemplo, los casos de la forma

· B · · E

los hemos descontado como ·B··· y como ····E, así que hay volver a
incluirlos una vez. ¿Cuantos son? Tenemos 5*4/2 pares posibles y por
cada uno 3! permutaciones del resto, lo que nos da

N = 5! - 5·4! + (5·4)/2 3!

o, usando el lenguaje de los números combinatorios

N = C(5,0)5! - C(5,1)4! + C(5,2)3!

4) Exclusión de nuevo. Al meter los casos anteriores de nuevo nos hemos
vuelto a pasar, ya que los casos de la forma AB··E los hemos re-incluido
con los AB···, los ·B··E y los A···E, así que descontamos de nuevo.
Tenemos C(5,3) tríos y 2! permutaciones de los elementos restantes, lo
que nos da

N = C(5,0)5! - C(5,1)4! + C(5,2)3! - C(5,3)2!

5) Otra inclusión. Ahora toca incluir los elementos tales que hay cuatro
fijos

N = C(5,0)5! - C(5,1)4! + C(5,2)3! - C(5,3)2! + C(5,4)1!

6) Exclusión final. Por último debemos descontar el caso en que todos
están quietos

N = C(5,0)5! - C(5,1)4! + C(5,2)3! - C(5,2)2! + C(5,4)1! - C(5,5)0!

La probabilidad de que ninguno coincida será

P = N/5! = 1/0! - 1/1! + 1/2! - 1/3! + 1/4! - 1/5!

(que obviamente tiende a 1/e cuando el número de elementos tiende a
infinito).

La idea de entonces del principio de inclusión-exclusión es primero
contar los casos aparentemente favorables, luego descontar los
repetidos, luego re-incluir los que hemos quitado más de la cuenta,
luego volver a incluir los que hemos quitado de más y así sucesivamente.






--

Antonio

tymy escribió:
> Estoy tratando de entender este principio , pero lo que me sale en la
> red habla en un lenguaje demasiado matematico para mi
>
> Me lo podrian explicar con palabras sencillas ojala acompañado con un
> ejemplo simple
>

El ejemplo más sencillo es el de los desórdenes ("derangements")

http://en.wikipedia.org/wiki/Derangement

Sea un conjunto de 5 elementos {A,B,C,D,E}. Se realiza una permutación
aleatoria. ¿Cuál es la probabilidad de que ninguno de los cinco
elementos coincida con su lugar original?

Vamos a contar los casos favorables. Luego dividiremos por los posibles.

1) Primero la inclusión: Una primera aproximación nos dice que tenemos
5! casos.

N = 5!

2) Exclusión. El cálculo anterior es claramente incorrecto pues cuenta
los casos en que uno de los elementos esté en su sitio. Por ejemplo,
supongamos que B no cambia de lugar,

· B · · ·

¿cuántos casos supone esto? Pues tenemos 4! permutaciones de los
elementos restantes. Como tenemos 5 elementos que pueden permanecer
fijos, debemos restar 5*4!

N = 5! - 5·4!

3) Inclusión de nuevo. Al restar antes nos hemos pasado (¡y tanto, nos
hemos quedado sin nada!). La razón es que hay casos que hemos descontado
dos veces. Por ejemplo, los casos de la forma

· B · · E

los hemos descontado como ·B··· y como ····E, así que hay volver a
incluirlos una vez. ¿Cuantos son? Tenemos 5*4/2 pares posibles y por
cada uno 3! permutaciones del resto, lo que nos da

N = 5! - 5·4! + (5·4)/2 3!

o, usando el lenguaje de los números combinatorios

N = C(5,0)5! - C(5,1)4! + C(5,2)3!

4) Exclusión de nuevo. Al meter los casos anteriores de nuevo nos hemos
vuelto a pasar, ya que los casos de la forma AB··E los hemos re-incluido
con los AB···, los ·B··E y los A···E, así que descontamos de nuevo.
Tenemos C(5,3) tríos y 2! permutaciones de los elementos restantes, lo
que nos da

N = C(5,0)5! - C(5,1)4! + C(5,2)3! - C(5,3)2!

5) Otra inclusión. Ahora toca incluir los elementos tales que hay cuatro
fijos

N = C(5,0)5! - C(5,1)4! + C(5,2)3! - C(5,3)2! + C(5,4)1!

6) Exclusión final. Por último debemos descontar el caso en que todos
están quietos

N = C(5,0)5! - C(5,1)4! + C(5,2)3! - C(5,2)2! + C(5,4)1! - C(5,5)0!

La probabilidad de que ninguno coincida será

P = N/5! = 1/0! - 1/1! + 1/2! - 1/3! + 1/4! - 1/5!

(que obviamente tiende a 1/e cuando el número de elementos tiende a
infinito).

La idea de entonces del principio de inclusión-exclusión es primero
contar los casos aparentemente favorables, luego descontar los
repetidos, luego re-incluir los que hemos quitado más de la cuenta,
luego volver a incluir los que hemos quitado de más y así sucesivamente.






--

Antonio