Diferencia entre revisiones de «Principio de inclusión-exclusión»
Contenido eliminado Contenido añadido
m Revertidos los cambios de 201.206.114.1 a la última edición de D'ohBot |
|||
Línea 65:
== Aplicaciones ==
Una conocida aplicación del principio de inclusión-exclusión es el problema de contar el número de desarreglos de un conjunto finito. Un ''desarreglo'' de un conjunto ''A'' es una biyección de ''A'' en si mismo sin puntos fijos. Usando el principio de inclusión-exclusión puede demostrarse que si el cardinal de ''A'' es ''n'', entonces el número de desarreglos es [''n''! / ''e''] donde [''x''] designa la entero más cercano a ''x''. Puede encontrarse una detallada demostración [[http://en.wikipedia.org/wiki/Random_permutation_statistics#Number_of_permutations_that_are_derangements|aquí]].
Esto se conoce también como el subfactorial de ''n'', se escribe !''n''. Se sigue que si asignamos la misma probabilidad a todas las biyecciones entonces la probabilidad de que una biyección aleatoria sea un desarreglo tiende rápidamente a 1/''e'' a medida que n crece
== Conteo de intersecciones ==
El principio de inclusión-exclusión puede utilizarse también, combinado con las leyes de Morgan, para contar la intersección de conjuntos. Con <math>\scriptstyle\overline{A}_k</math> representamos el complementario de ''A''<sub>''k''</sub> respecto a un conjunto universal ''A'' tal que <math>\scriptstyle A_k\, \subseteq\, A</math> para todo ''k''. Entonces
| |||