Principio de inclusión-exclusión

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Contando técnica en combinatoria

En combinatoria, una rama de las matemáticas, el principio de inclusión-exclusión es una técnica de conteo que generaliza el conocido método de obtener el número de elementos en la unión de dos conjuntos finitos; expresado simbólicamente como

{displaystyle |Acup B|=|A|+|B|-|Acap B|}

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 de doble conteo son aquellos en la intersección de los dos conjuntos y el conteo se corrige restando el tamaño de la intersección.

El principio de inclusión-exclusión, al ser una generalización del caso de dos conjuntos, quizás se vea más claramente en el caso de tres conjuntos, que para los conjuntos A, B y C viene dada por

{displaystyle |Acup Bcup C|=|A|+|B|+|C|-|Acap B|-|Acap C|-|Bcap C|+|Acap Bcap C|}

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 volver a sumarse para obtener el total correcto.

Inclusión–exclusión ilustrada por un diagrama Venn para tres conjuntos

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 cardenalidades de los sets.
Excluir las cardenalidades de las intersecciones pares.
Incluya las cardenalidades de las intersecciones triples.
Excluir las cardenalidades de las intersecciones cuádruple-wise.
Incluir las cardenalidades de las intersecciones quintuple-wise.
Continúe, hasta la cardenalidad de la $n$ - la intersección de tuple-wise se incluye (si $n$ es raro) o excluido ( $n$ incluso).

El nombre proviene de la idea de que el principio se basa en una inclusión excesivamente generosa, seguida de una exclusión compensatoria. Este concepto se atribuye a Abraham de Moivre (1718), aunque aparece primero en un artículo de Daniel da Silva (1854) y luego en un artículo de J. J. Sylvester (1883). A veces se hace referencia al principio como la fórmula de Da Silva o Sylvester, debido a estas publicaciones. El principio se puede ver como un ejemplo del método de tamiz ampliamente utilizado en la teoría de números y, a veces, se lo denomina fórmula de tamiz.

Como las probabilidades finitas se calculan como conteos 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 colocarse bajo el paraguas común de la teoría de la medida.

En un entorno muy abstracto, el principio de inclusión-exclusión se puede expresar como el cálculo de la inversa de una determinada matriz. Este inverso 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:

"Uno de los principios más útiles de la enumeración en la probabilidad discreta y la teoría combinatoria es el famoso principio de inclusión-exclusión. Cuando se aplica hábilmente, este principio ha dado la solución a muchos problemas combinatorios".

Fórmula

Did you mean:

In its general formula, the principle of inclusion–exclusion states that for finite sets AN₁, …, A_n, one has the identity

<math alttext="{displaystyle left|bigcup _{i=1}^{n}A_{i}right|=sum _{i=1}^{n}|A_{i}|-sum _{1leqslant i<jleqslant n}|A_{i}cap A_{j}|+sum _{1leqslant i<jSilencio⋃ ⋃ i=1nAiSilencio=.. i=1nSilencioAiSilencio− − .. 1⩽ ⩽ i.j⩽ ⩽ nSilencioAi∩ ∩ AjSilencio+.. 1⩽ ⩽ i.j.k⩽ ⩽ nSilencioAi∩ ∩ Aj∩ ∩ AkSilencio− − ⋯ ⋯ +()− − 1)n+1SilencioA1∩ ∩ ⋯ ⋯ ∩ ∩ AnSilencio.{displaystyle left durablebigcup ¿Por qué? ¿Qué? ################################################################################################################################################################################################################################################################ No, no. _{1leqslant i secuestría en la vida. cdots cap A_{n} 'justo de la vida.}<img alt="{displaystyle left|bigcup _{i=1}^{n}A_{i}right|=sum _{i=1}^{n}|A_{i}|-sum _{1leqslant i<jleqslant n}|A_{i}cap A_{j}|+sum _{1leqslant i<j

()1)

Cada término de la fórmula de inclusión-exclusión corrige gradualmente el conteo hasta que finalmente cada porción del diagrama Venn se cuenta exactamente una vez.

Esto se puede escribir compactamente como

<math alttext="{displaystyle left|bigcup _{i=1}^{n}A_{i}right|=sum _{k=1}^{n}(-1)^{k+1}left(sum _{1leqslant i_{1}<cdots Silencio⋃ ⋃ i=1nAiSilencio=.. k=1n()− − 1)k+1().. 1⩽ ⩽ i1.⋯ ⋯ .ik⩽ ⩽ nSilencioAi1∩ ∩ ⋯ ⋯ ∩ ∩ AikSilencio){displaystyle left durablebigcup ¿Por qué? ################################################################################################################################################################################################################################################################ i_{1} 0cdots n}viva_{i_{1}cap cdots cap A_{i_{i_{k}<img alt="{displaystyle left|bigcup _{i=1}^{n}A_{i}right|=sum _{k=1}^{n}(-1)^{k+1}left(sum _{1leqslant i_{1}<cdots

${displaystyle left|bigcup _{i=1}^{n}A_{i}right|=sum _{emptyset neq Jsubseteq {1,ldotsn}}(-1)^{|J|+1}left|bigcap _{jin J}A_{j}right|.}$

En palabras, para contar el número de elementos en una unión finita de conjuntos finitos, primero suma las cardenalidades de los conjuntos individuales, luego restar el número de elementos que aparecen en al menos dos conjuntos, luego añadir el número de elementos que aparecen en al menos tres conjuntos, luego restar el número de elementos que aparecen en al menos cuatro sets, etc. Este proceso siempre termina ya que no puede haber elementos que aparezcan en más que el número de conjuntos en la unión. (Por ejemplo, si ${displaystyle n=4,}$ no puede haber elementos que aparecen en más que $4$ conjuntos; equivalentemente, no puede haber elementos que aparezcan al menos $5$ sets.)

En las aplicaciones es común ver el principio expresado en su forma complementaria. Eso es, dejar $S$ ser un conjunto universal finito que contiene todo el $A i$ y dejar ${bar {A_{i}}}$ denota el complemento $A i$ dentro $S$ Por las leyes de De Morgan tenemos

$<math alttext="{displaystyle left|bigcap _{i=1}^{n}{bar {A_{i}}}right|=left|S-bigcup _{i=1}^{n}A_{i}right|=|S|-sum _{i=1}^{n}|A_{i}|+sum _{1leqslant iSilencio⋂ ⋂ i=1nAī ̄ Silencio=SilencioS− − ⋃ ⋃ i=1nAiSilencio=SilencioSSilencio− − .. i=1nSilencioAiSilencio+.. 1⩽ ⩽ i.j⩽ ⩽ nSilencioAi∩ ∩ AjSilencio− − ⋯ ⋯ +()− − 1)nSilencioA1∩ ∩ ⋯ ⋯ ∩ ∩ AnSilencio.{displaystyle left durablebigcap {cHFF} {fn} {fn}} {fn}} {fn}} {fn} {fn} {fn}fn}fnfnfnfnfnfnfnfn}fnfnfnfnH00}fnfnfnfnH00}}fnfnfnfnfnH00fnfnfnKfnH00fnKfnH00fnH00fnH00fn}fnKfnKfnh00fnh00fn}fnH00fn}}fn}fn}fn}fnh00fnfnh00}fnfn}fn}fnh00fn}fnH00fnh00fn}}fn} {A_{i}} 'justo en la vida= 'izquierda en la vida' ¿Por qué? ¿Qué? ################################################################################################################################################################################################################################################################ n} habitA_{i}cap A_{j} arrest-cdots +(-1)^{n}SobrevivirA_{1}cap cdots cap A_{n}<img alt="{displaystyle left|bigcap _{i=1}^{n}{bar {A_{i}}}right|=left|S-bigcup _{i=1}^{n}A_{i}right|=|S|-sum _{i=1}^{n}|A_{i}|+sum _{1leqslant i$

Como otra variante de la declaración, vea $p 1,..., p n$ Sea una lista de propiedades que los elementos de un set $s$ puede o no tener, 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. Simplemente deje $a i$ sea el subconjunto de elementos de $s$ que tienen la propiedad $p i$ y usa el principio en su forma complementaria. Esta variante se debe a J. J. Sylvester.

Observe que si tiene en cuenta solo el primer $m & lt; n$ suma a la derecha (en la forma general del principio), entonces Obtendrá una sobreestimación if $m$ es impar y un subestimado if $m es uniforme.$

Ejemplos

Contando enteros

Como un simple ejemplo del uso del principio de inclusión -exclusión, considere la pregunta:

¿Cuántos enteros en {1,..., 100} no son divisibles por 2, 3 o 5?

Let s = {1,..., 100} y p ₁ la propiedad que un entero es divisible por 2, P ₂ La propiedad de que un entero es divisible por 3 y p ₃ la propiedad que un entero es divisible por 5. dejar a _i ser el subconjunto de s cuyos elementos tienen propiedad p _i tenemos por conteo elemental: | a ₁ | = 50, | a ₂ | = 33, y | a ₃ | = 20. Hay 16 de estos 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 divisibles por cualquiera de los 2, 3 o 5 es dado por:

100 − (50 + 33 + 20) + (16 + 10 + 6) − 3 = 26.

Contado de trastornos

Un ejemplo más complejo es el siguiente.

Suponga que hay un mazo de cartas n numeradas de 1 a n . Supongamos que una tarjeta numerada m está en la posición correcta si es la tarjeta m en el mazo. ¿De cuántas maneras, w , se pueden barajar las tarjetas con al menos 1 tarjeta en la posición correcta?

Comience definiendo el conjunto a _m, que es todos los ordenamientos de tarjetas con m th th Tarjeta correcta. Entonces el número de pedidos, w , con al menos una tarjeta que está en la posición correcta, m , es

${displaystyle W=left|bigcup _{m=1}^{n}A_{m}right|.}$

Aplicar el principio de inclusión-exclusión,

$<math alttext="{displaystyle W=sum _{m_{1}=1}^{n}|A_{m_{1}}|-sum _{1leqslant m_{1}<m_{2}leqslant n}|A_{m_{1}}cap A_{m_{2}}|+cdots +(-1)^{p-1}sum _{1leqslant m_{1}<cdots W=.. m1=1nSilencioAm1Silencio− − .. 1⩽ ⩽ m1.m2⩽ ⩽ nSilencioAm1∩ ∩ Am2Silencio+⋯ ⋯ +()− − 1)p− − 1.. 1⩽ ⩽ m1.⋯ ⋯ .mp⩽ ⩽ nSilencioAm1∩ ∩ ⋯ ⋯ ∩ ∩ AmpSilencio+⋯ ⋯ {displaystyle W=sum _{m_{1}=1} {n}Principi} _{1leqslant m_{1} No, no. A_{m_{2}cdots +(-1)^{p-1}sum _{1leqslant m_{1} 0cdots n}viva_{m_{1}cap cdots cap A_{m_{p}<img alt="{displaystyle W=sum _{m_{1}=1}^{n}|A_{m_{1}}|-sum _{1leqslant m_{1}<m_{2}leqslant n}|A_{m_{1}}cap A_{m_{2}}|+cdots +(-1)^{p-1}sum _{1leqslant m_{1}<cdots$

Cada valor $A_{{m_{1}}}cap cdots cap A_{{m_{p}}}$ representa el conjunto de sábanas teniendo al menos p valores m₁,...,m_p en la posición correcta. Tenga en cuenta que el número de shuffles con al menos p valores correctos sólo depende de p, no sobre los valores particulares de $m$ . Por ejemplo, el número de sábanas que tienen las tarjetas 1a, 3a y 17a en la posición correcta es el mismo que el número de sábanas que tienen las tarjetas 2a, 5a y 13a en las posiciones correctas. Sólo importa el de la n tarjetas, 3 fueron elegidas para estar en la posición correcta. Así hay ${textstyle {n choose p}}$ en pie de igualdad pth summation (ver combinación).

${displaystyle W={n choose 1}|A_{1}|-{n choose 2}|A_{1}cap A_{2}|+cdots +(-1)^{p-1}{n choose p}|A_{1}cap cdots cap A_{p}|+cdots }$

${displaystyle |A_{1}cap cdots cap A_{p}|}$ es el número de pedidos que tienen p elementos en la posición correcta, que es igual al número de formas de ordenar el resto n−p elementos o (n−p)! Por lo tanto finalmente obtenemos:

${displaystyle {begin{aligned}W&={n choose 1}(n-1)!-{n choose 2}(n-2)!+cdots +(-1)^{p-1}{n choose p}(n-p)!+cdots \&=sum _{p=1}^{n}(-1)^{p-1}{n choose p}(n-p)!\&=sum _{p=1}^{n}(-1)^{p-1}{frac {n!}{p!(n-p)!}}(n-p)!\&=sum _{p=1}^{n}(-1)^{p-1}{frac {n!}{p!}}end{aligned}}}$

Una permutación donde no la tarjeta está en la posición correcta se llama trastorno. Tomando n ! Para ser el número total de permutaciones, la probabilidad q que una baraja aleatoria produce un trastorno viene dada por

$Q=1-{frac {W}{n!}}=sum _{{p=0}}^{n}{frac {(-1)^{p}}{p!}},$

Un truncamiento a n +1 términos de la expansión de Taylor de e −1 . Por lo tanto, la probabilidad de adivinar un orden para un mazo de cartas barajado y ser incorrecto sobre cada carta es aproximadamente e −1 o 37%.

un caso especial

La situación que aparece en el ejemplo de trastorno anterior ocurre con la suficiente frecuencia para merecer una atención especial. Es decir, cuando el tamaño de los conjuntos de intersección que aparecen en las fórmulas para el principio de inclusión -exclusión dependen solo del número de conjuntos en las intersecciones y no de qué conjuntos aparecen. Más formalmente, si la intersección

$A_{J}:=bigcap _{{jin J}}A_{j}$

tiene la misma cardinalidad, digamos α _k = | a _j |, por cada K -Element subconjunto j de {1,..., n }, entonces

${displaystyle left|bigcup _{i=1}^{n}A_{i}right|=sum _{k=1}^{n}(-1)^{k-1}{binom {n}{k}}alpha _{k}.}$

o, en la forma complementaria, donde el conjunto universal s tiene cardinalidad α ₀,

${displaystyle left|Ssmallsetminus bigcup _{i=1}^{n}A_{i}right|=sum _{k=0}^{n}(-1)^{k}{binom {n}{k}}alpha _{k}.}$

Generalización de fórmulas

Dada una familia (repeticiones permitidas) de subconjuntos A₁, A₂,..., 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 sería calcular el número de elementos de S que aparecen exactamente en algunos m fijos de estos conjuntos.

Vamos N =n# = {1,2,...,n}. Si definimos $A_{{emptyset }}=S$ , entonces el principio de inclusión-exclusión se puede escribir como, utilizando la notación de la sección anterior; el número de elementos de S contenida en ninguno de los A_i es:

$sum _{{Jsubseteq [n]}}(-1)^{{|J|}}|A_{J}|.$

Si I es un subconjunto fijo del conjunto de índices N, entonces el número de elementos que pertenecen a A_i para todos los i en I y para ningún otro valor es:

$sum _{{Isubseteq J}}(-1)^{{|J|-|I|}}|A_{J}|.$

Definir los conjuntos

${displaystyle B_{k}=A_{Icup {k}}{text{ for }}kin Nsmallsetminus I.}$

Buscamos el número de elementos en ninguno de los B_k que, por principio de inclusión-exclusión (con ${displaystyle B_{emptyset }=A_{I}}$ ), es

${displaystyle sum _{Ksubseteq Nsmallsetminus I}(-1)^{|K|}|B_{K}|.}$

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, mostrando que el resultado es válido.

En probabilidad

En probabilidad, para eventos A₁,... A_n en un espacio de probabilidad $(Omega{mathcal {F}},mathbb {P})$ , el principio de inclusión-exclusión se hace para n= 2

${mathbb {P}}(A_{1}cup A_{2})={mathbb {P}}(A_{1})+{mathbb {P}}(A_{2})-{mathbb {P}}(A_{1}cap A_{2}),$

para n = 3

${displaystyle mathbb {P} (A_{1}cup A_{2}cup A_{3})=mathbb {P} (A_{1})+mathbb {P} (A_{2})+mathbb {P} (A_{3})-mathbb {P} (A_{1}cap A_{2})-mathbb {P} (A_{1}cap A_{3})-mathbb {P} (A_{2}cap A_{3})+mathbb {P} (A_{1}cap A_{2}cap A_{3})}$

y en general

$<math alttext="{displaystyle mathbb {P} left(bigcup _{i=1}^{n}A_{i}right)=sum _{i=1}^{n}mathbb {P} (A_{i})-sum _{i<j}mathbb {P} (A_{i}cap A_{j})+sum _{i<j<k}mathbb {P} (A_{i}cap A_{j}cap A_{k})+cdots +(-1)^{n-1}sum _{i<...P()⋃ ⋃ i=1nAi)=.. i=1nP()Ai)− − .. i.jP()Ai∩ ∩ Aj)+.. i.j.kP()Ai∩ ∩ Aj∩ ∩ Ak)+⋯ ⋯ +()− − 1)n− − 1.. i.....nP()⋂ ⋂ i=1nAi),{displaystyle mathbb {P} left(bigcup ¿Por qué? - ¿Qué? {P} (A_{i})-sum _{i donej}mathbb {P} (A_{i}cap A_{j})+sum _{i wonjsek}mathbb {P} (A_{i}cap A_{j}cap A_{k})+cdots +(-1)^{n-1}sum _{i donen}mathbb {P} left(bigcap) - Sí.<img alt="{displaystyle mathbb {P} left(bigcup _{i=1}^{n}A_{i}right)=sum _{i=1}^{n}mathbb {P} (A_{i})-sum _{i<j}mathbb {P} (A_{i}cap A_{j})+sum _{i<j<k}mathbb {P} (A_{i}cap A_{j}cap A_{k})+cdots +(-1)^{n-1}sum _{i<...$

que se puede escribir en forma cerrada como

${displaystyle mathbb {P} left(bigcup _{i=1}^{n}A_{i}right)=sum _{k=1}^{n}left((-1)^{k-1}sum _{Isubseteq {1,ldotsn} atop |I|=k}mathbb {P} (A_{I})right),}$

donde la última suma se ejecuta sobre todos los subconjuntos i de los índices 1,..., n que contienen exactamente k elementos, y

$A_{I}:=bigcap _{{iin I}}A_{i}$

denota la intersección de todos aquellos 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 LHS. Esto se puede usar en casos en los que la fórmula completa es demasiado engorrosa.

Para un espacio de medida general (S,μ) y subconjuntos mensurables A₁,..., A_n de medida finita, las identidades anteriores también sostienen cuando la medida de probabilidad $mathbb {P}$ es reemplazado 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 por cada k en {1, …, n} hay un a_k tal que

${displaystyle a_{k}=mathbb {P} (A_{I}){text{ for every }}Isubset {1,ldotsn}{text{ with }}|I|=k,}$

entonces la fórmula anterior se simplifica a

${displaystyle mathbb {P} left(bigcup _{i=1}^{n}A_{i}right)=sum _{k=1}^{n}(-1)^{k-1}{binom {n}{k}}a_{k}}$

debido a la interpretación combinatoria del coeficiente binomio ${textstyle {binom {n}{k}}}$ . Por ejemplo, si los eventos $A_{i}$ son independientes y distribuidos idénticamente, entonces ${displaystyle mathbb {P} (A_{i})=p}$ para todos i, y tenemos ${displaystyle a_{k}=p^{k}}$ , en cuyo caso la expresión anterior simplifica

${displaystyle mathbb {P} left(bigcup _{i=1}^{n}A_{i}right)=1-(1-p)^{n}.}$

(Este resultado también puede derivarse más simplemente considerando la intersección de los complementos de los eventos $A_{i}$ .)

Una simplificación análoga es posible en el caso de un espacio de medida general $(S, Σ, μ)$ y subconjuntos medibles A₁, …, A_n de medida finita.

Otras fórmulas

El principio a veces se establece en la forma que dice que si

${displaystyle g(A)=sum _{Ssubseteq A}f(S)}$

entonces

{displaystyle f(A)=sum _{Ssubseteq A}(-1)^{|A|-|S|}g(S)}

()⁎⁎)

La versión combinatoria y probabilística del principio de inclusión-exclusión son instancias de (⁎⁎).

Prueba
Toma. $underline {m}={1,2,ldotsm}$ , $f(underline {m})=0$ , y
${displaystyle f(S)=left|bigcap _{iin {underline {m}}smallsetminus S}A_{i}smallsetminus bigcup _{iin S}A_{i}right|{text{ and }}f(S)=mathbb {P} left(bigcap _{iin {underline {m}}smallsetminus S}A_{i}smallsetminus bigcup _{iin S}A_{i}right)}$
respectivamente para todos los conjuntos $S$ con $Ssubsetneq underline {m}$ . Entonces obtenemos
${displaystyle g(A)=left|bigcap _{iin {underline {m}}smallsetminus A}A_{i}right|,quad g({underline {m}})=left|bigcup _{iin {underline {m}}}A_{i}right|{text{ and }}g(A)=mathbb {P} left(bigcap _{iin {underline {m}}smallsetminus A}A_{i}right),~~g({underline {m}})=mathbb {P} left(bigcup _{iin {underline {m}}}A_{i}right)}$
respectivamente para todos los conjuntos $A$ con $Asubsetneq underline {m}$ . Esto es porque elementos $a$ de ${displaystyle cap _{iin {underline {m}}smallsetminus A}A_{i}}$ puede ser contenido en otros $A_{i}$ () $A_{i}$ con $iin A$ ) también, y el ${displaystyle cap smallsetminus cup }$ -formula se ejecuta exactamente a través de todas las extensiones posibles de los conjuntos ${displaystyle {A_{i}mid iin {underline {m}}smallsetminus A}}$ con otros $A_{i}$ Contando $a$ sólo para el conjunto que coincide con el comportamiento de la membresía $a$ , si $S$ corre a través de todos los subconjuntos de $A$ (como en la definición de $g(A)$ ).
Desde $f(underline {m})=0$ , obtenemos de (⁎⁎Con $A=underline {m}$ que
${displaystyle sum _{{underline {m}}supseteq Tsupsetneq varnothing }(-1)^{|T|-1}g({underline {m}}smallsetminus T)=sum _{varnothing subseteq Ssubsetneq {underline {m}}}(-1)^{m-|S|-1}g(S)=g({underline {m}})}$
y por partes intercambiadoras, sigue la versión combinatoria y probabilística del principio de inclusión-exclusión.

Si uno ve un número $n$ como un conjunto de sus principales factores, entonces (⁎⁎) es una generalización de la fórmula de inversión Möbius para números naturales libres de cuadrados. Por lo tanto,⁎⁎) se ve como la fórmula de inversión 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 multisets. Para multisets en lugar de conjuntos, ( ⁎⁎ ) se convierte en

{displaystyle f(A)=sum _{Ssubseteq A}mu (A-S)g(S)}

()⁎⁎⁎)

Donde $A - S$ es el multiset para el cual $(A-S)uplus S=A$ , y

μ()S) = 1 si S es un conjunto (es decir, un multiconjunto sin elementos dobles) de incluso la cardinalidad.
μ()S) = −1 si S es un conjunto (es decir, un multiconjunto sin elementos dobles) de extraña cardenalidad.
μ()S) = 0 si S es un multiset adecuado (es decir, S tiene elementos dobles).

Note que ${displaystyle mu (A-S)}$ es sólo ${displaystyle (-1)^{|A|-|S|}}$ of (⁎⁎) en caso $A - S$ es un juego.

Prueba de (⁎⁎⁎)
Substituto
${displaystyle g(S)=sum _{Tsubseteq S}f(T)}$ en el lado derecho de (⁎⁎⁎). Note que $f(A)$ aparece una vez en ambos lados de (⁎⁎⁎). Así que debemos demostrarlo para todos $T$ con $Tsubsetneq A$ , los términos $f(T)$ cancelar en el lado derecho de (⁎⁎⁎). Con ese fin, tome un fijo $T$ tales que $Tsubsetneq A$ y tomar un fijo arbitrario $ain A$ tales que ${displaystyle anotin T}$ .
Note que $A - S$ debe ser un conjunto para cada aspecto positivo o negativo $f(T)$ en el lado derecho de (⁎⁎⁎) que se obtiene por medio del multiset $S$ tales que $Tsubseteq Ssubseteq A$ . Ahora cada apariencia de $f(T)$ en el lado derecho de (⁎⁎⁎) que se obtiene por medio de $S$ tales que $A - S$ es un conjunto que contiene $a$ cancela con el que se obtiene a través de la correspondiente $S$ tales que $A - S$ es un conjunto que no contiene $a$ . Esto da el resultado deseado.

Aplicaciones

El principio de inclusión-exclusión se usa ampliamente y solo algunas de sus aplicaciones pueden mencionarse aquí.

Trastornos del conteo

Una aplicación bien conocida del principio de inclusión-exclusión es al problema combinatorio de contar todos los desarreglos de un conjunto finito. Un desorden de un conjunto A es una biyección de A en sí mismo que no tiene puntos fijos. A través del principio de inclusión-exclusión se puede demostrar que si la cardinalidad de A es n, entonces el número de desarreglos es [n! / e] donde [x] denota el entero más cercano 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 temprano sobre juegos de azar: Essai d'analyse sur les jeux de hazard de P. R. de Montmort (1678 – 1719) y se conocía como "el problema de Montmort" o por el nombre que le dio, "problème des rencontres." El problema también se conoce como el problema de control de sombreros.

El número de trastornos también se conoce como el 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 aproxima rápidamente a 1/e a medida que crece n.

Contar intersecciones

El principio de inclusión-exclusión, combinado con la ley de De Morgan, se puede utilizar para contar la cardinalidad de la intersección de conjuntos también. Vamos ${displaystyle {overline {A_{k}}}}$ representan el complemento A_k con respecto a algún conjunto universal A tales que ${displaystyle A_{k}subseteq A}$ para cada uno k. Entonces tenemos

${displaystyle bigcap _{i=1}^{n}A_{i}={overline {bigcup _{i=1}^{n}{overline {A_{i}}}}}}$

convirtiendo así el problema de encontrar una intersección en el problema de encontrar una unión.

Coloreado de gráficos

El principio de inclusión y exclusión forma la base de los algoritmos para una serie de problemas de partición de gráficos NP-duros, como la coloración de gráficos.

Una aplicación bien conocida del principio es la construcción del polinomio cromático de un gráfico.

Concordancias perfectas de grafos bipartitos

El número de coincidencias perfectas de un gráfico bipartito se puede calcular usando el principio.

Número de funciones sobre

Dados conjuntos finitos A y B, ¿cuántas funciones sobreyectivas (sobre funciones) hay de A a B? Sin pérdida de generalidad podemos tomar A = {1,..., k} y B = {1,..., n}, ya que solo importan las cardinalidades de los conjuntos. Usando S como el conjunto de todas las funciones de A a B, y definiendo, para cada i en B, la propiedad P_i ya que "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 sobre funciones entre A y B como:

$sum _{{j=0}}^{{n}}{binom {n}{j}}(-1)^{j}(n-j)^{k}.$

Permutaciones con posiciones prohibidas

Una permutación del conjunto S = {1,..., n} donde cada elemento de S está restringido a no ser en determinadas posiciones (aquí la permutación se considera como una ordenación de los elementos de S) se denomina permutación con posiciones prohibidas. 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. Siendo A_i el conjunto de posiciones que ocupa el elemento i no puede estar dentro, y la propiedad P_i es la propiedad que una permutación pone al elemento i a una posición en A_i, el principio de inclusión-exclusión se puede usar para contar el número de permutaciones que satisfacen todas las restricciones.

En el ejemplo dado, hay 12 = 2(3!) permutaciones con propiedad P₁, 6 = 3! permutaciones con propiedad P₂ y ninguna permutación tiene propiedades P₃ o P₄ 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 ambas propiedades P₁ y P₂. No hay otras contribuciones distintas de cero a la fórmula.

Números de Stirling de segunda especie

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, contar el número de particiones de un conjunto n 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 (posiblemente vacías) cajas distinguibles, A₁, A₂, …, A_k, y las propiedades P_i lo que significa que la partición tiene el cuadro A_i vacío, el principio de inclusión-exclusión da una respuesta para el resultado relacionado. ¡Dividiendo por k! para eliminar el ordenamiento artificial da el número de Stirling de segunda especie:

${displaystyle S(n,k)={frac {1}{k!}}sum _{t=0}^{k}(-1)^{t}{binom {k}{t}}(k-t)^{n}.}$

Polinomios de torre

Un polinomio podrido es la función generadora del número de maneras de colocar rocosos no atacantes en un Junta B que parece un subconjunto de los cuadrados de un tablero de control; es decir, no dos rooks pueden estar en la misma fila o columna. El tablero B es cualquier subconjunto de los cuadrados de una tabla rectangular con n filas y m columnas; pensamos en ello como los cuadrados en los que se permite poner un giro. El coeficiente, r_k()B) de x^k en el polinomio roto R_B()x) es el número de maneras k Rooks, ninguno de los cuales ataca a otro, se puede organizar en los cuadrados de B. Para cualquier tablero B, hay una junta complementaria $B'$ que consiste en los cuadrados de la tabla rectangular que no están B. Esta tabla complementaria también tiene un polinomio podrido ${displaystyle R_{B'}(x)}$ con coeficientes ${displaystyle r_{k}(B').}$

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 asumir 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 completo n × m "tablero de ajedrez" (sin tener en cuenta si las torres están colocadas en las casillas del tablero B) viene dada por el factorial descendente:

$(m)_{n}=m(m-1)(m-2)cdots (m-n+1).$

Sea P_i 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 una casilla del tablero B, entonces por el principio de inclusión-exclusión tenemos:

${displaystyle r_{n}(B)=sum _{t=0}^{n}(-1)^{t}(m-t)_{n-t}r_{t}(B').}$

Did you mean:
Euler 's phi function
La función totient o phi de Euler, φ(n) es una función aritmética que cuenta el número de enteros positivos menores o iguales que n que son primos relativos a n. Es decir, si n es un entero positivo, entonces φ(n) es el número de enteros k en el rango 1 ≤ k ≤ n que no tienen factor común con n distinto de 1. El principio de inclusión-exclusión se utiliza para obtener una fórmula para φ( n). Sea S el conjunto {1, …, n} y definamos la propiedad P_i como que a número en S es divisible por el número primo p_i, para 1 ≤ i ≤ r, donde la descomposición en factores primos de
$n=p_{1}^{{a_{1}}}p_{2}^{{a_{2}}}cdots p_{r}^{{a_{r}}}.$
Entonces,
$<math alttext="{displaystyle varphi (n)=n-sum _{i=1}^{r}{frac {n}{p_{i}}}+sum _{1leqslant iφ φ ()n)=n− − .. i=1rnpi+.. 1⩽ ⩽ i.j⩽ ⩽ rnpipj− − ⋯ ⋯ =n∏ ∏ i=1r()1− − 1pi).{displaystyle varphi (n)=n-sum - ¿Qué? {n}{p_{i}}sum - ¿Por qué? {n}{i}p_{j}}cdots =nprod _{i=1}left(1-{frac {1}{p_{i}}right).}<img alt="{displaystyle varphi (n)=n-sum _{i=1}^{r}{frac {n}{p_{i}}}+sum _{1leqslant i$
Principio de inclusión-exclusión diluido
En muchos casos en los que el principio podría dar una fórmula exacta (en particular, contar números primos usando el tamiz de Eratóstenes), la fórmula que surge no ofrece contenido útil porque el número de términos en ella es excesivo. Si cada término individualmente puede estimarse con precisión, la acumulación de errores puede implicar que la fórmula de inclusión-exclusión no sea directamente aplicable. En teoría de números, esta dificultad fue abordada por Viggo Brun. Después de un comienzo lento, sus ideas fueron retomadas por otros y se desarrolló una gran variedad de métodos de cribado. Estos, por ejemplo, pueden tratar de encontrar los límites superiores para el "tamizado" conjuntos, en lugar de una fórmula exacta.
Sean arbitrarios A₁,..., A_n conjuntos y p₁, …, p_n números reales en la unidad cerrada intervalo $[0, 1]$ . Entonces, para cada número par k en {0, …, n}, las funciones indicadoras satisfacen la desigualdad:
$<math alttext="{displaystyle 1_{A_{1}cup cdots cup A_{n}}geq sum _{j=1}^{k}(-1)^{j-1}sum _{1leq i_{1}<cdots 1A1∪ ∪ ⋯ ⋯ ∪ ∪ An≥ ≥ .. j=1k()− − 1)j− − 1.. 1≤ ≤ i1.⋯ ⋯ .ij≤ ≤ npi1...... pij1Ai1∩ ∩ ⋯ ⋯ ∩ ∩ Aij.{displaystyle 1_{A_{1}cup cdots cup A_{n}geq sum _{j=1}^{k}(-1)^{j-1}sum _{1leq i_{1} buscadocdots ##########p_{i_{1}dots ¿Qué? cdots cap A_{i_{j}}}<img alt="{displaystyle 1_{A_{1}cup cdots cup A_{n}}geq sum _{j=1}^{k}(-1)^{j-1}sum _{1leq i_{1}<cdots$
Prueba de la declaración principal
Elige un elemento contenido en la unión de todos los conjuntos y deja $A_{1},A_{2},dotsA_{t}$ ser los conjuntos individuales que lo contienen. (Nota eso) t ■ 0.) Puesto que el elemento es contado precisamente una vez por el lado izquierdo de la ecuación (1Tenemos que demostrar que es contado precisamente una vez por el lado derecho. En el lado derecho, las únicas contribuciones no cero ocurren cuando todos los subconjuntos en un término particular contienen el elemento elegido, es decir, todos los subconjuntos se seleccionan de $A_{1},A_{2},dotsA_{t}$ . La contribución es una para cada uno de estos conjuntos (más o menos dependiendo del término) y por lo tanto es sólo el (firmado) número de estos subconjuntos utilizados en el término. Entonces tenemos:
$<math alttext="{displaystyle {begin{aligned}|{A_{i}mid 1leqslant ileqslant t}|&-|{A_{i}cap A_{j}mid 1leqslant iSilencio{}Ai▪ ▪ 1⩽ ⩽ i⩽ ⩽ t}Silencio− − Silencio{}Ai∩ ∩ Aj▪ ▪ 1⩽ ⩽ i.j⩽ ⩽ t}Silencio+⋯ ⋯ +()− − 1)t+1Silencio{}A1∩ ∩ A2∩ ∩ ⋯ ⋯ ∩ ∩ At}Silencio=()t1)− − ()t2)+⋯ ⋯ +()− − 1)t+1()tt).{displaystyle {begin{aligned}tuvo{A_{i}mid 1leqslant ileqslant t} habit- habit\{A_{i}cap A_{j}mid 1leqslant i donejleqslant t}Sobrevivir+cdots +(-1)^{t+1} A_{2}cap cdots cap A_{t}fncipiente={binom { t}{1}-{binom {t}{2}+cdots +(-1)^{t+1}{binom {t} {t}}.end{aligned}}<img alt="{displaystyle {begin{aligned}|{A_{i}mid 1leqslant ileqslant t}|&-|{A_{i}cap A_{j}mid 1leqslant i$
Por el teorema del binomio,
${displaystyle 0=(1-1)^{t}={binom {t}{0}}-{binom {t}{1}}+{binom {t}{2}}-cdots +(-1)^{t}{binom {t}{t}}.}$
Usando el hecho de que ${binom {t}{0}}=1$ y reorganización de términos, tenemos
${displaystyle 1={binom {t}{1}}-{binom {t}{2}}+cdots +(-1)^{t+1}{binom {t}{t}},}$
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
${displaystyle {begin{aligned}&mathbf {1} _{S}:Xto {0,1}\&mathbf {1} _{S}(x)={begin{cases}1&xin S\0&xnotin Send{cases}}end{aligned}}}$
Si $A$ y $B$ son dos subconjuntos de $X$ , entonces
${mathbf {1}}_{A}cdot {mathbf {1}}_{B}={mathbf {1}}_{{Acap B}}.$
Vamos A denota el sindicato ${textstyle bigcup _{i=1}^{n}A_{i}}$ de los conjuntos A₁,..., A_n. Para probar el principio de inclusión-exclusión en general, primero verificamos la identidad
${displaystyle mathbf {1} _{A}=sum _{k=1}^{n}(-1)^{k-1}sum _{Isubset {1,ldotsn} atop |I|=k}mathbf {1} _{A_{I}}}$
()⁎)
para funciones de indicador, donde:
$A_{I}=bigcap _{{iin I}}A_{i}.$
La siguiente función
${displaystyle left(mathbf {1} _{A}-mathbf {1} _{A_{1}}right)left(mathbf {1} _{A}-mathbf {1} _{A_{2}}right)cdots left(mathbf {1} _{A}-mathbf {1} _{A_{n}}right),}$
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 pertenece a algún A_m, entonces el correspondiente m^th factor es 1 − 1 = 0. Al expandir el producto en el lado izquierdo, se obtiene la ecuación (⁎).
Para probar el principio de inclusión-exclusión para la cardinalidad de los conjuntos, suma la ecuación (⁎) sobre todas las x en la unión de A₁, …, A_n. Para derivar la versión utilizada en probabilidad, tome la expectativa en (⁎). En general, integra la ecuación (⁎) con respecto a μ. Utilice siempre la linealidad en estas derivaciones.

Más resultados...