Fórmula de inclusión-exclusión

La fórmula de inclusión-exclusión (o principio de inclusión-exclusión ) es una fórmula combinatoria que permite determinar la potencia de la unión de un número finito de conjuntos finitos , que en el caso general pueden intersecarse entre sí. En la teoría de la probabilidad, un análogo del principio de inclusión-exclusión se conoce como la fórmula de Poincaré [1] .

Por ejemplo, en el caso de dos conjuntos, la fórmula de inclusión-exclusión es: $A,B$

$|A\taza B|=|A|+|B|-|A\tapa B|.$

En total , los elementos de intersección se tienen en cuenta dos veces, y para compensar esto, restamos del lado derecho de la fórmula. La validez de este razonamiento se puede ver en el diagrama de Euler-Venn para dos conjuntos, que se muestra en la figura de la derecha. ${\ estilo de visualización | A | + | B |}$ $A\cap B$ $|A\capB|$

De la misma forma, en el caso de los conjuntos, el proceso de encontrar el número de elementos de la unión consiste en incluir todo, luego excluir el exceso, luego incluir los erróneamente excluidos, y así sucesivamente, es decir, alternativamente incluir y excluir. De ahí viene el nombre de la fórmula. $n>2$ $A_{1}\taza A_{2}\taza \ldots \taza A_{n}$

Redacción

La fórmula de inclusión-exclusión se puede formular de diferentes formas.

En términos de conjuntos

Sean conjuntos finitos . La fórmula de inclusión-exclusión establece: $A_{1},A_{2},\ldots,A_{n}$

${\biggl |}\bigcup_{i=1}^{n}A_{i}{\biggl |}=\sum_{i}|A_{i}|-\sum_{i<j}|A_ {i}\cap A_{j}|+\sum _{i<j<k}|A_{i}\cap A_{j}\cap A_{k}|-\ldots +(-1)^{n -1}|A_{1}\cap A_{2}\cap \ldots \cap A_{n}|.$

En , obtenemos la fórmula para dos conjuntos dada arriba. $n=2$

En términos de propiedades

El principio de inclusión-exclusión se da a menudo en la siguiente formulación alternativa [2] . Sea dado un conjunto finito que consta de elementos, y sea un conjunto de propiedades . Cada elemento del conjunto puede o no tener alguna de estas propiedades. Denotar por el número de elementos que tienen propiedades (y, quizás, algunas otras). También denotamos el número de elementos que no tienen ninguna de las propiedades . Entonces la fórmula se lleva a cabo: $tu$ $norte$ $a_1, \ldots , a_n$ $tu$ $N(a_{i_{1))\ldots a_{i_{s)))$ $a_{i_{1}},\ldots,a_{i_{s}}$ $N({\overline {a}}_{i_{1}}\ldots {\overline {a}}_{i_{s}})$ $a_{i_{1}},\ldots,a_{i_{s}}$

$N({\overline {a}}_{1}\ldots {\overline {a}}_{n})=N-\sum_{i}N(a_{i})+\sum_{i< j}N(a_{i}a_{j})-\sum_{i<j<k}N(a_{i}a_{j}a_{k})+\ldots +(-1)^{n }N(a_{1}\ldots a_{n}).$

La formulación del principio de inclusión-exclusión en términos de conjuntos es equivalente a la formulación en términos de propiedades. De hecho, si los conjuntos son subconjuntos de algún conjunto , entonces, en virtud de las reglas de Morgan (una línea sobre un conjunto es una adición en un conjunto ), la fórmula de inclusión-exclusión se puede reescribir de la siguiente manera: $Ai}$ $tu$ $|\bigcup \nolimits _{i}A_{i}|=|U|-|\bigcap \nolimits _{i}{\overline {A_{i}}}|$ $tu$

${\biggl |}\bigcap _{i=1}^{n}{\overline {A_{i))}{\biggl |}=|U|-\sum _{i}|A_{i}|+ \sum _{i<j}|A_{i}\cap A_{j}|-\sum _{i<j<k}|A_{i}\cap A_{j}\cap A_{k}|+ \ldots +(-1)^{n}|A_{1}\cap A_{2}\cap \ldots \cap A_{n}|.$

Si ahora en lugar de " un elemento pertenece a un conjunto " decimos "un elemento tiene una propiedad ", entonces obtenemos la formulación del principio de inclusión-exclusión en términos de propiedades, y viceversa. $X$ $Ai}$ $X$ $ai}$

Indicar por el número de elementos que tienen exactamente las propiedades del conjunto Luego, la fórmula de inclusión-exclusión se puede reescribir de la siguiente forma: ${\ estilo de visualización N (r)}$ $r$ $a_1, \ldots , a_n$

$N(0)=\sum_{k=0}^{n}(-1)^{k}\sum_{i_{1}<\ldots <i_{k}}N(i_{1},\ ldots ,i_{k}).$

Prueba

Hay varias demostraciones de la fórmula de inclusión-exclusión.

Prueba por inducción

La fórmula de inclusión-exclusión se puede probar por inducción [1] [3] .

Para , la fórmula de inclusión-exclusión es trivial: $n=1$

$N({\overline {a)))=NN(a).$

Dejemos que la fórmula sea cierta para , demostrémosla para . $n=m$ ${\ estilo de visualización n = m + 1}$

Sea cada elemento del conjunto puede o no tener alguna de las propiedades . Apliquemos la fórmula de inclusión-exclusión para las propiedades : $tu$ ${\displaystyle a_{1},\ldots,a_{m},a_{m+1))$ ${\displaystyle a_{1},\ldots,a_{m))$

$N({\overline {a}}_{1}\ldots {\overline {a}}_{m})=N-\sum _{i\leq m}N(a_{i})+\sum _ {i<j\leq m}N(a_{i}a_{j})+\ldots +(-1)^{m}N(a_{1}\ldots a_{m}).$

Ahora aplicamos la fórmula de las propiedades al conjunto de objetos para los que se cumple la propiedad : $a_{1},\ldots,a_{m}$ ${\ Displaystyle N (a_ {m + 1})}$ $a_{m+1}$

$N({\overline {a}}_{1}\ldots {\overline {a}}_{m}a_{m+1})=N(a_{m+1})-\sum _{i\ leq m}N(a_{i}a_{m+1})+\sum _{i<j\leq m}N(a_{i}a_{j}a_{m+1})+\ldots +( -1)^{m}N(a_{1}\ldots a_{m}a_{m+1}).$

Finalmente, aplicamos la fórmula para una sola propiedad a una colección de objetos que no tienen propiedades : $a_{m+1}$ $N({\sobrelínea {a}}_{1}\ldots {\sobrelínea {a}}_{m})$ $a_{1},\ldots,a_{m}$

$N({\overline {a}}_{1}\ldots {\overline {a}}_{m}{\overline {a}}_{m+1})=N({\overline {a}} _{1}\ldots {\overline {a}}_{m})-N({\overline {a}}_{1}\ldots {\overline {a}}_{m}a_{m+1 }).$

Combinando las tres fórmulas anteriores, obtenemos la fórmula de inclusión-exclusión para propiedades . QED ■ $m+1$ $a_{1},\ldots,a_{m+1}$

prueba combinatoria

Considere un elemento arbitrario y calcule cuántas veces se tiene en cuenta en la parte derecha de la fórmula de inclusión-exclusión [2] . ${\ estilo de visualización e \ en U}$

Si el elemento no tiene ninguna de las propiedades , entonces se cuenta exactamente 1 vez en el lado derecho de la fórmula (en el miembro ). $mi$ $ai}$ $norte$

Deje que un elemento tenga exactamente las propiedades, digamos . Da 1 en aquellos sumandos para los que existe un subconjunto , y 0 para el resto. El número de tales subconjuntos es, por definición, el número de combinaciones . Por lo tanto, la contribución del elemento al lado derecho es $mi$ $r$ $a_{j_{1}},\ldots,a_{j_{r}}$ $\sum \nolimits _{i_{1}<\ldots <i_{s}}N(a_{i_{1}},\ldots ,a_{i_{s}})$ $\{i_{1},\ldots,i_{s}\}$ $\{j_{1},\ldots,j_{r}\}$ ${\tbinom {r}{s})$ $mi$

$1-{r \elegir 1}+{r \elegir 2}-\ldots +(-1)^{r}{r \elegir r}.$

Cuando el número de combinaciones es igual a cero. La suma restante, en virtud del teorema del binomio, es igual a ${\ estilo de visualización s> r}$

$\sum _{s=0}^{r}(-1)^{s}{r \choose s}={\bigg (}1+(-1){\bigg )}^{r}=0.$

Por lo tanto, el lado derecho de la fórmula de inclusión-exclusión tiene en cuenta cada elemento que no tiene las propiedades especificadas exactamente una vez, y cada elemento que tiene al menos una de las propiedades, cero veces. Por tanto, es igual al número de elementos que no tienen ninguna de las propiedades , es decir, . QED ■ $ai}$ $N({\sobrelínea {a}}_{1}\ldots {\sobrelínea {a}}_{n})$

Prueba a través de funciones de indicador

Sean conjuntos arbitrarios ( no necesariamente finitos) que son subconjuntos de algún conjunto , y sean funciones indicadoras (o, de manera equivalente, propiedades de ). $Ai}$ $tu$ $\mathbf {1} _{A_{i}}$ $Ai}$ $ai}$

La función indicadora de sus complementos es ${\ Displaystyle {\ overline {A_ {i}}}}$

$\mathbf {1} _{\overline {A_{i}}}=1-\mathbf {1} _{A_{i}},$

y la función indicadora de la intersección de complementos:

$\mathbf {1}_{\cap_{i}{\overline {A_{i}}}}=\prod_{i}(1-\mathbf {1}_{A_{i}}).$

Expandiendo los corchetes del lado derecho y usando nuevamente el hecho de que la función indicadora de la intersección de conjuntos es igual al producto de sus funciones indicadoras, obtenemos:

$\mathbf {1}_{\bigcap_{i}{\overline {A_{i}}}}=1-\sum_{i}\mathbf {1}__{A_{i}}+\sum__ i<j}\mathbf {1} _{A_{i}\cap A_{j}}-\sum _{i<j<k}\mathbf {1} _{A_{i}\cap A_{j} \cap A_{k}}+\ldots +(-1)^{n}\mathbf {1} _{A_{1}\cap \ldots \cap A_{n}}.$

Esta relación es una forma del principio de inclusión-exclusión. Expresa una identidad lógica [1] y es cierto para conjuntos arbitrarios . En el caso de conjuntos finitos (y, en consecuencia, bajo el supuesto de que el conjunto es finito ), sumando esta razón sobre todos y utilizando el hecho de que para un subconjunto arbitrario su potencia es igual a $Ai}$ $Ai}$ $tu$ $x\en ti$ ${\ estilo de visualización A \ subconjunto U}$

|A|=\sum_{x\in U}\mathbf {1}_{A}(x),

obtenemos una formulación del principio de inclusión-exclusión en términos de cardinalidades de conjuntos (o en términos de propiedades). ■

Prueba topológica

Dotamos a los conjuntos de una topología discreta. En este caso, para , y para , la identidad se cumple En el caso de dos conjuntos y , podemos usar la sucesión exacta de Mayer-Vietoris , que, teniendo en cuenta la desaparición de la cohomología superior, se verá como: $Ai}$ $H^{k}(A_{i})=0$ $k>0$ $k=0$ $\dim H^{0}(A_{i})=|A_{i}|.$ $A_{1}$ $A_{2}$ $0\a H^{0}(A_{1}\cup A_{2})\a H^{0}(A_{1})\oplus H^{0}(A_{2})\ a H^{0}(A_{1}\cap A_{2})\a 0.$ $\dim H^{0}(A_{1})\oplus H^{0}(A_{2})=\dim H^{0}(A_{1}\cup A_{2})+ \dim H^{0}(A_{1}\cap A_{2}),$ $|A_{1}|+|A_{2}|=|A_{1}\cup A_{2}|+|A_{1}\cap A_{2}|,$

En el caso de más de dos conjuntos, para probar la fórmula de inclusión-exclusión, en lugar de la secuencia exacta de Mayer-Vietoris, se debe escribir alguna secuencia espectral (a saber , la secuencia espectral de Leray para mapear la proyección de una unión disjunta a su unión), y también calcular los rangos de los grupos de cohomología. ■ $Ai}$

Aplicación

El problema de los disturbios

Un ejemplo clásico del uso de la fórmula de inclusión-exclusión es el problema del desorden [2] . Se requiere encontrar el número de permutaciones del conjunto tal que para todos . Estas permutaciones se denominan disturbios . $(p_{1},p_{2},\ldots,p_{n})$ $\{1,2,\ldots,n\}$ $p_{i}\neq yo$ $i$

Sea el conjunto de todas las permutaciones y exprese la propiedad de la permutación mediante la igualdad . Entonces el número de perturbaciones es . Es fácil ver que es el número de permutaciones que dejan los elementos en su lugar , y por tanto la suma contiene los mismos términos. La fórmula de inclusión-exclusión da una expresión para el número de perturbaciones: $tu$ $pags$ $ai}$ $p_{i}=i$ $N({\sobrelínea {a}}_{1},{\sobrelínea {a}}_{2},\ldots,{\sobrelínea {a}}_{n})$ $N(a_{i_{1}},\ldots,a_{i_{s}})=(ns)!$ $i_{1},\ldots,i_{s}$ $\sum N(a_{i_{1}},a_{i_{2}},\ldots,a_{i_{s}})$ ${\tbinom {n}{s})$ $D_{n}$

$D_{n}=n!-{n \elegir 1}(n-1)!+{n \elegir 2}(n-2)!-\ldots +(-1)^{n}{n \elegir n }0!.$

Esta relación se puede convertir a la forma

$D_{n}=n!\left(1-{\frac {1}{1!}}+{\frac {1}{2!}}-\ldots +{\frac {(-1)^{n }}{n!}}\derecha).$

Es fácil ver que la expresión entre paréntesis es una suma parcial de la serie . Así, con buena precisión, el número de perturbaciones es una fracción del número total de permutaciones: $\sum _{k=0}^{\infty}{\frac {(-1)^{k}}{k!}}=e^{-1}$ $1/e$ $P_{n}=n!$

$D_{n}/P_{n}\aprox. 1/e.$

Cálculo de la función de Euler

Otro ejemplo de aplicación de la fórmula de inclusión-exclusión es encontrar una expresión explícita para la función de Euler [4] , que expresa el número de números de , coprimos con . $\varfi (n)$ $\{1,2,\ldots,n\}$ $norte$

Sea la descomposición canónica de un número en factores primos de la forma $norte$

$n=p_{1}^{s_{1}}p_{2}^{s_{2}}\ldots p_{k}^{s_{k}}.$

Un número es coprimo con si y solo si ninguno de los divisores primos lo divide . Si ahora la propiedad significa que divide , entonces el número de números coprimos con es . $m\in \{1,\ldots n\}$ $norte$ $Pi}$ $metro$ $ai}$ $Pi}$ $metro$ $norte$ $N({\overline {a}}_{1},\ldots,{\overline {a}}_{k})$

El número de números que tienen propiedades es , porque . $N(a_{i_{1}},\ldots,a_{i_{s}})$ $a_{i_{1}},\ldots,a_{i_{s}}$ $n/p_{i_{1}}\ldots p_{i_{s}}$ $p_{i_{1}}|m,\ldots,p_{i_{s}}|m\Leftrightarrow p_{i_{1}}\ldots p_{i_{s}}|m$

Por la fórmula de inclusión-exclusión, encontramos

$\varphi (n)=n-\sum _{i}n/p_{i}+\sum _{i,j}n/p_{i}p_{j}-\ldots +(-1)^{k }n/p_{1}\ldots p_{k}.$

Esta fórmula se convierte a la forma:

$\varphi (n)=n\prod _{i=1}^{k}\left(1-{\frac {1}{p_{i}}}\right).$

Variaciones y generalizaciones

El principio de inclusión-exclusión para probabilidades

Sea un espacio de probabilidad . Entonces la fórmula [1] [3] [5] es válida para eventos arbitrarios $(\Omega,{\mathfrak {F)),{\mathcal {P)))$ $A_{1},A_{2},\ldots,A_{n}$

{\mathcal {P}}{\biggl (}\bigcup _{i=1}^{n}A_{i}{\biggr)}=\sum_{i}{\mathcal {P}}(A_{ i})-\sum _{i<j}{\mathcal {P}}(A_{i}\cap A_{j})+\sum _{i<j<k}{\mathcal {P}}( A_{i}\cap A_{j}\cap A_{k})+\ldots +(-1)^{n-1}\,{\mathcal {P}}\left(\bigcap _{i=1 }^{n}A_{i}\derecha).

Esta fórmula expresa el principio de inclusión-exclusión para probabilidades . Se puede obtener del principio de inclusión-exclusión en forma de funciones indicadoras:

$\mathbf {1}_{\bigcup_{i}A_{i}}=\sum_{i}\mathbf {1}__{A_{i}}-\sum_{i<j}\mathbf {1 } _ {A_{i}\cap A_{j}}+\sum_{i<j<k}\mathbf {1}__{A_{i}\cap A_{j}\cap A_{k}}+ \ldots +(-1)^{n-1}\,\mathbf {1} _{A_{1}\cap \ldots \cap A_{n}}.$

Sean eventos del espacio de probabilidad , es decir . Tomemos la expectativa matemática de ambas partes de esta razón y, usando la linealidad de la expectativa matemática y la igualdad para un evento arbitrario , obtengamos la fórmula de inclusión-exclusión para probabilidades. $Ai}$ $(\Omega,{\mathfrak {F)),{\mathcal {P)))$ $A_{i}\en {\mathfrak {F}}$ ${\ matemáticas {M}}$ ${\mathcal {P}}(A)={\mathcal {M}}(\mathbf {1} _{A})$ $A\en {\mathfrak {F}}$

El principio de inclusión-exclusión en los espacios de medida

Que sea un espacio con medida . Entonces, para conjuntos medibles arbitrarios de medida finita , se cumple la fórmula de inclusión-exclusión: $(X,{\mathfrak{S}),\mu )$ $Ai}$ $\mu (A_{i})<\infty$

$\mu {\biggl (}\bigcup _{i=1}^{n}A_{i}{\biggr)}=\sum _{i}\mu (A_{i})-\sum _{i< j}\mu (A_{i}\cap A_{j})+\sum _{i<j<k}\mu (A_{i}\cap A_{j}\cap A_{k})+\ldots +(-1)^{n-1}\,\mu \left(\bigcap _{i=1}^{n}A_{i}\right).$

Obviamente, el principio de inclusión-exclusión para probabilidades y para cardinalidades de conjuntos finitos son casos especiales de esta fórmula. En el primer caso, la medida es, naturalmente, una medida de probabilidad en el espacio de probabilidad correspondiente : . En el segundo caso, se toma como medida la cardinalidad del conjunto : . $\mu (A)={\mathcal {P}}(A)$ ${\ estilo de visualización \ mu (A) = | A |}$

El principio de inclusión-exclusión para espacios de medida también se puede derivar, como para los casos especiales anteriores, de la identidad para funciones indicadoras:

Sean conjuntos medibles del espacio , es decir . Integramos ambas partes de esta igualdad con respecto a la medida , usamos la linealidad de la integral y la relación , y obtenemos la fórmula de inclusión-exclusión para la medida. $Ai}$ $(X,{\mathfrak{S}),\mu )$ $A_{i}\in {\mathfrak{S))$ $\mu$ $\mu (A)=\int _{X}\mathbf {1} _{A}(x)\,d\mu$

Identidad de altibajos

La fórmula de inclusión-exclusión puede considerarse como un caso especial de la identidad de máximos y mínimos :

\max(a_{1},\ldots,a_{n})=\sum _{i}a_{i}-\sum _{i<j}\min(a_{i},a_{j})+ \ldots +(-1)^{n-1}\,\min(a_{1},\ldots,a_{n}).

Esta relación es válida para números arbitrarios . En un caso particular, cuando obtenemos una de las formas del principio de inclusión-exclusión. De hecho, si ponemos , donde es un elemento arbitrario de , entonces obtenemos la relación para funciones indicadoras de conjuntos: $ai}$ $a_{i}\in\{0,1\}$ $a_{i}=\mathbf {1} _{A_{i}}(x)$ $X$ $tu$

$\mathbf {1}_{\bigcup_{i}A_{i}}(x)=\sum_{i}\mathbf {1}__{A_{i}}(x)-\sum_{i< j}\mathbf {1} _{A_{i}\cap A_{j}}(x)+\sum_{i<j<k}\mathbf {1}__{A_{i}\cap A_{j }\cap A_{k}}(x)+\ldots +(-1)^{n-1}\,\mathbf {1} _{A_{1}\cap \ldots \cap A_{n}}( X).$

Inversión de Möbius

Sea un conjunto finito, y sea una función arbitraria definida sobre un conjunto de subconjuntos y tomando valores reales. Definimos la función de la siguiente manera: $S$ $f\colon 2^{S}\to \mathbb {R}$ $S$ $g\colon 2^{S}\to \mathbb {R}$

$g(Y)=\sum _{X\supset Y}f(X).$

Entonces la siguiente fórmula de inversión tiene [6] [7] :

f(Y)=\sum _{X\supset Y}(-1)^{|X|-|Y|}\,g(X).

Esta afirmación es un caso especial de la fórmula general de inversión de Möbius para el álgebra de incidencia del conjunto de todos los subconjuntos de un conjunto parcialmente ordenado por la relación de inclusión . ${\ estilo de visualización 2^{S}}$ $S$ $\subconjunto$

Mostremos cómo esta fórmula implica el principio de inclusión-exclusión para conjuntos finitos. Sea dada una familia de subconjuntos de un conjunto finito , denotemos el conjunto de índices . Para cada conjunto de índices , lo definimos como el número de elementos incluidos únicamente en aquellos conjuntos para los que . Matemáticamente, esto se puede escribir como: $A_{1},\ldots,A_{n}$ $tu$ $S=\{1,\lpuntos,n\}$ ${\ estilo de visualización X \ subconjunto S}$ $f(X)$ $Ai}$ ${\ estilo de visualización i \ en X}$

$f(X)=\left|\left(\bigcap _{i\in X}A_{i}\right)\cap \left(\bigcap _{j\notin X}{\overline {A_{j)) }\derecho)\derecho|.$

Entonces la función definida por la fórmula $g\colon 2^{S}\to \mathbb {R}$

g(Y)=\sum _{X\supset Y}f(X),

da el número de elementos, cada uno de los cuales está incluido en todos los conjuntos y , tal vez, en otros. Eso es $Ai}$ ${\ estilo de visualización i \ en X}$

g(X)=\left|\bigcap _{i\in X}A_{i}\right|.

Tenga en cuenta además que es el número de elementos que no tienen ninguna de las propiedades: $f(\varnada)$

f(\varnothing)=\left|\bigcap _{i}{\overline {A_{i))}\right|.

Teniendo en cuenta las observaciones realizadas, escribimos la fórmula de inversión de Möbius:

\left|\bigcap _{i}{\overline {A_{i}}}\right|=\sum _{X}(-1)^{|X|}\,\left|\bigcap _{i\ en X}A_{i}\right|.

Esta es exactamente la fórmula de inclusión-exclusión para conjuntos finitos, solo que no agrupa términos relacionados con los mismos valores . $|X|$

Historia

La fórmula de inclusión-exclusión fue publicada por primera vez por el matemático portugués Daniel da Silva en 1854 [1] . Pero ya en 1713, Nicholas Bernoulli utilizó este método para resolver el problema de Montmort , conocido como el problema de la reunión ( en francés: Le problème des rencontres ) [8] , del cual el problema del desorden es un caso especial . Además, la fórmula de inclusión-exclusión está asociada con los nombres del matemático francés Abraham de Moivre. y el matemático inglés Joseph Sylvester [9] .

Véase también

Fórmula de Grassmann
Boole

Notas

↑ 1 2 3 4 5 Riordan J. Introducción al análisis combinatorio = Introducción al análisis combinatorio. - M. : Editorial de literatura extranjera, 1963. - S. 63-66. — 289 pág.
— 424 págs.
↑ 1 2 Rybnikov K. A. Introducción al análisis combinatorio. - 2ª ed. - M. : Editorial de la Universidad Estatal de Moscú, 1985. - S. 69-73. — 309 pág.
↑ Rybnikov K. A. Introducción al análisis combinatorio. - 2ª ed. - M. : Editorial de la Universidad Estatal de Moscú, 1985. - S. 266. - 309 p.
↑ Borovkov, A. A. Teoría de la probabilidad. - 2ª ed. - M. : "Nauka", 1986. - S. 24. - 431 p.
↑ Hall M. Teoría combinatoria . - M. : "Mir", 1970. - S. 30 -31. — 424 págs.
↑ Stanley R. Combinatoria enumerativa = Combinatoria enumerativa. - M. : "Mir", 1990. - S. 103-107. — 440 s.
↑ Weisstein, Eric W. Derangement en el sitio web de Wolfram MathWorld .
↑ Rybnikov K. A. Introducción al análisis combinatorio. - 2ª ed. - M. : Editorial de la Universidad Estatal de Moscú, 1985. - S. 264. - 309 p.

Literatura

Riordan J. Introducción al análisis combinatorio = Introducción al análisis combinatorio. - M. : Editorial de Literatura Extranjera, 1963. - 289 p.
Rybnikov K. A. Introducción al análisis combinatorio. - 2ª ed.
Stanley R. Combinatoria enumerativa = Combinatoria enumerativa. — M .: Mir, 1990. — 440 p.
Hall M. Teoría Combinatoria . - M. : Mir, 1970. - 424 p.
I. Yaglom. Parches en el caftán // Kvant . - 1974. - Nº 2 . - S. 13-21 .

Enlaces

Weisstein, Eric W. Principio de inclusión-exclusión (inglés) en el sitio web de Wolfram MathWorld .