4.2: Pruebas combinatorias

Como dijimos en el apartado anterior, pensar en un problema de dos maneras distintas crea implícitamente una biyección, diciéndonos que el número de soluciones que obtengamos será el mismo de cualquier manera. Cuando miramos las bijecciones, estábamos usando esta idea para encontrar una manera más fácil de contar algo que parecía difícil. Pero si realmente podemos encontrar una fórmula (posiblemente desordenada) que cuente correctamente la respuesta a nuestro problema de alguna manera “difícil”, y también podemos encontrar una fórmula diferente que cuente correctamente la respuesta al mismo problema mirándolo de una manera diferente, entonces sabemos que los valores de las dos fórmulas deben sean iguales, por diferentes que se vean.

Esta es la idea de una “prueba combinatoria”.

Teorema\(\PageIndex{1}\)

Si\(f(n)\) y\(g(n)\) son funciones que cuentan el número de soluciones a algún problema que involucra\(n\) objetos, entonces\(f(n) = g(n)\) para cada\(n\)

Definición: Identidad combinatoria

Supongamos que contamos las soluciones a un problema sobre\(n\) objetos de una manera y obtenemos la respuesta\(f(n)\) para alguna función\(f\); y luego contamos las soluciones al mismo problema de una manera diferente y obtenemos la respuesta\(g(n)\) para alguna función\(g\). Esta es una prueba combinatoria de la identidad\(f(n) = g(n)\).

La ecuación\(f(n) = g(n)\) se conoce como identidad combinatoria.

En la afirmación de este teorema y definición, hemos hecho\(f\) y\(g\) funciones de una sola variable\(n\), pero las mismas ideas sostienen si\(f\) y\(g\) son funciones de más de una variable. Nuestro primer ejemplo lo demuestra.

Ejemplo\(\PageIndex{1}\)

Demostrar que para cada número natural\(n\) y cada número entero\(r\) entre\(0\) y\(n\), tenemos

\(\binom{n}{r} = \binom{n}{n-r}\)

Solución

Por definición de\(\binom{n}{r}\), esta es la cantidad de formas de elegir\(r\) objetos de un conjunto de objetos\(n\) distintos. Cada vez que elegimos\(r\) de los objetos, los otros\(n − r\) objetos se quedan fuera del conjunto que estamos eligiendo. Así que de manera equivalente, en lugar de elegir los\(r\) objetos a incluir en nuestro conjunto, podríamos elegir los\(n − r\) objetos a dejar fuera de nuestro conjunto. Por la definición de los coeficientes binomiales, hay\(\binom{n}{n-r}\) formas de hacer esta elección.

Por lo tanto, debe darse el caso de que por cada número natural\(n\) y cada número entero\(r\) entre\(0\) y\(n\), tenemos

\(\binom{n}{r} = \binom{n}{n-r}\)

según se desee,

Por supuesto, esta identidad particular también es bastante fácil de probar directamente, utilizando la fórmula para\(\binom{n}{r}\), ya que

\(\binom{n}{n-r} = \dfrac{n!}{(n-r)!(n-(n-r))!} = \dfrac{n!}{(n-r)!r!} = \binom{n}{r} \)

Muchas identidades que se pueden probar usando una prueba combinatoria también se pueden probar directamente, o usando una prueba por inducción. Lo bueno de una prueba combinatoria es que generalmente nos da una idea bastante más clara de por qué las dos fórmulas deberían ser iguales, que la que obtenemos de muchas otras técnicas de prueba.

En el Ejemplo 4.1.1, observamos que una forma de averiguar el número de subconjuntos de un conjunto de n-elementos sería contar el número de subconjuntos de cada tamaño posible, y sumarlos todos. Luego seguimos un enfoque biyectiva para demostrar que la respuesta es de hecho\(2n\). Si realmente llevamos a cabo la primera idea, esto conduce a otra identidad combinatoria (una que ya observamos a través del Teorema Binomial):

Ejemplo\(\PageIndex{2}\)

Demuéstralo por cada número natural\(n\)

\(\sum_{r=0}^{n} \binom{n}{r} = 2^n\)

Solución

Hemos visto en el Ejemplo 4.1.1 que el número de subconjuntos de un conjunto de\(n\) elementos es\(2^n\). Vamos a contar el mismo problema de una manera diferente, para obtener el otro lado de la igualdad.

Para determinar el número de subconjuntos de un conjunto de\(n\) elementos, dividimos el problema en\(n + 1\) casos y usamos la regla de suma. Los casos en los que vamos a dividir el problema son las diferentes cardinalidades posibles para los subconjuntos: todo desde el\(0\) principio\(n\). Hay\(\binom{n}{r}\) formas de elegir un subconjunto de\(r\) elementos del conjunto de\(n\) elementos, por lo que el número de subconjuntos que contienen\(r\) elementos es\(\binom{n}{r}\). Así, el número total de subconjuntos de nuestro conjunto original debe ser\(\sum_{r=0}^{n} \binom{n}{r}\).

Como hemos contado el mismo problema de dos maneras distintas y obtenido fórmulas distintas, el Teorema 4.2.1 nos dice que las dos fórmulas deben ser iguales; es decir,

\(\sum_{r=0}^{n} \binom{n}{r} = 2^n\)

según se desee.

También podemos producir una interesante identidad combinatoria a partir de una generalización del problema estudiado en el Ejemplo 4.1.2.

Ejemplo\(\PageIndex{3}\)

Supongamos que tenemos una colección de\(n\) hombres y\(n\) mujeres, y queremos elegir\(r\) de ellos para un grupo focal, pero debemos incluir al menos una mujer. ¿De cuántas maneras se puede hacer esto? Utilice dos métodos diferentes para contar las soluciones y deducir una identidad combinatoria.

Solución

Usando el mismo razonamiento que aplicamos en el Ejemplo 4.1.2, vemos que el número de formas de elegir un grupo que incluya al menos a una mujer es el número total de formas de elegir un grupo de\(r\) personas de estas\(2n\) personas, menos el número de formas que incluyen solo a los hombres; es decir:\(\binom{2n}{r} − \binom{n}{r}\).

Alternativamente, podemos dividir el problema en\(r\) casos dependiendo de cuántas mujeres se van a incluir en el grupo (debe haber\(i\) mujeres, para algunas\(1 ≤ i ≤ r\)). Hay\(\binom{n}{i}\) formas de elegir\(i\) mujeres para el grupo, y para cada una de estas, hay\(\binom{n}{r-i}\) formas de elegir\(r−i\) hombres para completar el grupo. Así, el número total de formas de elegir un grupo que incluya al menos a una mujer, es

\(\sum_{i=1}^{r} \binom{n}{i} \binom{n}{r - i}\)

Este argumento arroja la identidad combinatoria

\(\sum_{i=1}^{r} \binom{n}{i} \binom{n}{r - i} = \binom{2n}{r} - \binom{n}{r}\)

lo que con ello hemos probado.

Un contexto en el que las pruebas combinatorias surgen de manera muy natural es cuando estamos contando pares ordenados que tienen alguna propiedad. Es decir, para algún subconjunto de\(X \times Y\), es posible que deseemos contar todos los pares ordenados\((x, y)\), donde\(x ∈ X\) y\(y ∈ Y\), tal que\((x, y)\) tenga alguna propiedad. Podemos hacer esto considerando primero cada valor posible de\(x ∈ X\), y para cada uno de esos valores, contando el número de\(y ∈ Y\) tales que\((x, y)\) satisfaga la propiedad deseada, o considerando primero cada valor posible de\(y ∈ Y\), y para cada uno de esos valores, contando el número de\(x ∈ X\) tales que\((x, y)\) satisfaga la propiedad deseada.

Si bien esta idea puede no parecer muy práctica, en realidad es el contexto en el que surgirán muchas de las pruebas combinatorias en capítulos posteriores. Estaremos viendo un conjunto\(X\) de elementos, y un conjunto\(Y\) que en realidad es una colección de subconjuntos de elementos de\(X\), y contando pares\((x, y)\) para los que el elemento\(x\) aparece en el subconjunto\(y\). Al contar estos pares de dos maneras, encontraremos una identidad combinatoria.

Ejemplo\(\PageIndex{4}\)

Dejar\(B\) ser el conjunto de cuadras de ciudad en una ciudad pequeña, y dejar\(S\) ser el conjunto de segmentos de calle en la ciudad (donde un segmento de calle significa un tramo de calle que se encuentra entre dos intersecciones). Supongamos que cada bloque tiene al menos tres lados. Contar el número de pares\((s, b)\) con\(s ∈ S\) y\(b ∈ B\) tal que el segmento de calle\(s\) sea adyacente a la cuadra de dos\(b\) maneras. Usa esto para deducir una desigualdad combinatoria.

Solución

Vamos\(|S| = t\). Cada segmento de calle es adyacente a dos cuadras: las cuadras que se encuentran a cada lado de la calle. Por lo tanto, para cualquier segmento de calle dado\(s\), existen dos pares\((s, b)\) tales que\(s\) se encuentran adyacentes a la cuadra\(b\). Multiplicar este conteo por\(t\) (el número de segmentos de calle) nos dice que el número total de pares\((s, b) ∈ S \times B\) con\(s\) adyacente a\(b\) es\(2t\).

Vamos\(|B| = c\). Cada bloque es adyacente a al menos segmentos de\(3\) calle: los segmentos de calle que rodean la manzana. Por lo tanto, para cualquier bloque dado\(b\) en la ciudad, hay al menos\(3\) pares\((s,b)\) tales que\(b\) se encuentran adyacentes al segmento de calle\(s\). Multiplicar este conteo por\(c\) (el número de bloques) nos dice que el número total de pares\((s, b) ∈ S \times B\) con\(s\) adyacente a\(b\) es al menos\(3c\).

Eso lo deducimos\(2t ≥ 3c\).

Ejercicio\(\PageIndex{1}\)

Que\(P\) sea el conjunto de personas en un grupo, con\(|P| = p\). Dejemos\(C\) ser un conjunto de clubes formados por la gente de este grupo, con\(|C| = c\). Supongamos que cada club contiene exactamente\(g\) personas, y cada persona está exactamente en\(j\) clubes. Usa dos formas diferentes de contar el número de parejas de\((b, h) ∈ P \times C\) tal manera que esa persona\(b\) está en el club\(h\), y deducir una identidad combinatoria.

Ejercicio\(\PageIndex{2}\)

Demostrar las siguientes identidades combinatorias, utilizando pruebas combinatorias:

1. Para cualquier número natural\(r\),\(n\), con\(1 ≤ r ≤ n\),\(\binom{n}{r} = \binom{n−1}{r−1} + \binom{n−1}{r}\). [Pista: Considere la cantidad de formas de formar un equipo de\(r\) personas a partir de un grupo de\(n\) personas. Después divide el problema en dos casos dependiendo de si se elige o no a una persona específica para el equipo.]
2. Para cualquier número natural\(k\),\(r\),\(n\), con\(0 ≤ k ≤ r ≤ n\),\(\binom{n}{r} \binom{r}{k} = \binom{n}{k} \binom{n−k}{r−k}\). [Pista: Considere la cantidad de formas de elegir\(r\) perros que ingresarán a una competencia, de un conjunto de\(n\) perros, y elegir\(k\) de esos\(r\) perros para convertirse en los finalistas. Después elige primero a los finalistas, seguidos de los demás perros que ingresaron a la competencia.]
3. Para cualquier número natural\(n\),\(\sum_{r=0}^{n} \binom{n}{r}^2 = \binom{2n}{n}\).
4. Para\(n ≥ 1\) y\(k ≥ 1\),\(\dfrac{n!}{(n−k)!} = n \dfrac{(n−1)!}{(n−1−(k−1))!}\).
5. Para\(n ≥ 1\),\(3^n = \sum_{k=0}^{n} \binom{n}{k} 2^{n-k} \)

Ejercicio\(\PageIndex{3}\)

A veces, la parte más difícil de una prueba combinatoria puede ser averiguar a qué problema brinda una solución la fórmula dada. Para cada una de las siguientes fórmulas, indicar un problema de conteo que puede resolverse con la fórmula.

1. \(n2^{n−1}\).
2. \(\sum_{r=0}^{n} r \binom{n}{r}\).
3. \(\sum_{k=r}^{n} \binom{n}{k} \binom{k}{r}\).
4. \(2^{n−r} \binom{n}{r} \).