En combinatoria , una rama de las matemáticas , el principio de inclusión-exclusión es una técnica de conteo que generaliza el método familiar de obtener el número de elementos en la unión de dos conjuntos finitos ; expresado simbólicamente como
donde A y B son dos conjuntos finitos y | S | indica la cardinalidad de un conjunto S (que puede considerarse como el número de elementos del conjunto, si el conjunto es finito ). La fórmula expresa el hecho de que la suma de los tamaños de los dos conjuntos puede ser demasiado grande ya que algunos elementos pueden contarse dos veces. Los elementos contados dos veces son los que se encuentran en la intersección de los dos conjuntos y la cuenta se corrige restando el tamaño de la intersección.
El principio se ve más claramente en el caso de tres conjuntos, que para los conjuntos A , B y C viene dado por
Esta fórmula se puede verificar contando cuántas veces se incluye cada región en la figura del diagrama de Venn en el lado derecho de la fórmula. En este caso, al eliminar las contribuciones de los elementos contados en exceso, el número de elementos en la intersección mutua de los tres conjuntos se ha restado con demasiada frecuencia, por lo que debe agregarse nuevamente para obtener el total correcto.
La generalización de los resultados de estos ejemplos da el principio de inclusión-exclusión. Para encontrar la cardinalidad de la unión de n conjuntos:
- Incluya las cardinalidades de los conjuntos.
- Excluya las cardinalidades de las intersecciones por pares.
- Incluya las cardinalidades de las intersecciones triples.
- Excluya las cardinalidades de las intersecciones cuádruples.
- Incluya las cardinalidades de las intersecciones quíntuples.
- Continúe, hasta que la cardinalidad de la n -intersección en tuplas se incluya (si n es impar) o se excluya ( n par).
El nombre proviene de la idea de que el principio se basa en una inclusión demasiado generosa , seguida de una exclusión compensadora . Este concepto se atribuye a Abraham de Moivre (1718); [1] pero aparece primero en un artículo de Daniel da Silva (1854), [2] y más tarde en un artículo de JJ Sylvester (1883). [3] A veces, el principio se conoce como la fórmula de Da Silva, o Sylvester debido a estas publicaciones. El principio es un ejemplo del método del tamiz ampliamente utilizado en la teoría de números y a veces se lo denomina fórmula del tamiz , [4] aunque Legendre ya utilizó un dispositivo similar en el contexto del tamiz en 1808.
Como las probabilidades finitas se calculan como recuentos relativos a la cardinalidad del espacio de probabilidad , las fórmulas para el principio de inclusión-exclusión siguen siendo válidas cuando las cardinalidades de los conjuntos se reemplazan por probabilidades finitas. De manera más general, ambas versiones del principio pueden incluirse bajo el paraguas común de la teoría de la medida .
En un contexto muy abstracto, el principio de inclusión-exclusión se puede expresar como el cálculo de la inversa de una determinada matriz. [5] Esta inversa tiene una estructura especial, lo que hace que el principio sea una técnica extremadamente valiosa en combinatoria y áreas relacionadas de las matemáticas. Como dijo Gian-Carlo Rota : [6]
"Uno de los principios de enumeración más útiles en la probabilidad discreta y la teoría combinatoria es el celebrado principio de inclusión-exclusión. Cuando se aplica hábilmente, este principio ha dado la solución a muchos problemas combinatorios".
Declaración
En su forma general, el principio de inclusión-exclusión establece que para conjuntos finitos A 1 , ..., A n , uno tiene la identidad
( 1 )
Esto se puede escribir de forma compacta como
o
En palabras, para contar el número de elementos en una unión finita de conjuntos finitos, primero sume las cardinalidades de los conjuntos individuales, luego reste el número de elementos que aparecen en al menos dos conjuntos, luego vuelva a sumar el número de elementos que aparecen en al menos tres conjuntos, luego reste el número de elementos que aparecen en al menos cuatro conjuntos, y así sucesivamente. Este proceso siempre termina ya que no puede haber elementos que aparezcan en más de la cantidad de conjuntos en la unión. (Por ejemplo, si no puede haber elementos que aparezcan en más de conjuntos de manera equivalente, no puede haber elementos que aparezcan en al menos conjuntos.)
En las aplicaciones es común ver el principio expresado en su forma complementaria. Es decir, dejando que S sea un conjunto universal finito que contiene todos los A i y dejandodenotar el complemento de A i en S , por las leyes de De Morgan tenemos
Como otra variante del enunciado, sea P 1 , ..., P n una lista de propiedades que los elementos de un conjunto S pueden tener o no, entonces el principio de inclusión-exclusión proporciona una forma de calcular el número de elementos de S que no tienen ninguna de las propiedades. Sea A i el subconjunto de elementos de S que tienen la propiedad P i y use el principio en su forma complementaria. Esta variante se debe a JJ Sylvester . [1]
Observe que si tiene en cuenta solo las primeras m
Ejemplos de
Contando enteros
Como ejemplo simple del uso del principio de inclusión-exclusión, considérese la pregunta: [7]
- ¿Cuántos enteros en {1, ..., 100} no son divisibles entre 2, 3 o 5?
Sea S = {1, ..., 100} y P 1 la propiedad de que un número entero es divisible por 2, P 2 la propiedad de que un número entero es divisible por 3 y P 3 la propiedad de que un número entero es divisible por 5. Sea A i es el subconjunto de S cuyos elementos tienen la propiedad P i que tenemos por conteo elemental: | A 1 | = 50, | A 2 | = 33 y | A 3 | = 20. Hay 16 de estos números enteros divisibles por 6, 10 divisibles por 10 y 6 divisibles por 15. Finalmente, solo hay 3 enteros divisibles por 30, por lo que el número de enteros no es divisible por 2, 3 o 5 es dado por:
- 100 - (50 + 33 + 20) + (16 + 10 + 6) - 3 = 26.
Contando trastornos
Un ejemplo más complejo es el siguiente.
Suponga que hay una baraja de n cartas numeradas del 1 al n . Suponga que una carta numerada m está en la posición correcta si es la carta número m en la baraja. ¿De cuántas formas, W , se pueden barajar las cartas con al menos 1 carta en la posición correcta?
Comenzar por definir conjunto A m , que es todos los ordenamientos de las cartas con el m º tarjeta correcta. Entonces el número de órdenes, W , con al menos una tarjeta en la posición correcta, m , es
Aplicar el principio de inclusión-exclusión,
Cada valor representa el conjunto de barajas que tienen al menos p valores m 1 , ..., m p en la posición correcta. Tenga en cuenta que el número de barajas con al menos p valores correctos solo depende de p , no de los valores particulares de. Por ejemplo, el número de barajadas que tienen la 1ª, 3ª y 17ª cartas en la posición correcta es el mismo que el número de barajas que tienen la 2ª, 5ª y 13ª cartas en las posiciones correctas. Solo importa que de las n cartas, 3 fueron elegidas para estar en la posición correcta. Por lo tanto hayigualdad de condiciones en el p ésimo sumatorio (véase combinación ).
es el número de ordenamientos que tienen p elementos en la posición correcta, que es igual al número de formas de ordenar los n - p elementos restantes , o ( n - p ) !. Así finalmente obtenemos:
Una permutación en la que ninguna carta está en la posición correcta se denomina trastorno . Tomando n ! para ser el número total de permutaciones, la probabilidad Q de que una mezcla aleatoria produzca un trastorno viene dada por
un truncamiento en n + 1 términos de la expansión de Taylor de e −1 . Por lo tanto, la probabilidad de adivinar un orden para una baraja de cartas barajada y ser incorrecto en todas las cartas es aproximadamente e -1 o 37%.
Un caso especial
La situación que aparece en el ejemplo de trastorno anterior ocurre con suficiente frecuencia como para merecer una atención especial. [8] Es decir, cuando el tamaño de los conjuntos de intersección que aparecen en las fórmulas del principio de inclusión-exclusión depende únicamente del número de conjuntos en las intersecciones y no de los conjuntos que aparecen. Más formalmente, si la intersección
tiene la misma cardinalidad, digamos α k = | A J |, para cada subconjunto de elementos k J de {1, ..., n }, entonces
O, en la forma complementaria, donde el conjunto universal S tiene cardinalidad α 0 ,
Una generalización
Dada una familia (se permiten repeticiones) de subconjuntos A 1 , A 2 , ..., A n de un conjunto universal S , el principio de inclusión-exclusión calcula el número de elementos de S en ninguno de estos subconjuntos. Una generalización de este concepto calcularía el número de elementos de S que aparecen exactamente en algunos m fijos de estos conjuntos.
Sea N = [ n ] = {1,2, ..., n }. Si definimos, entonces el principio de inclusión-exclusión se puede escribir como, usando la notación de la sección anterior; el número de elementos de S contenidos en ninguno de los A i es:
Si I es un subconjunto fijo del conjunto de índices N , entonces el número de elementos que pertenecen a A i para todo i en I y para ningún otro valor es: [9]
Definir los conjuntos
Buscamos el número de elementos en ninguno de los B k que, por el principio de inclusión-exclusión (con), es
La correspondencia K ↔ J = I ∪ K entre subconjuntos de N \ I y subconjuntos de N que contienen I es una biyección y si J y K corresponden bajo este mapa, entonces B K = A J , lo que demuestra que el resultado es válido.
En probabilidad
En probabilidad , para eventos A 1 , ..., A n en un espacio de probabilidad , el principio de inclusión-exclusión se convierte en n = 2
para n = 3
y en general
que se puede escribir en forma cerrada como
donde la última suma corre sobre todos los subconjuntos I de los índices 1, ..., n que contienen exactamente k elementos, y
denota la intersección de todos los A i con índice en I .
Según las desigualdades de Bonferroni , la suma de los primeros términos de la fórmula es alternativamente un límite superior y un límite inferior para la LHS . Esto se puede utilizar en los casos en que la fórmula completa sea demasiado engorrosa.
Para un espacio de medida general ( S , Σ, μ ) y subconjuntos medibles A 1 , ..., A n de medida finita, las identidades anteriores también son válidas cuando la medida de probabilidadse reemplaza por la medida μ .
Caso especial
Si, en la versión probabilística del principio de inclusión-exclusión, la probabilidad de la intersección A I solo depende de la cardinalidad de I , lo que significa que para cada k en {1, ..., n } hay una a k tal que
entonces la fórmula anterior se simplifica a
debido a la interpretación combinatoria del coeficiente binomial . Por ejemplo, si los eventosson independientes e idénticamente distribuidos , entoncespor todo yo , y tenemos, en cuyo caso la expresión anterior se simplifica a
(Este resultado también se puede derivar más simplemente considerando la intersección de los complementos de los eventos .)
Una simplificación análoga es posible en el caso de un espacio de medida general ( S , Σ, μ ) y subconjuntos medibles A 1 , ..., A n de medida finita.
Otras formas
El principio a veces se enuncia en la forma [10] que dice que si
luego
La versión combinatoria y probabilística del principio de inclusión-exclusión son instancias de (**).
Prueba |
---|
Llevar , , y respectivamente para todos los conjuntos con . Entonces obtenemos respectivamente para todos los conjuntos con . Esto se debe a que los elementos de puede estar contenido en otros ( con ) también, y el la fórmula se ejecuta exactamente a través de todas las posibles extensiones de los conjuntos con otro , contando solo para el conjunto que coincide con el comportamiento de pertenencia de , Si recorre todos los subconjuntos de (como en la definición de ). Desde , obtenemos de (**) con que y al intercambiar lados, se sigue la versión combinatoria y probabilística del principio de inclusión-exclusión. |
Si uno ve un numero como un conjunto de sus factores primos, entonces (**) es una generalización de la fórmula de inversión de Möbius para números naturales libres de cuadrados . Por lo tanto, (**) es visto como la fórmula de inversión de Möbius para el álgebra de incidencia del conjunto parcialmente ordenado de todos los subconjuntos de A .
Para una generalización de la versión completa de la fórmula de inversión de Möbius, (**) debe generalizarse a conjuntos múltiples . Para conjuntos múltiples en lugar de conjuntos, (**) se convierte en
dónde es el multiset para el que , y
- μ ( S ) = 1 si S es un conjunto (es decir, un conjunto múltiple sin elementos dobles) de cardinalidad par .
- μ ( S ) = −1 si S es un conjunto (es decir, un conjunto múltiple sin elementos dobles) de cardinalidad impar.
- μ ( S ) = 0 si S es un multiset adecuado (es decir, S tiene elementos dobles).
Darse cuenta de es solo el de (**) en caso es un conjunto.
Prueba de (***) |
---|
Sustituir en el lado derecho de (***). Darse cuenta deaparece una vez a ambos lados de (***). Entonces debemos mostrar eso para todos con , los términos cancelar en el lado derecho de (***). Para ese propósito, tome un fijo tal que y tomar un fijo arbitrario tal que . Darse cuenta de debe ser un conjunto para cada aparición positiva o negativa de en el lado derecho de (***) que se obtiene mediante el multiset tal que . Ahora cada aparición de en el lado derecho de (***) que se obtiene mediante tal que es un conjunto que contiene anula con el que se obtiene mediante el correspondiente tal que es un conjunto que no contiene . Esto da el resultado deseado. |
Aplicaciones
El principio de inclusión-exclusión se utiliza ampliamente y aquí solo se pueden mencionar algunas de sus aplicaciones.
Contando trastornos
Una aplicación bien conocida del principio de inclusión-exclusión es el problema combinatorio de contar todos los trastornos de un conjunto finito. Un trastorno de un conjunto A es una biyección de A en sí mismo que no tiene puntos fijos. Mediante el principio de inclusión-exclusión se puede demostrar que si la cardinalidad de A es n , entonces el número de trastornos es [ n ! / E ] donde [ x ] indica la entero más próximo a x ; una prueba detallada está disponible aquí y también vea la sección de ejemplos anterior.
La primera aparición del problema de contar el número de trastornos se encuentra en un libro antiguo sobre juegos de azar: Essai d'analyse sur les jeux de hazard de PR de Montmort (1678-1719) y se conocía como "el problema de Montmort" o por el nombre que le dio, " problème des rencontres ". [11] El problema también se conoce como problema de hatcheck.
El número de trastornos también se conoce como subfactorial de n , ¡escrito! n . De ello se deduce que si a todas las biyecciones se les asigna la misma probabilidad, entonces la probabilidad de que una biyección aleatoria sea un trastorno se acerca rápidamente a 1 / e a medida que n crece.
Contando intersecciones
El principio de inclusión-exclusión, combinado con la ley de De Morgan , también se puede utilizar para contar la cardinalidad de la intersección de conjuntos. Dejarrepresentar el complemento de A k con respecto a algún conjunto universal A tal quepor cada k . Entonces nosotros tenemos
convirtiendo así el problema de encontrar una intersección en el problema de encontrar un sindicato.
Coloración gráfica
El principio de exclusión de inclusión forma la base de algoritmos para una serie de problemas de partición de gráficos NP-hard, como la coloración de gráficos. [12]
Una aplicación bien conocida del principio es la construcción del polinomio cromático de un gráfico. [13]
Emparejamientos perfectos de gráficos bipartitos
El número de coincidencias perfectas de un gráfico bipartito se puede calcular utilizando el principio. [14]
Número de funciones en
Dados los conjuntos finitos A y B , ¿cuántas funciones sobreyectivas (sobre funciones) hay de A a B ? Sin ninguna pérdida de generalidad podemos tomar A = {1, ..., k } y B = {1, ..., n }, ya que solo importan las cardinalidades de los conjuntos. Al usar S como el conjunto de todas las funciones de A a B , y definir, para cada i en B , la propiedad P i como "la función pierde el elemento i en B " ( i no está en la imagen de la función), el principio de inclusión-exclusión da el número de funciones sobre entre A y B como: [15]
Permutaciones con posiciones prohibidas
Una permutación del conjunto S = {1, ..., n } donde cada elemento de S está restringido a no estar en ciertas posiciones (aquí la permutación se considera como un ordenamiento de los elementos de S ) se llama permutación con prohibido. posiciones . Por ejemplo, con S = {1,2,3,4}, las permutaciones con la restricción de que el elemento 1 no puede estar en las posiciones 1 o 3, y el elemento 2 no puede estar en la posición 4 son: 2134, 2143, 3124, 4123, 2341, 2431, 3241, 3421, 4231 y 4321. Haciendo que A i sea el conjunto de posiciones en las que el elemento i no puede estar y que la propiedad P i sea la propiedad que una permutación pone al elemento i en una posición en A i , el principio de inclusión-exclusión se puede utilizar para contar el número de permutaciones que satisfacen todas las restricciones. [dieciséis]
En el ejemplo dado, hay 12 = 2 (3!) Permutaciones con la propiedad P 1 , 6 = 3! las permutaciones con propiedad P 2 y ninguna permutaciones tienen propiedades P 3 o P 4 ya que no hay restricciones para estos dos elementos. El número de permutaciones que satisfacen las restricciones es así:
- 4! - (12 + 6 + 0 + 0) + (4) = 24 - 18 + 4 = 10.
El último 4 en este cálculo es el número de permutaciones que tienen propiedades P 1 y P 2 . No hay otras contribuciones distintas de cero a la fórmula.
Números de Stirling del segundo tipo
Los números de Stirling del segundo tipo , S ( n , k ) cuentan el número de particiones de un conjunto de n elementos en k subconjuntos no vacíos ( cajas indistinguibles ). Se puede obtener una fórmula explícita para ellos aplicando el principio de inclusión-exclusión a un problema muy relacionado, a saber, contando el número de particiones de un n -set en k cajas no vacías pero distinguibles ( subconjuntos ordenados no vacíos) . Usando el conjunto universal que consta de todas las particiones del conjunto n en k cajas distinguibles (posiblemente vacías), A 1 , A 2 , ..., A k , y las propiedades P i, lo que significa que la partición tiene la caja A i vacía, el principio de inclusión-exclusión da una respuesta al resultado relacionado. Dividiendo por k ! para eliminar el orden artificial se obtiene el número de Stirling del segundo tipo: [17]
Polinomios de torre
Un polinomio de torres es la función generadora del número de formas de colocar torres que no atacan en un tablero B que parece un subconjunto de los cuadrados de un tablero de ajedrez ; es decir, no puede haber dos torres en la misma fila o columna. El tablero B es cualquier subconjunto de los cuadrados de un tablero rectangular con n filas y m columnas; lo pensamos como las casillas en las que se permite poner una torre. El coeficiente , r k ( B ) de x k en la torre polinomio R B ( x ) es el número de formas k torres, ninguno de los cuales los ataques de otros, pueden estar dispuestos en los cuadrados de B . Para cualquier tablero B , hay un tablero complementarioque consiste en las casillas del tablero rectangular que no están en B . Este tablero complementario también tiene un polinomio de torre con coeficientes
A veces es conveniente poder calcular el coeficiente más alto de un polinomio de torre en términos de los coeficientes del polinomio de torre del tablero complementario. Sin pérdida de generalidad podemos suponer que n ≤ m , por lo que este coeficiente es r n ( B ). El número de formas de colocar n torres no atacantes en el "tablero de ajedrez" completo de n × m (sin tener en cuenta si las torres se colocan en los cuadrados del tablero B ) viene dado por el factorial descendente :
Si P i es la propiedad de que una asignación de n torres no atacantes en el tablero completo tiene una torre en la columna i que no está en un cuadrado del tablero B , entonces por el principio de inclusión-exclusión tenemos: [18]
Función phi de Euler
De totient o función phi Euler, φ ( n ) es una función aritmética que cuenta el número de enteros positivos de menos de o igual a n , que son relativamente primos para n . Es decir, si n es un número entero positivo , entonces φ ( n ) es el número de enteros k en el rango 1 ≤ k ≤ n que no tienen un factor común con n distinto de 1. El principio de inclusión-exclusión se usa para obtener una fórmula para φ ( n ). Sea S el conjunto {1, ..., n } y defina la propiedad P i como que un número en S es divisible por el número primo p i , para 1 ≤ i ≤ r , donde la factorización prima de
Entonces, [19]
Principio de inclusión-exclusión diluido
En muchos casos donde el principio podría dar una fórmula exacta (en particular, contando números primos usando el tamiz de Eratóstenes ), la fórmula que surge no ofrece un contenido útil porque el número de términos que contiene es excesivo. Si cada término individualmente se puede estimar con precisión, la acumulación de errores puede implicar que la fórmula de inclusión-exclusión no es directamente aplicable. En teoría de números , Viggo Brun abordó esta dificultad . Después de un comienzo lento, sus ideas fueron retomadas por otros y se desarrolló una gran variedad de métodos de tamizado . Estos, por ejemplo, pueden intentar encontrar límites superiores para los conjuntos "tamizados", en lugar de una fórmula exacta.
Sean A 1 , ..., A n conjuntos arbitrarios y p 1 , ..., p n números reales en el intervalo unitario cerrado [0,1]. Entonces, para cada número par k en {0, ..., n }, las funciones del indicador satisfacen la desigualdad: [20]
Prueba de declaración principal
Elija un elemento contenido en la unión de todos los conjuntos y deje ser los conjuntos individuales que lo contienen. (Tenga en cuenta que t > 0). Dado que el elemento se cuenta precisamente una vez por el lado izquierdo de la ecuación ( 1 ), debemos demostrar que se cuenta precisamente una vez por el lado derecho. En el lado derecho, las únicas contribuciones distintas de cero ocurren cuando todos los subconjuntos en un término particular contienen el elemento elegido, es decir, todos los subconjuntos se seleccionan de. La contribución es uno para cada uno de estos conjuntos (más o menos según el término) y, por lo tanto, es solo el número (con signo) de estos subconjuntos utilizados en el término. Entonces tenemos:
Por el teorema del binomio ,
Usando el hecho de que y reorganizando los términos, tenemos
y así, el elemento elegido se cuenta solo una vez por el lado derecho de la ecuación ( 1 ).
Prueba algebraica
Se puede obtener una prueba algebraica usando funciones indicadoras (también conocidas como funciones características). La función indicadora de un subconjunto S de un conjunto X es la función
Si y son dos subconjuntos de , luego
Sea A la uniónde los conjuntos A 1 , ..., A n . Para probar el principio de inclusión-exclusión en general, primero verificamos la identidad
(∗)
para funciones de indicador, donde:
La siguiente función
es idénticamente cero porque: si x no está en A , entonces todos los factores son 0 - 0 = 0; y de lo contrario, si x hace pertenecen a alguna A m , entonces la correspondiente m ésimo factor es 1 - 1 = 0. Al expandir el producto en el lado de la mano izquierda, la ecuación (*) sigue.
Para probar el principio de inclusión-exclusión para la cardinalidad de conjuntos, sume la ecuación (∗) sobre todo x en la unión de A 1 , ..., A n . Para derivar la versión usada en probabilidad, tome la expectativa en (∗). En general, integre la ecuación (∗) con respecto a μ . Utilice siempre la linealidad en estas derivaciones.
Ver también
- Principios combinatorios
- La desigualdad de Boole
- Problema del collar
- Fórmula de Schuette-Nesbitt
- Identidad de máximos-mínimos
Notas
- ↑ a b Roberts y Tesman , 2009 , pág. 405
- ^ Mazur 2010 , pág. 94
- ^ van Lint y Wilson 1992 , pág. 77
- ^ van Lint y Wilson 1992 , pág. 77
- ^ Stanley 1986 , pág. 64
- ^ Rota, Gian-Carlo (1964), "Sobre los fundamentos de la teoría combinatoria I. Teoría de las funciones de Möbius", Zeitschrift für Wahrscheinlichkeitstheorie , 2 : 340–368, doi : 10.1007 / BF00531932
- ^ Mazur 2010 , págs. 83-4, 88
- ^ Brualdi 2010 , págs. 167–8
- ^ Cameron 1994 , pág. 78
- ^ Graham, Grötschel y Lovász 1995 , pág. 1049
- ^ van Lint y Wilson 1992 , págs. 77-8
- ^ Björklund, Husfeldt y Koivisto 2009
- ^ Bruto 2008 , págs. 211-13
- ^ Bruto 2008 , págs. 208-10
- ↑ Mazur , 2008 , págs. 84, 5, 90.
- ^ Brualdi 2010 , págs. 177–81
- ^ Brualdi 2010 , págs. 282–7
- ^ Roberts y Tesman 2009 , págs. 419-20
- ^ van Lint y Wilson 1992 , pág. 73
- ↑ ( Fernández, Fröhlich y Alan D. 1992 , Proposición 12.6)
Referencias
- Allenby, RBJT; Slomson, Alan (2010), Cómo contar: Introducción a la combinatoria , las matemáticas discretas y sus aplicaciones (2 ed.), CRC Press, págs. 51–60, ISBN 9781420082609
- Björklund, A .; Husfeldt, T .; Koivisto, M. (2009), "Establecer particiones mediante inclusión-exclusión", SIAM Journal on Computing , 39 (2): 546–563, doi : 10.1137 / 070683933
- Brualdi, Richard A. (2010), Introductory Combinatorics (5.a ed.), Prentice – Hall, ISBN 9780136020400
- Cameron, Peter J. (1994), Combinatoria: temas, técnicas, algoritmos , Cambridge University Press, ISBN 0-521-45761-0
- Fernández, Roberto; Fröhlich, Jürg ; Alan D., Sokal (1992), Random Walks, Critical Phenomena, and Triviality in Quantum Field Theory , Textos y monografías en física, Berlín: Springer-Verlag , págs. Xviii + 444, ISBN 3-540-54358-9, MR 1219313 , Zbl 0.761,60061
- Graham, RL; Grötschel, M .; Lovász, L. (1995), Hand Book of Combinatorics (volumen 2) , MIT Press - Holanda Septentrional, ISBN 9780262071710
- Gross, Jonathan L. (2008), Métodos combinatorios con aplicaciones informáticas , Chapman & Hall / CRC, ISBN 9781584887430
- "Principio de inclusión y exclusión" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
- Mazur, David R. (2010), Combinatorics A Guided Tour , The Mathematical Association of America, ISBN 9780883857625
- Roberts, Fred S .; Tesman, Barry (2009), Combinatoria aplicada (2.a ed.), CRC Press, ISBN 9781420099829
- Stanley, Richard P. (1986), Enumerative Combinatorics Volume I , Wadsworth y Brooks / Cole, ISBN 0534065465
- van Lint, JH; Wilson, RM (1992), Un curso de combinatoria , Cambridge University Press, ISBN 0521422604
Este artículo incorpora material del principio de inclusión-exclusión en PlanetMath , que está bajo la licencia Creative Commons Attribution / Share-Alike License .