A maior rede de estudos do Brasil

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

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

= n, es igual al coeficiente multinomial(
n
n1, n2, . . . , nr−1
)
:=
n!
n1!n2! · · · , nr!
.
Demostración: En efecto, primero distribúyanse los n ob-
jetos en dos conjuntos: el primer conjunto conteniendo n1
objetos, mientras que el segundo conteniendo los restantes
n − n1 objetos. Esto puede hacerse de ( nn1 ) diferentes man-
eras. Luego, para cada una de estas ( nn1 ) maneras, podemos
distribuir los restantes n−n1 objetos en otros dos conjuntos:
el primero de ellos conteniendo n2 objetos, mientras que el
segundo conteniendo los n− n1 − n2 objetos restantes. Esto
puede hacerse de (n−n1n2 ) maneras diferentes. Entonces hemos
encontrado que el número de maneras distintas de distribuir
matemáticos como mecánicos los problemas rećıprocos del análisis, de-
sarrollándose el método de flucciones para la solución de innumerables
problemas geométricos: el problema de la tangente a una curva; el
cálculo de cuadraturas (áreas bajo una curva); etc. Además en esta obra
Newton obtiene representaciones en términos de funciones elementales
de una serie de integrales de ráıces cuadradas de trinomios cuadráticos.
Gran importancia se da en el libro antes citado a la integración de ecua-
ciones diferenciales ordinarias, aśı como a la solución de algunos prob-
lemas del cálculo de variaciones.
Pese a que Leibniz publica sus resultados en 1708, se tiene certeza
que Newton conoćıa del mismo a fines del siglo XVII, lo cual es evidente
de sus otros trabajos cient́ıficos. El libro “Principios Matemáticos de la
Filosof́ıa Natural”, en cuya redacción tardó 20 años, y que salió a la luz
3 años después del de Leibniz, utiliza estos resultados de forma magis-
tral, mostrando su poder, y de paso poniendo en evidencia la enorme
habilidad de Newton con el cálculo infinitesimal.
El aporte de Newton a la matemática no se limita al descubrimiento
del cálculo diferencial e integral. Su obra incluye importantes aportes
24 Caṕıtulo 2. Arreglos, distribuciones, combinaciones . . .
los n objetos en 3 conjuntos, conteniendo respectivamente
n1, n2, y n− n1 − n2 objetos cada uno, está dado por(
n
n1
) (
n− n1
n2
)
=
n!
n1! n2! (n− n1 − n2)!
.
Si continuamos con este razonamiento, obtenemos que para
los r conjuntos, el número de distribuciones es
n!
n1! n2! · · ·nr!
=
(
n
n1, n2, . . . , nr−1
)
,
como se deseaba establecer.
Por ejemplo, una distribución completa de cartas en el
juego del bridge, consiste en distribuir las 52 cartas en 4
conjuntos de 13 cartas cada uno. Por lo tanto, la totalidad
de distribuciones completas de cartas en el bridge es de(
52
13, 13, 13
)
=
52!
13! 13! 13! 13!
≈ 5.36× 1028.
en métodos numéricos, cálculo aproximado de ráıces de ecuaciones al-
gebraicas (el llamado método de Newton), interpolación de polinomios
de grado arbitrario, geometŕıa anaĺıtica (secciones cónicas: clasificación
y definición de curvas de segundo y tercer grados, etc.).
No se puede dejar de mencionar el aporte de Newton a la mecánica.
Partiendo de los trabajos pioneros de Galileo y Huygens, Newton no sólo
resumió todo el conocimiento sobre el movimiento y la fuerza en un sis-
tema deductivo, sino que, después de establecer un reducido número de
leyes de la mecánica (ley de inercia, ley de la acción libre de una fuerza,
ley sobre la igualdad de acción y reacción), logró deducir a partir de
estas leyes todos los demás teoremas de la mecánica. La llamada ley de
la gravitación universal está indivisiblemente ligada al nombre de Isaac
Newton. Además de ser el primero en enunciarla en su forma más gen-
eral, Newton logró apoyarla con todo el conocimiento astronómico de su
época. También son conocidos los trabajos de Newton sobre óptica, tales
como los estudios acerca de la dispersión de la luz, la descomposición de
la luz blanca, la invención del primer telescopio con espejos (1668), los
estudios sobre la interferencia de la luz, y otros.
2.7. Selección simultánea de objetos de varias clases 25
2.7 Selección simultánea
de objetos de varias clases
Proposición 15 Supóngase que tenemos N objetos parti-
cionados en r subcolecciones que contienen N1, N2, . . . , Nr
elementos, respectivamente. Considérese la selección de n ≤
N objetos, de los cuales n1 ≤ N1 deben ser de la primera
subcolección, n2 ≤ N2 de la segunda, y aśı sucesivamente
hasta seleccionar nr ≤ Nr objetos de la última subcolección.
Entonces, el número total de diferentes selecciones es(
N1
n1
) (
N2
n2
)
· · ·
(
Nr
nr
)
.
Demostración: El lector no encontrará ninguna dificultad
para justificar este resultado.
Por ejemplo, el número de manos de póker mediante las
cuales se obtiene un full house (3 aces y 2 reyes) es igual a
(43) (
4
2) = 24.
Otro ejemplo: el número de manos de bridge que con-
tienen exactamente 6 corazones es igual a(
13
6
) (
39
7
)
= 26, 393, 687, 892.
En este último ejemplo, N = 52, N1 = 13, N2 = 39 (el
número de cartas que no son corazones), n1 = 6 (los cora-
zones), n2 = 7 (el resto de las cartas de la mano).
2.8 Combinaciones con repeticiones
¿Cuántas combinaciones con repeticiones podemos formar
con los objetos a, b, c, tomando 4 de ellos a la vez? En
26 Caṕıtulo 2. Arreglos, distribuciones, combinaciones . . .
total 15 combinaciones, las cuales son:
[a, a, a, a] [a, a, a, b] [a, a, a, c] [a, a, b, b] [a, a, b, c]
[a, a, c, c] [a, b, b, b] [a, b, b, c] [a, b, c, c] [a, c, c, c]
[b, b, b, b] [b, b, b, c] [b, b, c, c] [b, c, c, c] [c, c, c, c]
Proposición 16 El número de combinaciones de n objetos
distinguibles, tomando m de ellos a la vez y permitiendo las
repeticiones, es igual a
[n]m
m!
=
(
n+m− 1
m
)
=
(
n+m− 1
n− 1
)
.
Demostración: En efecto, como el lector puede observar,
cada una de las combinaciones con repetición,
[ai1 , ai2 , . . . , aim ],
se puede asociar con una y solo una “palabra” en orden cre-
ciente ai1 ai2 · · · aim , donde las “letras” son los objetos. El re-
sultado es entonces el mismo que el obtenido en la proposición
10, igual a [n]m/m!. La equivalencia de esta cantidad a los
coeficientes binomiales (n+m−1m ) y (
n+m−1
n−1 ) es evidente, de la
definición de estos últimos.
2.9 Selección de objetos no consecutivos
¿Cuántas selecciones distintas de 3 números no consecutivos
pueden hacerse a partir de los 8 d́ıgitos 1, 2, 3, 4, 5, 6, 7, 8,
dispuestos en ese orden? En total tendremos las siguientes
20 selecciones:
1,3,5 1,3,6 1,3,7 1,3,8 1,4,6
1,4,7 1,4,8 1,5,7 1,5,8 1,6,8
2,4,6 2,4,7 2,4,8 2,5,7 2,5,8
2,6,8 3,5,7 3,5,8 3,6,8 4,6,8.
2.9. Selección de objetos no consecutivos 27
Generalizando este problema, hallemos la cantidad de
selecciones distintas F (m, k) de k objetos no consecutivos,
que se puede obtener a partir de m objetos distinguibles
dispuestos en una ĺınea. Encontraremos la manera de aso-
ciar este problema con el conteo de soluciones enteras anal-
izado en la sección 2.3. Consideremos la selección espećıfica,
en la cual p1, p2, . . . , pk son las posiciones de los obje-
tos no consecutivos seleccionados. La restricción de la “no-
consecutividad” nos impone las condiciones pi − pi−1 ≥ 2,
para todo i ∈ {2, 3, . . . , k}. Además tendremos que p1 ≥ 1.
Definimos las k + 1 cantidades x1, x2, . . . , xk, xk+1 me-
diante x1 = p1, xi = pi − pi−1, para cada i ∈ {2, . . . , k}, y
xk+1 = m− pk. Luego, tendremos que
x1 + x2 + · · ·+ xk + xk+1 = m,
con las restricciones x1 ≥ 1, xi ≥ 2, para cada i ∈ {2, . . . , k}
y xk+1 ≥ 0. Aplicando el teorema 12 de la sección 2.3 y luego
de simplificar, obtenemos entonces la fórmula para F (m, k),
como se indica a continuación.
Teorema 17 El número F (m, k) de selecciones de k obje-
tos no consecutivos, a partir de m objetos dispuestos en una
ĺınea, es igual a
F (m, k) =
(
m− k + 1
k
)
.
Otra demostración completamente diferente de este resul-
tado es como sigue. El total F (m, k) de selecciones se puede
separar en dos grupos:
(a) Aquellas selecciones en las cuales el primer objeto ocupa
la primera posición. Los