Teoría de conjuntos y análisis combinatorio

Herramientas para el estudio de la probabilidad

Fabián Abarca Calderón

IE0405 – Modelos Probabilísticos de Señales y Sistemas

0
Tema I

EIE Escuela de
Ingeniería Eléctrica



Los “eventos” y “experimentos” que vamos a utilizar se

modelan y analizan matemáticamente. Dos

herramientas útiles para ello son la teoría de
conjuntos, para relacionar y agrupar eventos, y el

análisis combinatorio, para contar el número de

posibles resultados de un experimento.



Teoría de conjuntos



Eventos y conjuntos

Tema de estudio del curso: “la probabilidad

de ocurrencia de un evento”.

¿�é es un evento?

Definiremos un evento como un

conjunto de resultados elementales de

un experimento.

{ }

• Estos son resultados elementales

“favorables” a (o coincidentes con) el

evento en el que están incluidos.

• Ejemplo: el evento llamado { número

par en un dado } tiene los resultados

elementales 2, 4 y 6.

• Como conjunto que es, un evento sigue

las reglas y la notación del álgebra de
conjuntos.

◦ Teoría de conjuntos 1 / 30



Posibles eventos en un dado

Diagrama de Venn

S

A

B

•
ξ4

•
ξ2

•
ξ6

•
ξ5

•
ξ1

•
ξ3

Figura: Diagrama de Venn: representación gráfica de conjuntos.

Sean ξ1, . . . , ξ6 las caras de un dado. Sea A los números divisibles por 2 y B los números

divisibles por 3. Los resultados elementales ξn pueden formar parte de uno o más eventos

(conjuntos). El conjunto universal S contiene todos los eventos posibles: , , , , , .

◦ Teoría de conjuntos 2 / 30



Convenciones del álgebra de conjuntos I

Recordatorio

• Un par de llaves { } denota un

conjunto.

• Los elementos de un conjunto se

escriben separados por una coma:

{rojo, verde, azul}.
• El conjunto o evento puede ser descrito

en palabras.

• Un conjunto siempre se representa por

una letra mayúscula (A,B, . . .)

• Si los elementos del conjunto son

letras, van en minúscula

(a, b, c, . . . , α, β, γ, . . .).

• Los elementos de un conjunto se

pueden escribir en cualquier orden y

no pueden repetirse.

◦ Teoría de conjuntos 3 / 30



Convenciones del álgebra de conjuntos II

Recordatorio

Símbolo Significado Ejemplo

∈ pertenece a a1 ∈ A
6∈ no pertenece a b1 6∈ A
⊂ es un subconjunto de {a1, a2} ⊂ A
6⊂ no es un subconjunto de {a1, a2} 6⊂ B
: tal que {n : n > 100}
| tal que {x | −20 > x}

Cuadro: Algunos símbolos matemáticos del álgebra de conjuntos

◦ Teoría de conjuntos 4 / 30



Conjunto universal, igualdad y complemento

Álgebra de conjuntos

Conjunto universal S o U, tiene todos los elementos posibles.

Igualdad Dos conjuntos A y B son iguales, denotado por A = B, si y solo si A ⊂ B y

B ⊂ A.

Complemento Se supone que A ⊂ S. El complemento del evento A, denotado A, es el

conjunto que contiene todos los elementos en S pero no en A.

A = {ξ : ξ ∈ S y ξ 6∈ A} (1)

A
S

“Hay 10 tipos de personas en el mundo: los que entienden binario (A) y los que no (A)”

◦ Teoría de conjuntos 5 / 30



Unión

Álgebra de conjuntos

La unión de dos conjuntos A y B, denotado A ∪ B, es el conjunto que contiene todos los

elementos en A, en B o en ambos.

A ∪ B = {ξ : ξ ∈ A o ξ ∈ B}
A ∪ B = {ξ : ξ ∈ A ∨ ξ ∈ B}

(2)

A B

Tiene similitud con la operación lógica OR.

◦ Teoría de conjuntos 6 / 30



Intersección

Álgebra de conjuntos

La intersección de dos conjuntos A y B, denotado A ∩ B (o simplemente AB), es el

conjunto que contiene todos los elementos que están en A y en B.

A ∩ B = {ξ : ξ ∈ A y ξ ∈ B}
A ∩ B = {ξ : ξ ∈ A ∧ ξ ∈ B}

(3)

A B

Tiene similitud con la operación lógica AND.

◦ Teoría de conjuntos 7 / 30



Diferencia

Álgebra de conjuntos

La diferencia de dos conjuntos A y B, denotado A\B (que puede leerse como “A, no B”),

es el conjunto que contiene todos los elementos que están en A pero no en B.

A\B = {ξ : ξ ∈ A y ξ 6∈ B} (4)

A B

Notar que A\B = A ∩ B.

◦ Teoría de conjuntos 8 / 30



Diferencia simétrica

Álgebra de conjuntos

La diferencia simétrica de dos conjuntos A y B, denotado A4 B, es el conjunto que

contiene todos los elementos que están en A o en B pero no en ambos.

A4 B = {ξ : ξ ∈ A o ξ ∈ B y ξ 6∈ A ∩ B} (5)

A B

Tiene similitud con la operación lógica XOR.

◦ Teoría de conjuntos 9 / 30



Conjunto vacío y conjuntos disjuntos

Álgebra de conjuntos

Conjunto vacío El conjunto que no contiene elementos es llamado conjunto vacío,

denotado ∅. Notar que ∅ = S = {}.
Conjuntos disjuntos Dos conjuntos A y B son llamados disjuntos o mutuamente

excluyentes (ME) si no contienen elementos comunes, es decir, si

A ∩ B = ∅.

A B

◦ Teoría de conjuntos 10 / 30



Extensión a más de dos conjuntos

Álgebra de conjuntos

Las definiciones de unión e intersección de dos conjuntos puede ser extendida a

cualquier número finito de conjuntos, de la forma:

N⋃
i=1

Ai = A1 ∪ A2 ∪ · · · ∪ AN

= {ξ : ξ ∈ A1 o ξ ∈ A2 o · · · o ξ ∈ AN}

(6)

N⋂
i=1

Ai = A1 ∩ A2 ∩ · · · ∩ AN

= {ξ : ξ ∈ A1 y ξ ∈ A2 y · · · y ξ ∈ AN}

(7)

◦ Teoría de conjuntos 11 / 30



Partición del conjunto universal

Álgebra de conjuntos

Si

• Ai ∩ Aj = ∅ para i 6= j (son disjuntos o mutuamente excluyentes), y

•

⋃k
i=1

Ai = S (son exhaustivos),

entonces la colección {Ai; 1 ≤ i ≤ k} se dice que forma una partición de S.

A1

A2

A3 A4

A5

◦ Teoría de conjuntos 12 / 30



El mapa político de Costa Rica como un ejemplo de “partición del

conjunto universal”

Álgebra de conjuntos

◦ Teoría de conjuntos 13 / 30



Tamaño de un conjunto

Álgebra de conjuntos

Cuando los conjuntos son contables, el tamaño (o cardinalidad) del conjunto A, denotado

|A| o n(A), es el número de elementos contenidos en A.

Cuando los conjuntos tienen un número finito de elementos, el tamaño tiene las

siguientes propiedades:

• Si A ∩ B = ∅, entonces |A+ B| = |A|+ |B|.
• |∅| = 0.

• Si A ⊂ B, entonces |A| ≤ |B|.
• |A ∪ B|+ |A ∩ B| = |A|+ |B|.

◦ Teoría de conjuntos 14 / 30



Producto de conjuntos

Álgebra de conjuntos

El producto (o producto cartesiano) de los conjuntos A y B, denotado por A× B, es el

conjunto de pares ordenados de elementos de A y B. Notar que A× B 6= B× A, y que

|C| = |A× B| = |A| × |B|.

C = A× B = {(a, b) : a ∈ A, b ∈ B} (8)

b1 b2 · · · bn
a1 (a1, b1) (a1, b2) · · · (a1, bn)
a2 (a2, b1) (a2, b2) · · · (a2, bn)
.
.
.

.

.

.

.

.

.

.
.
.

.

.

.

am (am, b1) (am, b2) · · · (am, bn)

(9)

◦ Teoría de conjuntos 15 / 30



Ejemplo del dado con números divisibles por dos y tres I

Relaciones de conjuntos

S

A

B

•
ξ4

•
ξ2

•
ξ6

•
ξ5

•
ξ1

•
ξ3

Figura: Sean ξ1, . . . , ξ6 las caras de un dado, sea

el evento A los números divisibles por 2 y el

evento B los números divisibles por 3.

• S = {ξ1, ξ2, ξ3, ξ4, ξ5, ξ6}
• S = ∅
• A = {ξ2, ξ4, ξ6}
• A = {ξ1, ξ3, ξ5}
• B = {ξ3, ξ6}
• A ∪ B = {ξ2, ξ3, ξ4, ξ6}
• A ∩ B = {ξ6}
• A\B = {ξ2, ξ4}
• B\A = {ξ3}
• A4 B = {ξ2, ξ3, ξ4}
• A ∪ B = {ξ1, ξ5}

◦ Teoría de conjuntos 16 / 30



Identidades

Álgebra de conjuntos

• S = ∅
• ∅ = S
• A = A
• S ∪ A = S
• S ∩ A = A
• A ∪ A = S
• A ∩ A = ∅

• A ∪∅ = A

• A ∩∅ = ∅

• A\B = A ∩ B

• S\A = A

• A\∅ = A

• A4 B = (A ∩ B) ∪ (A ∩ B)

◦ Teoría de conjuntos 17 / 30



Leyes del álgebra de conjuntos I

Conmutatividad El orden en que se toman los elementos no altera el resultado.

A ∪ B = B ∪ A A ∩ B = B ∩ A (10)

Asociatividad El orden en que se ejecutan las operaciones no altera el resultado.

A ∪ (B ∪ C) = (A ∪ B) ∪ C (11)

A ∩ (B ∩ C) = (A ∩ B) ∩ C (12)

◦ Teoría de conjuntos 18 / 30



Leyes del álgebra de conjuntos II

Distributividad La intersección de una unión o la unión de una intersección pueden

separarse.

A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) (13)

A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) (14)

De Morgan Complemento de una unión o de una intersección.

A ∪ B = A ∩ B (15)

A ∩ B = A ∪ B (16)

◦ Teoría de conjuntos 19 / 30



Algunos resultados útiles del análisis combinatorio



Regla de la multiplicación

En un diagrama tipo árbol donde i-ésimo nivel tiene ni ramas, entonces la cantidad de

posibles combinaciones en r niveles es n1 × n2 · · · × nr .

Ejemplo

• ¿Cuántas combinaciones posibles hay con cuatro sabores de helados y tres conos

distintos?

• ¿Cuántas combinaciones posibles hay con cuatro sabores de helados, tres conos

distintos y diez toppings?

◦ Algunos resultados útiles del análisis combinatorio 20 / 30



Posibles arreglos de un mazo de cartas con 52 cartas

Regla de la multiplicación

52! = 80 658 175 170 943 878 571 660

636 856 403 766 975 289 505 440 883

277 824 000 000 000 000

Este número es grande.

◦ Algunos resultados útiles del análisis combinatorio 21 / 30



Combinatoria enumerativa: contar (números grandes)

En muchos análisis de la situación que se estudia, es necesario

“contar” todos los resultados elementales posibles de un

experimento. Este puede ser un número muy grande.

Los principales tipos son combinaciones, permutaciones,
particiones y composiciones.

◦ Algunos resultados útiles del análisis combinatorio 22 / 30



Combinaciones

Es la selección de k ítemes de una colección de n elementos, donde el orden no importa.

nCk ≡
(
n
k

)
≡ n!

k!(n− k)!
(17)

Se lee nCk como “de n escoge k” y

(n
k

)
es el coeficiente binomial.

Ejemplo
Para hacer un grupo de cinco personas de una clase de 30 alumnos hay

30C5 ≡
(

30

5

)
≡ 30!

5!(30− 5)!
= 142 506

combinaciones posibles.

Fuentes: MathWorld (h�p://mathworld.wolfram.com/Combination.html) y Wikipedia
(h�ps://en.wikipedia.org/wiki/Combination).

◦ Algunos resultados útiles del análisis combinatorio 23 / 30

http://mathworld.wolfram.com/Combination.html
https://en.wikipedia.org/wiki/Combination


Permutaciones

Es el arreglo de k ítemes de una colección de n elementos, donde el orden sí importa.

nPk ≡
n!

(n− k)!
(18)

Se lee nPk como “de n escoge k”.

Ejemplo
Para hacer una junta directiva de cinco personas de una clase de 30 alumnos hay

30P5 ≡
30!

(30− 5)!
= 17 100 720

permutaciones posibles.

Fuentes: MathWorld (h�p://mathworld.wolfram.com/Permutation.html) y Wikipedia
(h�ps://en.wikipedia.org/wiki/Permutation).

◦ Algunos resultados útiles del análisis combinatorio 24 / 30

http://mathworld.wolfram.com/Permutation.html
https://en.wikipedia.org/wiki/Permutation


Particiones I

Coeficiente multinomial

Sean r1, ..., rl , con l un entero positivo, números tales que r1 + r2 + rl = n. Entonces, la

cantidad de formas en las que una población de n elementos puede ser particionada en l
sub-poblaciones donde la primera contiene r1 elementos, la segunda r2 y así

sucesivamente, es:

n!
r1!r2! · · · rl!

(19)

Este coeficiente es conocido como coeficiente multinominal.

◦ Algunos resultados útiles del análisis combinatorio 25 / 30



Particiones II

Coeficiente multinomial

Ejemplo
Un vendedor de autos tiene 6 carros disponibles de distinto modelo cada uno y los

quiere acomodar en grupos de 1, 2 y 3 carros respectivamente por un tema de espacio.

¿De cuántas formas distintas los puede acomodar?

nE =
6!

1!× 2!× 3!
= 60 (20)

Fuentes: Stark, H., Woods, J. (2012) Probability, Statistics, and Random Processes for Engineers. Nueva

Jersey: Pearson.

◦ Algunos resultados útiles del análisis combinatorio 26 / 30



Composiciones I

Una composición en análisis combinatorio es un arreglo ordenado de k elementos no

negativos que suman n. Es por tanto una partición en la que el orden sí importa.

Por ejemplo, hay ocho composiciones de 4,

4 = 4

= 3 + 1

= 2 + 2

= 2 + 1 + 1

= 1 + 3

= 1 + 2 + 1

= 1 + 1 + 2

= 1 + 1 + 1 + 1

◦ Algunos resultados útiles del análisis combinatorio 27 / 30



Composiciones II

Un entero positivo n tiene 2
(n−1)

composiciones.

El número de composiciones de n en k partes (donde 0 no es una parte) está dado por

Ck(n) =
(
n− 1

k − 1

)
=

(n− 1)!

(k − 1)!(n− k)!

(21)

Fuente: Stover, Christopher y Weisstein, Eric W. “Composition”. De MathWorld – A Wolfram Web

Resource. h�p://mathworld.wolfram.com/Composition.html

◦ Algunos resultados útiles del análisis combinatorio 28 / 30

http://mathworld.wolfram.com/Composition.html


Otros ejemplos I

• Una “mano de poker” consiste en cinco cartas escogidas de un mazo de 52 cartas,

¿cuántas posibilidades hay?

52C5 ≡
(

52

5

)
≡ 52!

5!(52− 5)!
= 2 598 960

• Las placas de carros en el país tienen tres consonantes y tres números, ¿cuántas

placas son posibles? ¿Se agotarán pronto?

21× 21× 21× 10× 10× 10 = 9 261 000

• Las campanas de una iglesia, tocadas al estilo inglés.

◦ Algunos resultados útiles del análisis combinatorio 29 / 30



Videos y referencias en internet

Cuando sea posible, las presentaciones tendrán referencias a videos
5

o artículos útiles. . .

o al menos entretenidos.

v How secure is 256 bit security?, 3Blue1Brown, h�ps://youtu.be/S9JGmA5_unY

v Mathematical Impressions: Change Ringing, SimonsFoundation,

h�ps://youtu.be/3lyDCUKsWZs

5

Muchas veces los videos serán en inglés, quizá con subtítulos. Aunque espero que no sea un

inconveniente, ojalá sirva de gentil recordatorio de la importancia de seguir aprendiendo inglés.

◦ Algunos resultados útiles del análisis combinatorio 30 / 30

https://youtu.be/S9JGmA5_unY
https://youtu.be/3lyDCUKsWZs

	Teoría de conjuntos
	Diagrama de Venn
	Convenciones del álgebra de conjuntos
	Conjunto universal, igualdad y complemento
	Unión
	Intersección
	Diferencia
	Diferencia simétrica
	Conjunto vacío y conjuntos disjuntos
	Extensión a más de dos conjuntos
	Partición del conjunto universal
	Tamaño de un conjunto
	Producto de conjuntos
	Identidades del álgebra de conjuntos
	Leyes del álgebra de conjuntos

	Algunos resultados útiles del análisis combinatorio
	Combinaciones
	Permutaciones
	Particiones
	Composiciones