Download Tema 3: Técnicas de contar

Tema 3: Técnicas de contar
 Objetivo específico: Dado un conjunto finito
¿podemos contar sus elementos sin hacer la
lista de dichos elementos?
 Aplicaciones:
 Probabilidades (se cuentan casos
favorables y casos posibles)
 Cálculo de la complejidad o tiempo de
ejecución de un algoritmo (número de
operaciones medio o esperado que realiza un
algoritmo)
¿Qué vamos a contar?
• Todos los subconjuntos de un conjunto de 10
elementos.
• Los anagramas de la palabra CONTAR
(CORNAT, CARNOT,……)
• Si 5 niños comparten 12 canicas idénticas.
¿De cuántas maneras pueden repartirse las
canicas?
• ¿Cuántos números de 16 bits tienen
exactamente cuatro 1?
Propiedades del cardinal de un conjunto
finito
 Cardinal de un conjunto finito A es el número de
elementos de A y lo notamos por |A|
 Sea Ø ,el cardinal del conjunto vacio, |Ø| =0
 Cardinal de la diferencia:
| A  B || A |  | A  B |
SiB  A, | A  B || A |  | B |
 Principio de adición
 Principio del producto
Principio de adición
 Si A y B son conjuntos finitos, no vacíos y disjuntos,
(es decir, A  B  ) , entonces
| A  B || A |  | B |
A
B
 En una clase se sabe que hay 6 personas de no más
de 18 años ( conjunto A) y 7 personas de entre 19 y 22
años (conjunto B). ¿cuántas personas hay de no más
de 22 años?
Aplicando el principio de adición podemos concluir
que hay 6+7=13 personas de no más de 22 años.
Ejemplos:
 Si sólo sabemos que hay 6 personas de no más
de 18 años (conj. A) y 7 personas de entre 17 y
22 años (con. B), no somos capaces de dar el
número exacto de personas de menos de 22
años (porque A y B no son ahora disjuntos)
 En la plantilla de un equipo de fútbol, todos los
jugadores son españoles o argentinos. Diez son
españoles, 5 son argentinos. ¿Cuántos
jugadores son en total?
¿Y qué pasa si hay 3 jugadores que tienen la
doble nacionalidad? (Principio Inclusión-Exclusión)
Principio de adición
 Decimos que los conjuntos A1,A2,…..,An son
disjuntos dos a dos, si cada par de estos
conjuntos son disjuntos.
 Principio de la suma: Si los conjuntos
A1,A2,…..,An son disjuntos dos a dos, entonces el
cardinal de la unión de todos ellos es igual a la
suma de los cardinales de cada uno de ellos.
Principio del producto
 Si un procedimiento se puede separar en dos
etapas y si hay m posibles resultados para la
primera etapa y n para la segunda, entonces
el número de formas distintas de realizar el
procedimiento es el producto m · n
 ¿Cuántas palabras de longitud 4 se pueden
formar con las letras a,c,s?
 En una promoción de 50 estudiantes, se
reparten tres premios. ¿Cuáles son todas las
posibles reparticiones?
Principios de la suma y el producto
 En ocasiones hay que combinar ambos
principios para resolver un problema:
 En cierto sistema informático, una contraseña válida
tiene entre 6 y 8 caracteres válidos. El primero tiene
que ser un carácter alfabético, los siguientes son
alfabéticos o numéricos. Hay 52 caracteres
alfabéticos posibles A={a,b,c,d…..z,A,B,C,D,……Z} y
10 caracteres numéricos posibles N={0,1,2,3,4,….9}.
¿Cuántas contraseñas válidas hay?
Producto cartesiano. Cardinal.
 Dados dos conjuntos A y B, AxB es el conjunto
de todos los pares ordenados (a,b) donde a
pertenece a A y b pertenece a B.
 (a,b)=(c,d) si y sólo si a=c y b=d.
 Si A y B son finitos, se tiene que |AxB|=|A||B|
 Un experimento consiste en lanzar un solo dado
y anotar el resultado; a continuación se lanza
una moneda al aire y se anota el resultado.
Determinar cuántos y cuáles son todos los
posibles resultados del experimento.
Aplicación. Tipos de aplicaciones.
 Una correspondencia entre los conjuntos A
y B es cualquier subconjunto del producto
cartesiano AxB.
 Una aplicación entre los conjuntos A y B es
una correspondencia tal que a cada elemento
del conjunto de partida A le corresponde uno
y sólo un elemento del conjunto de llegada B
y se denota por b=f(a).
Tipos de aplicaciones
 Una aplicación f: A-->B se dice inyectiva cuando
cada elemento del conjunto de llegada B es
imagen de cómo mucho un elemento del
conjunto de partida A.(A cada elemento de B le
llega como máximo una flecha)
 Una aplicación f: A-->B se dice sobreyectiva
cuando cada elemento del conjunto de llegada B
es imagen de, al menos un elemento del
conjunto de partida A (A cada elemento de B le
llega como mínimo una flecha).
Biyección y aplicación a técnicas de contar
 Una aplicación se dice biyectiva cuando es
inyectiva y sobreyectiva a la vez (cuando
todo elemento del conjunto de llegada B es
imagen de uno y sólo un elemento de A)
 Contar los elementos de un conjunto finito A
es establecer una biyección f de A en un
conjunto de la forma {1,2,…,n}.
 Principio de la biyección: si existe una
biyección entre dos conjuntos finitos A y B
entonces ambos tienen el mismo cardinal
(número de elementos).
Ejemplos
 Sean los dos problemas siguientes:
 Contar las maneras de repartir 12 canicas
idénticas entre 5 niños.
 Contar los números de 16 bits con exactamente
cuatro 1.
A={maneras posibles de repartir 12 canicas entre 5
niños}
B={ números de 16 bits con exactamente cuatro 1}
Aplicación a técnicas de contar
¿Cuántos subconjuntos tiene el conjunto
{1,2,3,4,5,6,7,8,9,10}?
 Teorema: Un conjunto de n elementos tiene
exactamente dos elevado a n elementos.
 ¿Cuántas aplicaciones hay de {1,2,3} en
{1,2,3,4,5,6}?=¿Cuántas sucesiones de longitud
3 hay cuyos términos pueden valer {1,2,3,4,5,6}?
 Teorema: El número de aplicaciones de un
conjunto finito Y en un conjunto finito X es |X|
elevado a |Y|
Variaciones
 Variaciones: Sea Nm={1,2,…,m} conjunto con m
elementos. El número de aplicaciones inyectivas de Nm
en X recibe el nombre de variaciones (sin repetición) de
los elementos del conjunto X con longitud m y se denota
por Vn,m.
 Teorema: Si |X|=n, el número de variaciones de n
elementos de longitud m (tomadas de m en m) es
nx(n-1)x(n-2)x…..x(n-m+1)
 Ejemplo: ¿Cuántos números de tres cifras existen sin
cifras repetidas?
V10,3=10x9x8=720
Variaciones con repetición
 Si se permite repetición, las aplicaciones que
consideramos son todas (no sólo las inyectivas),
las notaremos por VRn,m y su número es n
elevado a m.
 Ejemplo: ¿Cuántos números de cuatro cifras
existen?
De ellos, ¿cuántos hay que sean múltiplos de 5?
Permutaciones
 Las permutaciones son un caso extremo de las
variaciones en el que podemos escoger todos los
elementos del conjunto X, es decir,
Pn=Vn,n=n!
 ¿Cuántos números de 3 cifras distintos se
pueden escribir con los dígitos {1,3,5}?
Principio del palomar
 Si 100 palomas vuelan hacia los 99 nidos de
un palomar, entonces por lo menos en uno
de los nidos habrá dos o más palomas.
 Principio del palomar: Si |A|>|B|, entonces
ninguna aplicación f de A en B es inyectiva,
es decir, para toda aplicación f de A en B
existen dos elementos distintos del conjunto
de partida A con la misma imagen por f.
Ejemplos
 Cualquier subconjunto de tamaño seis del
conjunto S={1,2,3,4,5,6,7,8,9} debe contener dos
elementos que sumen 10.
 Si en una oficina hay 13 empleados, entonces al
menos dos de ellos deben cumplir años en el
mismo mes.
 Lorenzo vuelve de la lavandería con 12 pares de
calcetines (cada par de distinto color) en una
bolsa. Si sacamos calcetines al azar de la bolsa,
entonces debemos extraer a lo sumo 13 para
obtener un par del mismo color.
Principio de distribución (del palomar
generalizado)
 Si |A|=n>k|B|=km, entonces para toda aplicación f de A
en B existen k+1 elementos de A que tiene la misma
imagen por f, o bien, si queremos repartir n objetos en m
cajas y n>km, entonces al menos una caja ha de recibir
más de k objetos (k+1 objetos como mínimo).
 Ejemplo: En Sevilla capital hay 700.000 personas y más
de 600.000 no son calvas. Si se sabe que nadie tiene
más de 200.000 pelos, entonces entre las personas no
calvas hay por lo menos cuatro personas que tienen el
mismo número de cabellos.
Ejercicio
 Si A es un conjunto de 101 enteros positivos
diferentes no superiores a 200 y elegidos al
azar, existen al menos dos elementos de A
tales que uno de ellos divide al otro.
Principio de división
 Una aplicación f:AB es de grado
combinatorio k, si todo elemento de B tiene
exactamente k antecedentes en A (i.e. para
todo b de B existen a1,…ak de a tales que
f(a1)=f(a2)=….=f(ak)=b).
 Principio de división: Si f:AB es de grado
combinatorio k, entonces |A|=k|B|
 Ejemplo: ¿cuántas manos de póker pueden
ser obtenidas en un juego de 52 cartas?
Combinaciones
 Los subconjuntos de k elementos de un conjunto dado
A (|A|=n) de manera que dos de ellos se consideran
distintos cuando contienen algún elemento distinto, se
llaman combinaciones de n elementos tomadas de k
en k. Los números de combinaciones de n elementos
tomados de k en k es el número combinatorio o
binómico
C (n, k )  Cn,k
n
n!
 C    
 k  k! (n  k )!
k
n
Permutaciones con repetición
 Teorema: el número de permutaciones con repetición de
un conjunto de n elementos donde existe un grupo de n1
elementos repetidos, otro de n2 elementos repetidos, etc
viene dado por
n!
PRn;n1,n2,..nk=
n1! n 2!  nk!

Son otra aplicación del principio de división:
¿De cuántas formas se pueden permutar las letras de la
palabra CASCARA?
Propiedades de los números combinatorios
o binómicos
 Propiedades:
n
n
   1
   1
0
n
n  n 
   
 para 0  k  n
k  n  k 
 n   n  1   n  1
   
  
 para 1  k  n
 k   k  1  k 
Triángulo de Tartaglia o Pascal
 La última propiedad anterior nos permite
calcular los números combinatorios de
manera recursiva construyendo:
1
1
1
2
1
1
3
3
1
1
4
6
4
1
 Cada fila i coincide con los coeficientes de
los términos del desarrollo del binomio de
Newton de grado i.
Teorema del binomio de Newton
 n  0 n  n  1 n1  n  2 n2
 n  k nk
n n 0
( x  y)    x y    x y    x y      x y      x y
0
1
 2
k 
n
n
n
Forma simplificada: el número combinatorio 
k 
 es el
 
coeficiente de x^k en el desarrollo de (x+1)^n
Corolario
1. 
2. 
n n n
n
n














2
 0 1  2
n
     
 
n n n
nn

0

1

 2
    ( 1) 
n
0
     
 
Combinaciones con repetición
 Son las combinaciones en el caso de permitir que
cualquiera de los elementos aparezcan en la selección
más de una vez
 n  k  1 (n  k  1)!
 
CRn,k  
 k  k! (n  1)!
Ejemplo: Palabras de 5 letras con el alfabeto {a,b,c},
podemos representarlas con una cadena binaria con 5
(k) unos y 2 ceros (n-1), que representan la alternancia
entre las 3 (n) letras que disponemos. Así, aabcc se
representaría por 1101011.
Combinaciones con repetición
Luego las combinaciones con repetición son las
maneras de distribuir k unos en una cadena
binaria de longitud n+k-1, es decir, combinaciones
de n+k-1 tomadas de k en k.
Ejemplo: De camino a casa, 7 estudiantes se
detienen en un restaurante de servicio rápido
donde cada uno puede escoger entre: una
hamburguesa con queso, un perrito caliente, un
bocadillo o un emparedado de pescado.
¿Cuántos pedidos diferentes se pueden hacer?