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 DE CONTEO son importantes en
Matemáticas y en las Ciencias De La Computación,
particularmente para el análisis de algoritmos.
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. 3
CONJUNTOS
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.
Cardinal de un conjunto finito
Es el número de ELEMENTOS del mismo
A= { x/ x es una vocal del abecedario}
A tiene 5 ELEMENTOS 4
5
6
7
. CONJUNTO VACIO, UNITARIO Y UNIVERSAL
• 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.
8
,
9
. Propiedades de la Inclusión
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
10
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
Sea A un conjunto de n elementos y r natural tal que 0r n. Entonces el número nCr ,
n n!
r r!(n r )!
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
4 4!
6
2 2!(4 2)!
50
Sea A un conjunto con n elementos. ¿Cuántos subconjuntos tiene A?
O sea: ¿Cuántos elementos tiene P(A)?
n n
P(A) tiene = 1 subconjuntos con ningún elemento, siendo 0! = 1, = n subconjuntos con 1 elemento ,
n 0 1
n n
Subconjuntos con 2 elementos , subconjuntos con 3 elementos…….. subconjuntos con n-3
2 3 n 3
n n n
elementos, subconjuntos con n-2 elementos, subconjuntos con n-1 elementos y
n 2 n 1 n
subconjuntos con n elementos .
En tonal tiene 2n puesto que la suma de todas las cantidades es
n n n n n n n
+ + + …………… + + + + = (1+1)n
0 1 2 n 3 n 2 n 1 n
Observamos inmediatamente que vale la igualdad n
= n
n r r
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
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}}
17
TRIÁNGULO DE PASCAL- NÚMEROS BINOMIALES
18
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:
n r!n!
r! n(n 1)(n 2)...(n r 1)
r r!(n r )!
O sea permutando todos los elementos de cada
subconjunto de r elementos que se obtienen de los n
que tiene el conjunto A
44
NÚMERO DE Arreglos a partir de los
elementos de un conjunto A con repetición
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
41
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
