Combinatoria

Cardinales finitos

Variaciones y Permutaciones

Combinaciones

´ Tema 5: Introduccion a la combinatoria

Cardinales finitos

Variaciones y Permutaciones

Combinaciones

1

Cardinales finitos

2

Variaciones y Permutaciones

3

Combinaciones

Cardinales finitos

Variaciones y Permutaciones

Combinaciones

´ Definicion Se denomina cardinal de un conjunto finito A (y sedenota por cd(A)) al numero de elementos que tiene. ´
´ Nota. Todos los conjuntos que consideremos en este tema seran finitos.

Propiedad 1 ( Regla de la suma) Si A ∩ B = ∅ entonces cd(A ∪ B) = cd(A) + cd(B) Si {A1 , A2 , . . . , An } es una familia de conjuntos disjuntos 2 a 2, entonces cd(A1 ∪ A2 ∪ . . . ∪ An ) = cd(A1 ) + cd(A2 ) + · · · + cd(An ) Propiedad 2 ( Cardinal de la diferencia) cd(A− B) = cd(A) − cd(A ∩ B)

Cardinales finitos

Variaciones y Permutaciones

Combinaciones

´ Propiedad 3 ( Cardinal de la union) Sean A, B y C conjuntos, entonces cd(A ∪ B) = cd(A) + cd(B) − cd(A ∩ B). cd(A ∪ B ∪ C) = cd(A) + cd(B) + cd(C)− cd(A ∩ B) − cd(A ∩ C) − cd(B ∩ C) + cd(A ∩ B ∩ C).
´ Ejemplo 1. En el patio de un colegio los alumnos solo juegan a futbol o a ´ baloncesto. Se sabeque de los 80 alumnos de una clase, 60 juegan a futbol, ´ ´ 50 a baloncesto y 12 no practican ninguno de los dos deportes. ¿Cuantos alumnos practican ambos deportes? Sea F el conjunto de alumnos que juegan a futbol y sea B el conjunto de ´ alumnos que juegan a baloncesto. Dado que hay 12 que no practican ninguno de los dos deportes, se tiene que cd(F ∪ B) = 68. Por tanto, aplicando la propiedad 3,obtenemos que cd(F ∩ B) = cd(F ) + cd(B) − cd(F ∪ B) = 50 + 60 − 68 = 42

Cardinales finitos

Variaciones y Permutaciones

Combinaciones

Propiedad 4 ( Regla del producto) Sean A1 , A2 , . . . , An conjuntos , entonces cd(A1 × A2 ) = cd(A1 ) · cd(A2 ) cd(A1 × A2 × . . . × An ) = cd(A1 ) · cd(A2 ) · . . . · cd(An )
Ejemplo 2. Sea V = {a, b, c, d}. Llamaremos palabra de longitud n sobre V acualquier secuencia (ordenada) de n elementos de V. Calcular (1) Numero de palabras de longitud 2 ´ (2) Numero de palabras de longitud 3 que no tienen la letra b ´ (3) Numero de palabras de longitud 4 que empiezan por la letra a ´ Aplicando la regla del producto obtenemos que (1) cd(V × V ) = 4 · 4 = 16 (2) cd(W × W × W ) = 3 · 3 · 3 = 27, siendo W = V − {b}, (3) cd({a} × V × V × V ) = 1 · 4 · 4· 4 = 64

Cardinales finitos

Variaciones y Permutaciones

Combinaciones

´ Las reglas de la suma y del producto constituyen los dos principios basicos ´ del conteo. Pueden ser expresadas en otros terminos de la siguiente forma: Regla de la suma Supongamos que A y B son dos sucesos disjuntos, es decir, no se presentan al mismo tiempo. Si el suceso A se puede realizar de m maneras y elsuceso B se puede realizar de n maneras, entonces el suceso A o B se puede realizar de m + n maneras. ´ Nota. La regla de la suma se puede aplicar a mas de dos sucesos siempre que sean disjuntos dos a dos. ´ Ejemplo 3. ¿Cuantas formas posibles hay de sacar un rey o un caballo en ˜ una baraja espanola? Sea A el suceso sacar un rey y sea B el suceso sacar un caballo. Como son sucesos disjuntos y hay 4reyes y 4 caballos, aplicando el principio de la suma, el total de maneras de sacar o bien rey o ´ bien caballo sera 4 + 4 = 8 ´ Ejercicio 1. ¿Cuantas formas posibles hay de sacar un rey o una espada en ˜ una baraja espanola de 40 cartas?

Cardinales finitos

Variaciones y Permutaciones

Combinaciones

Regla del producto Sea un suceso C que se puede descomponer en dos sucesos o etapassucesivas A y B independientes entre s´. Si hay m maneras de ralizar la ı etapa A y n maneras de realizar la etapa B, entonces el suceso C se puede realizar de m · n maneras. Nota. La regla del producto pude aplicarse a un numero finito de etapas. ´ Ejemplo 4. ¿Cuantas formas posibles hay de emparejar un rey con un as en ˜ una baraja espanola? Dado que hay 4 formas de realizar la etapa A (elegir un...