Combinatoria I
[2.1] ¿Cómo estudiar este tema?
[2.2] Breve introducción a la combinatoria
[2.3] Principios básicos de conteo
[2.4] Principio del palomar
[2.5] Permutaciones
2
T EMA
Combinatoria
Principios de conteo Principio del palomar Permutaciones
Esquema
TEMA 2 – Esquema
Reglas de la suma Sea k un número entero positivo. Si Una permutación de un conjunto de
Si una tarea se puede hacer de un modo de entre los n1 tenemos que colocar k+1 o más objetos en objetos distintos es una disposición
modos diferentes o de uno de los n2 modos diferentes, k cajas, entonces hay al menos una caja ordenada de estos objetos.
donde ninguno de las n1 modos es igual a las n2 modos, que contiene dos o más de los objetos.
entonces hay n1 +n2 modos de hacer la tarea.
Reglas del producto
Supongamos que un proceso se puede dividir en una
secuencia de dos tareas. Si hay n1 modos de hacer la
primera tarea y para cada uno de esos modos de hacer
la primera tarea hay n2 modos de hacer la segunda
tarea, entonces hay n1n2 modos de hacer el proceso.
Regla de la substracción. Principio de
inclusión-exclusión
Si una tarea se puede realizar de n1 modos o de n2
modos, entonces el número de modos en que se puede
realizar la tarea es n1+n2 menos el número de modos
en que se puede hacer la tarea que es común a los dos
modos diferentes.
Regla de la division
Tenemos n/d modos de hacer una tarea, si la tarea se
puede realizar llevando a cabo un proceso en n modos.
Y además, para cada modo w, exactamente d de los n
modos corresponden al modo w.
© Universidad Internacional de La Rioja (UNIR)
Ideas clave
2.1. ¿Cómo estudiar este tema?
Para estudiar esta lección lee atentamente las Ideas Clave que se presentan a
continuación.
Debido al desarrollo de los aparatos digitales, especialmente los ordenadores, las
matemáticas discretas se han convertido en un elemento importante.
La combinatoria trata principalmente con colecciones finitas de objetos discretos.
El punto de partida suele consistir en problemas que son fáciles de comprender incluso
si sus soluciones no son sencillas de obtener. La combinatoria suele consistir en
problemas que son fáciles de comprender incluso por aquellos que no conocen
ninguna técnica matemática.
Los problemas combinatorios tienen en cuenta los siguientes aspectos:
Contar el número de soluciones
Comprobar la existencia de una solución
Buscar la solución óptima
A lo largo del tema veremos las distintas herramientas de la combinatoria, tales
como: regla de la suma, del producto, de substracción y división.
Enunciaremos el principio del palomar y resolveremos varios ejemplos.
Introduciremos el concepto de permutación y lo aplicaremos a varios casos
prácticos.
TEMA 2 – Ideas clave © Universidad Internacional de La Rioja (UNIR)
2.2. Breve introducción a la combinatoria
Básicamente las matemáticas se basan en resolver problemas, basados en un mundo real
no matemático. Los conceptos matemáticos se desarrollan para abordar problemas del
mundo real.
Estas ideas matemáticas abstractas tienen entidad propia y a su vez generan más
problemas, estos problemas son más técnicos que los iniciales y su conexión con el
mundo exterior es más remota.
Prácticamente desde la época de Isaac Newton y hasta un periodo de tiempo reciente, las
matemáticas aplicadas se centraban en procesos que varían de forma continua. Estos
procesos son modelados por la matemática del continuo utilizando métodos
provenientes del cálculo diferencial e integral.
Por el contrario, la combinatoria trata principalmente con colecciones finitas de
objetos discretos. Debido al desarrollo de los aparatos digitales, especialmente los
ordenadores, las matemáticas discretas se convierten cada día en más y más importantes.
A veces la forma en que se plantea la enseñanza y aprendizaje de las matemáticas crea
una dificultad para que el alumno lleve a cabo este proceso. Generalmente se cree que es
mejor comenzar con las ideas más básicas e ir luego introduciendo poco a poco conceptos
más complicados. En realidad, esto parece más sensato que comenzar por la parte más
complicada con la esperanza de que el alumno aprenda a nadar sin llegar a ahogarse.
Sin embargo, este enfoque que parece ser el más lógico, con frecuencia oculta las razones
históricas por las que una idea matemática particular se ha desarrollado. Esto significa
que puede ser difícil para el estudiante comprender la conexión de la materia
estudiada con el problema real.
Por suerte, la combinatoria es diferente. El punto de partida suele consistir en problemas
que son fáciles de comprender incluso si sus soluciones no son sencillas de obtener. La
combinatoria suele consistir en problemas que son fáciles de comprender incluso
por aquellos que no conocen ninguna técnica matemática.
TEMA 2 – Ideas clave © Universidad Internacional de La Rioja (UNIR)
¿Qué tipo de problemas aborda la combinatoria?
Podemos encontrar los orígenes de la combinatoria en la estadística, los juegos de azar
y en problemas recreativos.
Una respuesta aproximada a la cuestión anterior es en cualquier lugar donde tengamos
que conocer «¿Cuánto?» (la respuesta puede ser «cero») es de nuestro interés. Así, por
ejemplo las técnicas combinatorias (o una versión generalizada de ellas) han sido
utilizadas en el diseño de ciertos experimentos, como por ejemplo:
Ensayos con cultivos (estadística)
Diseño de rutas de tráfico ( teoría de grafos)
Construcción de códigos
Organización de reuniones (permutaciones y combinaciones)
Ubicar personas en ciertos puestos de trabajo
Determinación de ciertos componentes químicos (teoría de grafos)
Realización de horarios escolares
Biología matemática, relacionado con el código del ADN
También hay aplicaciones en el campo matemático propiamente dicho, como la teoría
de números. En el campo de la computación, en cuestiones relacionadas con la
velocidad y complejidad de los algoritmos.
Como aplicación de la combinatoria a los juegos recreativos podemos citar, el cubo de
Rubik, los cuadrados «mágicos», la torre de Hanoi, y el famoso problema que dio lugar
a la teoría de grafos, el problema de los puentes de Königsberg.
TEMA 2 – Ideas clave © Universidad Internacional de La Rioja (UNIR)
En muchos problemas no solo se busca la solución sino la solución óptima. Por
ejemplo, podríamos querer buscar la máxima producción de una factoría, o minimizar el
flujo de tráfico o los costes de producción. También podemos querer seguir la ruta más
corta cuando se visita una serie de pueblos (el problema del vendedor viajero).
Los problemas anteriores, tienen en cuenta tres problemas básicos de
combinatoria: contar el número de soluciones, comprobar la existencia (¿existe alguna
solución?), y buscar una solución óptima.
2.3. Principios básicos de conteo
Muchas cuestiones surgen en la vida diaria en las que tenemos que aplicar el arte de
contar, como de cuántas maneras podemos combinar las camisas y los pantalones de
nuestro armario de tal manera que no se repita ninguno. Cuestiones como esta y otras
pertenecen a lo que se conoce como combinatoria enumerativa.
Contar es averiguar el número de elementos de un conjunto. Llamamos combinatoria al
arte de contar.
Decimos que es un arte porque resolver problemas combinatorios no es un proceso
automático, sino que depende de nuestra experiencia. Veremos muchos problemas que
tienen un enunciado sencillo pero que son «toscos» de resolver.
Aprenda y comprenda las formulas básicas, pero sea consciente de que sin el análisis
de cada problema el mero conocimiento de las fórmulas puede resultar casi inútil.
Reglas de la suma y del producto
Estas reglas son sencillas de aplicar y analizar. A veces se utilizan para resolver
problemas complejos, para ello estos problemas complejos se descomponen en
partes y se aplican estas reglas.
Regla de la suma: si una tarea se puede hacer de un modo de entre los n1 modos
diferentes o de uno de los n2 modos diferentes, donde ninguno de las n1 modos es igual
a las n2 modos, entonces hay n1 +n2 modos de hacer la tarea.
TEMA 2 – Ideas clave © Universidad Internacional de La Rioja (UNIR)
o Ejemplo: Supongamos que o un profesor de la facultad de ciencias o un estudiante
de ciencias son elegidos para representar a su facultad en el congreso de la
universidad. ¿De cuántos modos diferentes se puede elegir el representante si hay
30 profesores en la facultad de ciencias y 81 estudiantes de ciencias, y ninguno de
ellos puede ser las dos cosas, profesor y estudiante?
Hay 30 modos de elegir un profesor de la facultad de ciencias y hay 81 modos de
elegir un estudiante. Elegir un profesor no es lo mismo que elegir un estudiante, ya
que ninguno puede ser a la vez profesor y alumno de la facultad de ciencias.
Mediante la regla de la suma hay 30+81=111 modos posibles de elegir un
representante.
Esta regla de la suma se puede extender para más de dos tareas. Suponemos
que una tarea se puede hacer de un modo de entre n1 modos, de un modo de entre
n2 modos,…, o de ni modos, donde ninguno de los ni modos de hacer la tarea es
igual a ninguno de los nj modos, para todas las parejas i y j con 1 ≤ i < j ≤ m.
Entonces el número de modos de hacer la tarea es n1 + n2 + ⋯ + nm.
o Ejemplo: Un estudiante de ingeniería naval puede elegir el proyecto fin de grado
seleccionando uno de una lista de entre tres listas posibles. Las tres listas contienen
20, 10 y 21 proyectos diferentes cada una respectivamente. Ningún proyecto está
en más de una lista. ¿Cuántos proyectos diferentes es posible elegir?.
Los estudiantes pueden elegir un proyecto seleccionando uno de la primera lista,
de la segunda o de la tercera. Debido a que un proyecto no está en más de una lista,
mediante la regla de la suma, tenemos 20+10+21= 51 modos diferentes de elegir
un proyecto.
La regla de la suma se puede aplicar a los conjuntos: si A1, A2,…., Am son
conjuntos finitos disjuntos dos a dos, entonces el número de elementos de la unión de
estos conjuntos es la suma de los elementos de los conjuntos.
Para poder aplicar la regla de la suma, debemos darnos cuenta de que hay |Ai| modos
de elegir un elemento de Ai para i=1,2,…, m. Como los conjuntos son disjuntos dos a
dos, al elegir un elemento de uno de los conjuntos Ai no estamos eligiendo ningún
elemento de otro conjunto diferente Aj.
TEMA 2 – Ideas clave © Universidad Internacional de La Rioja (UNIR)
Por tanto mediante la regla de la suma y puesto que no podemos elegir un elemento
de dos conjuntos al mismo tiempo, el número de modos de elegir un elemento de un
conjunto, que resulta ser el número de elementos de la unión es
|𝐴𝐴1 ∪ 𝐴𝐴2 ∪ … ∪ 𝐴𝐴𝑚𝑚 | = |𝐴𝐴1 | + |𝐴𝐴2 | + ⋯ + |𝐴𝐴𝑚𝑚 | 𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑 𝐴𝐴𝑖𝑖 ∩ 𝐴𝐴𝑗𝑗 = ∅ 𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 𝑡𝑡𝑡𝑡𝑑𝑑𝑑𝑑 𝑖𝑖, 𝑗𝑗
Regla del producto: supongamos que un proceso se puede dividir en una secuencia
de dos tareas. Si hay n1 modos de hacer la primera tarea y para cada uno de esos modos
de hacer la primera tarea hay n2 modos de hacer la segunda tarea, entonces hay n1n2
modos de hacer el proceso.
La regla del producto se suele aplicar cuando un proceso está formado por tareas
separadas.
o Ejemplo: Una compañía de teléfonos tiene dos empleados en plantilla, Ruiz y
Pérez. La compañía alquila un piso de un edificio con 10 oficinas. ¿De cuantas
maneras se pueden asignar oficinas diferentes a estos dos empleados?
El proceso de asignar oficinas a estos dos empleados consiste en asignar una oficina
a Ruiz, esto se puede realizar de 10 modos diferentes, entonces asignar una oficina
a Pérez diferente de la oficina asignada a Ruiz, esto se puede hacer de 9 modos.
Mediante la regla del producto hay 10.9=90 modos de asignar oficinas a estos dos
empleados.
o Ejemplo: Las sillas del palacio de congresos de Murcia son etiquetadas con una
letra mayúscula del abecedario español seguida de un número entero que no
exceda de 100. ¿Cuál es el mayor número de sillas que se pueden etiquetar de modo
diferente?
El proceso de etiquetar una silla consiste en dos tareas, asignar a la silla una de las
29 letras del abecedario en mayúscula. Y entonces, asignar uno de los posibles 100
enteros. La regla del producto muestra que hay 29.100=2900 modos diferentes de
etiquetar una silla. Por lo tanto, el número mayor de sillas que se pueden etiquetar
de modo diferente es 2900.
TEMA 2 – Ideas clave © Universidad Internacional de La Rioja (UNIR)
La regla del producto se puede aplicar a conjuntos: Si A1, A2,… Am son
conjuntos finitos, entonces el número de elementos del producto cartesiano de estos
conjuntos es el producto del número de elementos de cada conjunto. Para relacionar
esto con la regla del producto, observar que la tarea de elegir un elemento del producto
cartesiano A1 xA2 x… Am se hace mediante la elección de un elemento de A1, un
elemento de A2,…, y un elemento de Am. Mediante la regla del producto se tiene que
|𝐴𝐴1 × 𝐴𝐴2 × ∙∙∙ × 𝐴𝐴𝑚𝑚 | = |𝐴𝐴1 | ∙ |𝐴𝐴2 | ∙ ∙∙∙ ∙ |𝐴𝐴𝑚𝑚 |
Muchos problemas de conteo no se pueden resolver aplicando solo la regla de la suma
o la regla del producto. Sin embargo, muchos problemas complejos se pueden resolver
combinando ambas reglas la de la suma y la del producto.
o Ejemplo: En un cierto sistema informático cada usuario tiene un password, que
consta de seis a ocho caracteres. Cada carácter puede ser una letra mayúscula o un
digito. Cada password debe contener al menos un digito. ¿Cuántos posibles
password hay?
Sea P el número total de posibles passwords, y denotamos por P6, P7, y P8 al número
de posibles passwords de longitud 6, 7, y 8, respectivamente. Mediante la regla de
la suma, P=P6 + P7 + P8. Ahora necesitamos calcular P6, P7, y P8. Encontrar P6
directamente es difícil. Para encontrar P6 es más fácil encontrar el número de
cadenas de letras mayúsculas y dígitos que tienen seis caracteres, incluyendo
aquellos que no tienen dígitos. Y eliminando de este número las cadenas que no
tienen dígitos. Por la regla del producto, el número de cadenas de seis caracteres
es 366, y el número de cadenas que no tienen dígitos es 266. De aquí,
𝑃𝑃6 = 366 − 266 = 2,176,782,336 − 308,915,776 = 1,867,866,560
De manera similar, tenemos
𝑃𝑃7 = 367 − 267 = 78,364,164,096 − 8,031,810,176 = 70,332,353,920
TEMA 2 – Ideas clave © Universidad Internacional de La Rioja (UNIR)
Y
𝑃𝑃8 = 368 − 268 = 2,821,109,907,456 − 208,827,064,576 = 2,612,282,842,880
Por lo tanto,
𝑃𝑃 = 𝑃𝑃6 + 𝑃𝑃7 + 𝑃𝑃8 = 2,684,483,063,360
La regla de la substracción. Inclusión-exclusión para dos conjuntos
Supongamos que podemos realizar una tarea de un modo de entre dos modos, pero
alguno de los modos de hacerlo es común a ambos modos. Si sumamos ambos modos,
para obtener el número total de modos de hacer la tarea, estamos contando dos veces los
modos que son comunes a ambos. Para realizar un cálculo correcto sobre el número de
modos de hacer las dos tareas, debemos eliminar el número de modos que hemos
contando dos veces. Esto nos conduce a la siguiente regla de conteo.
La regla de la substracción: Si una tarea se puede realizar de n1 modos o de n2 modos,
entonces el número de modos en que se puede realizar la tarea es n1+n2 menos el número
de modos en que se puede hacer la tarea que es común a los dos modos diferentes.
Esta regla de sustracción se conoce como principio de inclusión-exclusión,
especialmente cuando se utiliza para contar el número de elementos en la unión de dos
conjuntos.
Supongamos que A1 y A2 son conjuntos. Entonces, hay | A1 | modos de seleccionar un
elemento de A1 y | A2| de seleccionar un elemento de A2. El número de modos de
seleccionar un elemento de A1 o de A2, esto es, el número de modos de seleccionar un
elemento de su unión, es la suma de los números de modos de seleccionar un elemento
de A1 y el número de modos de seleccionar un elemento de A2, menos el número de modos
de seleccionar un elemento que está en ambos, o sea en A1 y A2.
Como hay |A1 ∪ A2 | modos de seleccionar un elemento o en A1 o en A2, y hay
|A1 ∩ A2 | modos de seleccionar un elemento común en ambos conjuntos, tenemos
|𝐴𝐴1 ∪ 𝐴𝐴2 | = |𝐴𝐴1 |+|𝐴𝐴2 | − |𝐴𝐴1 ∩ 𝐴𝐴2 |
TEMA 2 – Ideas clave © Universidad Internacional de La Rioja (UNIR)
Ejemplo: Una compañía recibe 340 solicitudes de graduados en ingeniería para abrir
una sucursal de atención al cliente. Supongamos que 210 de estas solicitudes son de
graduados en ingeniería industria, y 140 son de graduados en empresariales y 50 son
de graduados en una doble titulación de ingeniería y empresariales. ¿Cuántas de estas
solicitudes no son ni de graduados en ingeniería ni en empresariales?
Para encontrar el número de estas solicitudes que no son ni de graduados en
ingeniería ni en empresariales, debemos substraer el número de graduados o en
ingeniería o en empresariales (o en ambos) del total de solicitudes.
Sea A1 el conjunto de estudiantes graduados en ingeniería y A2 el conjunto de
estudiantes graduados en empresariales. Entonces A1 ∪ A2 es el conjunto de
estudiantes graduados en ingeniería o en empresariales (o en ambos), y A1 ∩ A2 es
el conjunto de estudiantes graduados en ambos en ingeniería y empresariales.
Mediante la regla de la substracción el número de estudiantes graduados o en
ingeniería o en empresariales (en ambos) es igual a
|𝐴𝐴1 ∪ 𝐴𝐴2 | = |𝐴𝐴1 |+|𝐴𝐴2 | − |𝐴𝐴1 ∩ 𝐴𝐴2 | = 210 + 140 − 50 = 300
Concluimos que 340-300=40 es el número de solicitudes que no son ni de ingenieros
ni de empresariales.
La regla de la substracción, o sea el principio de inclusión-exclusión, se puede generalizar
para encontrar el número de modos de hacer una de las n tareas diferentes, o
equivalentemente, encontrar el número de elementos en la unión de n conjuntos,
siempre que n sea un entero positivo.
La regla de la división
Tras introducir la regla del producto, de la suma y de la substracción uno puede
preguntarse si existe la regla de la división para el conteo.
Existe esta regla y se puede utilizar para resolver ciertos tipos de problemas de
enumeración.
TEMA 2 – Ideas clave © Universidad Internacional de La Rioja (UNIR)
Regla de la división: Tenemos n/d modos de hacer una tarea, si la tarea se puede
realizar llevando a cabo un proceso en n modos. Y además, para cada modo w,
exactamente d de los n modos corresponden al modo w.
Regla de la división para conjuntos: Si un conjunto finito A está formado por la
unión de n subconjuntos disjuntos dos a dos cada uno con d elementos, entonces n=A/d
Ejemplo: ¿De cuántos modos diferentes se pueden sentar cuatro personas alrededor
de una mesa?. Dos sitios se consideran el mismo cuando cada persona tiene el mismo
vecino de la izquierda y el mismo vecino de la derecha.
Nosotros arbitrariamente seleccionamos un sitio en la mesa y lo etiquetamos como
sitio 1. Enumeramos el resto de los sitios en orden numérico, procediendo en el
sentido de las agujas del reloj alrededor de la mesa.
Podemos observar que hay cuatro modos de seleccionar la persona para el sitio 1, tres
modos de seleccionar la persona para el sitio 2, dos modos de seleccionar la persona
para el sitio 3, y un modo de seleccionar la persona para el sitio 4.
Por lo tanto hay 4!=24 modos de ordenar cuatro personas en los sitios. Sin embargo,
cada una de las cuatro elecciones para el sito 1 lleva a la misma ordenación, dos
ordenaciones son distintas solo cuando la persona tiene un vecino diferente a la
izquierda y a la derecha.
Como hay cuatro modos de elegir la persona para el sitio 1, mediante la regla de la
división tenemos 24/4=6 diferentes ordenaciones para sentar a cuatro personas
alrededor de una mesa circular.
2.4. El principio del palomar
Supongamos que una bandada de 20 palomas tiene que acoplarse en un palomar que
tiene 19 huecos. Debido a que hay 20 palomas pero solo 19 huecos, al menos uno de los
19 huecos tiene que contener dos palomas.
TEMA 2 – Ideas clave © Universidad Internacional de La Rioja (UNIR)
Para ilustrar el principio llamado del palomar, ver la figura, que afirma que si hay más
palomas que huecos, debe haber al menos un hueco que contenga dos palomas.
Principio del palomar: Sea k un número entero positivo. Si tenemos que colocar k+1
o más objetos en k cajas, entonces hay al menos una caja que contiene dos o más de los
objetos.
En la figura hay más palomas que huecos en el palomar.
Corolario: Una función f que va de un conjunto con k+1 elementos a un conjunto con k
elementos no es una función uno a uno.
Ejemplo: Entre un grupo de 367 personas, debe haber al menos dos personas que
cumplen años el mismo día. Puesto que hay solo 366 fechas de cumpleaños posibles.
Ejemplo: En un grupo de 30 palabras españolas, debe haber al menos dos que
empiecen por la misma letra, porque hay 29 letras en el alfabeto español.
El principio del palomar nos dice que debe de haber al menos dos objetos en la misma
caja cuando hay más objetos que cajas. También lo podemos aplicar cuando el número
de objetos excede un múltiplo del número de cajas.
Principio generalizado del palomar: Si N objetos son colocados en k cajas, entonces
hay al menos una caja que contiene al menos ⌈N/k⌉ objetos.
TEMA 2 – Ideas clave © Universidad Internacional de La Rioja (UNIR)
Ejemplo: Entre 100 personas hay al menos 100/12=9 personas que nacieron el
mismo día.
Ejemplo: ¿Cuál es el mínimo número de estudiantes requeridos en una clase de
cálculo para asegurar de que al menos seis estudiantes reciben la misma nota, si hay
cinco notas posibles, suspenso, aprobado, bien, notable, sobresaliente?
El número mínimo de estudiantes necesarios para asegurar que al menos seis
estudiantes reciben la misma nota es el menor número entero N tal que N/5=6. El
menor de tales eneros es N=5.5+1=26. Con lo que 26 es el mínimo número de
estudiantes necesarios para asegurar que al menos seis estudiantes reciban el mismo
grado.
2.5. Permutaciones
Muchos problemas de conteo se pueden resolver encontrando el número de maneras de
un conjunto, donde el orden de estos elementos se tiene en cuenta.
Muchos otros problemas de conteo se pueden resolver encontrando el modo de
seleccionar un número de elementos de un conjunto en donde el orden de los
elementos no importa.
Ejemplo: ¿De cuantas maneras se pueden seleccionar tres estudiantes de un grupo
de cinco estudiantes para que permanezcan en línea con el fin de hacer una foto? ¿De
cuantas maneras se pueden ordenar los cinco estudiantes en línea para tomar una
foto?
En primer lugar debemos darnos cuenta de que el orden en que seleccionamos los
estudiantes importa. Hay cinco maneras de seleccionar el primer estudiante para
iniciar la línea. Una vez que este estudiante ha sido seleccionado, hay cuatro maneras
de seleccionar el segundo estudiante para ocupar el segundo lugar en la línea.
Después de haber seleccionado el primer y el segundo estudiante, hay tres maneras
de seleccionar el tercer estudiante para que ocupe su lugar en la línea. Mediante la
TEMA 2 – Ideas clave © Universidad Internacional de La Rioja (UNIR)
regla del producto tenemos 5.4.3=60 maneras de seleccionar tres estudiantes des un
grupo de cinco estudiantes para que permanezcan en línea en la foto.
Para organizar los cinco estudiantes en línea para una foto, primero seleccionamos el
primer estudiante de cinco modos, el segundo de cuatro modos, el tercero de tres
modos, el cuarto de dos modos y el quinto de un modo. Por lo tanto, hay 5.4.3.2.1=120
modos de ordenar los cinco estudiantes en línea para una foto.
Permutación: Una permutación de un conjunto de objetos distintos es una disposición
ordenada de estos objetos.
Una disposición ordenada de r elementos de un conjunto se llama r-permutación.
Ejemplo: Sea S = {1, 2, 3}. La disposición ordenada 3, 1, 2 es una permutación de S.
La disposición ordenada 3,2 es una 2-permutación de S.
El número de r-permutaciones de un conjunto con n elementos se denota por P(n,r).
Se puede obtener el valor de P(n,r) utilizando la regla del producto.
Ejemplo: Sea S = {𝒂𝒂, 𝒃𝒃, 𝒄𝒄}. Las 2-permutación de S son las disposiciones ordenadas
a,b; a,c; b,a; b,c; c,a; y c,b. Por lo tanto, hay seis 2-permutaciones del este conjunto
con tres elementos. Tenemos tres maneras de elegir el primer elemento de la
disposición. Hay dos maneras de elegir el segundo elemento de la disposición, ya que
debe ser diferente del primero. Mediante la regla del producto, vemos que
P(3,2)=3.2=6 .
Teorema: Sea n enteros positivos y r es un entero con 1 ≤ 𝑟𝑟 ≤ 𝑛𝑛, entonces hay
𝑃𝑃(𝑛𝑛, 𝑟𝑟) = 𝑛𝑛 (𝑛𝑛 − 1)(𝑛𝑛 − 2) ∙∙∙ (𝑛𝑛 − 𝑟𝑟 + 1)
r-permutaciones de un conjunto con n elementos distintos.
𝑛𝑛!
Corolario: Sea n y r enteros con 0 ≤ 𝑟𝑟 ≤ 𝑛𝑛, entonces 𝑃𝑃 (𝑛𝑛, 𝑟𝑟) = (𝑛𝑛−𝑟𝑟)!
TEMA 2 – Ideas clave © Universidad Internacional de La Rioja (UNIR)
Tener en cuenta que siempre que n sea un entero no negativo. Tenemos que:
𝑃𝑃(𝑛𝑛, 0) = 1
𝑃𝑃(𝑛𝑛, 𝑛𝑛) = 𝑛𝑛!
Ejemplo: ¿De cuantas maneras podemos seleccionar el primer premio, el segundo
premio y el tercer premio de entre 100 personas que han participado en un concurso?
Como importa quién es la persona y qué premio gana, el número de maneras de elegir
un tercer premio es el número de disposiciones ordenadas de tres elementos de un
conjunto de 100 elementos. Es decir, el número de 3-permutaciones de un conjunto
de 100 elementos. Por lo tanto la respuesta es
𝑃𝑃(100,3) = 100 ∙ 99 ∙ 98 = 970,200
Ejemplo: Imaginamos que hay ocho corredores en una carrera. El ganador recibe la
medalla de oro, el segundo la de plata y el tercero la de bronce. ¿De cuántas maneras
diferentes se pueden otorgar estas medallas? Teniendo en cuenta que pueden ocurrir
todos los resultados posibles y no se producen empates.
El número de modos diferentes de otorgar las medallas es igual al número de 3-
permutaciones de un conjunto con ocho elementos. Por lo tanto, hay P (8, 3) = 8 . 7 .
6 = 336 modos posibles de otorgar las medallas.
Ejemplo: Suponemos que una vendedora tiene que visitar ocho ciudades diferentes.
Tiene que comenzar su viaje en una ciudad específica, sin embargo ella puede visitar
las otras siete ciudades en cualquier orden que desee. ¿De cuantas maneras posibles
se pueden ordenar la visita a esas ciudades?
El número de posibles caminos entre las ciudades es el número de permutaciones de
los siete elementos. La primera ciudad está determinada sin embargo las siete
restantes se pueden ordenar de modo arbitrario. Por lo tanto hay la vendedora puede
tiene 7! = 7 ∙ 6 ∙ 5 ∙ 4 ∙ 3 ∙ 2 ∙ 1 = 5040 modos arbitrarios de elegir su viaje.
Ejemplo: ¿Cuántas permutaciones de las letras ABCDEFGH contienen la secuencia
ABC?
TEMA 2 – Ideas clave © Universidad Internacional de La Rioja (UNIR)
Ya que las letras ABC deben aparecer como un bloque, podemos averiguar la respuesta
encontrando el número de permutaciones de seis objetos. Estos objetos son el bloque
ABC y las letras individuales D, E, F, G, y H. Puesto que estos seis objetos pueden
ocurrir en cualquier orden, hay 6!=720 permutaciones de las letras ABCDEFG en las
que ABC aparecen como un bloque o elemento.
TEMA 2 – Ideas clave © Universidad Internacional de La Rioja (UNIR)
Lo + recomendado
Lecciones magistrales
Combinatoria I
En esta lección magistral se va a hacer
una breve introducción a la
combinatoria. Se van a introducir los
principios básicos de conteo, reglas de la
suma y del producto, principio de
inclusión-exclusión. Principio del
palomar y permutaciones.
La lección magistral está disponible en el aula virtual.
No dejes de leer…
Permutaciones
En este documento se va a introducir las permutaciones. Podrás encontrar también
varios ejercicios resueltos. Remarcando lo visto en este tema.
Accede al artículo a través del aula virtual o desde la siguiente dirección web:
http://recursos.salonesvirtuales.com/assets/bloques//combinaciones-y-
permutaciones.pdf
TEMA 2 – Lo + recomendado © Universidad Internacional de La Rioja (UNIR)
No dejes de ver…
Permutaciones
Se muestran varios vídeos explicativos
sobre permutaciones.
Accede al vídeo a través del aula virtual o desde la siguiente dirección web:
https://www.youtube.com/watch?v=3ZVq2KvClZ8
TEMA 2 – Lo + recomendado © Universidad Internacional de La Rioja (UNIR)
+ Información
A fondo
Estadística para todos
En este recurso se hace un repaso de diferentes aspectos de la combinatoria. De modo
que enfatiza y amplia lo visto en el tema.
Accede al artículo a través del aula virtual o desde la siguiente dirección web:
http://www.estadisticaparatodos.es/historia/histo_combi.html
Bibliografía
Grimaldi, R. (2003). Matemática discreta y combinatoria. Prentice Hall
TEMA 2 – + Información © Universidad Internacional de La Rioja (UNIR)
Test
1. Si una tarea se puede hacer de un modo de entre los n1 modos diferentes o de uno de
los n2 modos diferentes, donde ninguno de los n1 modos es igual a los n2 modos, entonces
hay n1 +n2 modos de hacer la tarea.
A. Solo bajo ciertas condiciones.
B. Falso.
C. Cierto.
D. A, B y C son correctas.
2. Suponiendo que un proceso se puede dividir en una secuencia de dos tareas. Si hay n1
modos de hacer la primera tarea y para cada uno de estos modos de hacer la primera
tarea hay n2 modos de hacer la segunda tarea, entonces hay n1 n2 modos de hacer el
proceso.
A. Falso.
B. Cierto.
C. En ciertas ocasiones.
D. A, B y C son correctas.
3. Si A1 y A2 son conjuntos. El principio de inclusión-exclusión tiene la siguiente
expresión
|𝐴𝐴1 ∪ 𝐴𝐴2 | = |𝐴𝐴1 |+|𝐴𝐴2 | − |𝐴𝐴1 ∩ 𝐴𝐴2 |
A. Cierto.
B. Falso.
C. Sólo bajo ciertas condiciones.
D. A, B y C son correctas.
4. Si un conjunto finito A está formado por la unión de n subconjuntos disjuntos dos a
dos cada uno con d elementos, entonces n=A/d.
A. Cierto.
B. Falso.
C. A veces.
D. Nunca.
TEMA 2 – Test © Universidad Internacional de La Rioja (UNIR)
5. Entre un conjunto de 200 personas hay al menos 200/12 personas que nacieron el
mismo día
A. Falso.
B. Cierto.
C. En ciertas ocasiones.
D. A, B y C son correctas.
6. Una permutación de un conjunto de objetos distintos es una disposición ordenada de
estos objetos.
A. Falso.
B. Cierto.
C. En ciertas ocasiones.
D. A, B y C son correctas.
7. Sea n enteros positivos y r es un entero con 1 ≤ 𝑟𝑟 ≤ 𝑛𝑛, entonces hay
𝑃𝑃(𝑛𝑛, 𝑟𝑟) = 𝑛𝑛 (𝑛𝑛 − 1)(𝑛𝑛 − 2) ∙∙∙ (𝑛𝑛 − 𝑟𝑟 + 1)
r-permutaciones de un conjunto con n elementos distintos.
A. Cierto.
B. Falso.
C. A veces.
D. Nunca.
8. Siempre que n sea un entero no negativo se cumple:
𝑃𝑃(𝑛𝑛, 0) = 1
A. Falso.
B. Cierto.
C. Solo bajo ciertas circunstancias.
D. A, B y C son correctas.
9. Siempre que n sea un entero no negativo se cumple:
𝑃𝑃(𝑛𝑛, 𝑛𝑛) = 𝑛𝑛!
A. Cierto.
B. Falso.
C. Solo bajo ciertas circunstancias.
D. A, B y C son correctas.
TEMA 2 – Test © Universidad Internacional de La Rioja (UNIR)
10. ¿Cuántas permutaciones de las letras DEFGHIJK contienen la secuencia DEF?
A. 230.
B. 820.
C. 740.
D. 720.
TEMA 2 – Test © Universidad Internacional de La Rioja (UNIR)
