Combinatoria

Leonardo Alex Tapia Quiróz

July 31, 2021

Leonardo Alex Tapia Quiróz Combinatoria July 31, 2021 1 / 18

Introducción a la Combinatoria
¿Qué es la Combinatoria?
La combinatoria es una rama de la matemática perteneciente al área de
matemáticas discretas que estudia la enumeración, construcción y
existencia de propiedades de configuraciones que satisfacen ciertas
condiciones establecidas

Principio de multiplicación
Sea A = {a1 , a2 , a3 , a4 , ...} un conjunto de m elementos y
B = {b1 , b2 , b3 , b4 , ...} un conjunto de n elementos, si lo que buscamos es
tomar aleatoriamente un elemento de cada conjunto para un fin
determinado, entonces el número de alternativas está dado por: m · n

Ejemplo
Lucio quiere comprar comprar libros de matemáticas y le ofrecen de 3
diferentes autores y de 4 editoriales diferentes cada uno.¿Cuántas opciones
de compra tiene Lucio?
Leonardo Alex Tapia Quiróz Combinatoria July 31, 2021 2 / 18
Principio de Multiplicación y Adición

Solución
Tenemos dos conjuntos:
A = {a1 , a2 , a3 } (Autores)
E = {e1 , e2 , e3 , e4 }(Editoriales)
Lucio debe elegir uno de cada conjunto es decir, un autor y una editorial.
Entonces por el principio de multiplicación tendrá:3 · 4 = 12 opciones de
compra.

Principio de Adición
Si dos decisiones son mutuamente excluyentes (que no pueden ocurrir
ambas a la vez), donde la primera decisión se puede tomar de m maneras
y la segunda decisión se puede tomar de n maneras entonces una o la otra
se puede tomar de m + n maneras.

Leonardo Alex Tapia Quiróz Combinatoria July 31, 2021 3 / 18

Principio de Adición y Factoriales

Ejemplo
Una persona quiere viajar de A a B en tren o en bus. Si hay cuatro rutas
para el tren y 5 rutas para el bus. ¿De cuántas formas puede hacer el viaje?

Solución
Claramente si la persona viaja en tren, no puede viajar en bus a la vez, o
viceversa.La elección es mutuamente excluyente. Por tanto, por el
principio de adición, la persona puede viajar de 4 + 5 = 9 formas.

Factorial de un número
Sea n un número entero positivo, el factorial de n, que se denota por n!,
es igual al producto de todos los naturales consecutivos desde 1 hasta n.

n! = n · (n − 1) · (n − 2) · ... · 3 · 2 · 1

Leonardo Alex Tapia Quiróz Combinatoria July 31, 2021 4 / 18

Factoriales y Permutaciones
Propiedades de los Factoriales
1) 0! = 1 (Por definición)
2) n! = n · (n − 1)! o (n + 1)! = (n + 1) · n!
3) (n + m)! 6= n! + m!
4) (n · m)! 6= n! · m!

Permutaciones
Se llaman permutaciones a las diversas ordenaciones que pueden formarse
con todos los elementos diferentes de un conjunto.

Permutaciones Simples
Son los diferentes arreglos que se pueden formar con todos los elementos
de un conjunto , cuya diferencia entre estos arreglos está dada solamente
en el orden. El número de permutaciones que pueden formarse con n
objetos distintos es:
Pn = n!
Leonardo Alex Tapia Quiróz Combinatoria July 31, 2021 5 / 18
Permutaciones
Ejemplo
¿Cuántos números de 4 dı́gitos podemos formar con los números 2,4,6 y 7?

Solución
Todos los números formados serán permutaciones de los de los 4 números
dados.
Por lo tanto tendremos 4! = 4 · 3 · 2 · 1 = 24 números de 4 dı́gitos que
podemos formar con los números 2,4,6 y 7.

Permutaciones con repetición

Son ordenaciones diferentes que pueden formarse con n elementos de un
conjunto, de los cuales uno de ellos se repite a veces, otro b veces y ası́
todos los elementos que se repiten. El número de permutaciones está dado
por:
n!
PRna,b,c,..,z =
a! · b! · c! · ... · z!
Leonardo Alex Tapia Quiróz Combinatoria July 31, 2021 6 / 18
Permutaciones y Variaciones

Ejemplo
De cuántas formas diferentes pueden ordenarse las letras de la palabra
osteoporosis

Solución
Se trata de permutar 12 letras de las cuales 4 son la letra ”o”, 3 son la
letra ”s”. Por lo tanto se tiene:
4,3 12!
PR12 = = 3326400
4! · 3!

Variaciones
Son arreglos que se hacen tomando un número determinado de elementos
de un conjunto. Donde el orden importa.

Leonardo Alex Tapia Quiróz Combinatoria July 31, 2021 7 / 18

Variaciones
Variaciones simples
Son las diferentes ordenaciones que se pueden hacer con r objetos tomados
de n objetos distintos de un conjunto. El número de ordenaciones que se
puede hacer con r elementos de un conjunto de n elementos está dado por:
n!
Vnr =
(n − r )!

Ejemplo
¿Cuántas variaciones con las letras x,w,g tomadas de 2 en 2 habrá?

Solución
Las variaciones serán: xw, xg, wg, gw, gx, wx. Ahora por fórmula:
3!
V23 = =6
(3 − 2)!
Leonardo Alex Tapia Quiróz Combinatoria July 31, 2021 8 / 18
Variaciones

Variaciones con repetición

Son aquellos arreglos o variaciones de r obejtos de un conjunto de n
elementos, cada objeto puede repetirse una, dos o más veces en cualquier
ordenamiento. El número de todos los arreglos con repetición de r objetos
de un conjunto de n elementos estádado por:

VRnr = nr

Ejemplo
Hallar cuántos números de 4 dı́gitos pueden formarse con los números
2,4,7,8,1 si los dı́gitos pueden repetirse.

Leonardo Alex Tapia Quiróz Combinatoria July 31, 2021 9 / 18

Variaciones y Combinaciones

Solución
Cómo los dı́gitos pueden repetirse habrán números como 2447, 7777,
8811, etc.
Luego los números formados son:

VR54 = 54 = 625

Combinaciones
Se denominan combinaciones a los grupos diferentes que pueden formarse
tomando algunos objetos de un conjunto, donde el orden no importa.

Combinaciones simples
Son las diversas formas de selección de r objetos de un conjunto de n
elementos, de manera que no hay grupos con los mismos elementos.

Leonardo Alex Tapia Quiróz Combinatoria July 31, 2021 10 / 18

Combinaciones

El número de combinaciones de r elementos de un conjunto de n

elementos está dado por:
 
r n n!
Cn = =
r r !(n − r )!

Números combinatorios
Son aquellos números cuyo valor viene dado por la expresión:
 
n n!
=
r r !(n − r )!

Estos números permiten calcular el número de formas de elegir r objetos

de n posibles.

Leonardo Alex Tapia Quiróz Combinatoria July 31, 2021 11 / 18

Números combinatorios

Propiedades de los números combinatorios

1)  
n
=1
0
2)  
n
=1
n
3)      
n n−1 n−1
= +
r r r −1
4)    
n n
=
r n−r

Leonardo Alex Tapia Quiróz Combinatoria July 31, 2021 12 / 18

Triángulo de Pascal

Leonardo Alex Tapia Quiróz Combinatoria July 31, 2021 13 / 18

Combinaciones

Ejemplo
¿Cuántos grupos de 5 alumnos se pueden formar de 20 alumnos?

Solución
Cómo no importa el orden, entonces se trata de combinaciones de 20
alumnos tomados de 5 en 5. Por tanto, el número de posibles grupos que
pueden formarse es:
 
5 20 20!
C20 = = = 15504
5 5!(20 − 5)!

Combinaciones con repetición

Es el número de cobinaciones de r objetos de los n objetos dados, de
manera que estos objetos pueden repetirse, que está dado por:

Leonardo Alex Tapia Quiróz Combinatoria July 31, 2021 14 / 18

Combinaciones y Sumatoria
 
n+r −1 (n + r − 1)!
CRnr = =
r r !(n − 1)!

Ejemplo
Las combinaciones con repetición de los cuatro elementos a, b, c y d
tomados de dos en dos son:
(a, a), (a, b), (a, c), (a, d), (b, c), (b, b), (b, d), (c, c), (c, d), (d, d) se tiene
10 combinaciones diferentes. Según la formula se tiene:
 
4+2−1 (4 + 2 − 1)!
CR42 = = = 10
2 2!(4 − 1)!

Sumatoria
Es laPsuma de una sucesión de terminos en una forma abreviada denotada
por . Por ejemplo la suma de n terminos tales como
a1 + a2 + a3 + ... + an puede repersentarse por:
Leonardo Alex Tapia Quiróz Combinatoria July 31, 2021 15 / 18
Sumatorias y Productorias
n
X
ai = a1 + a2 + a3 + ... + an
i=1

Donde la letra i es el ı́ndice de la suma, toma sucesivamente los valores

enteros positivos de 1 a n.

Ejemplo

4
X
(2i−1) = (2(1)−1)+(2(2)−1)+(2(3)−1)+(2(4)−1) = 1+3+5+7 = 16
i=1

Productorias
Es la que representa
Q al producto de una sucesión de términos en una forma
breve. Se denota , por ejemplo el producto de n términos se puede
representar por:
Leonardo Alex Tapia Quiróz Combinatoria July 31, 2021 16 / 18
Productorias

n
Y
ai = a1 · a2 · a3 · ... · an
i=1

Ejemplo

4
Y
(8 − i) = (8 − 0) · (8 − 1) · (8 − 2) · (8 − 3) · (8 − 4) = 8 · 7 · 6 · 5 · 4 = 6720
i=0

Leonardo Alex Tapia Quiróz Combinatoria July 31, 2021 17 / 18

Combinatoria

Leonardo Alex Tapia Quiróz Combinatoria July 31, 2021 18 / 18