4.1: Conteo vía Bijecciones

Puede ser difícil averiguar cómo contar el número de resultados para un problema en particular. A veces será posible encontrar un problema diferente, y demostrar que los dos problemas tienen el mismo número de resultados (encontrando una biyección entre sus resultados). Si podemos averiguar cómo contar los resultados para el segundo problema, ¡entonces también hemos resuelto el primer problema! Esto puede parecer descaradamente obvio de manera intuitiva, pero esta técnica puede proporcionar soluciones simples a problemas que a primera vista parecen muy difíciles.

Esta técnica de contar un conjunto (o el número de resultados a algún problema) indirectamente, a través de un conjunto o problema diferente, es la técnica biyectiva para contar. Comenzamos con un ejemplo clásico de esta técnica.

Ejemplo\(\PageIndex{1}\)

¿Cuántos subconjuntos posibles hay, a partir de un conjunto de\(n\) elementos?

Solución

Un enfoque sería averiguar cuántos subconjuntos\(0\) -elementos hay, cuántos subconjuntos\(1\) -elementos, etc., y sumar todos los valores que encontramos. Esto funciona, pero hay tantas piezas involucradas que es propenso al error. Además, el valor no será fácil de calcular una vez que\(n\) sea razonablemente grande.

En cambio, imaginamos crear una mesa. Las columnas están indexadas por los elementos del conjunto, por lo que hay\(n\) columnas. Indexamos las filas por los subconjuntos de nuestro conjunto (uno por fila). En cada entrada de la tabla, colocamos un\(1\) si el subconjunto que corresponde a esta fila contiene el elemento que corresponde a esta columna. Aquí hay un ejemplo de una tabla de este tipo cuando el conjunto es\(\{x, y, z\}\):

	\(x\)	\(y\)	\(z\)
\(0\)	\(0\)	\(0\)	\(0\)
\(\{x\}\)	\(1\)	\(0\)	\(0\)
\(\{y\}\)	\(0\)	\(1\)	\(0\)
\(\{z\}\)	\(0\)	\(0\)	\(1\)
\(\{x,y\}\)	\(1\)	\(1\)	\(0\)
\(\{x,z\}\)	\(1\)	\(0\)	\(1\)
\(\{y,z\}\)	\(0\)	\(1\)	\(1\)
\(\{x,y,z\}\)	\(1\)	\(1\)	\(1\)

Como puede ver, el patrón de\(1\) s y\(0\) s es diferente en cada fila de la tabla, ya que los elementos de cada subconjunto son diferentes. Además, cualquier patrón de\(1\) s y\(0\) s que tenga longitud\(3\), aparece en alguna fila de esta tabla.

Esto no es una coincidencia. En general, podemos definir una bijección entre las cadenas binarias de longitud\(n\), y los subconjuntos de un conjunto de\(n\) elementos, de la siguiente manera. Ya sabemos por la definición de cardinalidad, que hay una biyección entre nuestro conjunto de\(n\) elementos, y el conjunto\(\{1, . . . , n\}\), por lo que en realidad vamos a definir una biyección entre los subconjuntos de\(\{1, . . . , n\}\) y las cadenas binarias de longitud\(n\). Dado que la composición de dos bijecciones es una bijección, esto definirá indirectamente una bijección entre nuestro conjunto original, y las cadenas binarias de longitud\(n\).

Dado un subconjunto de\(\{1, . . . , n\}\), la cadena binaria que corresponde a este subconjunto será la cadena binaria que tiene\(1\) s en la\(i^{th}\) posición si y solo si\(i\) está en el subconjunto. Esto nos dice cómo determinar la cadena binaria a partir del subconjunto. También podemos invertir (invertir) el proceso. Dada una cadena binaria de longitud\(n\), el subconjunto correspondiente de\(\{1, . . . , n\}\) será el subconjunto cuyos elementos son las posiciones de la\(1\) s en la cadena binaria.

Aunque no hemos probado directamente que este mapa de subconjuntos a cadenas binarias sea tanto uno a uno como a uno, una función invertible debe ser una biyección, por lo que el hecho de que hayamos podido encontrar una función inversa sí demuestra que este mapa es una biyección. (Debe verificar que está de acuerdo en que la función que hemos reclamado como inversa realmente invierte la función original).

Ahora bien, nuestra mesa imaginaria no sería de mucha utilidad si realmente tuviéramos que escribirla. Para escribirlo, necesitaríamos conocer ya todos los subconjuntos de nuestro conjunto; y si los conociéramos a todos, ¡ciertamente podríamos contarlos! Afortunadamente, no necesitamos escribirlo. En cambio, usamos la bijección que acabamos de definir. En lugar de contar el número de subconjuntos de un\(n\) -set, contamos el número de cadenas binarias de longitud\(n\). ¡Podemos hacer esto usando solo la regla de multiplicación! En cada posición, hay o bien un cero o uno, por lo que hay\(2\) opciones para cada una de las\(n\) posiciones. De ahí que haya cadenas\(2^n\) binarias de longitud\(n\).

Se concluye que los\(2^n\) subconjuntos pueden formarse a partir de un conjunto de cardinalidad\(n\).

De alguna manera, en realidad hemos estado usando esta idea casi cada vez que se nos ocurre más de una forma de resolver un problema. Implícitamente, encontrar una manera diferente de pensar el problema equivale a encontrar una biyección entre las soluciones a estos diferentes enfoques.

Ejemplo\(\PageIndex{2}\)

¿Cuántas formas hay de elegir a diez personas de un grupo de\(30\) hombres y\(30\) mujeres, si el grupo debe incluir al menos a una mujer?

Solución

Atacar este problema directamente se pondrá feo. Tendríamos que considerar por separado los casos de incluir a una mujer, dos mujeres, etc., hasta diez mujeres, en nuestro grupo, y sumar todos los términos resultantes juntos. En cambio, observamos que existe una obvia bijección (el mapa de identidad) entre grupos que sí incluyen al menos a una mujer, y grupos que no incluyen exactamente a cero mujeres.

Esto último es relativamente fácil de entender: hay\(\binom{60}{10}\) posibles grupos de diez personas que podrían elegirse entre las\(60\) personas. De estos, hay\(\binom{30}{10}\) grupos que incluyen a cero mujeres (ya que los integrantes de cualquier grupo de ese tipo deben elegirse íntegramente entre los\(30\) hombres). Por lo tanto, el número de grupos que no incluyen exactamente a cero mujeres, es\(\binom{60}{10} - \binom{30}{10}\).

Gracias a nuestra bijección, concluimos que también lo es el número de grupos que se pueden elegir, que incluirán al menos a una mujer\(\binom{60}{10} - \binom{30}{10}\).

Ejercicio\(\PageIndex{1}\)

Los siguientes problemas deberían ayudarte a trabajar con la técnica biyectiva para contar.

1. Definimos una estructura que es como un subconjunto, excepto que cualquier elemento del conjunto original puede aparecer\(0\)\(1\), o\(2\) veces en la estructura. ¿Cuántas de estas estructuras podemos formar a partir del conjunto\(\{1, . . . , n\}\)?
2. Encuentra una biyección entre el coeficiente de\(x^r\) in\((1 + x)^n\), y el número de\(r\) -combinaciones de un\(n\) -set.
3. Encuentra una bijección entre la cantidad de formas en que tres muñecos diferentes se pueden poner en diez cunas numeradas, y la cantidad de formas en que diez contendientes olímpicos pueden ganar las medallas en su evento.