Método de inclusión-exclusión

¿Y si los conjuntos $ A $ y $ B$ no son disjuntos, es decir, si las dos colecciones tienen elementos en común? Bueno, en ese caso, tenemos que aplicar el principio de inclusión y exclusión. Que el lector juzgue la naturalidad de la fórmula que más abajo se apunta. (” Ana y Boris es un matrimonio de 6 hijos. Ana tiene 5 hijos y Boris tiene 3.”)

Una forma de ver un conjunto $ A $ de objetos es pensarlos como los objetos que tienen en común la propiedad a (a final de cuentas todos los objetos de $ A $ comparten la propiedad de pertenecer al conjunto $ A $ –esto respondería a la pregunta ¿y si no tienen ninguna propiedad en común?). Pensando los elementos de las colecciones de objetos $ A $ y $ B $ de esta manera, el principio de inclusión y exclusión se puede verbalizar de la siguinete manera: contamos los objetos con la propiedad $ a $ (los de $ A $), contamos los objetos con la propiedad $ b $ (los de $ B $), contamos los objetos con las dos propiedades (los de $AB=$elementos comunes a $ A $ y a$ B $), finalmente hacemos las cuentas $n(A)+n(B)-n(AB).$ En símbolos, $n(AUB)=n(A)+n(B)-n(AB). $

¿Por qué es válida esta forma de contar los elementos de $AUB$? Bueno, la clave está en que cuando contamos los objetos con la propiedad $ a $ también estamos contando algunos que tienen la propiedad $ b $, es decir, al contar los elementos de $ A $ incluimos en la cuenta los elementos de $AB$; y lo mismo es cierto cuando contamos los objetos con la propiedad $ B $. Así que al sumar $n(A)+n(B)$ estamos contando dos veces los objetos que tienen ambas propiedades; de ahí que debemos restar $n(AB)$ en las cuentas totales. Notemos que la fórmula de inclusiones y exclusiones tiene como caso particular el principio de adición, pues si las dos colecciones son disjuntas entonces $n(AB)=0$ –de hecho este es el significado de disjuntos.

Otra forma de ver la validez de la fórmula $n(AUB)=n(A)+n(B)-n(AB)$ es partiendo $AUB$ en tres conjuntos disjuntos y aplicar el principio de adición: $AUB=(A\backslash B)U(B\backslash A)UAB$, donde $A\backslash B$ tiene el significado usual de “los elementos en $ A $ pero no en $ B $”. (También hay que ver que los elementos de $ A $ pero no de $ B $ son los de $ A $ menos los de $AB$.) Entonces:$ n(AUB)=n(A\backslash B)+n(B\backslash A)+n(AB) $ $=n(A)-n(AB)+n(B)-n(AB)+n(AB$ $)=n(A)+n(B)+n(AB).$ Un obstáculo para el aprendizaje del principio de inclusión y exclusión (que parece ser muy difícil de superar para el aprendiz) es una “muy natural” incredulidad acerca del principio para más de dos conjuntos. (El único remedio conocido para salvar ese obstáculo es hacer muchos ejercicios que se resuelvan sin el principio y con el principio.)

Para tres conjuntos $A, B, C$ la fórmula sería:$ n(AUBUC)= n(A)+n(B)+n(C)-n(AB)-n(BC)-n(CA)+n(ABC) $

Una forma de convencerse de la validez de esta fórmula es tomar un elemento cualquiera, digamos x, de la unión AUBUC, y demostrar que la fórmula lo cuenta exactamente una vez:

1)si x perteneciera a exactamente uno de los conjuntos, digamos a A, entonces en el lado derecho se cuenta en n(A) solamente; por tanto, se ha contado exactamente una vez;

2)si x perteneciera a dos de los conjuntos, digamos a A y a B, entonces se suma en n(A) y n(B), se resta en n(AB), en resumen se cuenta exactamente una vez;

3)si pertenece a los tres se cuenta tres veces en n(A)+n(B)+n(C), se resta tres veces en -n(AB)-n(BC)-n(CA), y se cuenta una vez en n(ABC).

En todos los casos x se cuenta exactamente una vez.

Un problema elemental

¿De cuántas formas se pueden ordenar los dígitos 123 de tal manera que a ningún dígito le siga su consecutivo? Por ejemplo 231 no estaría permitido.

Solución (por enumeración exhaustiva)

132

213

312

Solución (por principio de inclusión y exclusión)

Todas las ordenaciones posibles: 3!=6

Las que tienen el 12: 2!=2 (el 12 se ve como un solo elemento y se permuta con el 3)

Las que tienen el 23: 2!=2 (el 23 se ve como un solo elemento y se permuta con el 1)

Las que contienen el 12 y el 23: 1 (la ordenación 123)

Por tanto, la solución es 6-4+1=3.

Comentario metódico sobre el uso de la fórmula

Conviene pensar aquí, para propósitos de aprender a aplicar la fórmula, que A=elementos con la propiedad 1 (contienen 12), B=elementos con la propiedad 2 (contienen 23) y C=elementos con las dos propiedades. Lo que estamos contando (y esto es lo usual al aplicar el principio) son los elementos que no tienen ninguna de las propiedades. Y claramente, todos los elementos se pueden partir en dos clases: los que no tienen ninguna propiedad y los que tienen al menos una propiedad, y ya podemos aplicar el principio de adición: n(todos)=n(ninguna)+n(al menos una). (Este es un detalle que tampoco se explica mucho en los textos.)

Se les llama desordenamientos a las permutaciones de n objetos en las que ningún elemento está en su lugar. Por ejemplo, los desordenamientos de 123 son 231, 312. Estos dos desordenamientos se pueden contar con el principio de inclusión y exclusión: 3!-C(3,1)(2!)+C(3,2)(1!)-C(3,3)(0!)=6-6+3-1=2. Es decir, todas las permutaciones menos las que dejan un elemento en su lugar más las que dejan dos elementos en su lugar menos las que dejan todos sus elementos en su lugar.

En el caso general, el número de desordenamientos de n objetos se calcula así (se acostumbra denotar con D_n este número):

D_n = n!-C(n,1)(n-1)!+C(n,2)(n-2)!-…

Si notamos que los dos primeros términos se eliminan, se puede ver que D_n = C(n,2)(n-2)!-C(n,3)(n-3)!+…

Y recordando que C(n,k)=n!/[k!(n-k)!], se puede ver que los términos C(n,k)(n-k)! se simplifican a n!/k!. De aquí que la fórmula para los desordenamientos de n objetos queda así: D_n=n![1/2!-1/3!+…]

Por el desierto, un beduino lleva 5 camellos cargados de mercancía. Los camellos marchan en caravana, es decir, uno detrás del otro. Como la travesía es larga, el beduino trata de que sus camellos no se aburran y de vez en cuando los acomoda de tal manera que cada camello vaya detrás de un camello diferente al camello con el que inició el viaje. ¿Cuántas formas tiene el beduino de acomodar a sus camellos?

Solución (con enumeración exhaustiva)

La solución exhaustiva es una tarea que requiere concentración y el aprendiz debe hacerla en sus primeros pasos hacia el aprendizaje de la combinatoria:

13254

13524

13542

14254

14325

14352

15243

15324

15432

Son 9 ordenaciones que empiezan con 1. Se deja al lector la tarea de enumerar las que empiezan con 2, con 3, con 4 y con 5. En cada una de ellas son 11 ordenaciones posibles. En total, el beduino tiene 9+44=53 formas de acomodar los camellos, de acuerdo a su objetivo de que no se aburran.

Solución (con inclusión y exclusión) T_5=5!-C(4,1)4!+C(4,2)3!-C(4,3)2!+C(4,4)1!=120-4(24)+6(6)-4(2)+1=53.

C(4,1)4! cuenta las ordenaciones en que aparecen dos camellos en el orden inicial, y se obtiene con el siguiente argumento: se escoge uno de los cuatro pares ii+1, i=1,2,3,4; este par se toma como un elemento más y, junto con los 3 elementos restantes, se permutan. En este caso debería ser claro que la expresión C(4,1)4! cuenta todos las permutaciones que incluyen un bloque ii+1 (sin excluir que puedan tener más de uno). Ahora bien, cuando se cuentan las ordenaciones de más de un bloque, puede quedar la duda de ¿qué pasa si los bloques no son disjuntos?

Por ejemplo, si en la ordenación obligamos a quedar juntos a 12 y 45, entonces estos bloques, más el 3, forman tres elementos y las permutaciones posibles son 3!; pero si obligamos a quedar juntos a 12 y 23, estos dos bloques comparten el 2. Claramente no podemos argumentar que esos dos bloques más los elementos 4 y 5 se permutan de 4! formas. ¿Qué pasa aquí? ¿Cuál es el argumento combinatorio que justifica C(4,2)3!? Bueno, después de un momento de meditación, el argumento que surge como válido es el siguiente: 123 lo tomo como un solo elemento, y junto con el 4 y el 5 se tienen 3 elementos a permutar.

En general, si dos bloques no son disjuntos, los dos se toman como un solo elemento de 3 números, y quedan n-3. Pero n-3+1=n-2. Por lo tanto es válido argumentar: escojo dos pares de la forma ii+1 de C(n-1,2) y, sean o no disjuntos, me quedan 3 elementos a permutar. Porque si son disjuntos, usan 4 elementos; y me quedan n-4 elementos que, junto con los dos bloques, forman n-4+2=n-2 elementos a permutar; y si no son disjuntos, usan 3 elementos y los 3 los tomo como uno solo; me quedan n-3 elementos que, junto con el bloque de los 3, forman n-3+1=n-2 elementos a permutar.

El argumento puede generalizarse a r bloques: si son disjuntos, usan 2r elementos y quedan n-2r elementos que, junto con los r bloques, forman n-r elementos a permutar; si no son disjuntos, cada par no disjunto lo compacto en uno solo. Por cada par no disjunto compacto 3 elementos, me quedan n-3, más el elementos compactado suman n-2. ¿Qué pasa si son 3 pares como 1234? Son tres pares que se compactan en uno solo. Quedan n-4 elementos, más el compactado son n-3 que debo permutar. En general, supongamos que hay r pares formados por r+1 elementos consecutivos. Entonces son r pares que voy a compactar en un sólo elemento. Quedan n-r-1 elementos, más el bloque de r +1 elementos, son n-r-1+1=n-r elementos a permutar.

¿Cuántas ordenaciones de los números 1, 2,…,n son posibles si en la ordenación no están permitidos bloques de la forma (i,i+1)?

Solución al problema general de la caravana del desierto

Sea X el conjunto de todas las ordenaciones sin restricciones. Como se sabe, su número es n!. Y sea A_i el subconjunto de X en cuyos elementos aparece el bloque ii+1. Hay n-1 de tales bloques. Entonces, de acuerdo al principio de inclusión y exclusión, el número de oredenaciones es:

T_n=n!-C(n-1,1)(n-1)!+C(n-1,2)(n-2)!-…(-1)^(n-1)C(n-1,n-1)1!

Y podemos observar una semejanza con el número de desordenaciones D_n de n objetos. Queda como ejercicio para el lector demostrar que T_n=D_n+D_{n-1}.