A maior rede de estudos do Brasil

Grátis
179 pág.
Análise combinatória matemática

Pré-visualização | Página 5 de 30

distintas se puede distribuir m bolas
indistinguibles entre n cajas ordenadas?
Asociemos a cada solución (x1, x2, . . . , xn) de la ecuación
(2.2) con la “palabra” en orden creciente
s1 s2 · · · sn−1, (2.3)
2.3. Número de soluciones de una ecuación 19
donde s1 = x1, s2 = x1 +x2, . . . , sn−1 = x1 +x2 + · · ·+xn−1.
Claramente esta asociación es biuńıvoca, pues a partir de
la “palabra” en orden creciente s1 s2 · · · sn−1 encontramos la
solución (x1, x2, . . . , xn) de la ecuación (2.2) sin ambigüedad,
tomando xn = m−sn−1. De esta forma, hemos transformado
el problema de contar el número de soluciones de la ecuación
(2.2), al problema de contar el número de “palabras” en orden
creciente del tipo (2.3), en las cuales las “palabras” son de
n−1 “letras”, provenientes de un “alfabeto” dem+1 “letras”:
{0, 1, . . . ,m}. Por lo tanto, tendremos el siguiente resultado:
Teorema 11 El número de soluciones enteras y no-negati-
vas de la ecuación x1 + x2 + · · ·+ xn = m es igual a
[m+ 1]n−1
(n− 1)!
=
(
n+m− 1
m
)
=
(
n+m− 1
n− 1
)
.
Este número coincide con la cantidad de maneras distintas
de distribuir m bolas indistinguibles entre n cajas ordenadas.
Una variación a este problema surge al imponer otras
restricciones en las soluciones. Por ejemplo, ¿cuántas solu-
ciones enteras de la ecuación
x1 + x2 + x3 = 17
hay, con la condición que x1 ≥ 1, x2 ≥ 2 y x3 ≥ 3? O en
forma equivalente, ¿de cuántas maneras distintas se puede
distribuir 17 bolas indistinguibles en 3 cajas ordenadas, de
forma tal que al final la primera caja contenga al menos una
bola, la segunda caja al menos dos bolas y la tercera caja al
menos tres bolas?
Podemos contar el número de distribuciones de la sigu-
iente manera: colocamos al principio una bola en la primera
caja, dos bolas en la segunda caja y tres bolas en la tercera
caja. Nos quedan disponibles entonces 11 = 17−6 bolas, que
debemos distribuir sin restricciones entre las tres cajas. Por
20 Caṕıtulo 2. Arreglos, distribuciones, combinaciones . . .
lo tanto, la solución es [11 + 1]3−1/(3− 1)! = (132 ) = 78. En
general, tendremos:
Teorema 12 El número de soluciones enteras de la ecuación
x1+x2+· · ·+xn = m, con las restricciones x1 ≥ a1, x2 ≥ a2,
. . . , xn ≥ an, es igual a(
n+m− a1 − a2 − · · · − an − 1
n− 1
)
.
Este número coincide con la cantidad de maneras distintas
de distribuir m bolas indistinguibles entre n cajas ordenadas,
de forma tal que la caja i-ésima quede con al menos ai bolas,
para cada i ∈ {1, 2, . . . , n}.
2.4 Combinaciones
Una combinación de una colección de objetos dados es cualquier
selección de uno o más de ellos sin considerar el orden en que
se seleccionen. Aśı, por ejemplo, 3 combinaciones diferentes
de los objetos a, b, c, d, tomando 2 objetos a la vez son:
{a, b}, {b, c}, {a, d} (no son las únicas).
Hemos utilizado en el ejemplo anterior la notación de con-
juntos para enfatizar que el orden de los objetos seleccionados
en cada combinación no interesa. Sin embargo, otro tipo de
combinaciones a considerar es aquel en el cual las repeticiones
de objetos son permitidas (combinaciones con repeticiones).
En tal caso no emplearemos la notación de conjunto {· · ·}
para describirlas, sino más bien la notación de corchetes [· · ·].
Por ejemplo, 3 combinaciones diferentes de los objetos a,
b, c, d, permitiendo repeticiones y tomando 2 objetos a la
vez, podŕıan ser: [a, a], [b, d], [c, c] (desde luego no son las
únicas). En esta notación de corchetes tampoco interesa el
orden de los objetos.
2.5. Combinaciones sin repeticiones 21
2.5 Combinaciones sin repeticiones
Proposición 13 Cuando m ≤ n, el número de combina-
ciones sin repeticiones de n objetos distinguibles, tomando
m de ellos a la vez, es igual a(
n
m
)
:=
n!
m! (n−m)!
=
[n]m
m!
. (2.4)
Demostración: En efecto, recordemos que la proposición 5
establece que existen [n]m permutaciones (sin reemplazo) de
los n objetos, tomando m de ellos a la vez. Ahora, una per-
mutación espećıfica, digamos i1 i2 · · · im, establece una y sólo
una combinación de las estudiadas, a saber: {i1, i2, . . . , im}.
Por otra parte, una combinación espećıfica sin repeticiones
de los n objetos, tomando m de ellos a la vez, digamos
{i1, i2, . . . , im}, establece m! diferentes permutaciones, cuales
son i1 i2 · · · im y todas las otras permutaciones obtenidas de
ésta al permutar los m objetos. En consecuencia, el número
de combinaciones buscado será [n]m/m! = ( nm).
Los números ( nm) son llamados coeficientes binomiales en
virtud de la conocida fórmula del binomio de Newton1, anal-
izada en el caṕıtulo siguiente. En general el coeficiente bino-
mial ( nm) se define como 0 cuando m > n o cuando m < 0.
1Isaac Newton (1643–1727) F́ısico, mecánico, astrónomo y
matemático inglés, nacido en Bullstorp. Miembro de la Real Sociedad de
Londres (1672), presidente de la misma (1703), miembro de la Academia
de Ciencias de Paŕıs (1699). De 1661 hasta 1665 estudia en la Univer-
sidad de Cambridge. Reconocido como uno de los grandes genios de
su época, fue sepultado en la Abad́ıa de Westminster. Ocupó algunos
puestos públicos, entre ellos el de Director de la Casa de la Moneda de
Londres.
La obra cient́ıfica de Newton debe considerarse como uno de los pun-
tos de viraje que marcan el paso del Renacimiento a la época contem-
poránea. En el siglo XVII uno de los problemas centrales de la ciencia
consist́ıa en hallar las leyes del movimiento, aśı como el establecer las
leyes de la mecánica. Para la solución de este problema, el aparato
matemático de la época resultaba claramente insuficiente.
22 Caṕıtulo 2. Arreglos, distribuciones, combinaciones . . .
El lector puede observar que los coeficientes multinomiales
(estudiados también en el caṕıtulo siguiente) coinciden con
los coeficientes binomiales cuando solamente hay r = 2 clases
distintas. En efecto, de la definición de ambos números, ten-
emos que (
n
m1,m2, . . . ,mr−1
)
=
(
n
m1
)
,
cuando r = 2. Estudiaremos algunas propiedades de los coe-
ficientes binomiales y multinomiales en el caṕıtulo siguiente.
Como ejemplos de las combinaciones sin repeticiones, el
número de diferentes manos de póker (5 cartas cualquiera de
un mazo ordinario de 52 cartas) es(
52
5
)
=
52!
5! 47!
= 2, 598, 960,
mientras que el número de diferentes manos de bridge (13
cartas cualquiera de un mazo ordinario de 52 cartas) es(
52
13
)
=
52!
13! 39!
= 635, 013, 559, 600.
El mérito de Newton consiste en que independientemente de Leibniz
construye el cálculo diferencial e integral, que permite la solución de los
problemas antes citados. A diferencia de Leibniz, Newton llega a sus
descubrimientos partiendo de los problemas concretos de la mecánica y
la f́ısica, en lugar de partir de problemas de ı́ndole abstracto. La es-
trecha relación entre la f́ısica y la matemática se percibe claramente en
su método de “flucciones”. Este método, que Newton desarrolla para la
solución de problemas de mecánica, se basa en los trabajos de Cavalieri,
Roberval, Fermat, Wallis, y su maestro y tutor Barrow. Este trabajo
coincide en el tiempo con su descubrimiento del carácter rećıproco de
las operaciones de diferenciación e integración, aśı como descubrimientos
fundamentales de la teoŕıa de series infinitas, acerca del llamado binomio
de Newton para exponentes arbitrarios, sobre la aproximación de fun-
ciones trascendentes por medio de series infinitas, sobre k-inversión de
series, etc.
En los años 1670–1671 Newton describe sus resultados acerca del
cálculo diferencial e integral en su libro “El método de las flucciones”
(publicado hasta 1736). En esta obra se describen en términos tanto
2.6. Distribución de objetos en varios subconjuntos 23
2.6 Distribución de objetos
en varios subconjuntos
Proposición 14 El número de maneras de distribuir n ob-
jetos distinguibles en r conjuntos, de manera que el con-
junto i-ésimo contenga ni de los objetos, (1 ≤ i ≤ r), con
n1 + n2 + · · ·+ nr