Principio de doble conteo y coeficientes binomiales#
Introducción#
En esta entrada supondremos que estás familiarizado con las nociones básicas de conteo combinatorio: la enumeración, la regla de la suma, la regla del producto y las permutaciones. En caso de no ser así, te recomendamos revisar el siguiente material:
Los videos de Combinatoria en la página https://blog.nekomath.com/videos/
El artículo «Estrategias básicas de conteo» en la revista Tzaloa 2011-2: https://www.ommenlinea.org/wp-content/uploads/2014/01/11-2.pdf
Lo que haremos ahora es introducir un principio nuevo: el de doble conteo. La idea es muy sencilla: dos formas distintas y válidas de contar una familia de objetos deben de dar cantidades iguales. Al contar de manera creativa, esto se puede utilizar para la resolución de muchos problemas. En particular, veremos cómo estas ideas se aplican al desarrollo de la teoría de coeficientes binomiales.
Principio de doble conteo#
El principio de doble conteo dice lo siguiente.
Proposición. Supongamos que tenemos un conjunto \(X\) de objetos. Supongamos que dos estrategias de conteo distintas, pero válidas, nos dicen que \(X\) tiene por un lado \(A\) elementos y por otro lado \(B\) elementos. Entonces, \(A=B\).
Probemos con este principio un resultado clásico.
Problema. Muestra que
Solución. Realicemos una demostración por doble conteo. Para ello, introducimos un problema auxiliar. Contaremos cuántas parejas \((a,b)\) existen para las cuales \(a\) es distinto de \(b\) y \(a,b\) son números de \(1\) a \(n+1\).
Una forma de contar es la siguiente. La primera entrada tiene \(n+1\) posibilidades. Una vez fija, la segunda entrada tiene \(n\) posibilidades. Así, por el principio del producto una posible respuesta al problema de conteo es \(n(n+1)\).
Otra forma de contar es la siguiente. Supongamos de momento que \(a>b\).
Si \(a=1\), entonces \(b\) no tiene posiblidades.
Si \(a=2\), entonces \(b\) tiene una posibilidad.
Si \(a=3\), entonces \(b\) tiene dos posibilidades.
\(\ldots\)
Si \(a=n+1\), entonces \(b\) tiene \(n+1\) posibilidades.
Así, hay \(1+2+\ldots+n\) posiblidades. Pero faltan los casos con \(b>a\), que por simetría son los mismos. Así, tenemos que:
Dividiendo entre \(2\) obtenemos el resultado deseado. \(\square\)
Coeficientes binomiales y su fórmula#
Quizás hayas encontrado con anterioridad a los coeficientes binomiales. Para un entero \(n\geq 0\) y un entero \(k\) con \(0\leq k \leq n\), se puede definir el símbolo \(\binom{n}{k}\) de varias maneras. Nosotros eligiremos definir al coeficiente binomial \(\binom{n}{k}\) a partir de su propiedad combinatoria fundamental.
Definición. El coeficiente binomial \(\binom{n}{k}\) es la cantidad de subconjuntos de tamaño \(k\) que tiene un conjunto de tamaño \(n\).
Así, estrictamente hablando, si quisiéramos calcular cuánto vale el coeficiente binomial \(\binom{4}{2}\), tendríamos que tomar un conjunto con cuatro elementos, por ejemplo \(\{A,B,C,D\}\), enlistar todos sus subconjuntos con dos elementos:
y contarlos. Como son \(6\), entonces \(\binom{4}{2}=6\).
Esto no es muy práctico para valores grandes de \(n\) y \(k\), pues tendríamos que enlistar muchos subconjuntos. Así, es importante encontrar una mejor fórmula para \(\binom{n}{k}\). Lo hacemos como sigue:
Proposición. Se tiene que
Demostración. Tomemos pelotas numeradas del \(1\) al \(n\). ¿Cuántas formas hay de ordenarlas en una línea? Por un lado, hay \(n!\) formas: \(n\) opciones para el primer lugar, \(n-1\) opciones para el segundo, etc. Estos números se multiplican y obtenemos el valor \(n\cdot (n-1) \cdot (n-2)\cdot \ldots \cdot 1 = n!\).
Hay otra forma de saber de cuántas formas podemos ordenar las pelotas. Primero podemos decidir cuáles serán las primeras \(k\) pelotas. Esto se puede hacer de \(\binom{n}{k}\) formas, pues es elegir un subconjunto \(K\) de tamaño \(k\). Luego, hay que elegir una forma de acomodar estas \(k\) pelotas, que se puede hacer de \(k!\) formas (por el arugmento de arriba). Finalmente, quedan \(n-k\) pelotas que debemos decir cómo acomodar. Esto se puede hacer de \((n-k)!\) formas. Así, hay \(\binom{n}{k}k!(n-k)!\) formas de acomodar las pelotas.
Como estamos contando exactamente lo mismo, debemos tener que
de donde se obtiene la fórmula que buscamos despejando \(\binom{n}{k}\). \(\square\)
La fórmula de Pascal#
Los coeficientes binomiales con \(k=0\) o \(k=n\) son muy fáciles: simplemente son iguales a \(1\). Para calcular el resto de los coeficientes binomiales podemos proceder «poco a poco». Cada uno de ellos es una suma de dos «más pequeños». Esto se formaliza mediante el siguiente resultado.
Proposición. Para un entero \(n\geq 0\) y un entero \(k\) con \(0\leq k \leq n-1\) se tiene que
A esta se le conoce como la identidad de Pascal para los coeficientes binomiales. Observa que nos está diciendo que los coeficientes binomiales justo cumplen la regla del triángulo de Pascal: cada uno es o bien igual a uno (en los extremos) o bien la suma de dos anteriores con un valor menor que \(n\) (es decir «en el renglón anterior»). Una vez que hayamos demostrado esta fórmula, tendremos la garantía de que el triángulo de Pascal se ve así:
\(\binom{0}{0}\) |
|||||||||||
\(\binom{1}{0}\) |
\(\binom{1}{1}\) |
||||||||||
\(\binom{2}{0}\) |
\(\binom{2}{1}\) |
\(\binom{2}{2}\) |
|||||||||
\(\binom{3}{0}\) |
\(\binom{3}{1}\) |
\(\binom{3}{2}\) |
\(\binom{3}{3}\) |
||||||||
\(\binom{4}{0}\) |
\(\binom{4}{1}\) |
\(\binom{4}{2}\) |
\(\binom{4}{3}\) |
\(\binom{4}{4}\) |
|||||||
\(\binom{5}{0}\) |
\(\binom{5}{1}\) |
\(\binom{5}{2}\) |
\(\binom{5}{3}\) |
\(\binom{5}{4}\) |
\(\binom{5}{5}\) |
Veamos dos maneras de demostrar la identidad de Pascal. Una es combinatoria y la otra es algebraica.
Demostración. La demostración combinatoria es por doble conteo. Podemos hacernos la siguiente pregunta: ¿cuántos subconjuntos de tamaño \(k+1\) tiene el conjunto \(\{1,2,\ldots,n+1\}\)? Por un lado, por la definición de coeficientes binomiales este número es \(\binom{n+1}{k+1}\). Por otro lado, podemos ver cuántos tienen a \(n+1\) y cuántos no. Los que tienen a \(n+1\) consisten de ese elemento y de otros \(k\) elementos elegidos en \(\{1,2,\ldots,n\}\), así que son \(\binom{n}{k}\). Los que no tienen a \(n+1\) consisten de elegir \(k+1\) elementos en \(\{1,2\ldots,n\}\), de modo que son \(\binom{n}{k+1}\). Así, como estamos contando la misma cosa, tenemos que
\(\square\)
Esto es una demostración perfectamente válida y podríamos concluir aquí. Pero demos ahora una demostración algebraica. Para ella, usamos la fórmula que ya conocemos.
Demostación. Procedemos como sigue:
En la segunda igualdad factorizamos lo más que podemos. Luego hacemos la operación con fracciones, reagrupamos y volvemos a usar la fórmula, pero ahora para \(\binom{n+1}{k+1}\). \(\square\)
Exploración computacional del triángulo de Pascal#
Una de las aplicaciones de la fórmula de Pascal es que nos permite escribir código para calcular los coeficientes binomiales, y por lo tanto para mostrar el triángulo de Pascal. En la siguiente celda podrás encontrar una forma de hacer esto. La función t_pascal muestra los primeros \(n\) renglones del triángulo de Pascal. El primero y segundo renglón son fáciles de dar de manera explícita. Los siguientes renglones son calculados usando la fórmula de Pascal. No entraremos mucho más en los detalles de lo que está sucediendo, pues los discutiremos más adelante cuando hablamos de programación dinámica.
def t_pascal(n):
renglon=[1]
for j in range(n):
nuevo_renglon=[]
for k in range(j+1):
if k==0 or k==j:
nuevo_renglon.append(1)
else:
nuevo_renglon.append(renglon[k-1]+renglon[k])
print(nuevo_renglon)
renglon=nuevo_renglon
t_pascal(10)
[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
[1, 5, 10, 10, 5, 1]
[1, 6, 15, 20, 15, 6, 1]
[1, 7, 21, 35, 35, 21, 7, 1]
[1, 8, 28, 56, 70, 56, 28, 8, 1]
[1, 9, 36, 84, 126, 126, 84, 36, 9, 1]
Tarea moral#
Los siguientes problemas te ayudarán a practicar lo visto en esta entrada. Para resolverlos, necesitarás usar herramientas matemáticas, computacionales o ambas.
Da una demostración por doble conteo para la siguiente igualdad:
\[1\cdot 1! + 2\cdot 2! + 3\cdot 3! + \ldots + n\cdot n! = (n+1)! - 1.\]Realiza una exploración computacional para conjeturar cuáles son los renglones del triángulo de Pascal en donde todos los números son impares.
La siguiente igualdad siempre se cumple:
\[\binom{n}{1}+2\binom{n}{2}+3\binom{n}{3}+\ldots+n\binom{n}{n}=n2^{n-1}.\]Verifica esto de manera computacional hasta \(n=10\). Luego, da una demostración combinatoria (por doble conteo) y una algebraica (por inducción).
Lee el artículo «Contando de dos formas distintas» en la revista Tzaloa 2011-3 para conocer más acerca del principio de doble conteo: https://www.ommenlinea.org/wp-content/uploads/2014/01/11-3.pdf
La siguente expresión se puede simplificar a un único coeficiente binomial:
\[\binom{n}{0}^2+\binom{n}{1}^2+\ldots+\binom{n}{n}^2.\]¿A cuál? Para determinar esto, realiza una exploración computacional que calcule la expresión en los primeros casos. Luego, compara el resultado con otros coeficientes binomiales. Haz una conjetura. Finalmente, realiza una demostración por doble conteo de la identidad que propones.