Varios

EL PRINCIPIO DE INCLUSIÓN Y EXCLUSIÓN
Ahora regresaremos al tema de conteo, analizando el principio de inclusión y exclusión.
Extendiendo las ideas de los problemas de conteo sobre los diagramas de Venn del capítulo 3,este principio nos ayudará a establecer la fórmula que conjeturamos en la sección 5.3 para el numero de funciones sobreyectivas f: AB, donde A, B son conjuntos finitos (novacíos). Otras aplicaciones de este principio demostrarán su naturaleza versátil en la matemática combinatoria como un método indirecto para los problemas de conteo que surgen en muchas situaciones muy diferentes.
8.1
El principio de inclusión y exclusión
En esta sección desarrollaremos algo de notación para enunciar nuestro nuevo principio de conteo. Después estableceremos el principio medianteun argumento combinatorio.
Los ejemplos mostrarán la forma en que se aplica dicho principio.
Sea S un conjunto tal que |S|=N y sean c1c2,….,ct una colección de condiciones o propiedades satisfechas por alguno, o todos, los elementos de S. Algunos elementos de S podrían satisfacer más de una de las condiciones, mientras que otros podrían no satisfacer ninguna. Para todo 1 ≤ i ≤ t, N (ci) denotael número de S que satisfacen la condición ci.
(Los elementos de S se cuentan solamente cuando satisfacen la condición de ci y también cuando satisfacen cj y otras condiciones cj, para j ≠ i) Para cualesquiera i,j {1,2,3,….t}, tales que i ≠ j , N(ci cj) denotará el número de elementos de S que satisfacen ambas condiciones ci,cj y tal vez otras más. [N (ci cj) no cuenta los elementos de S quesólo satisfacen ci,cj.] Continuando de esta forma, si 1≤ i, j, k ≤ t son tres enteros distintos, entonces N (ci cj ck) denota el número de elementos de S que satisfacen, tal vez entre otras, cada una de las condiciones ci cj y ck.
Para cada 1 ≤ i ≤ t, = N – N(ci) denota el número de elementos de S que no satisfacen la condición ci. Si 1 ≤ i , j ≤ t, con i ≠ j, denota el número de elementos de S queno satisfacen alguna de las condiciones cicj [Esto no es lo mismo que .]
Del diagrama de Venn de la figura 8.1, vemos que si N(ci) denota el número de elementos del círculo del lado izquierdo y N (cj)denota el número de elementos del círculo del lado derecho, entonces N (cicj) es el número de elementos en el solapamiento, mientras que N cuenta los elementos que quedan fuera de la unión de estoscírculos. 2 – 2
En consecuencia, de la figura8.1, = N – [N(ci) +N(cj)] +N(cicj), donde se suma el último término debido a que fue eliminado dos veces en el termino [N(ci + N(cj)].
De manera análoga, de la figura 8.2 obtenemos que:

.
A partir del patrón sugerido en estos dos casos, establecemos el siguiente teorema.
TEOREMA 8.1 El principio de inclusión y exclusión. Consideremos unconjunto S tal que | S | = N y las condiciones ci, 1 ≤ i ≤ t satisfechas por algunos de los elementos de S. El número de elementos de S que no satisfacen ninguna de las condiciones ci , 1 ≤ i ≤ t, se denota con donde
(1)
o
(2)

Demostración: Aunque este resultado puede establecerse mediante inducción en r, daremos aquí un argumentocombinatorio.
Para cada x Є S, mostramos que x contribuye con el mismo número, 0 o 1, a cada lado de la ecuación (2).

fig 8.1 y fig 8.2

Si x no satisface ninguna de las condiciones, entonces x se cuenta una vez en Ñ y una vez en N, pero no se cuenta en los demás términos de la ecuación (2). En consecuencia, x contribuye con 1 a cada lado de la ecuación.
La otra posibilidad es que xsatisfaga exactamente r de las condiciones, donde . En este caso, x no contribuye a . Pero, en el lado derecho de la ecuación (2), x se cuenta

1) una vez en N
2) r veces en (Una vez por cada una de las r condiciones.)
3) veces en (una vez por cada par de condiciones elegidas de las r que satisface.)
4) veces en (¿Por qué?)
(r+1) =1 vez en donde la...