Principios de multiplicidad

Apuntes de Matem´tica Discreta a 3. Principios B´sicos de Conteo a

Francisco Jos´ Gonz´lez Guti´rrez e a e
C´diz, Octubre de 2004 a

Universidad de C´diz a

Departamento de Matem´ticas a

ii

Lecci´n 3 o

Principios B´sicos de Conteo a
Contenido
3.1 Partici´n de un Conjunto o 3.1.1 3.1.2 3.1.3 3.2 3.2.1 3.2.2 3.3 3.3.1 3.3.2 3.4 3.4.1 3.4.2 3.4.3 3.5 3.5.1 3.5.2 . . . . . . . .. . . . . . . . . . . . . . . . . . . . . 37 37 38 39 39 39 40 41 41 42 45 45 49 59 69 69 70 Definici´n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . o Recubrimiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Cardinal de un conjunto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . Teorema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Regla de la Suma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Teorema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Regla del Producto . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . Teorema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Teorema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Generalizaci´n del Principio de Inclusi´n-Exclusi´n . . . . . . . . . . . . . . . . o o o Teorema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Corolario . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Principio de Adici´n o

Principio de Multiplicaci´n o

Principio de Inclusi´n-Exclusi´n . . . . . . . . . . . . . . . . . . . . . . . . . o o

Principio de Distribuci´n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . o

Desarrollamos en esta lecci´n los principios b´sicos para contar elementos de un conjunto,el de Adici´n, o a o el de Multiplicaci´n, el de Inclusi´n-Exclusi´n y finalizaremos con el de Distribuci´n. o o o o

3.1
3.1.1

Partici´n de un Conjunto o
Definici´n o

Dado un conjunto A, diremos que los subconjuntos de A, A1 , A2 , . . . , An , constituyen una partici´n o del mismo si se cumplen las siguientes condiciones: 1. Ai = ∅; ∀i = 1, 2, . . . . . . , n 2. Ai ∩ Aj = ∅; ∀i = j, i,j = 1, 2, . . . . . . n 3. A1 ∪ A2 ∪ · · · · · · ∪ An = A 37

Universidad de C´diz a

Departamento de Matem´ticas a

3.1.2

Recubrimiento

Si los subconjuntos B1 , B2 , . . . . . . , Bn de un conjunto A cumplen las condiciones 1. y 3. de la definici´n anterior, diremos que B1 , B2 , . . . . . . , Bn constituyen un recubrimiento de A. o Ejemplo 3.1

A

A2

A3

A1

A4Partici´n del conjunto A. Ejemplo 3.1 o Los subconjuntos A1 , A2 , A3 y A4 constituyen una partici´n de A. o Ejemplo 3.2 Si A = {a, b, c, d, e, f, g, h, i, j, k}, los conjuntos

A1 = {a, b, c, d} A2 = {c, d, e, f, g} A3 = {g, h, i} A4 = {j, k} constituyen un recubrimiento del conjunto A. Soluci´n o En efecto, Ai = ∅; i = 1, 2, 3, 4 A1 ∪ A2 ∪ A3 ∪ A4 = {a, b, c, d} ∪ {c, d, e, f, g} ∪ {g, h, i} ∪ {j, k}= {a, b, c, d, e, f, g, h, i, j, k} = A 38

Matem´tica Discreta a Sin embargo no es una partici´n ya que, por ejemplo, o

Francisco Jos´ Gonz´lez Guti´rrez e a e

A1 ∩ A2 = {a, b, c, d} ∩ {c, d, e, f } = {c, d} = ∅

3.1.3

Cardinal de un conjunto

Si A es un conjunto finito no vac´ designaremos por cardinal de A al n´mero de elementos que tiene ıo, u A. Si A es el conjunto vac´entonces su cardinal es cero. Lo notaremos |A|. ıo,

3.2

Principio de Adici´n o

Estudiamos el m´s b´sico y simple de los principios para contar elementos de un conjunto. a a

3.2.1

Teorema

Si A1 , A2 , . . . , An es una colecci´n de conjuntos finitos no vac´ disjuntos dos a dos, entonces o ıos, |A1 ∪ A2 ∪ · · · ∪ An | = |A1 | + |A2 | + · · · + |An | Demostraci´n o Procederemos por...