Coeficientes binomiales en resolución de problemas

Introducción

Los coeficientes binomiales aparecen en muchos problemas de matemáticas, y por ello es útil conocerlos bien y saber sus propiedades básicas. En esta entrada hablaremos de varios aspectos de los coeficientes binomiales: algebraicos, combinatorios y de teoría de números. Aunque resolvamos un problema con una técnica en particular, te recomendamos intentar usar las distintas herramientas en otros problemas, para conocer sus alcances y limitaciones.

Antes de empezar, ponemos una figura con un hecho curioso acerca de los coeficientes binomiales:

Coeficientes binomiales, Pascal y Fibonacci — «Las sumas de las diagonales del triángulo de Pascal dan los números de Fibonacci»

Definición algebraica de coeficientes binomiales

Como recordatorio, para $n \geq 0$ un entero, definimos $n!$ recursivamente como $0! = 1$ y $n! = n (n - 1)!$ . En otras palabras, para $n \geq 1$ tenemos $n! = 1 \cdot 2 \cdot \dots \cdot n .$

Definimos para $n \geq 0$ un entero y $k$ un entero en ${0, \dots, n}$ al coeficiente binomial $n$ en $k$ como $(\binom{n}{k}) := \frac{n!}{k! (n - k)!} .$ Si $n$ es un entero negativo o $k$ es un entero fuera del rango ${0, \dots, n}$ es conveniente definir $(\binom{n}{k}) = 0$ .

A partir de la definición, es claro que $(\binom{n}{n}) = (\binom{n}{0}) = 1$ para todo entero positivo $n$ . Lo que no es inmediato a partir de la definición es que $(\binom{n}{k})$ siempre sea un entero. Veremos eso en la siguiente sección.

Mientras tanto, veamos algunas propiedades de los coeficientes binomiales que se pueden verificar sin mostrar que $(\binom{n}{k})$ es entero.

Propiedad (simetría). $(\binom{n}{k}) = (\binom{n}{n - k}) .$

Propiedad (fórmula de Pascal). $(\binom{n + 1}{k + 1}) = (\binom{n}{k}) + (\binom{n}{k + 1}) .$

Propiedad (propiedad de entrada-salida). $(\binom{n + 1}{k + 1}) = \frac{n + 1}{k + 1} (\binom{n}{k}) .$

El siguiente problema se puede resolver usando estas identidades.

Propiedad (suma cambiando arriba). Muestra que para $n$ y $k$ enteros positivos se tiene que $\sum_{j = 0}^{k} (\binom{n + j}{n}) = (\binom{n + k + 1}{n + 1}) .$

Sugerencia pre-solución. Primero, formula un problema equivalente usando la propiedad de simetría. Luego, procede por inducción y usa otra de las propiedades de coeficientes binomiales mencionada arriba.

Solución. Usando la propiedad de simetría de coeficientes binomiales, el problema es equivalente a demostrar que $\sum_{j = 0}^{k} (\binom{n + j}{j}) = (\binom{n + k + 1}{k}) .$ Fijemos un entero $n \geq 0$ y hagamos inducción sobre $k$ . Para $k = 0$ , la identidad es cierta pues $(\binom{n}{0}) = 1 = (\binom{n + 1}{0}) .$

Para $k = 1$ , tenemos que mostrar que $(\binom{n}{0}) + (\binom{n + 1}{1}) = (\binom{n + 2}{1})$ . El primer término se puede escribir como $(\binom{n + 1}{0})$ , pues ambos son $1$ . Así, lo que hay que mostrar es $(\binom{n + 1}{0}) + (\binom{n + 1}{1}) = (\binom{n + 2}{1}),$ que es cierto por la fórmula de Pascal.

Suponiendo el resultado cierto para una $k$ dada, mostraremos que es cierto para $k + 1$ . Esto se sigue de la siguiente cadena de igualdades, en donde en la segunda igualdad usamos la hipótesis inductiva, y en la tercera la fórmula de Pascal:

$\begin{aligned} \sum_{j = 0}^{k + 1} (\binom{n + j}{j}) & = \sum_{j = 0}^{k} (\binom{n + j}{j}) + (\binom{n + k + 1}{k + 1}) \\ = (\binom{n + k + 1}{k}) + (\binom{n + k + 1}{k + 1}) \\ = (\binom{n + k + 2}{k + 1}) . \end{aligned}$

Esto termina la inducción.

Existen otras formas de demostrar identidades con coeficientes binomiales, y de hecho una misma identidad se puede mostrar de varias formas. Veamos más técnicas.

Aspectos combinatorios de los coeficientes binomiales

El coeficiente binomial $(\binom{n}{k})$ cuenta la cantidad de subconjuntos de tamaño $k$ de un conjunto de tamaño $n$ . Argumentar esto es relativamente fácil, usando un argumento de doble conteo. Supongamos que dicha cantidad de subconjuntos es igual a $A$ .

Respondamos la pregunta, ¿cuántos vectores de $k$ entradas existen, tales que las entradas son distintas y vienen de un conjunto de $n$ elementos? La pregunta es un poco distinta, pues como tenemos vectores, aquí sí importa el orden de los elementos. Supongamos que la respuesta es $B$ .

Una forma de responder la pregunta es la siguiente. Primero, elegimos cuál subconjunto de tamaño $k$ conformará las entradas. Esto se puede hacer de $A$ formas (que aunque no sepamos cuánto vale, lo podemos usar). Luego, hay que ordenar las $k$ entradas elegidas, que se puede hacer de $k!$ maneras. Así, esto muestra que $B = k! A$ .

Otra forma de responder la pregunta es la siguiente. Elegimos el primer elemento, que se puede hacer de $n$ formas. Luego el segundo, de entre los $n - 1$ restantes, que se puede hacer de $n - 1$ formas. Siguiendo de esta manera, el último de los $k$ hay que elegirlo entre $n - k + 1$ restantes. Así, esta otra forma de contar dice que $B = n \cdot (n - 1) \cdot \dots \cdot (n - k + 1) = \frac{n!}{(n - k)!} .$

Como ambas formas de contar son válidas, tenemos que $k! A = B = \frac{n!}{(n - k)!}$ , de donde $A = \frac{n!}{k! (n - k)!} = (\binom{n}{k})$ .

Hay problemas que de lejos parecen preguntar algo de álgebra, pero que pueden ser interpretados en términos combinatorios para dar una solución.

Problema. Para $n$ un entero positivo, muestra que $\sum_{k = 1}^{n} k (\binom{n}{k}) = n 2^{n - 1} .$

Sugerencia pre-solución. Construye un problema de conteo cuya respuesta se pueda poner tanto en términos del lado izquierdo, como en términos del lado derecho.

Solución. Preguntémonos, ¿de cuántas formas se puede elegir un subconjunto de un conjunto de $n$ elementos en el que uno de sus elementos está pintado de azul?

Por un lado, primero se puede elegir qué elemento va a ser el azul. Hay $n$ formas de hacer esta elección, y ésta forza a que el elemento en azul esté en el subconjunto. Luego, de los $n - 1$ elementos restantes hay que elegir un subconjunto para completar la elección, lo cual se puede hacer de $2^{n - 1}$ formas posibles. Así, una forma de contar da $n 2^{n - 1}$ .

Por otro lado, primero se puede decidir de qué tamaño $k$ va a ser el subconjunto. Como hay un elemento especial, el tamaño $k$ va de $1$ a $n$ . Ya elegido $k$ , hay $(\binom{n}{k})$ formas de elegir cuál será el subconjunto. Ya elegido el subconjunto, hay $k$ formas de elegir cuál será el elemento pintado de azul. Así, otra posible respuesta, también correcta, es $\sum_{k = 1}^{n} k (\binom{n}{k})$ .

Como estamos contando lo mismo con ambas expresiones, concluimos la igualdad del problema.

A este método de resolver problemas se le conoce como contar de dos formas distintas y funciona no sólo con coeficientes binomiales, sino también con cualquier otra expresión algebraica que tenga términos que se puedan interpretar de manera combinatoria. Hay otro ejemplo en el blog, en donde vemos cómo aparecen los números de Fibonacci en el triángulo de Pascal. En esa entrada también hablamos de cómo aparecen los coeficientes binomiales en el triángulo de Pascal.

Coeficientes binomiales y binomio de Newton

La interpretación combinatoria de los coeficientes binomiales nos da una demostración para la fórmula del binomio de Newton, que ya vimos en una entrada anterior. Aquí enunciamos la fómula como recordatorio.

Teorema (binomio de Newton). Para $a$ y $b$ números reales y $n$ un entero no negativo, se tiene que
$\begin{array}{r} (a + b)^{n} = \sum_{j = 0}^{n} (\binom{n}{j}) a^{n - j} b^{j} . \end{array}$

Si en el binomio de Newton ponemos $a = b = 1$ , obtenemos $(\binom{n}{0}) + (\binom{n}{1}) + \dots + (\binom{n}{n}) = (1 + 1)^{n} = 2^{n} .$ Otra forma de probar esta identidad es simplemente notar que tanto la suma de la izquierda como el término de la derecha cuentan la cantidad de subconjuntos de un conjunto de $n$ elementos: la de la izquierda los cuenta por tamaño, y el de la derecha decidiendo para cada elemento si está o no.

Si ponemos $a = 1$ , $b = - 1$ , obtenemos que $(\binom{n}{0}) - (\binom{n}{1}) + \dots + (- 1)^{n} (\binom{n}{n}) = 0,$ o bien $(\binom{n}{0}) + (\binom{n}{2}) + \dots = (\binom{n}{1}) + (\binom{n}{3}) + \dots .$

Se obtienen otras identidades de coeficientes binomiales interesantes si se usan raíces $n$ -ésimas de la unidad, como ya vimos en la entrada de aritmética compleja.

Hay otras formas de usar el binomio de Newton para probar identidades de coeficientes binomiales.

Problema. Muestra que ${(\binom{n}{0})}^{2} + {(\binom{n}{1})}^{2} + \dots + {(\binom{n}{n})}^{2} = (\binom{2 n}{n}) .$

Sugerencia pre-solución. Considera el polinomio $(1 + x)^{2 n}$ .

Solución. Consideremos el polinomio $(1 + x)^{2 n}$ y determinemos el coeficiente de su término $x^{n}$ .

Usando el binomio de Newton directamente, tenemos que $(1 + x)^{2 n} = \sum_{j = 0}^{2 n} (\binom{2 n}{j}) x^{j},$ de modo que el coeficiente de $x^{n}$ es $(\binom{2 n}{n})$ .

Por otro lado, podemos escribir $(1 + x)^{2 n} = (1 + x)^{n} (1 + x)^{n}$ . Usando el binomio de Newton, tenemos $(1 + x)^{n} = \sum_{j = 0}^{n} (\binom{n}{j}) x^{j} .$ Al multiplicar esta expresión consigo misma, los términos que quedan de grado $n$ son cuando, para cada $j$ , elegimos en un paréntesis al término que tiene $x^{j}$ (que tiene coeficiente $(\binom{n}{j})$ ) y en el otro al que tiene a $x^{n - j}$ (que tiene coeficiente $(\binom{n}{n - j})$ ).

De esta forma, el coeficiente del término de grado $n$ es $\sum_{j = 0}^{n} (\binom{n}{j}) (\binom{n}{n - j}) .$ Usando la identidad de simetría, podemos cambiar $(\binom{n}{n - j})$ por $(\binom{n}{j})$ , para obtener $\sum_{j = 0}^{n} {(\binom{n}{j})}^{2} .$ Igualando ambas formas de encontrar el coeficiente, obtenemos la identidad deseada.

Hay otras técnicas que usan herramientas de integrales o derivadas. Vimos un ejemplo de esto en una entrada anterior.

Coeficientes binomiales y teoría de números

El hecho de que los coeficientes binomiales son la respuesta a un problema de conteo, implica que son enteros no negativos. Alternativamente, esto se puede demostrar por inducción usando la identidad de Pascal.

Este hecho nos puede ayudar a resolver problemas de teoría de números. Veamos un ejemplo clásico.

Problema. Muestra que el producto de $n$ enteros consecutivos siempre es divisible entre $n!$ .

Sugerencia pre-solución. Haz una división en casos para ver si se incluye al cero, si son sólo negativos o sólo positivos. Reduce el caso de negativos a positivos y usa notación adecuada para escribir al producto de dichos enteros usando un coeficiente binomial.

Solución. Si alguno de los enteros es $0$ , entonces el producto es $0$ , que es divisible entre cualquier número. Si son $n$ enteros negativos, entonces podemos cambiar el signo a todos y su producto diferirá, quizás, en un factor $- 1$ que no afecta la divisibilidad, y habremos obtenido un problema con $n$ enteros positivos consecutivos. De esta manera, podemos enfocarnos en el caso de $n$ enteros positivos consecutivos.

Llamemos al primero $k + 1$ , para $k \geq 0$ . Los demás son entonces $k + 2, \dots, k + n$ . Su producto es
$\begin{aligned} (k + 1) (k + 2) \dots (k + n) & = \frac{k!}{k!} (k + 1) (k + 2) \dots (k + n) \\ = \frac{(n + k)!}{k!} \\ = n! (\binom{n + k}{k}) . \end{aligned}$

Como $(\binom{n + k}{k})$ es un entero, tenemos que el lado derecho es un múltiplo de $n!$ , como queríamos.

Otro tipo de técnicas hablan de la divisibilidad de un coeficiente binomial. Por ejemplo si tenemos un primo $p$ , sabemos que todos los siguiente coeficientes binomiales son enteros $(\binom{p}{1}), (\binom{p}{2}), \dots, (\binom{p}{p}) .$ Por su expresión en términos de factoriales, todos tienen a $p$ en el numerador, pero no tienen ningún divisor de $p$ distinto de $1$ en el denominador, pues $p$ es primo. Así, todos ellos son enteros divisibles entre $p$ . Eso puede ayudar en problemas como el siguiente.

Problema. Muestra que si $p$ es un número primo, entonces $p^{2}$ divide a $(\binom{2 p}{p}) - 2$ .

Sugerencia pre-solución. Formula un problema equivalente usando un resultado anterior.

Solución. Por un problema anterior, $(\binom{2 p}{p}) = {(\binom{p}{0})}^{2} + {(\binom{p}{1})}^{2} + \dots + {(\binom{p}{p})}^{2} .$

Por la discusión previa, para $j = 1, \dots, p - 1$ tenemos que $p ∣ (\binom{p}{j})$ , así que $p^{2} ∣ {(\binom{p}{j})}^{2}$ . De esta forma, trabajando módulo $2 p$ tenemos $\begin{aligned} (\binom{2 p}{p}) & \equiv {(\binom{p}{0})}^{2} + {(\binom{p}{p})}^{2} \\ \equiv 1 + 1 \equiv 2 (\mod p^{2}) . \end{aligned}$

Esto es justo lo que queríamos mostrar.

Más problemas

Puedes encontrar más problemas de coeficientes binomiales en la sección 5.1 del libro Problem Solving through Problems de Loren Larson.

El blog de Leo

Aprendiendo, creando y compartiendo matemáticas

Seminario de Resolución de Problemas: Coeficientes binomiales

Introducción

Definición algebraica de coeficientes binomiales

Aspectos combinatorios de los coeficientes binomiales

Coeficientes binomiales y binomio de Newton

Coeficientes binomiales y teoría de números

Más problemas

Me gusta esto:

Deja una respuesta Cancelar la respuesta

Introducción

Definición algebraica de coeficientes binomiales

Aspectos combinatorios de los coeficientes binomiales

Coeficientes binomiales y binomio de Newton

Coeficientes binomiales y teoría de números

Más problemas

Comparte esto:

Me gusta esto:

Deja una respuesta Cancelar la respuesta