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:

Principio de adición Principio del producto

|||||| BAABA

||||||, BABAASiB

Principio de adición

Si A y B son conjuntos finitos, no vacíos y disjuntos, (es decir, ) , entonces

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.

BA

|||||| BABA A B

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)

Ejemplos:

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 de adición

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:AB 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:AB 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

)!(!

!),( , knk

n

k

nCCknC knkn

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

PRn;n1,n2,..nk=

Son otra aplicación del principio de división:

¿De cuántas formas se pueden permutar las letras de la palabra CASCARA?

!!2!1

!

nknn

n

Propiedades de los números combinatorios

o binómicos Propiedades:

k

n

k

n

k

n

nkkn

n

k

n

n

nn

1

1

1

0 para

1 10

nk 1para

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

022110

210)( yx

n

nyx

k

nyx

nyx

nyx

nyx nknknnnn

0)1(210

.2

2210

.1

n

nnnn

n

nnnn

n

n

Corolario

Forma simplificada: el número combinatorio es el

coeficiente de x^k en el desarrollo de (x+1)^n

k

n

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

)!1(!

)!1(1,

nk

kn

k

knCR kn

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?