Download escuela de computación - Ing. Gerardo Alberto Leal, MSc

FACULTAD DE INGENIERÍA
ESCUELA DE COMPUTACIÓN
ESTRUCTURAS DISCRETAS (IC33)
PROFESOR: ING. GERARDO ALBERTO LEAL, MSc.
UNIDAD 6: TÉCNICAS DE COMBINATORIA
La combinatoria es un área de la Matemática Discreta que se encarga del
estudio de las posibles agrupaciones ordenadas o desordenadas de objetos,
permitiendo contar el número de objetos que cumplen con ciertas propiedades.
Por ejemplo permiten determinar la cantidad de número telefónicos de una red, el
número de contraseñas permitidas en un sistema informático, el número de
personas que ocupan posiciones en una organización, etc.
Los principios básicos de conteo en la combinatoria son: la Regla del Producto y la
Regla de la suma.
6.1 Principios Básicos de Conteo
Las técnicas de conteo, permite conocer la cantidad de combinaciones de
respuestas a un problema planteado, por ejemplo cuantas contraseñas pueden
existir para un sistema de 6 caracteres alfanuméricos.
Los principios básicos de conteo en la combinatoria son:
- La regla del producto.
- La regla de la suma.
a. Regla del Producto:
Sea una tarea T que puede dividirse en 2 tareas consecutivas. Si hay n1 formas
de realizar la primera tarea y n2 formas de realizar la segunda tarea después de
realizar la primera, entonces hay n1.n2 formas completar la tarea principal.
Para n tareas se tiene: T1.T2.T3……Tn
Ejemplo:
Se requiere etiquetar las butacas de un auditorio con una letra y un número Z+,
menor o igual a 100. ¿Cuál es el máximo número de butacas a las que se puede
asignar una etiqueta diferente?
Solución:
Se identifica la tarea principal y las subtareas:
T = Tarea principal de etiquetar las butacas
T1 = Subtarea de asignarle las letras al código
T2 = Subtarea de asignarle los números al código
Se desea obtener el número de soluciones de la tarea principal:
n = ? número de butacas que pueden ser etiquetadas
Se determinan el número de soluciones posibles para cada subtarea:
n1 = número de letras del alfabeto = 26
n2 = 100 posibles números del 1 al 100
Se aplica la regla del producto para obtener el numero de soluciones de T:
n = n1.n2 = 26 . 100 = 2600 butacas
Ejemplo:
Cuantas cadenas de bits diferentes hay con longitud 7.
Modulo Instruccional Estructuras Discretas. Teoría y Práctica
1
FACULTAD DE INGENIERÍA
ESCUELA DE COMPUTACIÓN
ESTRUCTURAS DISCRETAS (IC33)
PROFESOR: ING. GERARDO ALBERTO LEAL, MSc.
T = determinar la cantidad de cadenas de longitud 7
n = XXXXXXX, donde cada X es un Bit que puede tener 2 valores (0 y 1)
n = 2.2.2.2.2.2.2 = 27 = 128 cadenas
Ejemplo:
Cuantas placas de matriculas están disponibles para vehículos, con una serie de 3
letras y 3 números.
T = XXXYYY, donde XXX son las letras y YYY son los números.
n = 26.26.26.10.10.10 = 17576000 placas posibles.
Ejemplo:
Cuantos posibles números telefónicos puede haber en Ciudad Ojeda si el código
del número tiene 10 dígitos. Los 3 primeros son el código de área de DDN. Los
tres siguientes son para las tres zonas de la ciudad conectadas a cada central
(631, 641 y 662). Los cuatro últimos el terminal del suscriptor.
n = C.C.C.Z.Z.Z.T.T.T.T
C.C.C = Código de DDN 265 para todo número
Z.Z.Z = Zonas de centrales 631, 641 y 662
T.T.T.T = Terminal del suscriptor
n = 1.3.10.10.10.10 = 30000 suscriptores
b. Regla de la Suma:
Si una primera tarea T1 se puede realizar de n1 formas y una segunda tarea T2 se
puede realizar de n2 formas, y si las dos tareas son incompatibles (una no
depende de la otra o no se realizan simultáneamente), entonces hay n1 + n2
formas de realizar una de las dos tareas. Para n tareas se tiene:
T1+T2+T3+…..Tn
Ejemplo:
Para seleccionar un representante de la facultad de ingenieria para un proyecto de
investigación, se puede escoger un profesor o un estudiante de 8vo semestre.
¿De cuantas formas se puede escoger el representante si hay 37 profesores y 83
estudiantes?
Se identifican el número de alternativas para cada tarea:
T1 = Elegir un estudiante n1 = 37
T2 = Elegir un profesor n2 = 83
Se aplica la regla de la suma:
n = n1 + n2 = 120 formas
Ejemplo:
Un estudiante puede elegir un proyecto de investigación de tres listas según el
área de investigación. Cada lista contiene 23, 15 y 19 propuestas de trabajos.
¿Cuantos opciones de posibles proyectos puede elegir el estudiante?
T1 = 23
T2 = 15
Modulo Instruccional Estructuras Discretas. Teoría y Práctica
2
FACULTAD DE INGENIERÍA
ESCUELA DE COMPUTACIÓN
ESTRUCTURAS DISCRETAS (IC33)
PROFESOR: ING. GERARDO ALBERTO LEAL, MSc.
T3 = 19
n = 23 + 15 + 19 = 57 proyectos.
c. Uso combinado de la Regla del Producto y la Regla de la Suma:
Algunos problemas de conteo no permiten la aplicación de la regla de la suma o la
regla del producto por separado, su aplicación simultanea es la que permite llegar
a encontrar el numero de soluciones.
Ejemplo:
En una versión de lenguaje C, el nombre de una variable es una cadena de uno o
dos caracteres alfanuméricos y las letras mayúsculas y minúsculas no se
distinguen. Un nombre de la variable debe empezar con una letra y debe ser
diferente de 5 cadenas de 2 caracteres reservados. ¿Cuántos nombres de
variables distintas hay disponibles para se utilizadas en dicha versión de lenguaje
C?
T = VV
(2 caracteres alfanuméricos)
V = V1 = Nombres de 1 carácter
V2 = Nombres de 2 caracteres
V = V1 + V2
V1 = 26 (1 carácter) y
V2 = V2.V2’, donde V2 son números y V2’ letras.
V2 = (26.36) – 5 = 931 (se restan los 5 reservados al programa)
V = V1 + V2 = 26 + 931 = 957 variables
Ejemplo:
Cada usuario de un computador tiene una contraseña, con una longitud de entre 6
y 8 caracteres, cada uno de los cuales es un digito o una letra mayúscula. Cada
contraseña debe tener al menos 1 digito. ¿Cuántas contraseñas admite el
sistema?
P = número total de contraseñas
P6 = contraseñas de 6 caracteres
P7 = contraseñas de 7 caracteres
P8 = contraseñas de 8 caracteres
Por regla de la suma: P = P6 + P7 + P8
Luego se deben hallar P6, P7 y P8, analizando los excluidos.
C6 = contraseñas totales de 6 caracteres = 36.36.36.36.36.36 = 36 6 = 308915776
CA = caracteres alfabéticos = 26 CD = Caracteres digitos
P6 = C6 – CA = 366 – 266 = 1.867.866.560 contraseñas de 6 caracteres
P7 = C7 – CA = 367 – 267 = 70.332.353.920 contraseñas de 7 caracteres
P8 = C8 – CA = 368 – 268 = 2.612.282.842.880 contraseñas de 8 caracteres
P = P6 + P7 + P8 = 2.684.483.063.360
d. Principio de Inclusión y Exclusión:
Esta técnica de conteo, se refiere a cuando dos tareas se pueden realizar
simultáneamente y por tanto no se puede aplicar la regla de la suma. Para contar
las formas de realizar una de las dos tareas, se suman las maneras de realizar
Modulo Instruccional Estructuras Discretas. Teoría y Práctica
3
FACULTAD DE INGENIERÍA
ESCUELA DE COMPUTACIÓN
ESTRUCTURAS DISCRETAS (IC33)
PROFESOR: ING. GERARDO ALBERTO LEAL, MSc.
cada tarea individualmente y luego se restan las formas de realizar las dos tareas
simultáneamente. En este caso la ecuación esta dada por: n = n1 + n2 – n12
Ejemplo:
Cuantas cadenas de Bits existen que tengan longitud 8 y que bien comiencen con
1 o bien terminen con 00?
Solución:
- La primera tarea, construir una cadena de 8 bits que comience por 1 es: 2 7 = 128
- La segunda tarea, construir una cadena de 8 bits que termine en 00 es: 2 6 = 64
- Las tareas en forma simultánea son: 25 = 32 formas
Por tanto el numero de cadenas de 8 bits que comienzan por 1 o terminan en 00
se calcula por: N = 128 + 64 - 32 = 160 formas
6.2 Permutaciones y Combinaciones
Son técnicas para contar selecciones no ordenadas de distintos objetos y
listas ordenadas de objetos de un conjunto finito.
a. Permutaciones
Una permutación de un conjunto de objetos distintos es una colección
ordenada de esos objetos. También se relacionan las posibles ordenaciones de
un subconjunto de ellos. Una lisa ordenada de r elementos de un conjunto se
llama r-permutación o variación de r elementos. El número de rpermutaciones de un conjunto de n elementos se denota por P (n, r) y se
puede calcular utilizando la regla del producto:
P (n, r) = n(n-1) (n-2)…… (n-(r-1))
Ejemplo:
Sea S = 1, 2, 3
- Las listas de permutaciones de S son:
(3, 2, 1), (3, 1, 2), (2, 3, 1), (2, 1, 3), (1, 2, 3), (1, 3, 2).
- La listas (3, 2) y (3, 1), son variaciones de 2 elementos de S o una 2permutaciones.
Ejemplo:
¿Cuántas formas existen de escoger el primer, segundo y tercer clasificado de un
concurso, si hay un total de 100 participantes?
El número de formas de escoger los 3 ganadores será el número de listas
ordenadas de 3 elementos, de un conjunto de 100, es decir r = 3 y n = 100.
Aplicando el teorema 1 se tiene:
P (n, r) = n(n -1) (n-2) = 100 (100-1) (100-2) = 100.99.98 = 970200
Ejemplo: Supongamos que un viajante debe visitar 8 ciudades distintas, iniciado
su viaje desde una ciudad prefijada, pudiendo visitar las otras 7 en cualquier
orden. ¿De cuantas formas distintas puede organizar su viaje?
n = 8 -1 = 7 ciudades
Modulo Instruccional Estructuras Discretas. Teoría y Práctica
4
FACULTAD DE INGENIERÍA
ESCUELA DE COMPUTACIÓN
ESTRUCTURAS DISCRETAS (IC33)
PROFESOR: ING. GERARDO ALBERTO LEAL, MSc.
r = 7 recorridos
P (7, 7) = 7.6.5.4.3.2.1 = 5040 posibles recorridos
Ejemplo: ¿Cuántas permutaciones de las letras ABCDEFGH contienen la cadena
ABC?
Se considera ABC como un solo elemento fijo, por tanto se aplica el teorema de rpermutaciones para un conjunto de 6 elementos, donde un elemento es el bloque
ABC y el resto las letras D, E, F, G y H. En este caso n = 6 y r = 6
P (n, r) = P (6, 6) = 6.5.4.3.2.1 = 6! = 720 permutaciones.
Se concluye que P (n, n) = n! (cuando n = r)
b. Combinaciones
Una r-combinación de elementos de un conjunto es una selección sin ordenar de
r-elementos del conjunto, es decir un subconjunto de r-elementos.
El número de r-combinaciones de un conjunto de n elementos se denota por
C (n, r) y se puede obtener a través del siguiente teorema:
n!
C (n, r) = ----------- , si n y r son Z+ tal que r ≤ n
r! (n –r)!
C (n,r) = C(n, n-r), es decir no existe una combinación donde r sea igual a n.
Ejemplo:
Sea S el conjunto 1, 2, 3, 4Entonces 1, 3, 4es una r–combinación de S.
Ejemplo:
¿Cual es el número de combinaciones C (4, 2) estando el conjunto formado por
a, b, c, d?
Las 2-combinaciones, son las listas sin ordenar de pares de elementos del
conjunto dado:
a, ba, c,a, db, cb, dyc, des decir son 6 combinaciones posibles.
Ejemplo:
¿De cuantas formas se pueden seleccionar 5 jugadores de entre un grupo de 10
para formar un equipo?
n!
10!
5!.6.7.8.9.10
C (n, r) =
C (10, 5) = ----------- = -------------- = ------------------ = 252
r! (n –r)!
5! (10-5)!
5! . 5!
Ejemplo:
¿De cuantas formas se puede seleccionar una comisión para diseñar un programa
de una universidad, si la comisión debe tener 3 Ingenieros y 4 matemáticos. El
departamento de Ingeniería tiene 9 miembros y el de matemática tiene 11?
9!
11!
C (9, 3). C (11, 4) = ----------- . -------------- = 84 . 330 = 27.720
3!. 6!
4! .7!
Modulo Instruccional Estructuras Discretas. Teoría y Práctica
5
FACULTAD DE INGENIERÍA
ESCUELA DE COMPUTACIÓN
ESTRUCTURAS DISCRETAS (IC33)
PROFESOR: ING. GERARDO ALBERTO LEAL, MSc.
6.3 Ejercicios Propuestos de la Unidad 5:
1.- Un cuestionario se compone de 10 preguntas cada una de las cuales tiene cuatro
posibles respuestas.
a) ¿De cuantas formas puede contestar un estudiante al cuestionario, si responde
todas las preguntas?
b) ¿De cuantas formas puede contestar un estudiante al cuestionario, si puede
dejar preguntas sin contestar?
2.- Existen cuatro autopistas entre Boston y Detroit y seis entre Detroit y Los Ángeles.
¿Cuántos itinerarios distintos hay entre Boston y Los Ángeles pasando por Detroit?
3.- ¿Cuántas cadenas distintas de tres letras mayúsculas se pueden formar, si se requiere
que las tres letras sean distintas?
4.- ¿Cuántas cadenas distintas de diez bits empiezan y termina con 1?
5.- ¿Cuántas matriculas se pueden formar dos letras mayúsculas seguidas de cuatro
dígitos o dos dígitos seguidos de cuatro letras mayúsculas?
6.- ¿Cuántas cadenas de 7 bits comienzan con 00 o bien terminan con 111?
7.- ¿Cuántas permutaciones tiene el conjunto a, b, c, d, e, f, g?
8.- Sea el conjunto S = , 2, 3, 4, 5determina las 3-permutaciones y las 3combinaciones de S.
9.- Calcular las siguientes cantidades:
a) P(6, 3) b) P(8, 8) c) P(8, 5)
d)P(8, 1)
f) C (5, 1) g) C(5, 3) h) C(8, 0)
i) C(8, 4)
e)P(10, 9)
j)C(8, 8)
10.- ¿De cuantas formas puede terminar una carrera de 5 competidores si no hay
empates?
11.- ¿Cuántas posibilidades hay en una carrera de caballos con doce participantes si son
posibles todos los ordenes de llegada y no hay empates?
12.- ¿Cuántas permutaciones de las letras ABCDEFG contienen las cadenas:
a) BCD
b) CFGA
c) ABC y DE
d) CBA y FED
13.- Un club tiene 25 miembros. ¿De cuantas formas se puede escoger cuatro miembros
para escoger un comité ejecutivo? ¿Cuántas formas hay de escoger presidente,
vicepresidente, secretario y tesorero del club?
14.- ¿Cuantas cadenas de 10 bits tienen exactamente:
a) Tres ceros
b) Siete unos
c) Mas ceros que unos
15.-¿Cuántas placas de matricula formadas por tres letras seguidas de tres dígitos hay qe
no tengan letras ni dígitos repetidos?
Modulo Instruccional Estructuras Discretas. Teoría y Práctica
6
FACULTAD DE INGENIERÍA
ESCUELA DE COMPUTACIÓN
ESTRUCTURAS DISCRETAS (IC33)
PROFESOR: ING. GERARDO ALBERTO LEAL, MSc.
16.- El consejo de seguridad de las naciones unidas esta conformado por los
representantes de 10 países. Se deben elegir 3 países de un grupo de 12, 3 de un grupo
de 20 y el resto deben ser elegidos de un grupo de 7. Del ultimo grupo serán elegidos la
junta directiva, integrada por Presidente, Vicepresidente, Segundo Viceprecidente y
Secretario. Utilizando Permutaciones, Combinaciones y Regla del producto, determina de
cuantas formas se puede elegir los 10 representantes?
17.- Se desea diseñar una red local para una corporación, en la cual se requiere la
asignación de direcciones IP en los computadores. Las direcciones IP están compuestas
por el siguiente formato:
XXX: Indican 161 al 162 si es para Oficinistas, 163 para Operaciones y 164 para
ejecutivos.
YYY: Cualquier digito, siempre que sean distintos.
ZZZ: Cualquier digito, excepto 100 códigos reservados para el sistema.
TTT: Cualquier digito, puede ser de 2 o 3 dígitos, ambas opciones empiezan siempre
por 1 o 2.
¿Cuantas computadoras se pueden instalar a la Intranet, sin que haya conflicto de
direcciones IP?
18.- El nombre de una variable en lenguaje C es una cadena que puede tener letras
mayúsculas y minúsculas, dígitos y guión bajo. El primer carácter puede ser una letra
mayúscula o minúscula. Las variables pueden ser de 3, 4 o 5 caracteres. Utilizando la
regla del producto y la regla de la suma, determina cuantas variables como máximo,
admite el lenguaje?
19.- Se tiene un conjunto S, cuyos elementos son las letras A, B, C, D. Determinar las 2combinaciones y las 3-permutaciones. Cuales son las 2-combinaciones del conjunto S?
20.- Para la copa del Mundial de Fútbol FIFA Sudafrica 2010 clasificaran 32 equipos de
los 5 continentes. Aplicando los principios de conteo, determina:
a) Cuantas opciones hay para obtener en la quiniela el equipo Campeón y
Subcampeón?
b) Cuantas opciones hay de indicar los cuatro equipos semifinalistas, si los
favoritos eran: Argentina, España, Alemania, Holanda, Brasil, Inglaterra, Italia, Portugal,
Francia?
c) Cuantas opciones hay de acertar la quiniela con el orden de los 32 equipos?
21.- Se desea diseñar un sistema telefónico en el que la asignación de números se hará
con el siguiente esquema: el código de país es un número de 1, 2 o 3 dígitos, en el que
los códigos del 000 al 100 son de América y del 101 al 300 son de Europa. Luego le sigue
un número de 10 dígitos con el siguiente formato: NYX-NNX-XXXX. Donde X puede ser
cualquier digito, Y puede se cualquier valor ente 5 y 9, N es un digito que puede ser 0 o 1.
Utilizando la regla del producto y la suma para determinar:
a) Cuantos Números telefónicos pueden asignarse a todos los países?
b) Cuantos Números pueden asignarse en América?
c) Cuantos Números pueden asignarse en Europa?
Modulo Instruccional Estructuras Discretas. Teoría y Práctica
7