Leccion5

Vista previa del material en texto

Apuntes de Matemática Discreta
5. Combinaciones. Teorema del Binomio
Francisco José González Gutiérrez
Cádiz, Octubre de 2004
Universidad de Cádiz Departamento de Matemáticas
ii
Lección 5
Combinaciones. Teorema del
Binomio
Contenido
5.1 Combinaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
5.1.1 Definición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
5.1.2 Formación y número de combinaciones . . . . . . . . . . . . . . . . . . . . . . . 106
5.2 Teorema del Binomio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
5.2.1 Proposición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
5.2.2 Fórmula de Pascal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
5.2.3 Triángulo de Pascal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
5.3 Combinaciones con Repetición . . . . . . . . . . . . . . . . . . . . . . . . . . 121
5.3.1 Definición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
5.3.2 Número de combinaciones con repetición . . . . . . . . . . . . . . . . . . . . . . 123
Los elementos a combinar en estas cuestiones no tienen más
propiedades que su diversidad. No tienen valor o capacidad ar-
itméticos, salvo que se pueden contar. No se puede operar con
ellos, 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. ¿Cuántas manos de cinco cartas diferentes
pueden obtenerse de dicha baraja?
Supongamos calculadas todas las ordenaciones posibles de las 52 cartas de la baraja. Tendŕıamos P52
ordenaciones distintas. Parece que si elegimos cinco cartas cualesquiera en cada una de las ordenaciones
(las mismas en cada ordenación), el problema estaŕıa resuelto. Sin embargo, no es aśı, ya que por ejemplo
dos de los grupos elegidos podŕıan ser
a1a2a3a4a5 y a1a3a4a2a5
pero estas dos manos son iguales desde el punto de vista que se plantea la pregunta, es decir, el orden
en que nos den las cinco cartas es irrelevante. Entre las P52 ordenaciones habrá P5 que serán iguales.
105
Universidad de Cádiz Departamento de Matemáticas
Además cada una de ellas estará repetida P52−5 veces, luego por la regla del producto, dentro de las P52
ordenaciones habrá un total de P5 ·P(52−5) ordenaciones iguales. Aśı pues, el número de manos distintas,
M , por el número de veces que se repite cada una será igual al total de ordenaciones posibles de las 52
cartas, es decir,
M · P5 · P52−5 = P52
de aqúı que
M =
P52
P5 · P(52−5)
=
52!
5! · (52− 5)!
sea el número de manos diferentes de cinco cartas que pueden obtenerse. La nueva situación nos sitúa
ante la definición de combinación que ahora veremos.
5.1.1 Definición
Dada una colección de m objetos a1, a2, . . . , am−1, am distintos y un número entero positivo n 6 m,
llamaremos combinación de orden n a cualquier subcolección, a1, a2, . . . , an de n objetos de la colección
dada.
Dos combinaciones serán distintas si algún o algunos elementos de uno de los grupos no se encuentra en
el otro, es decir, si difieren en algún o algunos elementos.
5.1.2 Formación y número de combinaciones
Al número de combinaciones de orden n de una colección de m objetos, lo designaremos por Cm,n y
diremos que es el número de combinaciones de m elementos tomados n a n. Su número es
Cm,n =
m!
n!(m− n)!
Demostración
Procederemos por inducción para formar las combinaciones de m elementos tomados n a n y calcular su
número.
Paso básico. Para n = 1, las combinaciones de orden 1, serán:
a1 a2 a3 . . . . . . an
para n = 2, obtendremos las combinaciones de orden dos de m elementos. Estas podrán obtenerse
añadiendo a cada combinación 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 de
menor a mayor, las combinaciones de orden n, se obtienen añadiendo a cada combinación de orden n− 1
cada uno de los elementos posteriores al último de los que en ella figuren.
De esta forma, todas las combinaciones n-arias aśı formadas son distintas, bien porque proceden de
combinaciones de orden n− 1, o bien, por tener diferente el último elemento.
106
Matemática Discreta Francisco José González Gutiérrez
Además se obtienen todas las posibles, pues si faltara alguna, separando en una cualquiera de ellas el
último elemento nos quedaŕıa una combinación de orden n− 1 que no habŕıa figurado entre las que nos
hab́ıan servido de partida de orden n− 1 en contra de la hipótesis.
Calculemos ahora el número de combinaciones.
Supongamos formadas todas las combinaciones de orden n de m elementos, es decir, Cm,n. Si en cada
combinación permutamos de todos los modos posibles los n elementos que figuran en ella, obtendŕıamos
todas las variaciones posibles de esos m elementos tomados n a n. Aśı pues, cada combinación da lugar
a Pn variaciones, por tanto,
Vm,n = Cm,n · Pn =⇒ Cm,n =
Vm,n
Pn
=
m!
(m−n)!
n!
=
m!
n!(m− n)!
Al número resultante se le llama número combinatorio y se nota en la forma(
m
n
)
=
m!
n!(m− n)!
Ejemplo 5.1 Se dispone de doce puntos en un plano de tal manera que tres cualesquiera de ellos no
están alineados.
(a) ¿Cuántas rectas determinan dichos puntos?
(b) ¿Cuántas de las rectas anteriores pasan por un determinado punto a?
(c) ¿Cuántos triángulos contienen al punto a como vértice?
Solución
Recordemos que dos puntos cualesquiera del plano determinan una recta y que un tercer punto, o bien
está alineado con los otros dos, en cuyo caso pertenece a la recta que ambos determinan, o bien no lo
está, y en tal caso, determina con los otros puntos, dos rectas, una con cada uno de ellos. Dado que
disponemos de doce puntos y tres cualesquiera de ellos no están alineados, podremos asegurar que cada
dos de ellos determinan una recta distinta de las demás.
(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 determinan
los 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 la
determinada d y a, por tanto el orden en que tomemos los puntos no influye en la recta que ambos
determinan.
Sin embargo, los puntos a y d determinan una recta distinta de la que determinan d y e que, a su
vez, es distinta de la que determinan a y f , por tanto el cambio de algún o algunos puntos influye
en el hecho de que las rectas que determinan sean distintas.
Consecuentemente, las rectas que determinan los doce puntos seŕıan combinaciones de orden dos
elegidas entre ellos y
C12,2 =
(
12
2
)
=
12!
2! · 10!
=
11 · 12
2
= 66
será el número de rectas distintas que hay.
(b) Bastaŕıa dejar fijo el punto a y trazar una recta a cada uno de los restantes once puntos, luego
habrá, en total, once rectas que pasan por dicho punto.
(c) Cada tres puntos no alineados en el plano determinan un triángulo que los tiene como vértices.
Dejando fijo el punto a, bastaŕıa calcular las combinaciones de orden dos de los once puntos
restantes y obtendŕıamos
C11,2 =
(
11
2
)
=
11!
2! · 9!
=
10 · 11
2
= 55
107
Universidad de Cádiz Departamento de Matemáticas
triángulos diferentes que tienen al punto a como uno de sus vértices. �
Ejemplo 5.2 Un estudiante tiene que responder siete preguntas de un cuestionario de diez. ¿de cuántas
formas puede hacer su elección 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?
Solución
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 sicambiamos el orden entre ellas el grupo elegido es el mismo, sin embargo si cambiamos
alguna o algunas preguntas, el grupo es distinto, por tanto los grupos de siete preguntas serán combina-
ciones de orden siete elegidas entre las diez del cuestionario.
(a) Al no haber ningún tipo de restricciones la elección podrá hacerse de
C10,7 =
(
10
7
)
=
10!
7! · 3!
= 120
formas distintas.
(b) Si el estudiante debe responder a las dos primeras preguntas, hallamos todos los grupos distintos
de cinco preguntas que pueden elegirse entre las ocho restantes y a cada uno de ellos le añadimos
las dos primeras. Por tanto, la elección puede hacerse de
C8,5 =
(
8
5
)
=
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 ó 5 que pueden elegirse entre
las cinco primeras y para cada uno de ellos elegimos 7 − k preguntas entre las cinco restantes. El
número total de formas distintas de hacer la elección será, por tanto,
5∑
k=3
C5,k · C5,7−k =
5∑
k=3
(
5
k
)
·
(
5
7− k
)
=
(
5
3
)
·
(
5
4
)
+
(
5
4
)
·
(
5
3
)
+
(
5
5
)
·
(
5
2
)
= 11 ·
(
5
2
)
= 11 · 5!
2! · 3!
= 110
�
108
Matemática Discreta Francisco José González Gutiérrez
Ejemplo 5.3 Para hacer un apuesta de la Loteŕıa Primitiva hay que marcar seis números elegidos
entre el 1 y el 49. ¿De cuántas formas diferentes puede marcar una persona 6, 5, 4 ó 3 números?
Solución
Supongamos que marcamos los números 2, 3, 5, 7, 11 y 13 en este orden. Si los hubiéramos marcado
en cualquier otro orden la apuesta seŕıa la misma. Sin embargo, cambiando algún o algunos números de
éstos por otros, tendŕıamos una apuesta distinta.
Por tanto, las apuestas que pueden hacerse serán combinaciones de orden seis elegidas entre los cuarenta
y nueve números disponibles.
♦ Marcando seis números, el resultado será
C49,6 =
(
49
6
)
=
49!
6! · (49− 6)!
=
44 · 45 · 46 · 47 · 48 · 49
2 · 3 · 4 · 5 · 6
= 13.983.816
formas diferentes.
♦ Cinco números se podrán marcar de
C49,5 =
(
49
5
)
=
49!
5! · (49− 5)!
=
45 · 46 · 47 · 48 · 49
2 · 3 · 4 · 5
= 1.906.884
formas diferentes.
♦ Análogamente, cuatro números se podrán marcar de
C49,4 =
(
49
4
)
=
49!
4! · (49− 4)!
=
46 · 47 · 48 · 49
2 · 3 · 4
= 211876
formas distintas.
♦ Finalmente, podremos marcar tres números de
C49,3 =
(
49
3
)
=
49!
3! · (49− 3)!
=
47 · 48 · 49
2 · 3
= 18424
formas diferentes. �
Ejemplo 5.4 Demostrar que si n es un número entero positivo, entonces
C2n,n + C2n,n−1 =
1
2
C2n+2,n+1
Solución
109
Universidad de Cádiz Departamento de Matemáticas
C2n,n + C2n,n−1 =
(
2n
n
)
+
(
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)!
=
1
2
· (2n + 2)!
(n + 1)! · (n + 1)!
=
1
2
(
2n + 2
n + 1
)
=
1
2
C2n+2,n+1
�
Ejemplo 5.5 Se quiere elegir un comité de doce personas de un grupo formado por diez hombres y
diez mujeres. Decir de cuántas formas puede hacerse la elección
(a) Si no hay restricciones.
(b) Si debe haber 6 hombres y 6 mujeres.
(c) Si debe haber un número par de mujeres.
(d) Si debe haber 8 hombres como mı́nimo.
Solución
Se quieren elegir doce personas de entre las veinte que forman el grupo. Obviamente, el orden en el que se
elijan no influye en la composición del comité, aunque éste si vaŕıa cuando cambiamos alguna o algunas
personas. Se trata, por tanto, de combinaciones de orden doce escogidas de entre las veinte personas.
(a) Si no hay restricciones, quiere decir que la composición del comité puede ser cualquiera, luego la
elección puede hacerse de
C20,12 =
(
20
12
)
=
20!
12! · 8!
= 125970
(b) Si en el comité debe haber seis hombres y seis mujeres, elegimos seis hombres de entre los diez
que hay en el grupo y para cada uno de ellos se eligen seis mujeres de entre las diez que hay en el
mismo.
Los seis hombres pueden elegirse de C10,6 formas distintas y para cada una de estas combinaciones
habrá C10,6 formas distintas de elegir a las mujeres, consecuentemente, por la regla del producto, la
elección del comité podrá hacerse de
C10,6 · C10,6 =
(
10
6
)
·
(
10
6
)
=
10!
6! · 4!
· 10!
6! · 4!
= 210 · 210 = 44100
110
Matemática Discreta Francisco José González Gutiérrez
formas distintas.
(c) Si debe haber un número par de mujeres, entonces podemos representar su número en el comité
por 2k y el número 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 comités con un
número par de mujeres, por tanto el número total de formas de hacer la elección será
5∑
k=1
C10,2k · C10,12−2k =
5∑
k=1
(
10
2k
)
·
(
10
12− 2k
)
=
(
10
2
)
·
(
10
10
)
+
(
10
4
)
·
(
10
8
)
+
(
6
6
)
·
(
6
6
)
+(
10
8
)
·
(
10
4
)
+
(
10
10
)
·
(
10
2
)
= 45 · 1 + 210 · 45 + 210 · 210 + 45 · 210 + 45 · 1
= 63090
(d) Sea k el número de hombres que integran el comité, entonces k = 8, 9 ó 10, siendo el de mujeres
12− k, razonando igual que en el apartado anterior, habrá
10∑
k=8
C10,k · C10,12−k =
(
10
8
)
·
(
10
4
)
+
(
10
9
)
·
(
10
3
)
+
(
10
10
)
·
(
10
2
)
= 10695
formas distintas de hacer la elección. �
Ejemplo 5.6 Un comité de selección entrevista a cinco candidatos para un puesto de trabajo, entre-
gando al final una lista con las personas que propone. Decir cuántas listas distintas puede entregar el
comité en los casos siguientes:
(a) La lista ordena a los candidatos del uno al cinco.
(b) El comité selecciona un primer candidato, un segundo y un tercero.
(c) El comité decide proponer a un candidato para el puesto y seleccionar un grupo de dos suplentes.
Solución
(a) El número de listas, en estas condiciones, coincide con el número de formas de ordenar un conjunto
con cinco elementos, por tanto, habrá
P5 = 1 · 2 · 3 · 4 · 5 = 120
listas distintas.
(b) Si el comité selecciona un primer candidato, un segundo y un tercero, entonces es como seleccionar
ordenadamente tres personas de entre un grupo de cinco, por tanto, el número de listas distintas
es, en este caso,
V5,3 = 5 · 4 · 3 = 60
(c) Proponemos cualquiera de los cinco candidatos para el puesto y nos quedaŕıan cinco personas para
elegir a los dos suplentes. Dado que no importa el orden de éstos, las distintas formas de elegirlos
seŕıan combinaciones de orden dos elegidas entre las cuatro personas que restan. Por la regla del
producto, el número de listas distintas es
5 · C4,2 = 5 ·
(
4
2
)
= 5 · 4!
2! · 2!
= 30
�
111
Universidad de Cádiz Departamento de Matemáticas
5.2 Teorema del Binomio
Si n es un número entero positivo, entonces,
(a + b)n =
n∑
k=0
(
n
k
)
akbn−k
Demostración
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 y
luego el segundo sumando (la b) del primer factor por los dos del segundo. De esta forma vemos que
en cada uno de los cuatro sumandos que configuran el resultado figura uno, y sólo un elemento de cada
factor. El siguiente diagrama resume la situación.
a
•
b
•
•a
a2
• b
ab
•a
ba
• b
b2
(a + b)2 = a2 + 2ab + b2
Procediendo de forma idéntica,
(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 seŕı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
Matemática Discreta Francisco José González Gutiérrez
y el siguiente árbol nos permitiŕıa escribir el desarrollo de (a + b)4.
a
•
b
•
a
•
b
•
a
•
b
•
a• •b a• •b a• •b a• •b
a•
a4
•b
a3b
a•
a3b
•b
a2b2
a•
a3b
•
a2b2b 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
Obsérvese que al elegir una letra, y sólo una (la a o la b), de cada factor, todos y cada uno de los factores
resultantes han de tener el mismo número de letras, dos en (a + b)2, tres en (a + b)3, cuatro en (a + b)4
y aśı sucesivamente. Veamos un ejemplo de lo que decimos e intentemos sacar alguna conclusión.
Supongamos que queremos saber el coeficiente de alguno de los sumandos del desarrollo de (a+b)7. Como
hemos visto todos tendrán siete letras. Consideremos por ejemplo ababaaa, es decir a5b2 y fijémonos
únicamente en las aes. Teniendo en cuenta que cada una de ellas pertenece a un único factor y llamando
a éstos f1, f2, f3, f4, f5, f6 y f7 para calcular todas las opciones posibles, podemos utilizar el siguiente
esquema:
a a a a a
f1 f2 f3 f4 f5
f2 f1 f5 f3 f5
f7 f6 f3 f2 f4
...
...
...
...
...
Por lo tanto, el número de veces que se repetirá a5 (y, consecuentemente, a5b2) es igual al número de
grupos de 5 factores que podamos elegir entre los 7 de que disponemos y de tal forma que el orden no
influye 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 idéntico nos permite decir que el coeficiente de a3b4 en el mismo desarrollo es C7,3, y
aśı 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 número entero entre 0 y n, el sumando akbn−k tiene la a repetida k
veces correspondiendo una, y sólo una, a cada factor, luego son grupos de k elementos (factores) elegidos
entre n (total de factores) y donde el orden no importa. Por lo tanto su número es Cn,k.
113
Universidad de Cádiz Departamento de Matemáticas
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
=
(
n
0
)
a0bn +
(
n
1
)
abn−1 +
(
n
2
)
a2bn−2 + · · ·+
(
n
n− 1
)
an−1b +
(
n
n
)
anb0
=
n∑
k=0
(
n
k
)
akbn−k
�
Nota 5.1 Plantearemos ahora el mismo problema de forma ligeramente distinta. En el cálculo que
hicimos del coeficiente de a5b2 en el desarrollo de (a + b)7 nos hemos fijado únicamente en las aes. ¿Qué
pasaŕıa si nos fijamos tanto en las aes como en las bes? El esquema siguiente refleja la situación.
f1 f2 f3 f4 f5 f6 f7
a b a a b a a
b b a a a a a
a a b a b a a
...
...
...
...
...
...
...
El número de productos posibles de la forma a5b2 tal que cada a y cada b esté en uno y sólo un factor
seŕıa igual al de palabras de siete letras que podamos formar con cinco aes y dos bes o lo que es igual
todas las ordenaciones posibles que puedan hacerse con ellas, es decir, PR5,27 .
En general, el número de productos del tipo akbn−k seŕıa igual al número de palabras distintas que
pueden escribirse de tal forma que cada una tuviera n veces repetida la a y n− k veces repetida la b, es
decir,
PRk,n−kn =
n!
k! · (n− k)!
=
(
n
k
)
Por lo tanto,
(a + b)n = PR0,nn · a0bn + PR1,n−1n · a1bn−1 + · · ·+ PRn−1,1n · an−1b + PRn,0n · anb0
=
n∑
k=0
PRk,n−kn · akbn−k
=
n∑
k=0
n!
k! · (n− k)!
· akbn−k
=
n∑
k=0
(
n
k
)
akbn−k
�
Ejemplo 5.7 Se lanza una moneda al aire n veces. ¿De cuántas maneras pueden obtenerse una, dos,
tres, cuatro, . . . . . ., o n caras?
Solución
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
Matemática Discreta Francisco José González Gutiérrez
El conjunto
A1 ∪A2 ∪ · · · ∪An =
n⋃
k=1
Ak
estará formado por todos los resultados en los que aparezcan una, dos,. . ., o n caras. Por tanto, el número
pedido es el cardinal de dicho conjunto. Como los Ak son disjuntos dos a dos, por el principio de adición,∣∣∣∣∣
n⋃
k=1
Ak
∣∣∣∣∣ =
n∑
k=1
|Ak|
El esquema siguiente nos ayudará a calcular |Ak| para 1 6 k 6 n.
c c c
(k
· · · c c
1 2 3 · · · k − 1 k
2 3 k · · · 1 k − 1
2 n 3 · · · n− 1 1
...
...
...
. . .
...
...
Serán todos los grupos de k lanzamientos que podamos elegir entre los n, de tal forma que el orden no
influye en el hecho de que dos grupos sean distintos (obsérvese que las dos primeras filas de la tabla
anterior significan lo mismo aunque estén en distinto orden). Por lo tanto,
|Ak| = Cn,k.
De aqúı que ∣∣∣∣∣
n⋃
k=1
Ak
∣∣∣∣∣ =
n∑
k=1
|Ak|
=
n∑
k=1
Cn,k
=
n∑
k=1
(
n
k
)
=
n∑
k=0
(
n
k
)
1k · 1n−k −
(
n
0
)
= 2n − 1
Ejemplo 5.8 ¿De cuántas maneras puede elegir un profesor a uno o más estudiantes entre seis?
Solución
Sean a, b, c, d, e y f los seis estudiantes y supongamos que el profesor elige a un grupo de tres, abc. Es
obvio que el orden en que los escoja no influye en el grupo elegido, sin embargo el cambio de algún o
algunos estudiantes si influye ya que los grupos abc y ade son distintos.
Por tanto, las formas de elegir los estudiantes serán combinaciones de orden k seleccionadas de entre los
seis estudiantes, siendo 1 6 k 6 6, por tanto el profesor dispone de
6∑
k=1
C6,k =
6∑
k=1
(
6
k
)
=
6∑
k=0
(
6
k
)
−
(
6
0
)
=
6∑
k=0
(
6
k
)
1k16−k −
(
6
0
)
= (1 + 1)6 − 1 = 26 − 1 = 63
maneras distintas de elegir a uno o más estudiantes entre seis. �
Ejemplo 5.9 Para elaborar una pizza podemos utilizar, además de queso y tomate, los siguientes
ingredientes: carne, champiñones, pimientos, cebolla, salami y anchoas. Decir cuántas pizzas diferentes
es posible elaborar en los casos siguientes:
115
Universidad de Cádiz Departamento de Matemáticas
(a) pueden tener desde todos a ningún ingrediente.
(b) tienen al menos, champiñones y anchoas.
(c) no tienen ni carne ni salami.
Solución
Dos pizzas serán distintas cuando en su elaboración utilicemos, además de queso y tomate, diferentes
ingredientes. El orden en que se utilizan los mismos no es relevante, por tanto las diferentes pizzas serán
combinaciones de orden n elegidas entre los seis ingredientes de que se disponen.
(a) Si pueden tener desde todos a ningún ingrediente, entonces n variará entre seis y cero, por tanto,
el número total de pizzas diferentes
6∑
n=0
C6,n =
6∑
n=0
(
6
n
)
=
6∑
n=0
(
6
n
)
1n · 16−n = (1 + 1)6 = 26 = 64
(b) Si han de intervenir en su composición, champiñones y anchoas, entonces le añadimos estos dos
ingredientes a todas las posibles pizzas que puedan elaborarse con los otros cuatro. El total de
pizzas diferentes será, utilizando el mismo razonamiento que en (a),
4∑
n=0
C4,n =
4∑
n=0
(
4
n
)
=
4∑
n=0
(
4
n
)
1n · 14−n = (1 + 1)4 = 24 = 16
(c) Al no tener carne ni salami, el total de pizzas diferentes será igual al anterior ya que tendŕıamos
cuatro ingredientes, luego
4∑
n=0
C4,n = 16
es el total de pizzas diferentes que no llevan carne ni salami. �
Ejemplo 5.10 ¿Cuántos subconjuntos tiene un conjunto con n elementos?
Solución
Elegido cualquier subconjunto del conjunto dado, el orden en que estén situados los elementos en el
mismo es irrelevante luego dos subconjuntos serán distintos si, y sólo śı se diferencian en, al menos, un
elemento, de aqúı que los subconjuntos con k elementos sean las combinaciones de orden k que puedan
elegirse entre los n elementos del conjunto dado, siendo 0 6 k 6 n.
Obsérvese que k = 0 se corresponde con subconjuntos con cero elementos, es decir, el conjunto vaćıo.
Pues bien, de acuerdo con este razonamiento, el número de subconjuntos que tiene un conjunto con n
elementos será
1 +
n∑
k=1
Cn,k =
(
n
0
)
+
n∑
k=1
(
n
k
)
=
n∑
k=0
(
n
k
)
1n1n−k = (1 + 1)n = 2n
�
Ejemplo 5.11 Dado el conjunto A = {1, 2, 3, 4, 5, 6, 7}, determinar el número de
(a) subconjuntos de A.(b) subconjuntos no vaćıos de A.
116
Matemática Discreta Francisco José González Gutiérrez
(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 número par de elementos.
(f) subconjuntos de A con un número impar de elementos y que incluyan al elemento 3.
Solución
(a) Veamos cuantos subconjuntos tiene A.
Directamente del ejemplo anterior, el número de subconjuntos que tiene A será
1 +
7∑
k=1
C7,k =
(
7
0
)
+
7∑
k=1
(
7
k
)
=
7∑
k=0
(
7
k
)
1717−k = (1 + 1)7 = 27 = 128
(b) El número de subconjuntos no vaćıos de A se calcula directamente del punto anterior,
128− 1 = 127
es decir, al total le hemos restado uno ya que hay un sólo subconjunto vaćıo en A. (Se corresponde
con k = 0).
(c) El número de subconjuntos de A que contienen tres elementos también se sigue directamente del
apartado (a) para k = 3, luego es
C7,3 =
(
7
3
)
=
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 añadimos el 1 y el 2. Por tanto, el número de subconjuntos
de este tipo será
5∑
k=0
C5,k =
5∑
k=0
(
5
k
)
1515−k = (1 + 1)5 = 25 = 32
(e) Siguiendo el mismo razonamiento que en (a), bastaŕıa calcular el número de subconjuntos de A
para k = 2, 4 y 6, es decir habrá
C7,2 + C7,4 + C7,6 =
(
7
2
)
+
(
7
4
)
+
(
7
6
)
= 63
subconjuntos de A que tengan un número par de elementos.
(f) Bastaŕıa hallar todos los subconjuntos de {1, 2, 4, 5, 6, 7} que tengan cero, dos, cuatro y seis ele-
mentos y añadirle a cada uno de ellos el 3, por tanto, habrá
1 + C6,2 + C6,4 + C6,6 = 1 +
(
6
2
)
+
(
6
4
)
+
(
6
6
)
= 1 + 2 · 6!
2! · 4!
+ 1 = 32
subconjuntos de A con un número impar de elementos entre los cuales se incluya el 3. �
Ejemplo 5.12 ¿De cuántas formas distintas puede descomponerse el número 8 como suma de enteros
positivos?
Solución
Una posible descomposición seŕıa
5 + 2 + 1 = 8
117
Universidad de Cádiz Departamento de Matemáticas
que consideraremos distinta de la
1 + 5 + 2 = 8
y otra podŕıa ser
7 + 1 = 8
Las descomposiciones más extremas seŕıan en un único sumando
8 = 8
y en ocho sumandos
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 8.
Aśı pues habrá que calcular cuántas descomposiciones pueden hacerse con 1, 2, 3, 4, 5, 6, 7 y 8 sumandos
y luego sumarlas todas. Calcularemos el número de descomposiciones con k sumandos donde k vaŕıa
entre 1 y 8.
El número de descomposiciones que hay con k sumandos será igual al número de soluciones de la ecuación,
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 habŕıa k sumandos sino
k − 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 número de soluciones enteras no negativas de la ecuación anterior
que, como ya sabemos, es
PRk−1,8−kk−1+8−k = PR
k−1,8−k
7 , para 1 6 k 6 8
Por lo tanto, el número total de descomposiciones, será
8∑
k=1
PR8−k,k−17 =
8∑
k=1
7!
(k − 1)!(8− k)!
=
8∑
k=1
(
7
k − 1
)
=
7∑
k=0
(
7
k
)
=
7∑
k=0
(
7
k
)
1k · 17−k
= (1 + 1)7
= 27
= 128
�
118
Matemática Discreta Francisco José González Gutiérrez
5.2.1 Proposición
Si n y k son dos números enteros no negativos tales que 0 6 k 6 n, entonces,(
n + 1
k
)
=
(
n
k
)
+
(
n
k − 1
)
Demostración
Sea A un conjunto con n elementos y B un conjunto con un sólo elemento, por ejemplo, B = {b} y tal
que b no pertenezca a A. Entonces, A ∩ B = ∅ y si C = A ∪ B, por el principio de adición, tendremos
que
|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} .
Además,
P = Q ∪R, con Q ∩R = ∅
luego por el principio de adición,
|P | = |Q|+ |R|
pero,
|P | = Cn+1,k
|Q| = Cn,k
|R| = Cn,k−1
de aqúı que
Cn+1,k = Cn,k + Cn,k−1
es decir, (
n + 1
k
)
=
(
n
k
)
+
(
n
k − 1
)
�
5.2.2 Fórmula de Pascal
Si n y k son dos enteros positivos tales que 1 6 k 6 n− 1, entonces(
n
k
)
=
(
n− 1
k
)
+
(
n− 1
k − 1
)
Demostración
119
Universidad de Cádiz Departamento de Matemáticas
Para obtener la fórmula de Pascal1, basta sustituir n por n− 1 en la igualdad anterior. �
Ejemplo 5.13 Demostrar la proposición 5.2.1 efectuando los números combinatorios.
Solución
En efecto, desarrollando los números combinatorios del segundo miembro,
(
n
k
)
+
(
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 + 1
k
)
�
1Blaise Pascal, matemático, f́ısico, filósofo y escritor francés (Clermont-Ferrand 1623-Paŕıs 1662). Hijo de una familia de
la alta burgueśıa auvernesa, que, en 1631, fijó su residencia en Paŕıs, donde los medios literarios y cient́ıficos que frecuentó
le ayudaron a crear una vocación precoz. Se dice que su padre trató de mantenerlo, al principio, alejado de los libros de
matemáticas, con objeto de estimular al joven Blaise a desarrollar otros intereses, pero a la edad de doce años el muchacho
demostraba ya tal grado de inteligencia geométrica que, en adelante, se favoreció su inclinación matemática. A los catorce
años ya acompañaba a su padre a las reuniones informales de la “Academia de Mersenne” en Paŕıs. Aqúı fue donde se
familiarizó con las ideas de Desargues, y dos años más tarde, en 1640, el joven Pascal publicó su Essay pour les coniques.
A la edad de dieciocho años aproximadamente cambió de tema y para ayudar a su padre en un trabajo fiscal, se dedicó a
diseñar una máquina calculadora; en unos pocos años construyó y vendió unas cincuenta de estas máquinas. Durante este
tiempo la familia Pascal entró en relación con los jansenitas Saint-Cyran y Antoine Arnauld. Durante esta época, Pascal
continuó sus investigaciones y tuvo dos entrevistas con Descartes, pero sin que al parecer pudieran encontrar ambos un
camino de inteligencia común; sin duda les separaron, entre otras cosas, sus teoŕıas sobre el vaćıo. A continuación, en 1648,
se interesó Pascal en la hidrostática, y los resultados de sus investigaciones fueron el famoso experimento de Puy-de-Dôme
que confirmaba el peso del aire, y los experimentos acerca de la presión ejercida por un fluido, que clarificaron la aparente
paradoja hidrostática. Su padre murió en 1651 y su hermana Jacqueline ingresó en 1652 en el convento de Port-Royal.
Entonces Pascal se dedicó más febrilmente a las ciencias. Comenzó a frecuentar algunos amigos, si no libertinos, al menos
bastante independientes, el duque de Roannez, Mitton y el caballero de Méré. Fue en esta época cuando Pascal, buscando
soluciones a un problema propuesto por Méré, se interesó por el Cálculo de Probabilidades. Pascal relacionó el estudio de las
probabilidades con el triángulo aritmético, superando en sus discusiones la obra de Cardano en tal medida que la conocida
distribución triangular de números ha venido recibiendo, desde entonces, el nombre de triángulo de Pascal. Durante la
noche del 23 de noviembre de 1654 (del que queda emocionante testimonio en su Memorial), experimentó Pascal una
especie de éxtasis religioso que lo impulsó a abandonar la ciencia y la matemática para dedicarse a la teoloǵıa. Siguiendo
los M. Singlin, que tomó como director espiritual en 1655, se retiró a Port-Royal des Champs, donde, sin convertirse en
miembro activode la abad́ıa, se dedicó a la penitencia. Cuando Arnauld fue amenazado con la condenación en la Sorbona,
Pascal le defendió revelándose como un excepcional polemista. Desde enero de 1656 a marzo de 1657 bajo el seudónimo de
MONTALTE publicó las dieciocho cartas conocidas con el nombre de Provinciales donde ataca a la Sorbona, a los jesuitas
y, sobre todo, los abusos de la casúıstica. Ya sólo volveŕıa a los estudios matemáticos durante un breve peŕıodo de tiempo
en 1658-1659. Una noche de 1658 en que un dolor de muelas un otra dolencia le imped́ıa dormir, decidió, como distracción
contra el dolor, dedicarse al estudio de la cicloide. Milagrosamente, el dolor cesó, lo que interpretó Pascal como un signo de
que el estudio de la matemática no desagradaba a Dios. En 1661 intervino en el drama de conciencia en que se debat́ıan los
jansenitas obligados a firmar la condenación de Jansenio. La hermana de Pascal (que murió aquel mismo año) influyó en su
hermano para que tomará partido por la intransigencia y aśı lo hizo contra los propios maestros jansenitas Arnauld y Nicole
inclinados a firmar. Ante la resistencia que encontró, Pascal se retiró de la lucha, dedicándose desde entonces a una vida de
piedad personal. Su obra fundamental quedó incompleta. En el contexto de una integración de la función seno en su Traité
des sinus du quart de cercle, de 1658, Pascal se aproximó extraordinariamente a lo que pudo haber sido el descubrimiento
del cálculo; tan cerca estuvo de ellos que Leibniz escribiŕıa más tarde que fue leyendo esta obra de Pascal cuando se le
mostró súbitamente la luz. Si Pascal no hubiera muerto poco después de cumplir 39 años, o bien si su mentalidad hubiera
sido más exclusivamente matemática, no cabe prácticamente duda de que se hubiera anticipado a Newton y a Leibniz en
sus más grandes descubrimientos.
120
Matemática Discreta Francisco José González Gutiérrez
5.2.3 Triángulo de Pascal
Con la fórmula de Pascal puede obtenerse un método para el cálculo de los coef icientes del desarrollo
de (a + b)n.
En efecto, si tenemos en cuenta que para cualquier entero no negativo n se verifica que(
n
0
)
=
(
n
n
)
= 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 triángulo de Pascal.2(
0
0
)
(
1
0
) (
1
1
)
(
2
0
) (
2
1
) (
2
2
)
(
3
0
) (
3
1
) (
3
2
) (
3
3
)
(
4
0
) (
4
1
) (
4
2
) (
4
3
) (
4
4
)
(
5
0
) (
5
1
) (
5
2
) (
5
3
) (
5
4
) (
5
5
)
que desarrollando los números 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 número en el triángulo es suma
de los dos que están encima suya. �
5.3 Combinaciones con Repetición
Supongamos que disponemos de m objetos a1, a2, . . . , am y que son bocadillos.
Supongamos, también, para fijar ideas supongamos que m = 4, es decir, hay cuatro clases distintas de
bocadillos, por ejemplo a1 es de jamón (j), a2 de chorizo (c), a3 de salchichón (s) y a4 de tortilla (t).
2Figura en el Traité du Triangle Arithmétique publicado por Pascal en 1665. También recibe el nombre de triángulo
de Yang Hui’s, en honor al matemático chino que lo descubrió en 1261. El matemático Chu Shih-Chieh, también chino, lo
incluye en su libro El espejo precioso de los cuatro elementos de 1303.
121
Universidad de Cádiz Departamento de Matemáticas
Supongamos que diez estudiantes de Matemática Discreta entran en la cafeteŕıa de la Escuela dispuestos
a comerse un bocadillo cada uno.
¿De cuántas maneras distintas pueden pedir los bocadillos los estudiantes?
Designaremos con las letras c, j, s y t a los bocadillos de chorizo, jamón, salchichón y tortilla, respectiva-
mente. Uno de los pedidos puede ser cccjjstttt que, obviamente, es igual al pedido ccjcstttt y distinto al
ccjjssttt. El orden, por tanto, es irrelevante y lo único que hace a dos peticiones distintas es el cambio
de algún o algunos elementos entre los que no sean iguales entre śı.
Estamos, pues, ante un problema de combinaciones, aunque los elementos pueden repetirse, luego no
podremos utilizar lo estudiado en el apartado anterior.
Calcularemos este número con el método 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 habrá cuatro unos, aśı, la petición, cjjtttccss se corresponderá con el grupo, 10001001001000. La
siguiente tabla representa alguna de las peticiones y los grupos de ceros y unos correspondientes.
A B
cccjjcjctt 10000011000100
cccjjtttss 10001001001000
ssssjjjjjj 11000010000001
tttttttttt 11110000000000
En la columna A tenemos todas las combinaciones con repetición de cuatro elementos tomados diez a
diez y su número coincidirá con el número de grupos distintos que haya en la columna B.
Obsérvese que los grupos de la columna B comienzan todos con un uno. Para calcular cuántos grupos
hay podemos prescindir de la primera posición y quedan, por tanto, trece elementos, de los cuales tres
son unos y los diez restantes son ceros. Consecuentemente, el número total de grupos es igual al de
permutaciones con repetición de trece elementos donde hay tres iguales entre śı y distintos a otros diez,
también iguales entre śı, por tanto, el número será
PR3,1013
Aśı pues,
CR4,10 = PR
3,10
13 =
13!
3! · 10!
=
(4− 1 + 10)!
(4− 1)! · 10!
=
(
4− 1 + 10
10
)
= 286
Las combinaciones con repetición se definen de la misma forma que las combinaciones simples, salvo que
ahora, no es necesario que todos los elementos sean distintos. Por tanto, dos combinaciones con repetición
serán iguales cuando estén formadas por los mismos elementos repetidos igual número de veces.
5.3.1 Definición
Llamaremos combinaciones con repetición 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 elementos
dados, de modo que dos grupos sean distintos cuando difieran, al menos, en un elemento.
El orden n de una combinación con repetición puede ser mayor que el número de elementos con los cuales
se forma. Cuando n 6 m, entre las combinaciones con repetición figuran las combinaciones simples del
mismo orden.
122
Matemática Discreta Francisco José González Gutiérrez
5.3.2 Número de combinaciones con repetición
El número de combinaciones con repetición de orden n de una colección de m objetos lo simbolizaremos
por CRm,n y lo llamaremos combinaciones con repetición de m elementos tomados n a n. Su valor es
CRm,n =
(
m− 1 + n
n
)
Demostración
Disponemos los elementos que forman cada una de las CRm,n (combinaciones con repetición de m
elementos a1, a2, . . . , am tomados de n en n) de manera que sus ı́ndices respectivos sigan el orden natural.
Entonces, una combinación genérica se puede expresar mediante una sucesión de śı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 dicho
elemento en la combinación considerada; a continuación se escribe otro uno, que representará el elemento
a2 y se le hace seguir de tantos ceros como veces figure dicho elemento en la citada composición y aśı
sucesivamente, conviniendo que si faltase algún elemento se expresará esta circunstancia escribiendo un
uno por cada uno de ellos sin ir seguido de ningún cero.
Por ejemplo, la combinación de orden tres a1a1a3 elegida entre los cuatro elementos a1, a2, a3, a4 se
escribirá:
1001101
De este modo cada combinación que estamosconsiderando viene representada por una expresión que
comienza por uno y contiene en forma ordenada m veces uno y n veces cero.
Rećıprocamente, toda expresión de este tipo representa una de tales combinaciones.
Consecuentemente, para determinar el número de estas combinaciones lo que haremos es calcular el
número de expresiones del tipo 100 . . . . . .. Pues bien, el primer śı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 hacerse
de
Pm−1,nm−1+n
formas distintas. Por tanto,
CRm,n = P
m−1,n
m−1+n =
(m− 1 + n)!
(m− 1)! · n!
=
(
m− 1 + n
n
)
= Cm−1+n,n
�
Ejemplo 5.14 Se dispone de tres bolsas iguales con caramelos de fresa, de menta y de limón. Cada
una de las bolsas contiene, al menos, diez caramelos. Decir de cuántas formas pueden seleccionarse diez
caramelos en los siguientes casos:
(a) sin ninguna restricción.
(b) en cada selección deben figurar, al menos, un caramelo de fresa, dos de menta y tres de limón.
(c) en cada selección han de figurar exactamente, uno de fresa y, al menos, uno de menta.
Solución
(a) Veamos de cuántas formas pueden seleccionarse diez caramelos si no hay ninguna restricción.
Una de las posibles distribuciones de los diez caramelos es
ffmflmmfll
123
Universidad de Cádiz Departamento de Matemáticas
donde f,m y l representan los sabores fresa, menta y limón, respectivamente. Observamos que
si en esta distribución elegida al azar, intercambiamos entre śı uno o varios sabores, la misma no
vaŕıa, sin embargo si cambiamos uno o varios caramelos por otros de distinto sabor, tendremos una
distribución diferente, por tanto, las distribuciones de los diez caramelos son combinaciones con
repetición de orden diez elegidas entre los tres tipos de caramelos distintos. Consecuentemente, los
diez caramelos pueden seleccionarse de
CR3,10 =
(
3− 1 + 10
10
)
=
(
12
10
)
=
12!
10! · 2!
= 66
formas distintas.
(b) En cada selección fijamos un caramelo de fresa, dos de menta y tres de limón, quedarán, por tanto,
cuatro caramelos de entre los tres sabores para elegir, el mismo razonamiento del apartado anterior
nos conduce a que el número de selecciones distintas es
CR3,4 =
(
3− 1 + 4
4
)
=
(
6
4
)
=
6!
4! · 2!
= 15
(c) Ahora fijamos en cada selección un caramelo de fresa y uno de menta. Entonces, quedarán por
elegir ocho caramelos de entre dos sabores, menta y limón, ya que ha de haber, exactamente, uno
de fresa en cada selección, luego el número de selecciones distintas es
CR2,8 =
(
2− 1 + 8
8
)
=
(
9
8
)
=
9!
8! · 1!
= 9
�
Ejemplo 5.15 Hallar de cuántas maneras pueden distribuirse cuatro pelotas de golf en diez cajas
numeradas, si
(a) todas las pelotas son diferentes y en ninguna caja cabe más de una pelota.
(b) las pelotas son indistinguibles y en ninguna caja cabe más 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.
Solución
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 las
pelotas por p1, p2, p3 y p4.
Fijamos las cuatro pelotas y calculamos el número de grupos distintos de cuatro cajas que podemos
elegir entre las diez. El esquema siguiente nos muestra la situación.
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 y
c4, respectivamente. El grupo c1c2c4c3 que tiene las mismas cajas que el anterior, significa que la
pelota 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
Matemática Discreta Francisco José González Gutiérrez
distintos, es decir, el orden el que situemos los elementos en el grupo influye para que éstos sean
diferentes.
Además, el grupo c1c2c5c6 también es distinto de los anteriores, luego el cambio de algún o algunos
elementos también hace distintos a dos grupos.
Consecuentemente, el número total de grupos distintos que pueden formarse son las variaciones de
orden cuatro de diez elementos, de aqúı 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 podŕıa escribirse en la forma:
p p p p
c1 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 son
iguales, luego el orden en que se sitúen los elementos dentro de un grupo es irrelevante. Sin
embargo, el grupo c1c2c5c6 es distinto, es decir, el cambio de algún o algunos elementos si hace a
dos grupos diferentes.
Consecuentemente, el número total de grupos distintos que pueden formarse son las combinaciones
de orden cuatro elegidas entre diez elementos, por tanto, en este caso, hay
C10,4 =
(
10
4
)
=
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 aśı con todos los que
repitan caja. El razonamiento es idéntico al del apartado (a) con la salvedad de en que cada caja
podemos introducir cuántas pelotas queramos, por tanto las variaciones de orden cuatro elegidas
entre las diez cajas serán con repetición, es decir, el número de distribuciones distintas es
V R10,4 = 104 = 10000
(d) Ahora son, otra vez, todas las pelotas iguales. El esquema es,
p p p p
c1 c1 c1 c1
c1 c1 c2 c2
c1 c2 c1 c2
...
...
...
...
125
Universidad de Cádiz Departamento de Matemáticas
Ahora los grupos c1c1c2c2 y c1c2c1c2 son iguales, ya que ambos significan lo mismo, es decir, dos
pelotas 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 caja
c1 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 algún o algunos elementos si hace distintos a dos grupos.
Consecuentemente, en este caso, hay
CR10,4 =
(
10− 1 + 4
4
)
=
(
13
4
)
=
13!
4! · 9!
= 715
formas distintas de distribuir las cuatro pelotas en las diez cajas. �
Ejemplo 5.16 Dada la siguiente lista de números:
−5,−4,−3,−2,−1, 1, 2, 3, 4
se seleccionan cuatro de ellos.
(a) ¿De cuántas maneras pueden hacerse las selecciones de modo que el producto de los cuatro resulte
positivo y
(a.1) los números sean distintos?
(a.2) cada número pueda seleccionarse hasta cuatro veces?
(a.3) cada número pueda seleccionarse, a lo sumo, tres veces?
(b) Contéstese el apartado (a) siendo el producto de los cuatro números, negativo.
Solución
Sean a, b, c y d los cuatro números, las distintas opciones que pueden presentarse atendiendo al signo del
producto de los cuatro se reflejan en el cuadro siguiente:
opciones a b c d Signo del producto
1 + + + + +
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 números son distintos.
− En la primera opción sólo hay una posibilidad ya que hay, únicamente cuatro números
positivos.
− En la tercera opción podremos elegir dos números de entre los cuatro positivos y dos de
entre los cuatro negativos.
Obsérvese que para el signo del producto el orden en que elijamos los números es irrele-
vante, luego dos grupos serán distintos cuando cambiemos algún(os) elementos, por tanto,
serán combinaciones de orden dos tanto para los cuatro positivos, como para los cinco
negativos.
126
Matemática Discreta Francisco José González Gutiérrez
Los dos positivospueden elegirse, pues, de C4,2 formas y para cada una de ellas hay C5,2
maneras diferentes de elegir los dos negativos. El número de formas de hacer la selección
de los números en la tercera opción es, por la regla del producto,
C4,2 · C5,2
− Para la quinta opción, los cuatro números han de ser negativos, luego razonando igual
que en la opción anterior y teniendo en cuenta que hay cinco números negativos, habrá
C5,4
formas distintas de seleccionar los cinco números negativos y que el producto de ellos sea
positivo.
Consecuentemente, el número de maneras distintas en que pueden hacerse las selecciones de
modo que el producto de los cuatro números resulte positivo es, por la regla de la suma,
1 + C4,2 · C5,2 + C5,4 = 1 +
(
4
2
)
·
(
5
2
)
+
(
5
4
)
= 66
(a.2) Cada número puede seleccionarse hasta cuatro veces. El razonamiento es idéntico al del
apartado anterior con la salvedad de que al poder repetirse los números las combinaciones
serán con repetición.
− En la opción primera las selecciones pueden hacerse de
CR4,4
formas distintas.
− En la tercera opción, las formas distintas de hacer las selecciones es
CR4,2 · CR5,2
− Para la quinta opción las selecciones pueden hacerse de
CR5,4
maneras diferentes.
Consecuentemente, el número de formas diferentes en que pueden seleccionarse cuatro números
de entre los dados de forma que el producto sea positivo, pudiendo seleccionar cada número
hasta cuatro veces es
CR4,4 + CR4,2 · CR5,2 + CR5,4 = 180
(a.3) Cada número puede seleccionarse, a lo sumo, tres veces
Al no poder seleccionar ninguno de los números cuatro veces, el resultado seŕıa igual al anterior
descontando los productos en los que un número se repita cuatro veces que son cuatro para
los 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, según el cuadro del principio, la 2 y la 4.
(b.1) Los números son diferentes.
− Para la segunda opción hay que elegir tres números positivos y uno negativo. Los tres
positivos pueden elegirse de C4,3 formas distintas y para el negativo hay cinco opciones
ya que son cinco los propuestos. Por la regla del producto, la elección puede hacerse de
5 · C4,3 formas distintas.
− Para la cuarta opción, hay que elegir un número positivo y tres negativos. Razonando
exactamente igual, la elección puede hacerse de 4 · C5,3 formas distintas.
127
Universidad de Cádiz Departamento de Matemáticas
Consecuentemente, el número de maneras en que puede hacerse la selección de los cuatro
números de forma que todos sean distintos y el producto resulte negativo es, por la regla de
la suma,
5 · C4,3 + 4 · C5,3 = 5
(
4
3
)
+ 4
(
5
3
)
= 5
4!
3! · 1!
+ 4
5!
3! · 2!
= 60
(b.2) Cada número puede seleccionarse hasta cuatro veces.
− Para la opción 2, los tres positivos pueden elegirse de CR4,3 formas distintas y para el
negativo, al igual que en el apartado anterior, hay cinco opciones. La elección puede
hacerse, por tanto, de 5 · CR4,3 formas distintas.
− Para la cuarta opción y razonando exactamente igual, la elección puede hacerse de 4·CR5,3
formas distintas.
Por la regla de la suma, habrá
5 · CR4,3 + 4 · CR5,3 = 5 ·
(
4− 1 + 3
3
)
+ 4 ·
(
5− 1 + 3
3
)
= 240
formas distintas de hacer la selección en la forma pedida.
(b.3) El resultado es el mismo que el del apartado anterior, ya que no han podido seleccionarse
nunca los cuatro números.
�
Ejemplo 5.17 Resolver las siguientes cuestiones:
(a) ¿De cuántas formas puede distribuirse cinco dulces diferentes entre diez personas si ninguna de
ellas puede recibir más de uno?
(b) ¿De cuántas formas pueden distribuirse cinco dulces diferentes entre diez personas si cualquiera de
ellas puede recibir cualquier número de dulces?
(c) ¿De cuántas formas puede distribuirse cinco manzanas idénticas entre diez personas si ninguna de
ellas puede recibir más de una?
(d) ¿De cuántas formas pueden distribuirse cinco manzanas idénticas entre diez personas si cualquiera
de ellas puede recibir cualquier número de manzanas?
Solución
(a) Sea
D = {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 situación que se
plantea.
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
Matemática Discreta Francisco José González Gutiérrez
− Los grupos (1) y (2) son distintos ya que en el primero a la persona p1 le corresponde el dulce
d1 y a la p3 el d1 y en el segundo es al contrario, por tanto, el orden influye en el hecho de
que dos grupos sean distintos.
− El grupo (3) es, asimismo, distinto de los anteriores ya que hemos cambiado las personas, luego
el cambio de algún o algunos elementos también es relevante para discernir si dos grupos son
iguales o distintos.
Consecuentemente, los distintos grupos son las variaciones de orden cinco elegidas de entre las diez
personas y el número de formas pedido es:
V10,5 = 10 · 9 · 8 · 7 · 6 = 30240
(b) La situación es idéntica a la del caso anterior, aunque ahora las variaciones de orden cinco elegidas
entre las diez personas, serán con repetición. El número total de formas distintas será, por tanto,
V R10,5 = 105 = 100000
(c) Como ahora las manzanas son idénticas, el esquema seŕı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 algún o algunos
elementos es lo único que influye para que dos grupos sean distintos. Consecuentemente, éstos son
combinaciones de orden cinco elegidas entre de las diez personas, aśı pues, habrá
C10,5 =
(
10
5
)
=
10!
5! · 2!
= 15120
formas distintas de distribuir las manzanas.
(d) Dado que cada persona puede recibir cualquier número de manzanas, el planteamiento seria idéntico
al del apartado anterior, aunque en este caso los grupos seŕıan combinaciones con repetición de
orden cinco elegidas entre las diez personas, luego
CR10,5 =
(
10− 1 + 5
5
)
=
(
14
5
)
=
14!
5! · 9!
= 2002
será el total de formas en que pueden distribuirse cinco manzanas idénticas entre las diez personas
si cualquiera de ellas puede recibir cualquier número de manzanas. �
129