Embed Size (px)
Citation preview
Apuntes de Matematica Discreta
5. Combinaciones. Teorema del Binomio
Francisco Jose Gonzalez Gutierrez
Cadiz, Octubre de 2004
Universidad de Cadiz Departamento de Matematicas
ii
Leccion 5
Combinaciones. Teorema delBinomio
Contenido5.1 Combinaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
5.1.1 Definicion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
5.1.2 Formacion y numero de combinaciones . . . . . . . . . . . . . . . . . . . . . . . 106
5.2 Teorema del Binomio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
5.2.1 Proposicion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
5.2.2 Formula de Pascal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
5.2.3 Triangulo de Pascal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
5.3 Combinaciones con Repeticion . . . . . . . . . . . . . . . . . . . . . . . . . . 121
5.3.1 Definicion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
5.3.2 Numero de combinaciones con repeticion . . . . . . . . . . . . . . . . . . . . . . 123
Los elementos a combinar en estas cuestiones no tienen maspropiedades que su diversidad. No tienen valor o capacidad ar-itmeticos, salvo que se pueden contar. No se puede operar conellos, sumarlos o restarlos, multiplicarlos o dividirlos. Simple-mente, se pueden combinar.
Thomas Kirkman (1857)
5.1 Combinaciones
Supongamos que disponemos de una baraja de 52 cartas. ¿Cuantas manos de cinco cartas diferentespueden obtenerse de dicha baraja?
Supongamos calculadas todas las ordenaciones posibles de las 52 cartas de la baraja. Tendrıamos P52
ordenaciones distintas. Parece que si elegimos cinco cartas cualesquiera en cada una de las ordenaciones(las mismas en cada ordenacion), el problema estarıa resuelto. Sin embargo, no es ası, ya que por ejemplodos de los grupos elegidos podrıan ser
a1a2a3a4a5 y a1a3a4a2a5
pero estas dos manos son iguales desde el punto de vista que se plantea la pregunta, es decir, el ordenen que nos den las cinco cartas es irrelevante. Entre las P52 ordenaciones habra P5 que seran iguales.
105
Universidad de Cadiz Departamento de Matematicas
Ademas cada una de ellas estara repetida P52−5 veces, luego por la regla del producto, dentro de las P52
ordenaciones habra un total de P5 ·P(52−5) ordenaciones iguales. Ası pues, el numero de manos distintas,M , por el numero de veces que se repite cada una sera igual al total de ordenaciones posibles de las 52cartas, es decir,
M · P5 · P52−5 = P52
de aquı que
M =P52
P5 · P(52−5)=
52!5! · (52− 5)!
sea el numero de manos diferentes de cinco cartas que pueden obtenerse. La nueva situacion nos situaante la definicion de combinacion que ahora veremos.
5.1.1 Definicion
Dada una coleccion de m objetos a1, a2, . . . , am−1, am distintos y un numero entero positivo n 6 m,llamaremos combinacion de orden n a cualquier subcoleccion, a1, a2, . . . , an de n objetos de la colecciondada.
Dos combinaciones seran distintas si algun o algunos elementos de uno de los grupos no se encuentra enel otro, es decir, si difieren en algun o algunos elementos.
5.1.2 Formacion y numero de combinaciones
Al numero de combinaciones de orden n de una coleccion de m objetos, lo designaremos por Cm,n ydiremos que es el numero de combinaciones de m elementos tomados n a n. Su numero es
Cm,n =m!
n!(m− n)!
Demostracion
Procederemos por induccion para formar las combinaciones de m elementos tomados n a n y calcular sunumero.
Paso basico. Para n = 1, las combinaciones de orden 1, seran:
a1 a2 a3 . . . . . . an
para n = 2, obtendremos las combinaciones de orden dos de m elementos. Estas podran obtenerseanadiendo a cada combinacion de orden 1 los elementos que le siguen, uno a uno, es decir,
a1a2 a1a3 a1a4 · · · · · · a1an
a2a3 a2a4 · · · · · · a2an
a3a4 · · · · · · a3an
...
an−1an
Supuestas formadas las de orden n − 1, de modo que en cada una aparezcan los ındices ordenados demenor a mayor, las combinaciones de orden n, se obtienen anadiendo a cada combinacion de orden n− 1cada uno de los elementos posteriores al ultimo de los que en ella figuren.
De esta forma, todas las combinaciones n-arias ası formadas son distintas, bien porque proceden decombinaciones de orden n− 1, o bien, por tener diferente el ultimo elemento.
106
Matematica Discreta Francisco Jose Gonzalez Gutierrez
Ademas se obtienen todas las posibles, pues si faltara alguna, separando en una cualquiera de ellas elultimo elemento nos quedarıa una combinacion de orden n− 1 que no habrıa figurado entre las que noshabıan servido de partida de orden n− 1 en contra de la hipotesis.
Calculemos ahora el numero de combinaciones.
Supongamos formadas todas las combinaciones de orden n de m elementos, es decir, Cm,n. Si en cadacombinacion permutamos de todos los modos posibles los n elementos que figuran en ella, obtendrıamostodas las variaciones posibles de esos m elementos tomados n a n. Ası pues, cada combinacion da lugara Pn variaciones, por tanto,
Vm,n = Cm,n · Pn =⇒ Cm,n =Vm,n
Pn=
m!(m−n)!
n!=
m!n!(m− n)!
Al numero resultante se le llama numero combinatorio y se nota en la forma(mn
)=
m!n!(m− n)!
Ejemplo 5.1 Se dispone de doce puntos en un plano de tal manera que tres cualesquiera de ellos noestan alineados.
(a) ¿Cuantas rectas determinan dichos puntos?
(b) ¿Cuantas de las rectas anteriores pasan por un determinado punto a?
(c) ¿Cuantos triangulos contienen al punto a como vertice?
Solucion
Recordemos que dos puntos cualesquiera del plano determinan una recta y que un tercer punto, o bienesta alineado con los otros dos, en cuyo caso pertenece a la recta que ambos determinan, o bien no loesta, y en tal caso, determina con los otros puntos, dos rectas, una con cada uno de ellos. Dado quedisponemos de doce puntos y tres cualesquiera de ellos no estan alineados, podremos asegurar que cadados de ellos determinan una recta distinta de las demas.
(a) Supongamos que los puntos son a, b, c, d, e, f, g, h, i, j y k y notemos ad como la recta que determinanlos puntos a y d.
Pues bien, ad y por da son iguales ya que la recta que determinan a y d es la misma que ladeterminada d y a, por tanto el orden en que tomemos los puntos no influye en la recta que ambosdeterminan.
Sin embargo, los puntos a y d determinan una recta distinta de la que determinan d y e que, a suvez, es distinta de la que determinan a y f , por tanto el cambio de algun o algunos puntos influyeen el hecho de que las rectas que determinan sean distintas.
Consecuentemente, las rectas que determinan los doce puntos serıan combinaciones de orden doselegidas entre ellos y
C12,2 =(
122
)=
12!2! · 10!
=11 · 12
2= 66
sera el numero de rectas distintas que hay.
(b) Bastarıa dejar fijo el punto a y trazar una recta a cada uno de los restantes once puntos, luegohabra, en total, once rectas que pasan por dicho punto.
(c) Cada tres puntos no alineados en el plano determinan un triangulo que los tiene como vertices.Dejando fijo el punto a, bastarıa calcular las combinaciones de orden dos de los once puntosrestantes y obtendrıamos
C11,2 =(
112
)=
11!2! · 9!
=10 · 11
2= 55
107
Universidad de Cadiz Departamento de Matematicas
triangulos diferentes que tienen al punto a como uno de sus vertices. �
Ejemplo 5.2 Un estudiante tiene que responder siete preguntas de un cuestionario de diez. ¿de cuantasformas puede hacer su eleccion si
(a) no hay restricciones?
(b) debe responder a las dos primeras preguntas?
(c) debe responder, como mınimo, a tres preguntas de las cinco primeras?
Solucion
Supongamos que las diez preguntas son:
p1, p2, p3, p4, p5, p6, p7, p8, p9, p10
y elegimos un grupo cualquiera de siete de ellas,
p1p3p5p7p8p9p10
es claro que si cambiamos el orden entre ellas el grupo elegido es el mismo, sin embargo si cambiamosalguna o algunas preguntas, el grupo es distinto, por tanto los grupos de siete preguntas seran combina-ciones de orden siete elegidas entre las diez del cuestionario.
(a) Al no haber ningun tipo de restricciones la eleccion podra hacerse de
C10,7 =(
107
)=
10!7! · 3!
= 120
formas distintas.
(b) Si el estudiante debe responder a las dos primeras preguntas, hallamos todos los grupos distintosde cinco preguntas que pueden elegirse entre las ocho restantes y a cada uno de ellos le anadimoslas dos primeras. Por tanto, la eleccion puede hacerse de
C8,5 =(
85
)=
8!5! · 3!
= 56
formas distintas.
(c) El estudiante debe responder, como mınimo, a tres preguntas de entre las cinco primeras.
Hallamos todos los grupos distintos de k preguntas, con k = 3, 4 o 5 que pueden elegirse entrelas cinco primeras y para cada uno de ellos elegimos 7 − k preguntas entre las cinco restantes. Elnumero total de formas distintas de hacer la eleccion sera, por tanto,
5∑k=3
C5,k · C5,7−k =5∑
k=3
(5k
)·(
57− k
)
=(
53
)·(
54
)+
(54
)·(
53
)+
(55
)·(
52
)
= 11 ·(
52
)
= 11 · 5!2! · 3!
= 110
�
108
Matematica Discreta Francisco Jose Gonzalez Gutierrez
Ejemplo 5.3 Para hacer un apuesta de la Loterıa Primitiva hay que marcar seis numeros elegidosentre el 1 y el 49. ¿De cuantas formas diferentes puede marcar una persona 6, 5, 4 o 3 numeros?
Solucion
Supongamos que marcamos los numeros 2, 3, 5, 7, 11 y 13 en este orden. Si los hubieramos marcadoen cualquier otro orden la apuesta serıa la misma. Sin embargo, cambiando algun o algunos numeros deestos por otros, tendrıamos una apuesta distinta.
Por tanto, las apuestas que pueden hacerse seran combinaciones de orden seis elegidas entre los cuarentay nueve numeros disponibles.
♦ Marcando seis numeros, el resultado sera
C49,6 =(
496
)=
49!6! · (49− 6)!
=44 · 45 · 46 · 47 · 48 · 49
2 · 3 · 4 · 5 · 6= 13.983.816
formas diferentes.
♦ Cinco numeros se podran marcar de
C49,5 =(
495
)=
49!5! · (49− 5)!
=45 · 46 · 47 · 48 · 49
2 · 3 · 4 · 5= 1.906.884
formas diferentes.
♦ Analogamente, cuatro numeros se podran marcar de
C49,4 =(
494
)=
49!4! · (49− 4)!
=46 · 47 · 48 · 49
2 · 3 · 4= 211876
formas distintas.
♦ Finalmente, podremos marcar tres numeros de
C49,3 =(
493
)=
49!3! · (49− 3)!
=47 · 48 · 49
2 · 3= 18424
formas diferentes. �
Ejemplo 5.4 Demostrar que si n es un numero entero positivo, entonces
C2n,n + C2n,n−1 =12C2n+2,n+1
Solucion
109
Universidad de Cadiz Departamento de Matematicas
C2n,n + C2n,n−1 =(
2nn
)+
(2n
n− 1
)=
2n!n! · n!
+2n!
(n− 1)! · (n + 1)!
=2n! · (n + 1)n! · (n + 1)!
+2n! · n
n! · (n + 1)!
=2n! · (2n + 1)n! · (n + 1)!
=(2n + 1)!
n! · (n + 1)!
=(2n + 1)! · (2n + 2)
(2n + 2) · n! · (n + 1)!
=12· (2n + 2)!(n + 1)! · (n + 1)!
=12
(2n + 2n + 1
)=
12C2n+2,n+1
�
Ejemplo 5.5 Se quiere elegir un comite de doce personas de un grupo formado por diez hombres ydiez mujeres. Decir de cuantas formas puede hacerse la eleccion
(a) Si no hay restricciones.
(b) Si debe haber 6 hombres y 6 mujeres.
(c) Si debe haber un numero par de mujeres.
(d) Si debe haber 8 hombres como mınimo.
Solucion
Se quieren elegir doce personas de entre las veinte que forman el grupo. Obviamente, el orden en el que seelijan no influye en la composicion del comite, aunque este si varıa cuando cambiamos alguna o algunaspersonas. Se trata, por tanto, de combinaciones de orden doce escogidas de entre las veinte personas.
(a) Si no hay restricciones, quiere decir que la composicion del comite puede ser cualquiera, luego laeleccion puede hacerse de
C20,12 =(
2012
)=
20!12! · 8!
= 125970
(b) Si en el comite debe haber seis hombres y seis mujeres, elegimos seis hombres de entre los diezque hay en el grupo y para cada uno de ellos se eligen seis mujeres de entre las diez que hay en elmismo.
Los seis hombres pueden elegirse de C10,6 formas distintas y para cada una de estas combinacioneshabra C10,6 formas distintas de elegir a las mujeres, consecuentemente, por la regla del producto, laeleccion del comite podra hacerse de
C10,6 · C10,6 =(
106
)·(
106
)=
10!6! · 4!
· 10!6! · 4!
= 210 · 210 = 44100
110
Matematica Discreta Francisco Jose Gonzalez Gutierrez
formas distintas.
(c) Si debe haber un numero par de mujeres, entonces podemos representar su numero en el comitepor 2k y el numero de hombres por 12− 2k, donde k = 1, 2, 3, 4, 5.Razonando igual que en el apartado (b), para cada k tendremos C10,2k · C10,12−2k comites con unnumero par de mujeres, por tanto el numero total de formas de hacer la eleccion sera
5∑k=1
C10,2k · C10,12−2k =5∑
k=1
(102k
)·(
1012− 2k
)
=(
102
)·(
1010
)+
(104
)·(
108
)+
(66
)·(
66
)+(
108
)·(
104
)+
(1010
)·(
102
)= 45 · 1 + 210 · 45 + 210 · 210 + 45 · 210 + 45 · 1
= 63090
(d) Sea k el numero de hombres que integran el comite, entonces k = 8, 9 o 10, siendo el de mujeres12− k, razonando igual que en el apartado anterior, habra
10∑k=8
C10,k · C10,12−k =(
108
)·(
104
)+
(109
)·(
103
)+
(1010
)·(
102
)= 10695
formas distintas de hacer la eleccion. �
Ejemplo 5.6 Un comite de seleccion entrevista a cinco candidatos para un puesto de trabajo, entre-gando al final una lista con las personas que propone. Decir cuantas listas distintas puede entregar elcomite en los casos siguientes:
(a) La lista ordena a los candidatos del uno al cinco.
(b) El comite selecciona un primer candidato, un segundo y un tercero.
(c) El comite decide proponer a un candidato para el puesto y seleccionar un grupo de dos suplentes.
Solucion
(a) El numero de listas, en estas condiciones, coincide con el numero de formas de ordenar un conjuntocon cinco elementos, por tanto, habra
P5 = 1 · 2 · 3 · 4 · 5 = 120
listas distintas.
(b) Si el comite selecciona un primer candidato, un segundo y un tercero, entonces es como seleccionarordenadamente tres personas de entre un grupo de cinco, por tanto, el numero de listas distintases, en este caso,
V5,3 = 5 · 4 · 3 = 60
(c) Proponemos cualquiera de los cinco candidatos para el puesto y nos quedarıan cinco personas paraelegir a los dos suplentes. Dado que no importa el orden de estos, las distintas formas de elegirlosserıan combinaciones de orden dos elegidas entre las cuatro personas que restan. Por la regla delproducto, el numero de listas distintas es
5 · C4,2 = 5 ·(
42
)= 5 · 4!
2! · 2!= 30
�
111
Universidad de Cadiz Departamento de Matematicas
5.2 Teorema del Binomio
Si n es un numero entero positivo, entonces,
(a + b)n =n∑
k=0
(nk
)akbn−k
Demostracion
Observemos lo siguiente:
(a + b)2 = (a + b)(a + b) = a · a + a · b + b · a + b · b
donde hemos multiplicado el primer sumando (la a) del primer factor (a + b) por los dos del segundo yluego el segundo sumando (la b) del primer factor por los dos del segundo. De esta forma vemos queen cada uno de los cuatro sumandos que configuran el resultado figura uno, y solo un elemento de cadafactor. El siguiente diagrama resume la situacion.
a•
b•
•aa2
• bab
•aba
• bb2
(a + b)2 = a2 + 2ab + b2
Procediendo de forma identica,
(a + b)3 = (a + b)(a + b)(a + b) = a · a · a + a · a · b + a · b · a + a · b · b + b · a · a + b · a · b + b · b · a + b · b · b
y un diagrama similar al anterior serıa,
a•
b•
a•
b•
a•
b•
a •a3
•a2b
b a •a2b
b•ab2
a •a2b
b•ab2
a •ab2
•b3
b
(a + b)3 = a3 + 3a2b + 3ab2 + b3
112
Matematica Discreta Francisco Jose Gonzalez Gutierrez
y el siguiente arbol nos permitirıa escribir el desarrollo de (a + b)4.
a•
b•
a•
b•
a•
b•
a• •b a• •b a• •b a• •b
a•a4
•ba3b
a•a3b
•ba2b2
a•a3b
•a2b2
b a•a2b2
•ab3
b a•a3b
•a2b2
b a•a2b2
•ab3
b a•a2b2
•ab3
b a•ab3
•b4
b
(a + b)4 = a4 + 6a2b2 + 4ab3 + b4
Observese que al elegir una letra, y solo una (la a o la b), de cada factor, todos y cada uno de los factoresresultantes han de tener el mismo numero de letras, dos en (a + b)2, tres en (a + b)3, cuatro en (a + b)4
y ası sucesivamente. Veamos un ejemplo de lo que decimos e intentemos sacar alguna conclusion.
Supongamos que queremos saber el coeficiente de alguno de los sumandos del desarrollo de (a+b)7. Comohemos visto todos tendran siete letras. Consideremos por ejemplo ababaaa, es decir a5b2 y fijemonosunicamente en las aes. Teniendo en cuenta que cada una de ellas pertenece a un unico factor y llamandoa estos f1, f2, f3, f4, f5, f6 y f7 para calcular todas las opciones posibles, podemos utilizar el siguienteesquema:
a a a a af1 f2 f3 f4 f5
f2 f1 f5 f3 f5
f7 f6 f3 f2 f4
......
......
...
Por lo tanto, el numero de veces que se repetira a5 (y, consecuentemente, a5b2) es igual al numero degrupos de 5 factores que podamos elegir entre los 7 de que disponemos y de tal forma que el orden noinfluye en el hecho de que dos grupos sean distintos, es decir, el coeficiente de a5b2 en el desarrollo de(a + b)7 es C7,5.
Un razonamiento identico nos permite decir que el coeficiente de a3b4 en el mismo desarrollo es C7,3, yası podemos calcular los coeficientes de todos los sumandos.
Este mismo razonamiento puede utilizarse para calcular el coeficiente de cualquier sumando en el desar-rollo de (a + b)n. Si k es cualquier numero entero entre 0 y n, el sumando akbn−k tiene la a repetida kveces correspondiendo una, y solo una, a cada factor, luego son grupos de k elementos (factores) elegidosentre n (total de factores) y donde el orden no importa. Por lo tanto su numero es Cn,k.
113
Universidad de Cadiz Departamento de Matematicas
De acuerdo con todo lo expuesto, ya estamos en condiciones de escribir el desarrollo de (a + b)n.
(a + b)n = Cn,0 · a0bn + Cn,1 · a1bn−1 + Cn,2 · a2bn−2 + · · ·+ Cn,n−1 · an−1b + Cn,n · anb0
=(
n0
)a0bn +
(n1
)abn−1 +
(n2
)a2bn−2 + · · ·+
(n
n− 1
)an−1b +
(nn
)anb0
=n∑
k=0
(nk
)akbn−k
�
Nota 5.1 Plantearemos ahora el mismo problema de forma ligeramente distinta. En el calculo quehicimos del coeficiente de a5b2 en el desarrollo de (a + b)7 nos hemos fijado unicamente en las aes. ¿Quepasarıa si nos fijamos tanto en las aes como en las bes? El esquema siguiente refleja la situacion.
f1 f2 f3 f4 f5 f6 f7
a b a a b a ab b a a a a aa a b a b a a...
......
......
......
El numero de productos posibles de la forma a5b2 tal que cada a y cada b este en uno y solo un factorserıa igual al de palabras de siete letras que podamos formar con cinco aes y dos bes o lo que es igualtodas las ordenaciones posibles que puedan hacerse con ellas, es decir, PR5,2
7 .
En general, el numero de productos del tipo akbn−k serıa igual al numero de palabras distintas quepueden escribirse de tal forma que cada una tuviera n veces repetida la a y n− k veces repetida la b, esdecir,
PRk,n−kn =
n!k! · (n− k)!
=(
nk
)Por lo tanto,
(a + b)n = PR0,nn · a0bn + PR1,n−1
n · a1bn−1 + · · ·+ PRn−1,1n · an−1b + PRn,0
n · anb0
=n∑
k=0
PRk,n−kn · akbn−k
=n∑
k=0
n!k! · (n− k)!
· akbn−k
=n∑
k=0
(nk
)akbn−k
�
Ejemplo 5.7 Se lanza una moneda al aire n veces. ¿De cuantas maneras pueden obtenerse una, dos,tres, cuatro, . . . . . ., o n caras?
Solucion
Sea Ak con 1 6 k 6 n el conjunto formado por todos los resultados posibles en los que aparezcan,exactamente, k caras al lanzar la moneda n veces, es decir,
A1 = {(c, x, x, . . . , x), (x, c, x, . . . , x), . . .}
A2 = {(c, c, x, . . . , x), (x, c, c, . . . , x), . . .}...
An = {(c, c, c, . . . , c)}
114
Matematica Discreta Francisco Jose Gonzalez Gutierrez
El conjunto
A1 ∪A2 ∪ · · · ∪An =n⋃
k=1
Ak
estara formado por todos los resultados en los que aparezcan una, dos,. . ., o n caras. Por tanto, el numeropedido es el cardinal de dicho conjunto. Como los Ak son disjuntos dos a dos, por el principio de adicion,∣∣∣∣∣
n⋃k=1
Ak
∣∣∣∣∣ =n∑
k=1
|Ak|
El esquema siguiente nos ayudara a calcular |Ak| para 1 6 k 6 n.
c c c(k· · · c c
1 2 3 · · · k − 1 k2 3 k · · · 1 k − 12 n 3 · · · n− 1 1...
......
. . ....
...
Seran todos los grupos de k lanzamientos que podamos elegir entre los n, de tal forma que el orden noinfluye en el hecho de que dos grupos sean distintos (observese que las dos primeras filas de la tablaanterior significan lo mismo aunque esten en distinto orden). Por lo tanto,
|Ak| = Cn,k.
De aquı que ∣∣∣∣∣n⋃
k=1
Ak
∣∣∣∣∣ =n∑
k=1
|Ak|
=n∑
k=1
Cn,k
=n∑
k=1
(nk
)
=n∑
k=0
(nk
)1k · 1n−k −
(n0
)= 2n − 1
Ejemplo 5.8 ¿De cuantas maneras puede elegir un profesor a uno o mas estudiantes entre seis?
Solucion
Sean a, b, c, d, e y f los seis estudiantes y supongamos que el profesor elige a un grupo de tres, abc. Esobvio que el orden en que los escoja no influye en el grupo elegido, sin embargo el cambio de algun oalgunos estudiantes si influye ya que los grupos abc y ade son distintos.
Por tanto, las formas de elegir los estudiantes seran combinaciones de orden k seleccionadas de entre losseis estudiantes, siendo 1 6 k 6 6, por tanto el profesor dispone de6∑
k=1
C6,k =6∑
k=1
(6k
)=
6∑k=0
(6k
)−
(60
)=
6∑k=0
(6k
)1k16−k −
(60
)= (1 + 1)6 − 1 = 26 − 1 = 63
maneras distintas de elegir a uno o mas estudiantes entre seis. �
Ejemplo 5.9 Para elaborar una pizza podemos utilizar, ademas de queso y tomate, los siguientesingredientes: carne, champinones, pimientos, cebolla, salami y anchoas. Decir cuantas pizzas diferenteses posible elaborar en los casos siguientes:
115
Universidad de Cadiz Departamento de Matematicas
(a) pueden tener desde todos a ningun ingrediente.
(b) tienen al menos, champinones y anchoas.
(c) no tienen ni carne ni salami.
Solucion
Dos pizzas seran distintas cuando en su elaboracion utilicemos, ademas de queso y tomate, diferentesingredientes. El orden en que se utilizan los mismos no es relevante, por tanto las diferentes pizzas serancombinaciones de orden n elegidas entre los seis ingredientes de que se disponen.
(a) Si pueden tener desde todos a ningun ingrediente, entonces n variara entre seis y cero, por tanto,el numero total de pizzas diferentes
6∑n=0
C6,n =6∑
n=0
(6n
)=
6∑n=0
(6n
)1n · 16−n = (1 + 1)6 = 26 = 64
(b) Si han de intervenir en su composicion, champinones y anchoas, entonces le anadimos estos dosingredientes a todas las posibles pizzas que puedan elaborarse con los otros cuatro. El total depizzas diferentes sera, utilizando el mismo razonamiento que en (a),
4∑n=0
C4,n =4∑
n=0
(4n
)=
4∑n=0
(4n
)1n · 14−n = (1 + 1)4 = 24 = 16
(c) Al no tener carne ni salami, el total de pizzas diferentes sera igual al anterior ya que tendrıamoscuatro ingredientes, luego
4∑n=0
C4,n = 16
es el total de pizzas diferentes que no llevan carne ni salami. �
Ejemplo 5.10 ¿Cuantos subconjuntos tiene un conjunto con n elementos?
Solucion
Elegido cualquier subconjunto del conjunto dado, el orden en que esten situados los elementos en elmismo es irrelevante luego dos subconjuntos seran distintos si, y solo sı se diferencian en, al menos, unelemento, de aquı que los subconjuntos con k elementos sean las combinaciones de orden k que puedanelegirse entre los n elementos del conjunto dado, siendo 0 6 k 6 n.
Observese que k = 0 se corresponde con subconjuntos con cero elementos, es decir, el conjunto vacıo.
Pues bien, de acuerdo con este razonamiento, el numero de subconjuntos que tiene un conjunto con nelementos sera
1 +n∑
k=1
Cn,k =(
n0
)+
n∑k=1
(nk
)=
n∑k=0
(nk
)1n1n−k = (1 + 1)n = 2n
�
Ejemplo 5.11 Dado el conjunto A = {1, 2, 3, 4, 5, 6, 7}, determinar el numero de
(a) subconjuntos de A.
(b) subconjuntos no vacıos de A.
116
Matematica Discreta Francisco Jose Gonzalez Gutierrez
(c) subconjuntos de A que contienen tres elementos.
(d) subconjuntos de A que contienen a los elementos 1 y 2.
(e) subconjuntos de A con un numero par de elementos.
(f) subconjuntos de A con un numero impar de elementos y que incluyan al elemento 3.
Solucion
(a) Veamos cuantos subconjuntos tiene A.
Directamente del ejemplo anterior, el numero de subconjuntos que tiene A sera
1 +7∑
k=1
C7,k =(
70
)+
7∑k=1
(7k
)=
7∑k=0
(7k
)1717−k = (1 + 1)7 = 27 = 128
(b) El numero de subconjuntos no vacıos de A se calcula directamente del punto anterior,
128− 1 = 127
es decir, al total le hemos restado uno ya que hay un solo subconjunto vacıo en A. (Se correspondecon k = 0).
(c) El numero de subconjuntos de A que contienen tres elementos tambien se sigue directamente delapartado (a) para k = 3, luego es
C7,3 =(
73
)=
7!3! · 4!
= 35
(d) Para hallar todos los subconjuntos que contienen al 1 y al 2, hallamos todos los subconjuntos de{3, 4, 5, 6, 7} y a cada uno de ellos le anadimos el 1 y el 2. Por tanto, el numero de subconjuntosde este tipo sera
5∑k=0
C5,k =5∑
k=0
(5k
)1515−k = (1 + 1)5 = 25 = 32
(e) Siguiendo el mismo razonamiento que en (a), bastarıa calcular el numero de subconjuntos de Apara k = 2, 4 y 6, es decir habra
C7,2 + C7,4 + C7,6 =(
72
)+
(74
)+
(76
)= 63
subconjuntos de A que tengan un numero par de elementos.
(f) Bastarıa hallar todos los subconjuntos de {1, 2, 4, 5, 6, 7} que tengan cero, dos, cuatro y seis ele-mentos y anadirle a cada uno de ellos el 3, por tanto, habra
1 + C6,2 + C6,4 + C6,6 = 1 +(
62
)+
(64
)+
(66
)= 1 + 2 · 6!
2! · 4!+ 1 = 32
subconjuntos de A con un numero impar de elementos entre los cuales se incluya el 3. �
Ejemplo 5.12 ¿De cuantas formas distintas puede descomponerse el numero 8 como suma de enterospositivos?
Solucion
Una posible descomposicion serıa5 + 2 + 1 = 8
117
Universidad de Cadiz Departamento de Matematicas
que consideraremos distinta de la
1 + 5 + 2 = 8
y otra podrıa ser
7 + 1 = 8
Las descomposiciones mas extremas serıan en un unico sumando
8 = 8
y en ocho sumandos
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 8.
Ası pues habra que calcular cuantas descomposiciones pueden hacerse con 1, 2, 3, 4, 5, 6, 7 y 8 sumandosy luego sumarlas todas. Calcularemos el numero de descomposiciones con k sumandos donde k varıaentre 1 y 8.
El numero de descomposiciones que hay con k sumandos sera igual al numero de soluciones de la ecuacion,
x1 + x2 + · · · · · ·+ xk = 8, 1 6 k 6 8
donde xi > 0, i = 1, 2, . . . , k, ya que si alguna de las xi fuese cero, entonces no habrıa k sumandos sinok − 1. Pues bien,
xi > 0 =⇒ xi > 1 =⇒ xi − 1 > 0
y haciendo yi = xi − 1 y sustituyendo, tendremos que
y1 + 1 + y2 + 1 + · · · · · ·+ yk + 1 = 8
es decir,
y1 + y2 + · · · · · ·+ yk = 8− k, con yi > 0, i = 1, 2, . . . , k
luego el problema se reduce a calcular el numero de soluciones enteras no negativas de la ecuacion anteriorque, como ya sabemos, es
PRk−1,8−kk−1+8−k = PRk−1,8−k
7 , para 1 6 k 6 8
Por lo tanto, el numero total de descomposiciones, sera
8∑k=1
PR8−k,k−17 =
8∑k=1
7!(k − 1)!(8− k)!
=8∑
k=1
(7
k − 1
)
=7∑
k=0
(7k
)
=7∑
k=0
(7k
)1k · 17−k
= (1 + 1)7
= 27
= 128
�
118
Matematica Discreta Francisco Jose Gonzalez Gutierrez
5.2.1 Proposicion
Si n y k son dos numeros enteros no negativos tales que 0 6 k 6 n, entonces,(n + 1
k
)=
(nk
)+
(n
k − 1
)
Demostracion
Sea A un conjunto con n elementos y B un conjunto con un solo elemento, por ejemplo, B = {b} y talque b no pertenezca a A. Entonces, A ∩ B = ∅ y si C = A ∪ B, por el principio de adicion, tendremosque
|C| = |A|+ |B| = n + 1.
Pues bien, sea P el conjunto formado por todos los subconjuntos de C con k elementos, es decir,
P = {X ⊆ C : |X| = k}
y sea X cualquiera de P . Hay dos opciones:
Los k elementos de X son de A, es decir X es un elemento de
Q = {X ⊆ A : |X| = k}
o
los k elementos de X son k − 1 de A y b es elemento que le falta, o sea es un elemento de
R = {X = D ∪B : D ⊆ A, |D| = k − 1} .
Ademas,P = Q ∪R, con Q ∩R = ∅
luego por el principio de adicion,|P | = |Q|+ |R|
pero,|P | = Cn+1,k
|Q| = Cn,k
|R| = Cn,k−1
de aquı queCn+1,k = Cn,k + Cn,k−1
es decir, (n + 1
k
)=
(nk
)+
(n
k − 1
)�
5.2.2 Formula de Pascal
Si n y k son dos enteros positivos tales que 1 6 k 6 n− 1, entonces(nk
)=
(n− 1
k
)+
(n− 1k − 1
)
Demostracion
119
Universidad de Cadiz Departamento de Matematicas
Para obtener la formula de Pascal1, basta sustituir n por n− 1 en la igualdad anterior. �
Ejemplo 5.13 Demostrar la proposicion 5.2.1 efectuando los numeros combinatorios.
Solucion
En efecto, desarrollando los numeros combinatorios del segundo miembro,
(nk
)+
(n
k − 1
)=
n!k!(n− k)!
+n!
(k − 1)!(n− k + 1)!
=n!(n− k + 1) + n!k
k!(n− k + 1)!
=n!(n− k + 1 + k)
k!(n− k + 1)!
=n!(n + 1)
k!(n− k + 1)!
=(n + 1)!
k!(n− k + 1)!
=(
n + 1k
)
�
1Blaise Pascal, matematico, fısico, filosofo y escritor frances (Clermont-Ferrand 1623-Parıs 1662). Hijo de una familia dela alta burguesıa auvernesa, que, en 1631, fijo su residencia en Parıs, donde los medios literarios y cientıficos que frecuentole ayudaron a crear una vocacion precoz. Se dice que su padre trato de mantenerlo, al principio, alejado de los libros dematematicas, con objeto de estimular al joven Blaise a desarrollar otros intereses, pero a la edad de doce anos el muchachodemostraba ya tal grado de inteligencia geometrica que, en adelante, se favorecio su inclinacion matematica. A los catorceanos ya acompanaba a su padre a las reuniones informales de la “Academia de Mersenne” en Parıs. Aquı fue donde sefamiliarizo con las ideas de Desargues, y dos anos mas tarde, en 1640, el joven Pascal publico su Essay pour les coniques.A la edad de dieciocho anos aproximadamente cambio de tema y para ayudar a su padre en un trabajo fiscal, se dedico adisenar una maquina calculadora; en unos pocos anos construyo y vendio unas cincuenta de estas maquinas. Durante estetiempo la familia Pascal entro en relacion con los jansenitas Saint-Cyran y Antoine Arnauld. Durante esta epoca, Pascalcontinuo sus investigaciones y tuvo dos entrevistas con Descartes, pero sin que al parecer pudieran encontrar ambos uncamino de inteligencia comun; sin duda les separaron, entre otras cosas, sus teorıas sobre el vacıo. A continuacion, en 1648,se intereso Pascal en la hidrostatica, y los resultados de sus investigaciones fueron el famoso experimento de Puy-de-Domeque confirmaba el peso del aire, y los experimentos acerca de la presion ejercida por un fluido, que clarificaron la aparenteparadoja hidrostatica. Su padre murio en 1651 y su hermana Jacqueline ingreso en 1652 en el convento de Port-Royal.Entonces Pascal se dedico mas febrilmente a las ciencias. Comenzo a frecuentar algunos amigos, si no libertinos, al menosbastante independientes, el duque de Roannez, Mitton y el caballero de Mere. Fue en esta epoca cuando Pascal, buscandosoluciones a un problema propuesto por Mere, se intereso por el Calculo de Probabilidades. Pascal relaciono el estudio de lasprobabilidades con el triangulo aritmetico, superando en sus discusiones la obra de Cardano en tal medida que la conocidadistribucion triangular de numeros ha venido recibiendo, desde entonces, el nombre de triangulo de Pascal. Durante lanoche del 23 de noviembre de 1654 (del que queda emocionante testimonio en su Memorial), experimento Pascal unaespecie de extasis religioso que lo impulso a abandonar la ciencia y la matematica para dedicarse a la teologıa. Siguiendolos M. Singlin, que tomo como director espiritual en 1655, se retiro a Port-Royal des Champs, donde, sin convertirse enmiembro activo de la abadıa, se dedico a la penitencia. Cuando Arnauld fue amenazado con la condenacion en la Sorbona,Pascal le defendio revelandose como un excepcional polemista. Desde enero de 1656 a marzo de 1657 bajo el seudonimo deMONTALTE publico las dieciocho cartas conocidas con el nombre de Provinciales donde ataca a la Sorbona, a los jesuitasy, sobre todo, los abusos de la casuıstica. Ya solo volverıa a los estudios matematicos durante un breve perıodo de tiempoen 1658-1659. Una noche de 1658 en que un dolor de muelas un otra dolencia le impedıa dormir, decidio, como distraccioncontra el dolor, dedicarse al estudio de la cicloide. Milagrosamente, el dolor ceso, lo que interpreto Pascal como un signo deque el estudio de la matematica no desagradaba a Dios. En 1661 intervino en el drama de conciencia en que se debatıan losjansenitas obligados a firmar la condenacion de Jansenio. La hermana de Pascal (que murio aquel mismo ano) influyo en suhermano para que tomara partido por la intransigencia y ası lo hizo contra los propios maestros jansenitas Arnauld y Nicoleinclinados a firmar. Ante la resistencia que encontro, Pascal se retiro de la lucha, dedicandose desde entonces a una vida depiedad personal. Su obra fundamental quedo incompleta. En el contexto de una integracion de la funcion seno en su Traitedes sinus du quart de cercle, de 1658, Pascal se aproximo extraordinariamente a lo que pudo haber sido el descubrimientodel calculo; tan cerca estuvo de ellos que Leibniz escribirıa mas tarde que fue leyendo esta obra de Pascal cuando se lemostro subitamente la luz. Si Pascal no hubiera muerto poco despues de cumplir 39 anos, o bien si su mentalidad hubierasido mas exclusivamente matematica, no cabe practicamente duda de que se hubiera anticipado a Newton y a Leibniz ensus mas grandes descubrimientos.
120
Matematica Discreta Francisco Jose Gonzalez Gutierrez
5.2.3 Triangulo de Pascal
Con la formula de Pascal puede obtenerse un metodo para el calculo de los coef icientes del desarrollode (a + b)n.
En efecto, si tenemos en cuenta que para cualquier entero no negativo n se verifica que(n0
)=
(nn
)= 1
y los tomamos como valores inicial y final, respectivamente, los coeficientes de las sucesivas potencias de(a + b)n pueden distribuirse en una figura que se conoce como triangulo de Pascal.2(
00
)(
10
) (11
)(
20
) (21
) (22
)(
30
) (31
) (32
) (33
)(
40
) (41
) (42
) (43
) (44
)(
50
) (51
) (52
) (53
) (54
) (55
)que desarrollando los numeros combinatorios, resulta
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Todas y cada una de las filas empiezan y terminan con 1 y cualquier otro numero en el triangulo es sumade los dos que estan encima suya. �
5.3 Combinaciones con Repeticion
Supongamos que disponemos de m objetos a1, a2, . . . , am y que son bocadillos.
Supongamos, tambien, para fijar ideas supongamos que m = 4, es decir, hay cuatro clases distintas debocadillos, por ejemplo a1 es de jamon (j), a2 de chorizo (c), a3 de salchichon (s) y a4 de tortilla (t).
2Figura en el Traite du Triangle Arithmetique publicado por Pascal en 1665. Tambien recibe el nombre de triangulode Yang Hui’s, en honor al matematico chino que lo descubrio en 1261. El matematico Chu Shih-Chieh, tambien chino, loincluye en su libro El espejo precioso de los cuatro elementos de 1303.
121
Universidad de Cadiz Departamento de Matematicas
Supongamos que diez estudiantes de Matematica Discreta entran en la cafeterıa de la Escuela dispuestosa comerse un bocadillo cada uno.
¿De cuantas maneras distintas pueden pedir los bocadillos los estudiantes?
Designaremos con las letras c, j, s y t a los bocadillos de chorizo, jamon, salchichon y tortilla, respectiva-mente. Uno de los pedidos puede ser cccjjstttt que, obviamente, es igual al pedido ccjcstttt y distinto alccjjssttt. El orden, por tanto, es irrelevante y lo unico que hace a dos peticiones distintas es el cambiode algun o algunos elementos entre los que no sean iguales entre sı.
Estamos, pues, ante un problema de combinaciones, aunque los elementos pueden repetirse, luego nopodremos utilizar lo estudiado en el apartado anterior.
Calcularemos este numero con el metodo siguiente: a cada grupo de diez elementos le hacemos corre-sponder otro de catorce elementos escribiendo tantos unos como elementos distintos haya en los grupos,seguidos de tantos ceros como veces se repita el elemento en el mismo.
En nuestro ejemplo, hay cuatro clases de bocadillos que lo supondremos ordenados en la forma csjt,luego habra cuatro unos, ası, la peticion, cjjtttccss se correspondera con el grupo, 10001001001000. Lasiguiente tabla representa alguna de las peticiones y los grupos de ceros y unos correspondientes.
A Bcccjjcjctt 10000011000100
cccjjtttss 10001001001000
ssssjjjjjj 11000010000001
tttttttttt 11110000000000
En la columna A tenemos todas las combinaciones con repeticion de cuatro elementos tomados diez adiez y su numero coincidira con el numero de grupos distintos que haya en la columna B.
Observese que los grupos de la columna B comienzan todos con un uno. Para calcular cuantos gruposhay podemos prescindir de la primera posicion y quedan, por tanto, trece elementos, de los cuales tresson unos y los diez restantes son ceros. Consecuentemente, el numero total de grupos es igual al depermutaciones con repeticion de trece elementos donde hay tres iguales entre sı y distintos a otros diez,tambien iguales entre sı, por tanto, el numero sera
PR3,1013
Ası pues,
CR4,10 = PR3,1013 =
13!3! · 10!
=(4− 1 + 10)!(4− 1)! · 10!
=(
4− 1 + 1010
)= 286
Las combinaciones con repeticion se definen de la misma forma que las combinaciones simples, salvo queahora, no es necesario que todos los elementos sean distintos. Por tanto, dos combinaciones con repeticionseran iguales cuando esten formadas por los mismos elementos repetidos igual numero de veces.
5.3.1 Definicion
Llamaremos combinaciones con repeticion de orden n definidas en un conjunto A con m elementos,a los diferentes grupos de n elementos, iguales o distintos, que pueden formarse con los m elementosdados, de modo que dos grupos sean distintos cuando difieran, al menos, en un elemento.
El orden n de una combinacion con repeticion puede ser mayor que el numero de elementos con los cualesse forma. Cuando n 6 m, entre las combinaciones con repeticion figuran las combinaciones simples delmismo orden.
122
Matematica Discreta Francisco Jose Gonzalez Gutierrez
5.3.2 Numero de combinaciones con repeticion
El numero de combinaciones con repeticion de orden n de una coleccion de m objetos lo simbolizaremospor CRm,n y lo llamaremos combinaciones con repeticion de m elementos tomados n a n. Su valor es
CRm,n =(
m− 1 + nn
)
Demostracion
Disponemos los elementos que forman cada una de las CRm,n (combinaciones con repeticion de melementos a1, a2, . . . , am tomados de n en n) de manera que sus ındices respectivos sigan el orden natural.Entonces, una combinacion generica se puede expresar mediante una sucesion de sımbolos de dos clases,1 y 0 en la forma siguiente:
Para representar el elemento a1 se escribe un uno seguido de tantos ceros como veces se repite dichoelemento en la combinacion considerada; a continuacion se escribe otro uno, que representara el elementoa2 y se le hace seguir de tantos ceros como veces figure dicho elemento en la citada composicion y asısucesivamente, conviniendo que si faltase algun elemento se expresara esta circunstancia escribiendo ununo por cada uno de ellos sin ir seguido de ningun cero.
Por ejemplo, la combinacion de orden tres a1a1a3 elegida entre los cuatro elementos a1, a2, a3, a4 seescribira:
1001101
De este modo cada combinacion que estamos considerando viene representada por una expresion quecomienza por uno y contiene en forma ordenada m veces uno y n veces cero.
Recıprocamente, toda expresion de este tipo representa una de tales combinaciones.
Consecuentemente, para determinar el numero de estas combinaciones lo que haremos es calcular elnumero de expresiones del tipo 100 . . . . . .. Pues bien, el primer sımbolo es uno, luego si lo dejamos fijo,nos queda por disponer en cualquier orden los m− 1 unos restantes y los n ceros, lo cual puede hacersede
Pm−1,nm−1+n
formas distintas. Por tanto,
CRm,n = Pm−1,nm−1+n =
(m− 1 + n)!(m− 1)! · n!
=(
m− 1 + nn
)= Cm−1+n,n
�
Ejemplo 5.14 Se dispone de tres bolsas iguales con caramelos de fresa, de menta y de limon. Cadauna de las bolsas contiene, al menos, diez caramelos. Decir de cuantas formas pueden seleccionarse diezcaramelos en los siguientes casos:
(a) sin ninguna restriccion.
(b) en cada seleccion deben figurar, al menos, un caramelo de fresa, dos de menta y tres de limon.
(c) en cada seleccion han de figurar exactamente, uno de fresa y, al menos, uno de menta.
Solucion
(a) Veamos de cuantas formas pueden seleccionarse diez caramelos si no hay ninguna restriccion.
Una de las posibles distribuciones de los diez caramelos es
ffmflmmfll
123
Universidad de Cadiz Departamento de Matematicas
donde f,m y l representan los sabores fresa, menta y limon, respectivamente. Observamos quesi en esta distribucion elegida al azar, intercambiamos entre sı uno o varios sabores, la misma novarıa, sin embargo si cambiamos uno o varios caramelos por otros de distinto sabor, tendremos unadistribucion diferente, por tanto, las distribuciones de los diez caramelos son combinaciones conrepeticion de orden diez elegidas entre los tres tipos de caramelos distintos. Consecuentemente, losdiez caramelos pueden seleccionarse de
CR3,10 =(
3− 1 + 1010
)=
(1210
)=
12!10! · 2!
= 66
formas distintas.
(b) En cada seleccion fijamos un caramelo de fresa, dos de menta y tres de limon, quedaran, por tanto,cuatro caramelos de entre los tres sabores para elegir, el mismo razonamiento del apartado anteriornos conduce a que el numero de selecciones distintas es
CR3,4 =(
3− 1 + 44
)=
(64
)=
6!4! · 2!
= 15
(c) Ahora fijamos en cada seleccion un caramelo de fresa y uno de menta. Entonces, quedaran porelegir ocho caramelos de entre dos sabores, menta y limon, ya que ha de haber, exactamente, unode fresa en cada seleccion, luego el numero de selecciones distintas es
CR2,8 =(
2− 1 + 88
)=
(98
)=
9!8! · 1!
= 9
�
Ejemplo 5.15 Hallar de cuantas maneras pueden distribuirse cuatro pelotas de golf en diez cajasnumeradas, si
(a) todas las pelotas son diferentes y en ninguna caja cabe mas de una pelota.
(b) las pelotas son indistinguibles y en ninguna caja cabe mas de una pelota.
(c) todas las pelotas son diferentes y en cada caja caben cuantas pelotas se desee.
(d) las pelotas son indistinguibles y en cada caja caben cuantas pelotas se desee.
Solucion
Sean ci para i = 1, 2, 3, 4, 5, 6, 7, 8, 9 y 10 las diez cajas disponibles.
(a) Como las pelotas son diferentes, las distinguiremos con un subındice, es decir, designaremos a laspelotas por p1, p2, p3 y p4.
Fijamos las cuatro pelotas y calculamos el numero de grupos distintos de cuatro cajas que podemoselegir entre las diez. El esquema siguiente nos muestra la situacion.
p1 p2 p3 p4
c1 c2 c3 c4
c1 c2 c4 c3
c1 c2 c5 c6
......
......
El grupo c1c2c3c4 significa, pues, que las pelotas p1, p2, p3 y p4 se asignan a las cajas c1, c2, c3 yc4, respectivamente. El grupo c1c2c4c3 que tiene las mismas cajas que el anterior, significa que lapelota p1 va a al caja c1, la p2 a la c2, la p3 a la c4 y la p4 a la c3, por tanto ambos grupos son
124
Matematica Discreta Francisco Jose Gonzalez Gutierrez
distintos, es decir, el orden el que situemos los elementos en el grupo influye para que estos seandiferentes.
Ademas, el grupo c1c2c5c6 tambien es distinto de los anteriores, luego el cambio de algun o algunoselementos tambien hace distintos a dos grupos.
Consecuentemente, el numero total de grupos distintos que pueden formarse son las variaciones deorden cuatro de diez elementos, de aquı que, en este caso, haya
V10,4 = 10 · 9 · 8 · 7 = 5040
formas diferentes de distribuir las pelotas de golf en las diez cajas.
(b) Al ser iguales las cuatro pelotas, el esquema del apartado anterior podrıa escribirse en la forma:
p p p pc1 c2 c3 c4
c1 c2 c4 c3
c1 c2 c5 c6
......
......
donde hemos eliminado los subındices de las pelotas. Ahora los grupos c1c2c3c4 y c1c2c4c3 soniguales, luego el orden en que se situen los elementos dentro de un grupo es irrelevante. Sinembargo, el grupo c1c2c5c6 es distinto, es decir, el cambio de algun o algunos elementos si hace ados grupos diferentes.
Consecuentemente, el numero total de grupos distintos que pueden formarse son las combinacionesde orden cuatro elegidas entre diez elementos, por tanto, en este caso, hay
C10,4 =(
104
)=
10!4! · 6!
= 210
maneras de distribuir las cuatro pelotas de golf en diez cajas numeradas.
(c) Las pelotas vuelven a ser diferentes. Un esquema de este caso es
p1 p2 p3 p4
c1 c1 c1 c1
c1 c1 c2 c2
c1 c2 c1 c2
......
......
donde el grupo c1c1c1c1 significa que a la caja c1 se le asignan cuatro pelotas y ası con todos los querepitan caja. El razonamiento es identico al del apartado (a) con la salvedad de en que cada cajapodemos introducir cuantas pelotas queramos, por tanto las variaciones de orden cuatro elegidasentre las diez cajas seran con repeticion, es decir, el numero de distribuciones distintas es
V R10,4 = 104 = 10000
(d) Ahora son, otra vez, todas las pelotas iguales. El esquema es,
p p p pc1 c1 c1 c1
c1 c1 c2 c2
c1 c2 c1 c2
......
......
125
Universidad de Cadiz Departamento de Matematicas
Ahora los grupos c1c1c2c2 y c1c2c1c2 son iguales, ya que ambos significan lo mismo, es decir, dospelotas en la caja c1 y otras dos en la caja c2, es decir, el orden es irrelevante.
Sin embargo, los grupos c1c1c1c1 y c1c1c2c2 son distintos ya que el primero significa que en la cajac1 hay cuatro pelotas y el segundo que hay dos pelotas en la caja c1 y otras dos en la c2, por tanto,el cambio de algun o algunos elementos si hace distintos a dos grupos.
Consecuentemente, en este caso, hay
CR10,4 =(
10− 1 + 44
)=
(134
)=
13!4! · 9!
= 715
formas distintas de distribuir las cuatro pelotas en las diez cajas. �
Ejemplo 5.16 Dada la siguiente lista de numeros:
−5,−4,−3,−2,−1, 1, 2, 3, 4
se seleccionan cuatro de ellos.
(a) ¿De cuantas maneras pueden hacerse las selecciones de modo que el producto de los cuatro resultepositivo y
(a.1) los numeros sean distintos?
(a.2) cada numero pueda seleccionarse hasta cuatro veces?
(a.3) cada numero pueda seleccionarse, a lo sumo, tres veces?
(b) Contestese el apartado (a) siendo el producto de los cuatro numeros, negativo.
Solucion
Sean a, b, c y d los cuatro numeros, las distintas opciones que pueden presentarse atendiendo al signo delproducto de los cuatro se reflejan en el cuadro siguiente:
opciones a b c d Signo del producto1 + + + + +
2 + + + − −
3 + + − − +
4 + − − − −
5 − − − − +
(a) Las opciones en que el signo del producto es positivo son la 1, la 3 y la 5.
(a.1) Los numeros son distintos.
− En la primera opcion solo hay una posibilidad ya que hay, unicamente cuatro numerospositivos.
− En la tercera opcion podremos elegir dos numeros de entre los cuatro positivos y dos deentre los cuatro negativos.Observese que para el signo del producto el orden en que elijamos los numeros es irrele-vante, luego dos grupos seran distintos cuando cambiemos algun(os) elementos, por tanto,seran combinaciones de orden dos tanto para los cuatro positivos, como para los cinconegativos.
126
Matematica Discreta Francisco Jose Gonzalez Gutierrez
Los dos positivos pueden elegirse, pues, de C4,2 formas y para cada una de ellas hay C5,2
maneras diferentes de elegir los dos negativos. El numero de formas de hacer la seleccionde los numeros en la tercera opcion es, por la regla del producto,
C4,2 · C5,2
− Para la quinta opcion, los cuatro numeros han de ser negativos, luego razonando igualque en la opcion anterior y teniendo en cuenta que hay cinco numeros negativos, habra
C5,4
formas distintas de seleccionar los cinco numeros negativos y que el producto de ellos seapositivo.
Consecuentemente, el numero de maneras distintas en que pueden hacerse las selecciones demodo que el producto de los cuatro numeros resulte positivo es, por la regla de la suma,
1 + C4,2 · C5,2 + C5,4 = 1 +(
42
)·(
52
)+
(54
)= 66
(a.2) Cada numero puede seleccionarse hasta cuatro veces. El razonamiento es identico al delapartado anterior con la salvedad de que al poder repetirse los numeros las combinacionesseran con repeticion.
− En la opcion primera las selecciones pueden hacerse de
CR4,4
formas distintas.− En la tercera opcion, las formas distintas de hacer las selecciones es
CR4,2 · CR5,2
− Para la quinta opcion las selecciones pueden hacerse de
CR5,4
maneras diferentes.
Consecuentemente, el numero de formas diferentes en que pueden seleccionarse cuatro numerosde entre los dados de forma que el producto sea positivo, pudiendo seleccionar cada numerohasta cuatro veces es
CR4,4 + CR4,2 · CR5,2 + CR5,4 = 180
(a.3) Cada numero puede seleccionarse, a lo sumo, tres vecesAl no poder seleccionar ninguno de los numeros cuatro veces, el resultado serıa igual al anteriordescontando los productos en los que un numero se repita cuatro veces que son cuatro paralos positivos y cinco para los negativos, luego el resultado es
CR4,4 + CR4,2 · CR5,2 + CR5,4 − 9 = 180− 9 = 171
(b) Las opciones en las que el producto es negativo son, segun el cuadro del principio, la 2 y la 4.
(b.1) Los numeros son diferentes.
− Para la segunda opcion hay que elegir tres numeros positivos y uno negativo. Los trespositivos pueden elegirse de C4,3 formas distintas y para el negativo hay cinco opcionesya que son cinco los propuestos. Por la regla del producto, la eleccion puede hacerse de5 · C4,3 formas distintas.
− Para la cuarta opcion, hay que elegir un numero positivo y tres negativos. Razonandoexactamente igual, la eleccion puede hacerse de 4 · C5,3 formas distintas.
127
Universidad de Cadiz Departamento de Matematicas
Consecuentemente, el numero de maneras en que puede hacerse la seleccion de los cuatronumeros de forma que todos sean distintos y el producto resulte negativo es, por la regla dela suma,
5 · C4,3 + 4 · C5,3 = 5(
43
)+ 4
(53
)= 5
4!3! · 1!
+ 45!
3! · 2!= 60
(b.2) Cada numero puede seleccionarse hasta cuatro veces.
− Para la opcion 2, los tres positivos pueden elegirse de CR4,3 formas distintas y para elnegativo, al igual que en el apartado anterior, hay cinco opciones. La eleccion puedehacerse, por tanto, de 5 · CR4,3 formas distintas.
− Para la cuarta opcion y razonando exactamente igual, la eleccion puede hacerse de 4·CR5,3
formas distintas.
Por la regla de la suma, habra
5 · CR4,3 + 4 · CR5,3 = 5 ·(
4− 1 + 33
)+ 4 ·
(5− 1 + 3
3
)= 240
formas distintas de hacer la seleccion en la forma pedida.
(b.3) El resultado es el mismo que el del apartado anterior, ya que no han podido seleccionarsenunca los cuatro numeros.
�
Ejemplo 5.17 Resolver las siguientes cuestiones:
(a) ¿De cuantas formas puede distribuirse cinco dulces diferentes entre diez personas si ninguna deellas puede recibir mas de uno?
(b) ¿De cuantas formas pueden distribuirse cinco dulces diferentes entre diez personas si cualquiera deellas puede recibir cualquier numero de dulces?
(c) ¿De cuantas formas puede distribuirse cinco manzanas identicas entre diez personas si ninguna deellas puede recibir mas de una?
(d) ¿De cuantas formas pueden distribuirse cinco manzanas identicas entre diez personas si cualquierade ellas puede recibir cualquier numero de manzanas?
Solucion
(a) SeaD = {d1, d2, d3, d4, d5}
el conjunto de los dulces, y
P = {p1, p2, p3, p4, p5, p6, p7, p8, p9, p10}
el conjunto de las personas. El esquema siguiente muestra algunos ejemplos de la situacion que seplantea.
d1 d2 d3 d4 d5
(1) p1 p3 p5 p7 p9
(2) p3 p1 p5 p7 p9
(3) p1 p3 p6 p8 p10
......
......
......
Veamos lo que ocurre:
128
Matematica Discreta Francisco Jose Gonzalez Gutierrez
− Los grupos (1) y (2) son distintos ya que en el primero a la persona p1 le corresponde el dulced1 y a la p3 el d1 y en el segundo es al contrario, por tanto, el orden influye en el hecho deque dos grupos sean distintos.
− El grupo (3) es, asimismo, distinto de los anteriores ya que hemos cambiado las personas, luegoel cambio de algun o algunos elementos tambien es relevante para discernir si dos grupos soniguales o distintos.
Consecuentemente, los distintos grupos son las variaciones de orden cinco elegidas de entre las diezpersonas y el numero de formas pedido es:
V10,5 = 10 · 9 · 8 · 7 · 6 = 30240
(b) La situacion es identica a la del caso anterior, aunque ahora las variaciones de orden cinco elegidasentre las diez personas, seran con repeticion. El numero total de formas distintas sera, por tanto,
V R10,5 = 105 = 100000
(c) Como ahora las manzanas son identicas, el esquema serıa
m m m m m(1) p1 p3 p5 p7 p9
(2) p3 p1 p5 p7 p9
(3) p1 p3 p6 p8 p10
......
......
......
Los grupos (1) y (2) son iguales, luego el orden no es relevante para que dos grupos sean distintos.Sin embargo, el tercer grupo si es distinto de los dos anteriores luego el cambio de algun o algunoselementos es lo unico que influye para que dos grupos sean distintos. Consecuentemente, estos soncombinaciones de orden cinco elegidas entre de las diez personas, ası pues, habra
C10,5 =(
105
)=
10!5! · 2!
= 15120
formas distintas de distribuir las manzanas.
(d) Dado que cada persona puede recibir cualquier numero de manzanas, el planteamiento seria identicoal del apartado anterior, aunque en este caso los grupos serıan combinaciones con repeticion deorden cinco elegidas entre las diez personas, luego
CR10,5 =(
10− 1 + 55
)=
(145
)=
14!5! · 9!
= 2002
sera el total de formas en que pueden distribuirse cinco manzanas identicas entre las diez personassi cualquiera de ellas puede recibir cualquier numero de manzanas. �
129
