Combinaciones especiales

En estas notas vamos a introducir la fórmula de pascal y veremos algunas de sus aplicaciones.
Por ejemplo, el triángulo de pascal, también conocido como triángulo de Tartaglia, que es una
forma gráfica de visualizar los números combinatorios. A continuación veremos cómo contar el
número de subconjuntos de un conjunto y finalizaremos mostrando una fórmula para el desarrollo
binomial y su generalización, el desarrollo multinomial.

1. Fórmula de Pascal y triángulo de Pascal

1.1. Fórmula de Pascal
La fórmula de Pascal nos da una fórmula recursiva para calcular los números combinatorios.
Esta fórmula, como veremos más adelante, da lugar a una representación gráfica de los números
combinatorios conocida como el triángulo de Pascal o triángulo de Tartaglia.

Teorema 1. Para todo par de enteros n y k tal que 1 ≤ k ≤ n − 1,

     
n n−1 n−1
= + .
k k−1 k

Demostración. Una forma inmediata para demostrar esta fórmula es aplicando la fórmula para
calcular el número combinatorio y ver que ambos lados de las igualdad coinciden. Nosotros pre-
sentaremos una demostración que permite entender la naturaleza combinatoria de esta identidad.
Consideremos el conjunto S con n elementos. Sea x un elemento de S. Llamemos A al conjunto
formado por los subconjuntos de S con k elementos y que contienen al elemento x y sea B el
conjunto formado por los subconjuntos de S con k elementos y que
no contienen al elemento x.
Notar que la cantidad de subconjuntos de S con k elementos es nk . Por otro lado, dado que un
subconjunto de S con k elementos pertenece exactamente a uno de los conjuntos A o B, se sigue
por el principio aditivo que
 
n
= |A| + |B|.
k
Dado que los subconjuntos de S en A están formados por x y otros k − 1 elementos de S, A tiene
tantos subconjuntos como formas de elegir k − 1 elementos del conjunto S \ {x}, es decir, tiene
n−1

k−1 elementos. Los subconjuntos de S en B están formados por k elementos en S \ {x}, por lo
tanto B tiene tantos elementos como formas de elegir k elementos del conjunto S \ {x}, es decir,
n−1

tiene k elementos. Por lo tanto concluimos que

1
      
n n−1 n−1
= + .
k k−1 k

Para ilustrar la prueba consideremos el siguiente ejemplo. Sean n = 5, k = 3 y S = {x, a, b, c, d}.

Los subconjuntos de S con 3 elementos que están en A son los siguientes 6

{x, a, b}, {x, a, c}, {x, a, d}, {x, b, c}, {x, b, d}, {x, c, d}.
Los subconjuntos de S con 3 elementos que están en B son los siguientes 4

{a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}.

Por otro lado sabemos que hay un total de 53 subconjuntos de S con 3 elementos, luego

 
5
= 6 + 4 = 10.
3

1.2. Triángulo de Pascal

Notemos que esta
fórmula da una forma recursiva para calcular todos los números combina-
n 1
1

torios de la forma k para 1 ≤ k ≤ n − 1 a partir de los valores 0 = 1 y 1 = 1. Veamos cómo
podemos calcular estos números combinatorios para todo 1 ≤ k < n ≤ 4 aplicando la fórmula de
Pascal
     
2 1 1
= + = 1 + 1 = 2,
1 0 1
     
3 2 2
= + = 1 + 2 = 3,
1 0 1
     
3 2 2
= + = 2 + 1 = 3,
2 1 2
     
4 3 3
= + = 1 + 3 = 4,
1 0 1
     
4 3 3
= + = 3 + 3 = 6,
2 1 2
     
4 3 3
= + = 3 + 1 = 4,
3 2 3

Estos números combinatorios se pueden representar de manera gráfica usando un triángulo

como el que vemos a continuación, que se conoce con el nombre de triángulo de Pascal. Dicho
triángulo tiene n + 1 filas indexadas del

0 al n. Y la fila j tiene j + 1 columnas donde la columna i
representa el número combinatorio ij , para j = 0, 1, . . . , n e i = 0, 1, . . . , k, con 0 ≤ k ≤ n.

2
 0

0

1
1

0 1

2
2
2

0 1 2

3
3
3
3

0 1 2 3

4
4
4
4
4

0 1 2 3 4

n

A continuación se muestran los números combinatorios k con 0 ≤ k ≤ n ≤ 6

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

Consideremos el triángulo de Pascal con n + 1 filas, indexadas del 0 al n. En la fila j, con

0 ≤ j ≤ n se tiene en las columnas 0 y j un 1, y la columna i, con 1 ≤ i < j ≤ n − 1, se calcula a
partir de la fila j − 1 usando la fórmula de Pascal, es decir, se coloca el número que se obtiene de
sumar los números que están en la fila j − 1 y las columnas i − 1 e i.

1.3. Cantidad de subconjuntos de un conjunto

Está claro que la cantidad total de subconjuntos de un conjunto con n elementos se puede cal-
cular mediante la suma de la cantidad de subconjuntos con i elementos que tiene dicho subconjunto
para i = 0, 1, 2 . . . , n, es decir,
         
n n n n n
+ + +···+ + ,
0 1 2 n−1 n
donde ni es la cantidad de subconjuntos con i elementos, el caso particular i = 0 ( n0 = 1)

cuenta una vez al conjunto vacío que es subconjunto de todo conjunto.

Estudiemos el problema en un ejemplo concreto.
Ejemplo 1. Ezequiel tiene 15 libros para donar y le dice a Melina que elija los que quiera y se los
lleve a su casa.¿De cuántas maneras distintas puede hacer la elección Melina?

3
 Este problema es equivalente a aquel de contar cuántos subconjuntos tiene un conjunto con
15 elementos. En este caso el conjunto está formado por 15 libros y cada uno de sus subconjuntos
representa una elección distinta de Melina. Etiquetemos los libros usando los símbolos del conjunto
A = {x1 , x2 , . . . , x15 }. A partir de ahora nos referiremos al libro haciendo referencia a la etiqueta del
conjunto A que se le haya asignado. Por cada i = 1, 2, . . . , 15, Melina tiene dos posibles elecciones:
elegir el libro xi o no elegir el libro xi . Se sigue del principio multiplicativo que Melina tiene un
total de 215 posibles elecciones.

Usando la estrategia utilizada en este ejemplo podemos probar la siguiente identidad.

Teorema 2. Para todo n ≥ 0,

       
n n n n
+ + +···+ = 2n .
0 1 2 n
Demostración. La estrategia para demostrar esta igualdad se conoce con el nombre de conteo
doble. Consiste en contar de dos formas distintas la cantidad de elementos de un conjunto. En este
caso aplicaremos esta técnica al conjunto formado por todos los subconjuntos de un conjunto con
n elementos. Sabemos que la cantidad de subconjunos de un conjunto S con n elementos es igual a
         
n n n n n
+ + +···+ + .
0 1 2 n−1 n
Podemos contar también la cantidad de subconjuntos del conjunto S usando la misma estrategia
que en el ejercicio anterior. Sean x1 , x2 , . . . , xn los elementos de S. Por cada subconjunto de S, xi
tiene dos posibilidades: pertencer al subonjunto o no pertenecer, para todo i = 1, 2, . . . , n. Por lo
tanto, por el principio multiplicactivo, hay 2n posibles formas de armar un subconjunto de S. Por
lo tanto ambas cantidades son iguales, es decir,
       
n n n n
+ + +···+ = 2n .
0 1 2 n

El teorema anterior interpretado en términos del triángulo de Pascal se entiende como que la
suma de los elementos de la fila i es igual a 2i . Se deduce de la demostración de este teorema que

Corolario 1. El número de subconjuntos de un subconjunto con n elementos es 2n .

2. Desarrollos binomial y multinomial

2.1. Fórmula para el desarrollo de las potencias de un binomio
La suma de dos símbolos diferentes es llamado un binomio. Por ejemplo x + y es un binomio.
Si multiplicamos, aplicando la propiedad distributiva, a los siguientes tres binomios se obtiene la
siguiente identidad

4
 (a + b) · (c + d) · (e + f ) =
= ace + ac f + ade + ad f + bce + bc f + bde + bd f .

Claramente, cada uno de los términos de este producto se obtiene multiplicando tres símbolos
cada uno de ellos elegidos de un factor distinto. Generalizando el razonamiento anterior se deduce,
a partir del principio multiplicativo, que el desarrollos del producto de n binomios tienen un total
de 2n términos. Veamos qué ocurre ahora si consideramos tres binomios iguales.

(x + y) · (x + y) · (x + y) = (x + y)3
= xxx + xxy + xyx + xyy + yxx + yxy + yyx + yyy
= x3 + 3x2 y + 3xy2 + y3 .

Tratemos de entender qué es lo que sucede en el ejemplo anterior. Como estoy multiplicando
tres veces el mismo binomio ocurre que aparecen términos que son iguales entre si, por ejemplo

xxy = xyx = yxx = x2 y.

Por lo tanto el coeficiente que multiplica a x2 y es igual al número de formas en que puedo elegir
3

x en dos factores e y en un factor. Sabemos que esto puede ser hecho de 2 = 3 formas distintas.
Veamos cómo se puede generalizar este argumento.

Teorema 3. Dado un número natural n entonces

n
 
n n n−k k
(x + y) = ∑ x y.
k=0 k

Demostración. Escribimos (x + y)n como el producto

(x + y)(x + y) · · · (x + y)
de n factores. Desarrollamos completamente este producto, usando la propiedad distributiva y
agrupando los términos que son iguales. Como por cada factor (x + y) elegimos la x o la y en el
desarrollo de (x + y)n , hay un total de 2n términos. A su vez, cada uno de estos términos son igual a
un término de la forma xn−k yk para algún k = 0, 1, . . . , n. Notar que los términos de la forma xn−k yk
se obtienen elgiendo la y en k de los n factores y la x en los restantes n
− k factores. Por lo tanto el
número de veces que aparece xn−k yk en el desarrollo de (x + y)n es nk . Luego
n  
n n n−k k
(x + y) = ∑ x y.
k=0 k

Por ejemplo si queremos desarrollar la potencia cuarta y quinta del binomio (x + y) no tenemos
más que mirar la fila 4 y 5 del triángulo de Tartaglia respectivamente

5
 (x + y)4 = x4 + 4x3 y + 6x2 y2 + 4xy3 + y4 ,
(x + y)5 = x5 + 5x4 y + 10x3 y2 + 10x2 y3 + 5xy4 + y5 .
Note que reemplazando x = 1 e y = 1 en la fórmula del teorema 3 obtenemos una demostración
alternativa del teorema 2. Si, reemplazamos en dicha fórmula x = 1 e y = −1 se obtiene el siguiente
resultado
Teorema 4. Para todo n ≥ 0,
       
n n n n n
− + − · · · + (−1) = 0.
0 1 2 n
Esta fórmula cobrará relevancia, más adelante, cuando estudiemos el principio de inclusión-
exclusión.

2.2. Desarrollo multinomial

Razonando como en el caso del desarrollo de un binomio, si queremos desarrollar (x + y + z)6
tenemos que aplicar la propiedad distributiva al producto de 6 factores

(x + y + z)(x + y + z)(x + y + z)(x + y + z)(x + y + z)(x + y + z).

En este caso los términos van a ser de la forma xi y j zk , donde i + j + k = 6. Por ejemplo, para
contar la cantidad de términos de la forma x3 y2 z deberíamos contar de cuántas formas distintas
podemos elegir x en 3 factores de los 6, y en 2 factores de los 3 restantes y para z queda por elegir
un único factor. Usando el principio multiplicativo se sigue que hay un total de
     
6 3 1 6!
· · =
3 2 1 3! · 2!
de estos términos. El cálculo de este coeficiente se puede hacer observando que hay tantos de
estos términos como palabras de 6 letras con 3 x’s, 2 y’s y una z. A cada elección de exactamente
un símbolo por cada factor le asignamos una palabra de seis letras que tiene en la posición i la letra
correspondiente a la variable elegida en el i-ésimo factor recorriéndolos de izquierda a derecha
para cada i = 1, 2, . . . , 6. Recíprocamente, cada palabra de seis letras formadas con las letras x, y y
z representa el término que se obtiene elgiendo en el i-ésimo factor el símbolo correspondiente a la
letra en la posición i. Por ejemplo al término que se obtiene eligiendo el símbolo x en el primero,
segundo y cuarto factor, el símbolo y en el tercero y sexto factor y el símbolo z en el quinto factor
se representa mediante la palabra xxyxzy. De aquí se deduce que hay tantos términos de la forma
x3 y2 z como palabras de seis letra formadas con tres letras x, dos letras y y una letra z. Esto sabemos
que da un total de
6!
.
3! · 2!
Siguiendo esta línea argumental se puede probar que el coeficiente que multiplica a xi y j zk es
3!
i! j!k! , para todos los enteros i, j, k tales que i + j + k = 3.
El siguiente teorema generaliza este argumento.

6
Teorema 5. Sea n un número natural. Para todo x1 , x2 , . . . , xt ,
n!
(x1 + x2 + · · · + xt )n = ∑ xn1 xn2 · · · xtnt ,
n1 !n2 ! · · · nt ! 1 2
donde el símbolo ∑ indica la suma sobre todos las posibles soluciones en los enteros no nega-
tivos de la ecuación n1 + n2 + · · · + nt = n.

Demostración. Escribimos la expresión (x1 + x2 + · · · + xt )n como el producto de n factores, cada

uno de ellos igual a x1 + x2 + · · · + xt . Desarrollamos el producto de estos n factores aplicando
la propiedad distributiva. Por cada uno de los n factores elegimos uno de los t términos y los
multiplicamos entre si. Como resultado de este desarrollo obtenemos una suma con t n términos
y cada uno de ellos se puede escribir de la forma x1n1 x2n2 · · · xtnt , donde n1 , n2 , . . . , nt son enteros
no negativos tales que n1 + n2 + · · · + nt = n. Notar que cada uno de estos términos se obtienen
eligiendo la veriable xi en ni de los factores, para cada i = 1, 2, . . . ,t. Asignémosle a cada término
de la forma x1n1 x2n2 · · · xtnt la palabra con n letras en el alfabeto de t letras F = {x1 , x2 , . . . , xt }

xi1 xi2 · · · xit ,

que en la posición i j tiene la letra correspondiente a la variable elegida en el factor j cuando se
realizó la propiedad distributiva. Recíprocamente, a cada palabra xi1 xi2 · · · xit cuyas letras forman
parte del alfabeto F le asignamos la expresión

xi1 xi2 · · · xit = x1n1 x2n2 · · · xtni

,
donde ni indica la cantidad de veces que aparece el símbolo xi en la cadena xi1 xi2 · · · xit . Por lo
tanto, se deduce que, el número de veces que aparece el término = x1n1 x2n2 · · · xtni en el desarrollo de
(x1 + x2 + · · · + xt )n es igual al número de permutaciones con repetición de todos los elementos del
multiconjunto {n1 · x1 , . . . , nt · xt }, n = n1 + n2 + · · · + nt . Que sabemos que es
n!
,
n1 !n2 ! . . . nt !
como queríamos probar.
Note que para contar la cantidad de términos que tiene la sumatoria del teorema anterior de-
beríamos ser capaces de responder a la pregunta de cuántas soluciones en los enteros no negativos
tiene la ecuación

n1 + n2 + · · · + nt = n.
Esta pregunta la responderemos en la próxima clase.