Facultad Regional San Nicolás
Tecnicatura Universitaria en Programación
Unidad Nº 6
Cálculo combinatorio.
Profesores: Lautaro Martí,
Leonardo Pons,
Ezequiel Ramírez.
2022
MATEMÁTICA 1
Tecnicatura Universitaria en Programación
FRSN
Introducción
En los últimos años el interés por la Combinatoria ha aumentado
considerablemente.
En gran parte esto se debe al desarrollo de la Ciencia de la Computación, en la cual juega
un rol central el concepto de algoritmo. Para estimar la eficiencia de un algoritmo es
necesario contar el número de veces que se ejecutara cada paso del mismo, y esto es un
típico problema combinatorio. Asimismo, la Combinatoria tiene aplicaciones en otras
áreas.
Reseña histórica
Se puede considerar que la combinatoria surge en el siglo XVII con
los trabajos de Blaise Pascal y de Pierre Fermat sobre la teoría de
juegos de azar. Comenzaron a recoger muestras de experimentos
que realizaban en las mesas de juegos y a registrarlos
estadísticamente para estudiar las leyes y regularidades bajo las cuales se regían. Estos
trabajos formaron los fundamentos de la teoría de la probabilidad. Posteriormente el
término “combinatoria” tal y como lo usamos actualmente fue introducido por
Wihem Leibniz, el cual se fue consolidando con los aportes de Jacob Bernoullii.
3
MATEMÁTICA 1
Tecnicatura Universitaria en Programación
FRSN
Combinatoria
¿Qué es la Combinatoria?
La Combinatoria es una rama de la Matemática que estudia la enumeración, construcción y
existencia de propiedades que satisfacen ciertas condiciones establecidas. Además, analiza
las ordenaciones o agrupaciones de un determinado número de elementos de un conjunto
finito.
Situación inicial
Diez estudiantes decidieron celebrar la terminación de sus estudios en la escuela
secundaria con un almuerzo en un restaurante. Una vez reunidos, se entabló entre ellos
una discusión sobre el orden en que habían de sentarse a la mesa. Unos propusieron que la
colocación fuera por orden alfabético; otros, con arreglo a la edad; otros, por los resultados
de los exámenes; otros, por la estatura, etc. La discusión se prolongaba, la sopa se enfrió y
nadie se sentaba a la mesa. Los reconcilió el camarero, dirigiéndoles las siguientes
palabras:
Jóvenes amigos, dejen de discutir. Siéntense a la mesa en cualquier orden y escúchenme
Todos se sentaron sin seguir un orden determinado. El camarero continuó:
Que uno cualquiera anote el orden en que están sentados ahora. Mañana vienen a comer y
se sientan en otro orden. Pasado mañana vienen de nuevo a comer y se sientan en orden
distinto, y así sucesivamente hasta que hayan probado todas las combinaciones posibles.
Cuando llegue el día en que ustedes tengan que sentarse de nuevo en la misma forma que
ahora, les prometo solemnemente, que en lo sucesivo les convidaré a comer gratis
diariamente, sirviéndoles los platos más exquisitos y escogidos.
La proposición agradó a todos y fue aceptada. Acordaron reunirse cada día en aquel
restaurante y probar todos los modos distintos, posibles, de colocación alrededor de la
mesa, con el objeto de disfrutar cuanto antes de las comidas gratuitas.
Sin embargo, no lograron llegar hasta ese día. Y no porque el camarero no cumpliera su
palabra sino porque el número total de combinaciones diferentes alrededor de la mesa es
extraordinariamente grande. Éstas son exactamente
3.628.800. Es fácil calcular, que este número de días son casi 10.000 años.
4
MATEMÁTICA 1
Tecnicatura Universitaria en Programación
FRSN
Técnicas de conteo
¿Cuántas veces nos vemos frente a un problema donde debemos contar y agrupar
elementos de un conjunto y no sabemos cómo abordarlo? A continuación, se presentan
técnicas de conteo, que no son ni más ni menos que herramientas útiles para hacer fácil lo
que en un principio puede resultar difícil.
Las técnicas de conteo son diferentes estrategias Matemáticas que permiten y
facilitan determinar el número total de resultados a partir de combinaciones de conjuntos.
Se utilizan en situaciones en las que se busca (como su nombre lo indica) contar, y resulta
imposible o difícil realizarlo de forma manual.
Principio de la multiplicación
Uno de los principios básicos, que permiten hallar solución en problemas de conteo
es el principio de la multiplicación.
En muchos casos el número elementos no es muy grande y así la enumeración o
cuenta directa no resulta difícil. Sin embargo, surgen problemas cuando la cuenta directa
se convierte en una imposibilidad práctica. En tales casos se emplea el Análisis
Combinatorio, que podría llamarse “una sofisticada forma de contar”.
Ejemplo1: Para hacer un viaje desde la ciudad A hasta ciudad C necesito pasar por la
ciudad B. Y para ello cuento con diferentes medios de transportes. Para ir a la ciudad B,
desde la ciudad A puedo elegir ir en remis, taxi o colectivo. Mientras que desde la ciudad B
hasta la ciudad destino C puedo decidirme por tomar un tren o un avión. Me surge la
pregunta ¿De cuántas formas diferentes se puede viajar desde la ciudad A hasta la ciudad
C?
5
MATEMÁTICA 1
Tecnicatura Universitaria en Programación
FRSN
Observación: Un diagrama, llamado diagrama de árbol (citado de esa forma debido
a su apariencia), se emplea frecuentemente en distintas situaciones, sobre todo en
problemas con gran complejidad. Y si bien en esta práctica no es necesario, facilitará la
interpretación como se muestra a continuación:
6
MATEMÁTICA 1
Tecnicatura Universitaria en Programación
FRSN
En este diagrama cada segmento representa un viaje entre dos de las ciudades
señaladas en el problema.
Para realizar el viaje completo es necesario seleccionar dos segmentos. Puede
observarse con claridad que existen tantas posibilidades como segmentos hay entre la
ciudad A y la ciudad C; es decir 6. A este resultado se llega fácilmente aplicando el Principio
Multiplicativo. (3x2=6)
Concluyendo que se puede realizar el viaje de 6 formas diferentes. (remis-tren;
remis-avión; taxi-tren; taxi-avión; colectivo-tren y colectivo-avión)
Por lo tanto, el Principio me asegura que:
Si una cosa (decisión, operación, acción) puede realizarse en n1 maneras diferentes y
después de esto una segunda cosa puede realizarse en n2 maneras diferentes, y así
sucesivamente hasta una k-ésima cosa puede realizarse en nk maneras diferentes, entonces
todas las k cosas pueden realizarse en el orden especifico en n1xn2x…xnk maneras
diferentes.
Ejemplo 2: Imaginá que tenés 2 pantalones (uno negro y uno azul), 3 remeras (una roja,
una blanca y una verde) y 2 pares de zapatillas (un par blanco y un par negro).
¿De cuántas formas distintas podrías vestirte?
A través de un Diagrama de árbol expresaremos la situación:
7
MATEMÁTICA 1
Tecnicatura Universitaria en Programación
FRSN
El resultado es: 2 . 3 . 2 = 12. Es decir que con dos pantalones, tres
remeras y dos pares de zapatillas podrás vestirte de 12 maneras diferentes.
8
MATEMÁTICA 1
Tecnicatura Universitaria en Programación
FRSN
ACTIVIDAD 1
Teniendo en cuenta la siguiente tabla ¿De cuántas maneras distintas puedo vacacionar?
Principio de la adición
Otro de los principios básicos, que permiten hallar solución en problemas de conteo
es el principio de la adición. El cual enuncia que: “Si un suceso A puede ocurrir de m
maneras y otro suceso B puede ocurrir de n maneras, y no pueden ocurrir ambos
simultáneamente, entonces el suceso `A o B' puede ocurrir de m+n maneras".
(En los problemas de conteo, en gral, la palabra "o" se traduce en suma)
Ejemplo 1: Existen 3 profesores y 2 profesoras que imparten la materia de cálculo.
Un estudiante puede elegir un profesor de 3 + 2 = 5 formas.
Ejemplo 2: En una biblioteca hay 3 libros de novelas de misterio diferentes, 5
novelas de romance y 4 novelas de aventura diferentes.
Existen 3 + 5 + 4 = 12 formas de escoger una novela.
9
MATEMÁTICA 1
Tecnicatura Universitaria en Programación
FRSN
ACTIVIDAD 2
Cinco empresas de transporte terrestre tienen servicio diario entre Rosario y San
Carlos de Bariloche. Tres empresas de aviación tienen vuelo diario entre Rosario y San
Carlos de Bariloche.
¿Cuántas maneras existen de ir de Rosario a San Carlos de Bariloche en avión o en
colectivo?
Importante: DEFINICION DE FACTORIAL.
La operación de factorial aparece en muchas áreas de las matemáticas,
particularmente en combinatoria y análisis matemático. De manera fundamental el
factorial de n representa el número de formas distintas de ordenar n objetos distintos
(elementos sin repetición). Este hecho ha sido conocido desde hace varios siglos, en el siglo
XII por los estudiosos hindúes.
Para un entero n ≥ 1, n factorial, se expresa n! y se define por:
n! = (n) x (n −1) x (n − 2) x...x 3 x 2 x 1
El factorial de cero se define así: 0! = 1
Es decir que el factorial de un entero positivo n, se define en principio como el
producto de todos los números enteros positivos desde 1 hasta n. Por ejemplo: 6!=
1x2x3x4x5x6 =720
Observación: Podemos calcular el factorial de un número mediante la calculadora
presionando la tecla adecuada, que dependerá del modelo que utilicemos. A continuación,
un ejemplo:
10
MATEMÁTICA 1
Tecnicatura Universitaria en Programación
FRSN
Dado un conjunto de n objetos existen ciertas formas típicas de agrupar,
distribuir o seleccionar sus elementos. Y para saber qué caso de combinatoria estamos
tratando hay que determinar tres características:
*Si influye o no el orden de los elementos.
*Si el número de elementos disponibles en el conjunto(n) es igual o menor de
los presentes en cada suceso (r).
*Si se producen o no repeticiones en el suceso.
La combinatoria estudia tres tipos de casos con elementos finitos:
combinaciones, variaciones y permutaciones (con y sin repetición).
11
MATEMÁTICA 1
Tecnicatura Universitaria en Programación
FRSN
Permutaciones sin repetición
Las Permutaciones sin repetición de n elementos (de orden n), son los distintos
grupos de n elementos diferentes que se pueden hacer, de forma que dos grupos se
diferencian únicamente en el orden de colocación de los elementos. Se representa
por Pn.
Hay tres condiciones en la permutación sin repetición:
Importa el orden.
No hay elementos repetidos.
Participan todos los elementos en los ordenamientos.
Ejemplo 1:¿Cuántas palabras de 3 letras podemos armar con las letras de la
palabra sol? Respondamos este interrogante desde diferentes estrategias.
Podemos mover imaginariamente las tarjetas y escribimos todas las posibilidades.
12
MATEMÁTICA 1
Tecnicatura Universitaria en Programación
FRSN
Sabemos, de esta manera, que podemos escribir 6 palabras código con las letras
de la palabra sol.
*Otra estrategia es llenar casilleros.
Podemos llenar el primer casillero de 3 maneras (con la letra S, la letra O o la letra
L). Una vez completo el primer casillero, nos quedan 2 posibilidades para
llenar el segundo. Y, finalmente, nos quedará 1 posibilidad para completar el
último casillero.
13
MATEMÁTICA 1
Tecnicatura Universitaria en Programación
FRSN
Para resolver este problema realizamos la multiplicación 3 . 2 . 1 = 6.
Nuevamente, llegamos a la misma respuesta: se pueden escribir 6 palabras código
con las letras de la palabra sol.
*Otra forma es mediante un diagrama de árbol donde se ven también las 6
posibilidades.
Ejemplo 2: Ahora pensemos ¿cuántos números de 4 cifras pueden armarse con los
dígitos 1, 2, 3 y 4 sin repetir ninguna cifra? Rta= 1 . 2 .3 .4 = 24
14
MATEMÁTICA 1
Tecnicatura Universitaria en Programación
FRSN
Concluimos que:
Las Permutaciones sin repetición se resuelven usando la expresión:
ACTIVIDAD 3
¿De cuantas maneras distintas podemos formar palabras código con las letras P,
A, T, O, sin repetir ninguna?
Permutaciones con repetición
Las permutaciones con repetición son las posibles ordenaciones de una secuencia
de n elementos entre los que hay algunos repetidos (uno se repite x veces, otro y veces,
otro z veces… etc.).
Hay tres condiciones en la permutación con repetición:
Importa el orden.
Hay elementos repetidos.
Participan todos los elementos en los ordenamientos.
Las Permutaciones con repetición se resuelven usando la expresión:
15
MATEMÁTICA 1
Tecnicatura Universitaria en Programación
FRSN
Ejemplo 1: En una urna, hay 5 bolas del mismo tamaño y peso, de los cuales, 3 son
rojas y 2 son azules. ¿De cuántas maneras se pueden extraer una a una las bolas de la
urna?
En cada forma de extraer las bolas, importa el orden, hay elementos repetidos y
participan todos los elementos (bolas), por ello, usaremos la fórmula de permutación con
elementos repetidos.
Número de bolas rojas: 3.
Número de bolas azules: 2.
Número total de elementos: n = 3+2 ➜ n=5
En total, se pueden extraer las bolas de 10 formas diferentes.
Ejemplo 2: Con las cifras 2,2,2,3,3,3,3,4,4 ; ¿Cuántos números de nueve cifras se
pueden formar?
Primero formemos grupos con los elementos de la misma clase. El primero es
formado por el valor 2, el segundo por el valor 3 y el ultimo por el valor 4. Si
denotan el número de valores en cada grupo tenemos que
Podemos llegar a la conclusión a través de la formula:
16
MATEMÁTICA 1
Tecnicatura Universitaria en Programación
FRSN
ACTIVIDAD 4
En el palo de señales de un barco se pueden izar tres banderas rojas, dos azules y
cuatro verdes. ¿Cuántas señales distintas pueden indicarse con la colocación de las nueve
banderas?
Variaciones sin repetición
Las variaciones sin repetición de n elementos tomados de r en r : posibles muestras
ordenadas de r elementos distintos que se pueden extraer de un conjunto de n elementos,
siendo r≤n.
Hay tres condiciones en las Variaciones sin repetición:
Importa el orden.
No hay elementos repetidos.
Se agrupan de todas las formas parte del total.
Las Variaciones sin repetición se resuelven usando la expresión:
17
MATEMÁTICA 1
Tecnicatura Universitaria en Programación
FRSN
Observación: Nótese que:
Ejemplo 1: En una carrera de 100 metros participan 8 corredores. ¿De cuántas
maneras diferentes se podrán repartir las medallas de oro, plata y bronce?
Rta:
n = Número de corredores que participan = 8
r = Número de medallas en cada variación = 3
Las medallas de oro, plata y bronce se pueden repartir de 336 maneras diferentes.
Ejemplo 2: ¿Cuántas elecciones distintas puede haber en un grupo de 15 personas donde
se va a elegir un presidente, un vicepresidente, un secretario, un tesorero, un contador, un
fiscal y un vocal?
Rta:
15!
= 32432400
(15 − 7)!
La cantidad de elecciones distintas podrán ser 32432400.
ACTIVIDAD 5
¿De cuántas maneras diferentes se puede contestar un examen de 10 preguntas, si solo
hay que contestar 4 de ellas?
18
MATEMÁTICA 1
Tecnicatura Universitaria en Programación
FRSN
Variaciones con repetición
Las variaciones con repetición de n elementos tomados de r en r: posibles muestras
ordenadas de r elementos no necesariamente distintos que se pueden extraer de un
conjunto de n elementos.
Hay tres condiciones en las Variaciones con repetición:
Importa el orden.
Hay elementos repetidos.
Se agrupan de todas las formas parte del total.
Las Variaciones con repetición se resuelven usando la expresión:
Ejemplo 1: ¿Cuántos números de tres cifras se pueden formar con los dígitos: 1, 2, 3, 4, 5 ?
Aquí logramos ver que hay cinco elementos n = 5 colocados en tres posiciones r = 3
aplicando la fórmula obtenemos que:
Por lo tanto, se pueden formar 125 números de tres cifras con los dígitos indicados.
Observa que sí importa el orden, ya que por ejemplo 123 es distinto al 132, y además es
posible la repetición ya que el número 223 es uno de los 125 posibles de construir.
Ejemplo 2: Sabiendo que existen 27 letras en el abecedario, ¿cuántas formas diferentes
hay de escribir grupos de tres letras (pudiendo repetirlas)? Por ejemplo JEJ, AYT, BBC...
19
MATEMÁTICA 1
Tecnicatura Universitaria en Programación
FRSN
Rta:
n= 27
r = 3 letras en cada grupo
Se pueden escribir 19683 grupos diferentes.
ACTIVIDAD 6
¿cuántas formas diferentes hay de escribir grupos de cuatro números (pudiendo
repetirlos)? Por ejemplo 0157, 9945, 8118, 4505, 0026...
Combinaciones sin repetición
Las combinaciones de n elementos tomados de r en r: posibles muestras sin orden
de r elementos distintos que se pueden extraer de un conjunto de n elementos r≤n.
Hay condiciones en las Combinaciones sin repetición:
No importa el orden.
No hay elementos repetidos.
Las Combinaciones sin repetición se resuelven usando la expresión:
20
MATEMÁTICA 1
Tecnicatura Universitaria en Programación
FRSN
Ejemplo 1: Se tienen los 4 ases de una baraja y se quieren tomar al azar dos cartas.
¿Cuántas son las combinaciones que pueden resultar?
n = 4 = Número cartas para escoger
r = 2 = Número de cartas en cada combinación
Rta:
Pueden resultar 6 combinaciones posibles de 2 cartas con los 4 ases. Grupos: (trébol
, Corazones) (trébol , Diamantes) (trébol , Pica) (Corazones, Diamantes)
(Corazones , Pica) (Diamantes , Pica)
Ejemplo 2: Un alumno se decide presentar 3 de las 5 evaluaciones ( Aritmética,
Español, Inglés, Religión, Sociales) que tiene pendiente en su colegio.
¿De cuántas maneras diferentes puede elegir esas evaluaciones?
Rta:
n = 5 = Número de evaluaciones para escoger
r = 3 = Número de evaluaciones en cada combinación.
Hay 10 maneras posibles de elegir las 3 evaluaciones, entre las 5
Elecciones: ( Aritmética, Español, Inglés ), ( Aritmética, Español, Religión ),
(Aritmética, Español, Sociales ), ( Aritmética, Inglés, Religión ), ( Aritmética, Inglés, Sociales),
( Aritmética, Religión, Sociales ), ( Español, Inglés, Religión ), ( Español, Inglés, Sociales ),
(Español, Religión, Sociales ), ( Inglés, Religión, Sociales )
21
MATEMÁTICA 1
Tecnicatura Universitaria en Programación
FRSN
ACTIVIDAD 7
Se dispone de 12 bebidas distintas para formar tragos.
¿Cuántos combinaciones distintas se pueden preparar utilizando cada vez 4 de las
12 bebidas?
Combinaciones con repetición
Las combinaciones con repetición de n elementos tomados de r en r: posibles muestras no
ordenadas de r elementos no necesariamente distintos que se pueden extraer de un
conjunto de n elementos.
Hay condiciones en las Combinaciones con repetición:
No importa el orden.
Hay elementos repetidos.
Las Combinaciones con repetición se resuelven usando la expresión:
(𝑛 + 𝑟 − 1)!
=
𝑟! (𝑛 − 1)!
22
MATEMÁTICA 1
Tecnicatura Universitaria en Programación
FRSN
Ejemplo 1: En una heladería tienen 12 sabores distintos.
¿Cuántos cucuruchos de 2 sabores distintos se pueden elegir, sabiendo que puedo repetir
los gustos? (Por ejemplo, puedo pedir que un cucurucho sólo tenga chocoate)
(12+2−1)!
Rta = = 78
2!(12−1)!
Puedo elegir de 78 formas los sabores.
Ejemplo 2: ¿Cuántos grupos podemos formar al extraer 4 cartas de una baraja
española de 40, con reposición?
130320960
Rta: = = 1086008
120
Puedo formar 1086008 de grupos.
ACTIVIDAD 8
Una pizzería ofrece seis ingredientes para añadir a una base de mozzarella y
tomate. Si la oferta consiste en añadir dos ingredientes (que se pueden repetir), ¿cuántas
pizzas diferentes se pueden elaborar?
23
MATEMÁTICA 1
Tecnicatura Universitaria en Programación
FRSN
Diferencias
A continuación se presentan dos esquemas, a modo de breve resumen, para poder
interpretar fácilmente frente a que tipo de agrupaciones estamos trabajando:
24