A maior rede de estudos do Brasil

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

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

distinguibles en tres grupos, de forma que en un grupo haya
m objetos, en otro n, y en el tercero p (el orden de los grupos
es indistinguible)?
52. ¿De cuántas formas se puede seleccionar un grupo entre
15 personas para trabajar? En el mismo puede haber 1,
2, . . . , 15 personas. Generalice el problema, para el caso en
que haya que seleccionar entre n personas.
53. Sean p1, . . . , pn números primos diferentes. ¿Cuántos
divisores tiene el número q = pα11 · · · pαnn , siendo α1, . . . , αn
números naturales? ¿A qué es igual la suma de estos divi-
sores?
54. 30 personas votan por 5 mociones. ¿De cuántas formas
se puede distribuir los votos, si cada una vota por una moción
y si se tiene en cuenta solamente el número de votos que
obtuvo cada una?
55. ¿Cuántas formas existen de seleccionar 12 personas de
entre 17, si dos personas dadas de estas 17 no pueden ser
seleccionadas juntas? Generalice el problema para cuando
tenemos N personas y debemos seleccionar n < N , con la
restricción de que k personas espećıficas no pueden ser selec-
cionadas juntas.
56. El marido tiene 12 conocidos, 5 mujeres y 7 hombres, y
la esposa 7 mujeres y 5 hombres (diferentes a los del marido).
¿De cuántas maneras se puede formar un grupo de 6 hombres
y 6 mujeres, de modo que 6 personas sean invitadas por el
marido y 6 por la esposa?
57. A cada costado de un bote hay que sentar 4 personas.
¿De cuántas maneras se puede seleccionar las 8 personas a
sentar en el bote, si hay 31 candidatos y si además 10 de
34 Caṕıtulo 2. Arreglos, distribuciones, combinaciones . . .
ellos quieren sentarse en el costado izquierdo del bote, 12 en
el costado derecho y a los restantes 9 les es indiferente dónde
sentarse?
58. Una persona tiene 6 amigos y durante cada fin de semana
invita a su casa a 3 de ellos, de modo tal que el grupo no se
repita ni una sola vez. ¿De cuántas maneras puede hacerlo?
59. Un coro está formado por 10 participantes. ¿De cuántas
maneras se puede seleccionar 6 participantes durante tres
d́ıas, de forma que cada d́ıa el coro tenga distinta composición?
Generalice el problema al caso en que el coro tiene N partic-
ipantes y se seleccionan n de ellos durante tres d́ıas.
60. De cuántas maneras se puede formar palabras a partir
de 9 consonantes y 7 vocales, en las que figuren 4 conso-
nantes distintas y 3 vocales diferentes? ¿En cuántas de estas
palabras no habrá dos consonantes juntas?
61. ¿Cuántas palabras que contengan cinco letras cada una
se puede formar con 26 letras distintas, si se admiten repeti-
ciones, pero no puede haber en la palabra formada dos le-
tras vecinas que coincidan, es decir, si palabras tales como
“llama” o “perro” no se admiten? Generalice el problema
para el caso en que tenemos N letras distintas y las palabras
son de largo n, con las mismas condiciones.
62. Un grupo formado por 10 parejas de casados se divide en
5 grupos de 4 personas para un paseo en bote. ¿De cuántas
formas se las puede dividir, de manera que en cada bote haya
dos hombres y dos mujeres?
63. En el problema anterior, ¿en cuántos casos un hombre
dado quedará en el mismo bote que su esposa? ¿En cuántos
casos dos hombres quedarán en un solo bote junto con sus
esposas?
Caṕıtulo 3
Coeficientes binomiales
y multinomiales
Hemos visto que la solución de muchos problemas com-
binatorios involucra los coeficientes binomiales y multinomi-
ales. Por tal razón, analizaremos en este caṕıtulo algunas
de las propiedades más significativas que tienen estos coefi-
cientes, viéndolas desde el punto de vista combinatorio. Al-
gunas otras propiedades son planteadas en los ejercicios.
Primeramente demostraremos el bien conocido teorema
del binomio de Newton. Generalmente, en el primer contacto
que el estudiante tiene con este teorema, la demostración del
mismo se establece por el método de la inducción matemática.
Sin embargo, aqúı demostraremos este importante resultado
empleando argumentos de tipo combinatorio, poniendo en ev-
idencia, de esta forma, algo del poder que tienen las técnicas
combinatorias.
3.1 El binomio de Newton
Proposición 19 (Binomio de Newton)
(x+ y)n =
n∑
k=0
(
n
k
)
xk yn−k. (3.1)
Demostración: En efecto, cada término de la parte derecha
de la fórmula (3.1) es claramente obtenido por la selección
35
36 Caṕıtulo 3. Coeficientes binomiales y multinomiales
reiterada de cada uno de los n factores, ya sea la letra x, o
la letra y. Si seleccionamos la letra x en k de los factores,
tendremos entonces que seleccionar la letra y en los restantes
n − k factores. Luego, claramente, el coeficiente de xk es
justamente el número de maneras en las cuales la letra x
puede ser seleccionada en k de los n factores, que es igual a
(nk ).
Corolario 20 (Subconjuntos del conjunto potencia)
n∑
k=0
(
n
k
)
= 2n.
Demostración: En efecto, al sustituir x = y = 1 en la
fórmula (3.1), se obtiene este resultado de apariencia in-
ocente.
De paso, este corolario puede ser interpretado como una
demostración combinatoria de la proposición 1(c), en la cual
se dice que si A es un conjunto con n elementos, entonces el
conjunto potencia, P(A), tiene 2n elementos.
En efecto, P(A) está compuesto por todos los subconjun-
tos de A, cuyo número total lo podemos contar aśı: el número
de los subconjuntos con cero elementos, más el número de los
subconjuntos con 1 elemento, más el número de los subcon-
juntos con 2 elementos, etc., hasta sumar el número de los
subconjuntos con n elementos. Esta suma es precisamente(
n
0
)
+
(
n
1
)
+ · · ·+
(
n
n
)
= 2n.
Corolario 21
n∑
k=0
(−1)k
(
n
k
)
= 0.
Demostración: En efecto, tómese x = −1 y y = 1 en el
binomio de Newton y la conclusión es inmediata.
3.2. El triángulo de Pascal 37
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
Figura 3.1: Triángulo de Pascal.
3.2 El triángulo de Pascal
Otro resultado familiar al estudiante, que derivaremos a con-
tinuación, es la identidad del Triángulo de Pascal1. Esto es,
los coeficientes binomiales de ı́ndice superior n+1 pueden ser
obtenidos de la suma de cada par de coeficientes binomiales
adyacentes de ı́ndice superior n. Expresamos este hecho a
través del conocido triángulo de Pascal, como se ilustra en la
1Blaise Pascal (1623–1662) Matemático, f́ısico e inventor francés,
nacido en Clermont, Auvergne. Fue el tercer hijo y único varón de
una familia cuya madre murió cuando Pascal teńıa solamente tres años
de edad. En 1632 su familia se mudó a Paŕıs. Su padre teńıa puntos
de vista poco ortodoxos con respecto a la educación de sus hijos y de-
cidió enseñarles él mismo. Además le prohibió a Pascal que estudiara
matemática antes de cumplir los 15 años. De esa forma, todos los textos
de matemática fueron sacados de la casa. Sin embargo, la curiosidad de
Pascal pudo más que la intransigencia de su padre y empezó un trabajo
de geometŕıa a la edad de 12 años, descubriendo que la suma de los
ángulos de un triángulo es igual a dos ángulos rectos. Cuando su padre
se dio cuenta de la habilidad de su hijo, se ablandó un poco y le permitió
leer una copia de Los Elementos de Euclides.
A la edad de 14 años Pascal comenzó a acompañar a su padre a
los encuentros con Mersenne, un predicador que pertenećıa a la orden
religiosa de los Minims, cuya morada era punto de reunión frecuentado
por personalidades tales como Gassendi, Roberval, Carcavi, Auzout,
Mydorge, Mylon, Desargues y otros. Pronto, Pascal admiró el trabajo
de Desargues. A la edad de 16 años presentó un pequeño estudio en
una de las reuniones de Mersenne, con algunos teoremas de geometŕıa
proyectiva, entre ellos el hexágono mı́stico de Pascal .
38 Caṕıtulo 3. Coeficientes binomiales y multinomiales
Figura 3.1.
Formalmente, expresamos lo anterior mediante (n+1k ) =
(nk ) + (
n
k−1), resultado que pasaremos a establecer desde el
punto de vista combinatorio (desde luego que esta sencilla
fórmula puede ser fácilmente demostrada mediante manipu-
laciones algebraicas