Clase 3, permutaciones lineales y circulares

permutaciones

1. UNIVERSIDAD GERARDO BARRIOS

SEDE CENTRAL SAN MIGUEL /CENTRO REGIONAL USULUTAN


Datos Generales
Facultad Ciencias y Humanidades
Asignatura Teoría combinatoria
Docente Lic.: Cristian Martínez
No. de Unidad Unidad 2
Contenido a desarrollar Permutaciones

1. INTRODUCCIÓN AL CONTENIDO
En la presente clase introduce las nociones de permutación, que constituyen instrumentos eficaces
de recuento de casos de amplias clases de problemas. Estas nociones se introducen por medio de
la resolución de situaciones particulares y su posterior generalización y formalización.

Genéricamente, permutar es: variar la disposición u orden en que estaban dos o más objetos. Es
necesario precisar si estas cosas son o no indistinguibles, para asegurar que la nueva configuración
sea en esencia distinta a la antigua.

Considere la siguiente situación: Sea � = {1; 2; 3} la lista 3; 2; 1, es una permutación de �;
al igual que la lista 3; 1; 2.


2. DESARROLLO DEL CONTENIDO.
PERMUTACIONES ORDINARIAS O SIN REPETICÓN

A continuación, estudiaremos la cantidad de formas de ordenar en fila los elementos de un conjunto
de � objetos.

2. Sea � un conjunto finito. Ordenar elementos de � es darle a cada elemento del conjunto una
posición determinada, es decir; definir que elemento ocupa la primera posición, que elemento
ocupa la segunda posición y así sucesivamente.
Dos ordenamientos de elementos de �, se dirá que son idénticos, si todos los elementos en ambos
ordenamientos se encuentran en la misma posición; en consecuencia, dos ordenamientos serán
diferentes, si difieren en la posición en la que se encuentra alguno de los elementos.
Considere la siguiente situación.
Hay cuatro candidatos, Samuel, Ignacio, Hector y Vilma, postulados para el mismo puesto. Para
que la posición de los nombres en las boletas de votación no influya en los votantes; es necesario
imprimir boletas con los nombres en todos los órdenes. ¿Cuántas boletas diferentes habrá?
Por el principio de la multiplicación el resultado será: 4x3x2x1=24, boletas diferentes.
Permutaciones ordinarias o sin repetición.
Se llaman, permutaciones ordinarias o sin repetición de � elementos, denotada ??????
??????, a los distintos
grupos que se pueden formar, de tal manera, que en cada grupo entren los ?????? elementos y que un
grupo se diferencie de los demás, en el orden de colocación de los elementos.
En una permutación, los � elementos se permutan, es decir; que en cada permutación los
� elementos figuran. Diremos que dos permutaciones serán distintas si existen al menos dos
elementos que difieren de su posición.

Considere los siguientes arreglos de las letras mayúsculas de � a la �:

1. ������
2. ������
3. ������

Los arreglos 1 y 2, son permutaciones idénticas, porque el orden de colocación de los elementos
no difiere. El arreglo en 3, es distintos al 1 y 2, porque existe al menos dos elementos de difieren,
en su orden de colocación.

Notas:

1. En una permutación el orden es importante, es decir, importa que elemento ocupa la primera
posición, que elemento ocupa la segunda posición, y así sucesivamente.
2. Las permutaciones ordinarias o sin repetición, también se conocen como permutaciones lineales
o en fila.
3. La notación ??????
?????? representa, el número de permutaciones lineales sin repetición de �
elementos.

3. Veamos un ejemplo:
Sea � = {1; 2; 3; 4}. Mediante un diagrama de árbol, se obtiene el listado de todas las
permutaciones de �.

1234,2134,3124,4123
1243,2143,3142,4132
1324,2314,3214,4213
1342,2341,3241,4231
1423,2413,3412,4312
1432,2431,3421,4321
Por lo tanto ??????
4= 24.

Factorial.
Se define el factorial, de un número entero positivo � y se escribe �! como el producto de los �
primeros números positivos. Matemáticamente se escribe.

�!=�×(�−1)×(�−2)×⋯×3×2×1
Propiedades:
✓ 0!=1
✓ 1!=1
✓ �!=�(�−1)!

Teorema: Existen �! permutaciones de � elementos.

Demostración:
Sea �={??????
1,??????
2,...,??????
??????−1,??????
??????}, un conjunto con � elementos. Las permutaciones lineales de � se
encuentran asignando a cada elemento una posición. Como existen � elementos, por tanto, hay �
posiciones que completar. Así, el elemento ??????
1 dispone de � posiciones, el elemento ??????
2 dispone de
�−1 posiciones, y así sucesivamente, …, el elemento ??????
?????? dispone de 1 posición.

Veamos el siguiente esquema:

� �−1 …

2 1
??????
1 ??????
2 ??????
??????−1 ??????
??????

4. Es decir, que el número de permutaciones lineales de � objetos, coincide con el producto de los �
primeros números enteros positivos, definido como el factorial de �. Por tanto ??????
??????=�!.

Nota:
✓ En consecuencia, del teorema anterior, el número de permutaciones lineales, de n objetos, es
igual a �!.
✓ Existen 10! = 10 × 9 × 8 × 7 ×6 ×5 ×4 ×3 × 2 × 1, permutaciones de 10
elementos.

Permutaciones lineales con repetición de objetos distintos.
Existen otro tipo de permutaciones llamadas, permutaciones lineales con repetición de objetos
distintos. En este caso, imagine una urna con � objetos y una fila con “n” posiciones, numeradas
de la “1” a la “n”. Para este caso tomamos un elemento de la urna, lo asignamos en la primera
posición y lo regresamos a la urna, es decir, que para la segunda posición volvemos a disponer
de � objetos.
Por tanto, resulta:
????????????=�×�×�×⋯×�=�
??????

que representa el total de permutaciones lineales con repetición de � objetos distintos.

Ejemplos:

1. ¿Cuántas permutaciones de las letras ABCDEF contienen la subcadena DEF?

Solución:

Para garantizar la presencia del patrón DEF en la subcadena, estas tres letras deben estar
juntas en este orden. Las letras restantes, A, B y C, se pueden colocar de forma arbitraria.

Podemos pensar en construir permutaciones de las letras ABCDEF que contengan el patrón
DEF con la permutación de cuatro fichas: una con la etiqueta DEF y las otras con etiquetas A,
B y C.

Por tanto, existen 4! permutaciones de cuatro objetos. Entonces, el número de permutaciones
de las letras ABCDEF que contienen la subcadena DEF es 4! = 24.

5. 2. ¿Cuántas permutaciones de las letras ABCDEF contienen a las letras DEF juntas en cualquier
orden?

Solución:

Este problema se resuelve mediante un procedimiento de dos pasos:

✓ Se selecciona un orden de las letras DEF;

✓ se construye una permutación de ABCDEF que contenga el orden dado de las letras
DEF.

El primer paso se puede realizar de 3! = 6 maneras y, el segundo paso se puede realizar de
24 maneras. Por el principio de la multiplicación, el número de permutaciones de las letras
ABCDEF que contienen las letras DEF juntas en cualquier orden es:

3!×4!=144

3. ¿Cuántas permutaciones del conjunto A, B, C, D, E, F satisfacen las
siguientes condiciones? (Sin repetición)
a. La letra A en la primera posición o D en la cuarta.

Solución:
En este caso vamos a utilizar el principio de inclusión exclusión, porque existen cadenas
con la letra A, en la primera posición, cadenas con la letra D, en la cuarta posición, y
cadenas con la letra A en la primera posición y la letra D en cuarta de manera
simultánea.

Definimos los conjuntos:
??????={????????????⁄�� ��� ������ ��� �� ������ ������}
�={??????∕?????? �� ��� ������ ��� �� ����� �,�� �� ��??????���� ���??????�??????ó�.}
�={??????∕?????? �� ��� ������ ��� �� ����� �,�� �� ������ ���??????�??????ó�.}

Luego:
A 5 4 3 2 1
1° 2° 3° 4° 5° 6°

5 4 3 D 2 1
1° 2° 3° 4° 5° 6°

6. A 4 3 D 2 1
1° 2° 3° 4° 5° 6°

Por tanto, |�|=5!; |�|=5! y |�∩�|=4!

Por el principio de inclusión exclusión, las permutaciones con letra A en la primera
posición o D en la cuarta será:

|�∪�|=|�|+|�|−|�∩�|=5!+5!−4!=216

b. La letra A no está en la primera posición o la D no está en la cuarta.

Solución:
En este caso, buscamos las permutaciones, donde la letra A no está en la primera
posición o la D no está en la cuarta. Matemáticamente será:

|�
??????
∪�
??????
|=|(�∩�)
??????
|=|??????−(�∩�)|=|??????|−|�∩�|=6!−4!=696

c. Aparece la A antes que la D.

Solución:
En esta situación, fijamos la letra A, desde la primera posición hasta la 5°, y
movilizamos la letra D, el número de posiciones disponible a la derecha.

Caso 1: Fijamos la letra A en primera posición y movilizamos la letra D, desde la 2°
a la 6°.

A D 4 3 2 1
=4!×5=120
1° 2° 3° 4° 5° 6°
Multiplico por 5, porque la letra D, se puede mover desde la posición 2 a la 6.
A 4 D 3 2 1
=4!×4=96
1° 2° 3° 4° 5° 6°
Multiplico por 4, porque la letra D, se puede mover desde la posición 3 a la 6.
A 4 3 D 2 1
=4!×3=72
1° 2° 3° 4° 5° 6°
Multiplico por 3, porque la letra D, se puede mover desde la posición 4 a la 6.
A 4 3 2 D 1
=4!×2=48
1° 2° 3° 4° 5° 6°
Multiplico por 2, porque la letra D, se puede mover desde la posición 5 a la 6.
A 4 3 2 1 D
=4!×1=24
1° 2° 3° 4° 5° 6°

7. Caso 2: Fijamos la letra A en la segunda posición y movilizamos la letra D, desde la
3° a la 6°.

4 A D 3 2 1
=4!×4=96
1° 2° 3° 4° 5° 6°

4 A 3 D 2 1
=4!×3=72
1° 2° 3° 4° 5° 6°

4 A 3 2 D 1
=4!×2=48
1° 2° 3° 4° 5° 6°

4 A 3 2 1 D
=4!×1=24
1° 2° 3° 4° 5° 6°

Caso 3: Fijamos la letra A en la tercera posición y movilizamos la letra D, desde la 4°
a la 6°.

4 3 A D 2 1
=4!×3=72
1° 2° 3° 4° 5° 6°

4 3 A 2 D 1
=4!×2=48
1° 2° 3° 4° 5° 6°

4 3 A 2 1 D
=4!×1=24
1° 2° 3° 4° 5° 6°

Caso 4: Fijamos la letra A en la cuarta posición y movilizamos la letra D, desde la 5°
a la 6°.

4 3 2 A D 1
=4!×2=48
1° 2° 3° 4° 5° 6°

4 3 2 A 1 D
=4!×1=24
1° 2° 3° 4° 5° 6°

Caso 5: Fijamos la letra A en la quinta posición y la letra D, en la 6°.

4 3 2 1 A D
=4!×1=24
1° 2° 3° 4° 5° 6°

Los 5 casos son disjuntos, por tanto, por el principio de la suma, el resultado es: 840

8. d. No contiene las subcadenas AB, CD.

Solución:
En este caso, usaremos el conteo por complemento, definiendo al conjunto A como:

�={??????: ?????? �� �� ������ ��� ����??????��� ��� ���������� ��,��}

Para garantizar la presencia del patrón AB y CD en las cadenas, estos dos grupos de
dos letras deben estar juntas en ese orden.

AB CD E F

Así, disponemos de 4 objetos y el total de permutaciones de 4 objetos es 4!. Luego
|�|=24. Buscamos las cadenas que no contiene las subcadenas AB, CD. Este dato
que obtiene de la siguiente relación.

|�
??????
|=|??????−�|=|??????|−|�|=6!−4!=696

e. Aparece A antes que C y la C antes que E. (Un análisis similar al literal c)

4. ¿De cuántas maneras distintas podemos sentar a 6 niños en fila, de modo que 2 de ellos,
(M y N) ya determinados previamente no estén juntos? (ejercicio de tarea)
5. Considere la siguiente situación: 6 chicos y 3 chicas se ordenarán en fila, de tal forma que
los extremos de la fila estén ocupados por chicos y ninguna chica este a la par de otra
chica. Determine la cantidad de formas en que la fila se puede construir. (ejercicio de
tarea)

PERMUTACIONES CIRCULARES
En la sección anterior, se estudiaron las permutaciones ordinarias o sin repetición, conocidas como
permutaciones lineales.
Estudiaremos ahora las permutaciones circulares, que como su nombre lo indica son permutaciones
de objetos diferentes en un círculo, generalmente en este tipo de problemas interesa la posición
relativa de los objetos, sin embargo, existen situaciones en lo que nos interesa la posición fija de
los objetos. Definiremos ahora algunos términos para comprender mejor a que nos referimos con
los tipos de posición en las permutaciones
Posición Fija: Interesa que objeto está a la izquierda y que objeto está a la derecha de un objeto
dado (con respecto a un observador determinado) y, además, qué lugar como posición fija en un
arreglo ocupa el objeto. Es decir, existe una primera posición.

9. Observe el siguiente arreglo lineal
A B C D
muestra un claro ejemplo de posición fija para cada elemento. Por ejemplo, al estudiar el objeto
B observamos que su posición fija es: lugar fijo, segunda posición, elemento a la izquierda: A;
elemento a la derecha C.
Posición Relativa: No hay una orientación preasignada en el arreglo, es decir, no existe una
primera posición, solo interesa que objeto está a la izquierda y que objeto está a la derecha de
un objeto dado con respecto a un observador dado.
Observe el siguiente arreglo circular

muestra un claro ejemplo de posición relativa para cada elemento. Por ejemplo, al estudiar el
objeto B observamos que su posición fija es: elemento a la izquierda: A; elemento a la derecha
C. Pero no se puede decir en ningún momento si posee un lugar antes o después de A o de C.
En la posición relativa de los objetos, lo que importa, que objeto está a mi derecha y que objeto
está a mi izquierda. Por ejemplo, los siguientes arreglos ABCDEF…, y ZABCDEF…, dejan al objeto
B en la misma posición relativa, por tanto, en una circunferencia, los dos arreglos son iguales.

Nota:
La mayoría de las situaciones sobre permutaciones circulares, consideran a las permutaciones como un
ordenamiento en círculo de objetos distintos, donde lo que interesa es la posición relativa, por lo tanto,
salvo que el enunciado o la situación del problema indiquen lo contrario, será esta posición la que
tomaremos para abordar los problemas.

Permutaciones circulares sin repetición
Se llaman permutaciones circulares (sin repetición) de � elementos, denotada por ??????�
??????, a los distintos
grupos que se pueden formar, de tal manera que en cada grupo entren los ?????? elementos y que un
grupo se diferencie de los demás en la posición relativa de los elementos unos respecto a los otros.
Notas:

1. En una permutación circular, entran los n elementos, y lo importante es la posición relativa
de los objetos.
2. La notación PC
n representa, el número de permutaciones circulares sin repetición de n
elementos.

10. Consideremos un grupo de � objetos.
✓ Dos ordenamientos se consideran diferentes cuando los objetos ocupan posiciones
numeradas diferentes, entonces el número de posibles ordenamientos, será igual a un
ordenamiento en una fila, es decir ??????
??????; es decir, permutaciones lineales.

✓ Sin embargo, puede ser que solo nos interese la posición relativa que guardan entre sí, los
objetos y no el número de la posición que ocupa, a estas permutaciones les llamaremos
permutaciones circulares.

Supongamos, que tenemos una circunferencia con � posiciones numeradas, del “1” a la "�".
Distribuimos los � objetos, en cada una de esas � posiciones. Cada objeto puede movilizarse
desde la posición “1” a la posición "�", más sin embargo las permutaciones que resultan, se
consideran idénticas.
Por tanto, hay � permutaciones lineales que dejarán a los objetos con la misma permutación
circular, en efecto, la rotación de los objetos pasando por las � posiciones numeradas dejan a los
objetos en la misma posición relativa.
En consecuencia, hay � permutaciones lineales por cada permutación circular. El total de
permutaciones lineales es ??????
??????=�!, y el total de permutaciones circulares, el cual denotamos por
PC
n será:
PC
n=
�!
�
=(�−1)!
Ejemplos:
1. Se quiere confeccionar un collar con � cuentas de colores, todas de distinto color. ¿De
cuántas formas se puede formar el collar si se utilizan todas ellas?
2. ¿De cuántas maneras se pueden sentar seis personas alrededor de una mesa circular?
3. Determine la cantidad de formas en las que cuatro chicos y dos chicas se pueden sentar en
una mesa circular, si las dos chicas no se quieren sentar una al lado de la otra.
4. ¿De cuántas formas se pueden sentar 3 parejas de casados alrededor de una mesa
circular, sí, no debe haber dos mujeres juntas ni dos hombres juntos?
5. ¿De cuántas maneras se pueden ubicar 5 parejas de esposos alrededor de una fogata, si:
a. Un matrimonio se sienta junto.
b. Dos matrimonios se sientan juntos.
c. Los 5 matrimonios se sientan juntos. (ejercicio de tarea)

11. Los invito a ver los siguientes recursos complementarios.
RECURSOS COMPLEMENTARIOS
Recurso

Título Cita referencial
Video Permutaciones
ordinarias sin repetición
https://www.youtube.com/watch?v=Anu4h4xVeFw&t=2s
Permutaciones circulares https://www.youtube.com/watch?v=AVShnd882xQ

ACTIVIDAD DE EVALUACIÓN DE LA SEMANA
Nombre de la Actividad Actividad evaluada semana 3.
Tipo de Actividad Actividad grupal.
Tipo de Participación Obligatoria
Instrucciones para la
actividad
Organizados en equipos deberán, resolver la guía de ejercicios
sobre permutaciones lineales y circulares, y enviar al docente en el
espacio reservado para esta actividad.
Fecha de Entrega
La fecha límite de entrega está programada, para el día domingo
5 de abril a las 23.59 pm.
Criterios de Evaluación
Portada: incluye generalidades, nombres completos de los
integrantes en orden alfabético. (Apellidos-Nombre), carrera,
grupo (A), nombre de la asignatura, fecha de entrega.
Presentación del documento: puntualidad y responsabilidad en la
entrega del documento.
Dominio y aplicación correcta de elementos teóricos: se observa
en la resolución de los problemas, el dominio teórico y la aplicación
de los conceptos de permutación lineal y circular.
Presentación de la solución: se evidencia en la solución del
problema una buena presentación, ordenada, detallando cada uno
de los pasos hasta llegar a la respuesta correcta.