Métodos de Conteo

Vista previa del material en texto

TÉCNICAS DE CONTEO:
COMBINACIONES Y 
PERMUTACIONES
Matemática Discreta 
Universidad Tecnológica Nacional Facultad Regional Tucumán
1
¿Cuántas son las claves bancarias formadas por 4 dígitos 
distintos que no comiencen en cero?
¿Cuántas palabras de tres letras pueden formarse a partir 
de las letras del conjunto { a , b , x , y } si no se permiten 
repeticiones
¿Cuántas palabras de longitud 7 del alfabeto 
A = {a,b,c} tienen la propiedad de que la letra “a” aparece un 
número par de veces?
2
Las técnicas que permiten contar la cantidad de
elementos de un conjunto, ya sean de objetos de
cualquier naturaleza, eventos o sucesos posibles sin
contarlos uno por uno, se basan en dos principios:
• PRINCIPIO DE LA MULTIPLICACION
• El PRINCIPIO DE ADICION, aplicable a casos donde
participan las operaciones entre conjuntos.
Las TÉCNICAS DE CONTEO son importantes en
Matemáticas y en las Ciencias De La Computación,
particularmente para el análisis de algoritmos.
3
Un conjunto es un grupo o colección de objetos todos distintos, 
a los que se conoce como ELEMENTOS del mismo. Bien 
definido, significa que es posible decidir si un objeto dado 
pertenece o no al conjunto.
A= { x/ x es una vocal del abecedario} 
A tiene 5 ELEMENTOS
CONJUNTOS
Cardinal de un conjunto finito
Es el número de ELEMENTOS del mismo
4
5
6
7
. CONJUNTO VACIO, UNITARIO Y UNIVERSAL
8
• Un conjunto se dice vacio si no tiene elementos. Su cardinal
es 0 y se lo indica con  . Y con { }
• Un conjunto se dice Unitario si tiene exactamente un
elemento. Su cardinal es 1
• Al conjunto que contiene todos los elementos del tema de
referencia se le llama Conjunto universal y se denota con la
letra U.
,
9
. Propiedades de la Inclusión
10
1) 1) Si A es un conjunto cualquiera, se cumple que
a) A A b) Ø  A c) A  U
2) Si A , B y C son conjuntos cualesquiera, se cumple
que:
a) Si A  B y B A entonces A = B, también vale el 
recíproco
b) Si A  B y B C entonces A C
Sea A un conjunto en un universo U. Definimos la siguiente 
función:
11
12
13
Conjunto Potencia o 
Conjunto Partes de un conjunto
Si A es un conjunto, el conjunto de todos los
subconjuntos de A se denomina conjunto potencia de A
o conjunto partes de A y se designa por P(A).
Ejemplo:
Si A = {a,b} entonces P (A) = { Ø , {a} , {b} , A }. 
Observaciones
Diremos que Ø P(A) , A P(A) ,..
También que {Ø}  P(A) , {{a}} , {{b}} P(A),…
14
Sea A un conjunto con n elementos. ¿Cuántos subconjuntos tiene 
A?
CCada subconjunto de A puede expresarse como un arreglo de 
ceros y unos de longitud n. El primer elemento del arreglo puede 
llenarse de dos maneras (con un cero o con un uno), y esto es 
igualmente cierto para todos los elementos que le siguen. En 
consecuencia hay 
222x2x2…..2 x2x2 = 2n
2nn n factores
15
NÚMERO Combinatorio
50
Sea A un conjunto de n elementos y r natural tal que 0r n. Entonces el número nCr , 
Es el número que cuenta la cantidad de subconjuntos de r elementos 
tomados de los n que tiene dicho conjunto.
Ejemplo: si el número de elementos de un conjunto es n=4, entonces la cantidad de subconjuntos 
de 2 elementos tomados de los 4 es el número combinatorio
6
)!24(!2
!4
2
4








)!(!
!
rnr
n
r
n







Sea A un conjunto con n elementos. ¿Cuántos subconjuntos tiene A?
O sea: ¿Cuántos elementos tiene P(A)?
Contamos la cantidad de elementos que tiene P(A) que es lo mismo que la cantidad de subconjuntos de A:
Caso particular: n = 4 Si A = {a,b,c,d} entonces P(A) tiene 24 = 16 elementos
17
P (A) = { Ø , {a} , {b}, {c} , {d} , {a,b} , {a,c} , {a,d} , {b,c} , {b,d} {c,d} , {a,b,c}, {a,b,d}, {c,b,d}, {a,c,d},{a,b,c,d}}
P(A) tiene = 1 subconjuntos con ningún elemento, siendo 0! = 1, = n subconjuntos con 1 elemento ,
Subconjuntos con 2 elementos , subconjuntos con 3 elementos…….. subconjuntos con n-3 
elementos, subconjuntos con n-2 elementos, subconjuntos con n-1 elementos y 
subconjuntos con n elementos .
En tonal tiene 2n puesto que la suma de todas las cantidades es 
+ + + …………… + + + + = (1+1)n






0
n






1
n






2
n






3
n






3
 
n
n






 2
 
n
n






n
n






1
 
n
n






0
n






1
n






2
n






1
 
n
n






 2
 
n
n






3
 
n
n






n
n
Observamos inmediatamente que vale la igualdad = 






 rn
n 






r
n
18
TRIÁNGULO DE PASCAL- NÚMEROS BINOMIALES
PERMUTACIONES
Cuando cambia el orden de los elementos en una secuencia en la que no se 
permiten repeticiones se denomina “Permutación”. Dos arreglos que tienen 
los mismos elementos pero varían en el orden son diferentes .
La permutaciones se cuentan con n! 
n! = n (n-1)(n-2)(n-3)…..3.2.1
Con el número n! contamos todos los arreglos posibles que se obtienen al 
permutar la lista de todos los elementos de un conjunto A cuyo cardinal sea n
44
PERMUTACIONES
Si permutamos los elementos de un subconjunto de tamaño r tomados de un 
conjunto A cuyo cardinal es n, todos los arreglos que se obtienen se cuentan de la 
siguiente manera, siempre aplicando el principio de la multiplicación:
O sea permutando todos los elementos de cada 
subconjunto de r elementos que se obtienen de los n 
que tiene el conjunto A
44
)1)...(2)(1(
)!(!
!!
 ! 







rnnnn
rnr
nr
r
n
r
NÚMERO DE Arreglos a partir de los 
elementos de un conjunto A con repetición
41
Sea A un conjunto de n elementos y r natural tal 
Entonces el número de secuencias de longitud 
r que pueden formarse con los elementos de A , 
permitiendo repeticiones, es 
n.n.n….. .n.n = nr
r factores
ALFABETOS Y CADENAS
• Dado un conjunto A. Se define el conjunto A* como 
aquel formado por todas las sucesiones finitas de los 
elementos de A. En general A no es un conjunto 
numérico sino un conjunto de símbolos. En este caso a 
A se le llama ALFABETO, y a las sucesiones finitas que 
forman A* se las llama PALABRAS procedentes de A, o 
CADENAS de A. 
• En este caso, al escribir las sucesiones que hay en A* no 
se usan comas. Se supone que A* contiene a la 
SUCESIÓN VACÍA o CADENA VACÍA, que no contiene 
símbolos, y se designa por 
57