Página Principal Todo para Matemáticas Finitas Todo para Cálculo Aplicado Todo Resumen de Temas Tutoriales En Línea Utilidades En Línea
← Tema anterior Tema siguiente → Artículo de Wikipedia Ejercicios de repaso Libro de Texto Take me to the English page
Matemáticas finitas resumen del tema: conjuntos y algoritmos de recuento

Herramientas: Calculador pop-up de factoriales, permutaciones y combinaciones

Tópicos: Conjuntos y elementos | Conjuntos de resultados | Diagramas de Venn | Operaciones con conjuntos: unión, intersección, y complemento | Producto cartesiano | Cardinalidad | Algoritmo decisión | Principio multiplicativo | Principio aditivo | Permuaciones y combinaciones

Conjuntos y elementos

Un conjunto es una colección de objetos, conocidos como los elementos del conjunto.

x A significa que x es un elemento del conjunto A.
x A significa que x no es un elemento del conjunto A.
B = A significa que A y B tienen los mismos elementos.
B A significa que B es un subconjunto de A; Cada elemento de B es también un elemento de A.
B A significa que B es un conjunto propio de A; es decir, B A, pero BA.
es el conjunto vacío, el conjunto con ningunos elementos, y es un subconjunto de cada conjunto.

Un conjunto finito es un conjunto que tiene un cierto número de elementos. Un conjunto infinito es un conjunto no está finito.

Inicio de página
Ejemplos
b {a, b, c, d}
e {a, b, c, d}
{1, 2, 4, 5} = {2, 1, 5, 4}
{1, 2, 3} {1, 2, 3}
{1, 2, 3} {1, 2, 3, 4}
{1, 2, 3} {1, 2, 3, 4}
{1, 2, 3, ..., 1000} es un conjunto finito.
{1, 2, 3, ...} es un conjunto infinito.
Cada conjunto   es un subconjunto propio de sí mismo
es un subconjunto de sí mismo
no es un subconjunto de sí mismo
 
El conjunto vacío   es un subconjunto propio de cada conjunto
no es un subconjunto de sí mismo
es un subconjunto propio de cada conjunto salvo sí mismo

Inicio de página

Conjuntos de resultados

Si hacemos un tipo de experimento que tiene uno o más que uno resultados, podemos pensar de los resultados como los elementos de un conjunto de resultados asociado con el experimento. (Hay más análisis de conjuntos de resultados en el resumen de probabilidad.)

Como muestran los ejemplos, podemos con frecuencia representar el mismo conjunto de resultados en distintas maneras.

Inicio de página
Ejemplos

1. Si lanzamos una moneda al aire y observamos si sale cara o cruz, el conjunto de resultados puede expresar como

S = {águila, sol}
o simplemente
S = {a, s}.     (a = águila, s = sol)

2. Si tiramos un dado al aire cuyas caras son numerados 1 al 6, el conjunto de resultados se puede representar por

    S = { , , , , , },
o simplemente
S = {1, 2, 3, 4, 5, 6}.

3. Si tiramos dos dados distinguibles (por ejemplo, un rojo y un verde) cuyas caras son numerados 1 al 6, el conjunto de resultados se puede representar por

S =

o simplemente

    S = (1, 1),(1, 2),(1, 3),(1, 4),(1, 5),(1, 6),
    (2, 1),(2, 2),(2, 3),(2, 4),(2, 5),(2, 6),
    (3, 1),(3, 2),(3, 3),(3, 4),(3, 5),(3, 6),
    (4, 1),(4, 2),(4, 3),(4, 4),(4, 5),(4, 6),
    (5, 1),(5, 2),(5, 3),(5, 4),(5, 5),(5, 6),
    (6, 1),(6, 2),(6, 3),(6, 4),(6, 5),(6, 6)

4. Si tiramos dos dados indistinguibles (es decir, dos dados idénticos) cuyas caras son numerados 1 al 6, el conjunto de resultados se puede representar por

    S = (1, 1),(1, 2),(1, 3),(1, 4),(1, 5),(1, 6),
    (2, 2),(2, 3),(2, 4),(2, 5),(2, 6),
    (3, 3),(3, 4),(3, 5),(3, 6),
    (4, 4),(4, 5),(4, 6),
    (5, 5),(5, 6),
    (6, 6)

Inicio de página

Diagramas de Venn

Cada diagrama en el siguiente figura representa la relación muestra de abajo.


Ni A ni B un subconjunto del otro

Para ilustrar una inclusión propio, es disco que representa B debe ser más pequeña que el disco que representa A. Generalmente usamos, por sencillez, el dibujo que representa B A para representar también B A.

Inicio de página
Ejemplo

La siguiente diagrama de Venn ilustra la relación entre los tres conjuntos

{marzo}, {marzo, abril, mayo}, y {junio, julio, agosto}.

Inicio de página
Operaciones con conjuntos: unión, intersección, y complemento

La unión de A y B es el conjunto de todos los elementos que están en A o en B (o en ambos).

A B = {x | x A o x B}
Podemos representar la unión A B por la siguiente diagrama de Venn;

La intersección de A y B es el conjunto de todos los elementos que están en A y también en B.

A B = {x | x A y x B}
Podemos representar la intersección A B por la siguiente diagrama de Venn;

Si A es un subconjunto de S, entonces A' es el complemento de A en S, el conjunto de todos los elementos de S que no están en A.

Podemos representar el complemento A' por la siguiente diagrama de Venn:

Inicio de página
Ejemplos

Sea S el conjunto de todos números enteros, y sea

A = {2, 4, 6, 8}
B = {5, 6, 7, 8}
C = {números enteros pares}
D = {1, 2, 3}.

Entonces

A B = {2, 4, 5, 6, 7, 8}
A B = {6, 8}
A C = A
C' = {0, 1, -1, -2, 3, -3, -4, 5, -5, . . .}
A (B C) = A.

A D = { }
   
A D = { }
   
D A' = { }
   
A (B D) = { }
   

Tenemos también las leyes de Morgan, que son consecuencias de las definiciones más arriba:

Leyes de Morgan

(A B)' = A' B'
(A B)' = A' B'

Pulse aquí y avance a la discusión después de Ejemplo 7 para ver los homólogos en lógica proposicional (¡y haga una visita al entero sitio de lógica ya que está en eso!).

Inicio de página
Producto cartesiano

El producto cartesiano de dos conjuntos, A y B, es el conjunto de todos pares ordenados (a, b) tal que a A y b B.

A × B = { (a, b) | a A y b B }.

En palabras:

A×B es el conjunto de todos pares ordenados tal que la primera coordenada pertenece a A y la segunda coordenada pertenece a B.

Inicio de página
Ejemplos

1. Si A = {a, b} y B = {1, 2, 3}, entonces

A × B = { (a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3) }.

2. Sea S = {a, s}.       (a representa águila, s representa sol)

S × S = { (a,a), (a,s), (s,a), (s,s) }.

En otras palabras, si S es el conjunto de resultados cuando lanzamos una moneda una vez, entonces S×S es el conjunto de resultados cuando lanzamos una moneda dos veces (o un par de monedas distinguibles una vez).

3. S = {1, 2, 3, 4, 5, 6}    El conjunto de resultados por tirar un dado

S × S =
(1, 1),(1, 2),(1, 3),(1, 4),(1, 5),(1, 6),
(2, 1),(2, 2),(2, 3),(2, 4),(2, 5),(2, 6),
(3, 1),(3, 2),(3, 3),(3, 4),(3, 5),(3, 6),
(4, 1),(4, 2),(4, 3),(4, 4),(4, 5),(4, 6),
(5, 1),(5, 2),(5, 3),(5, 4),(5, 5),(5, 6),
(6, 1),(6, 2),(6, 3),(6, 4),(6, 5),(6, 6)

En otras palabras, si S es el conjunto de resultados cuando tiramos un dado una vez, entonces S×S es el conjunto de resultados cuando tiramos un dado dos veces (o un par de dados distinguibles una vez).

4. Sea A = {Mustang, Firebird} y B = {Rojo, Amarillo}. Entonces

A×B = { (Mustang, Rojo), (Firebird, Rojo), (Mustang, Amarillo), (Firebird, Amarillo)},

que podemos escribir también como

A×B = { Mustang Rojo, Firebird Rojo, Mustang Amarillo, Firebird Amarillo }.

Inicio de página
Cardinalidad

Si A es un conjunto finito, entonces n(A), el número de elementos que contiene A, se llama la cardinalidad de A.

Si A y B son conjuntos finitos, entonces

n(A B) = n(A) + n(B) - n(A B).
En particular, si A y B son disjuntos (es decir, A B = ), entonces
n(A B) = n(A) + n(B).

Si S es un conjunto universal finito y A es un subconjunto de S, entonces

n(A') = n(S) - n(A) y n(A) = n(S) - n(A').

Si A y B son conjuntos finitos, entonces

n(A×B) = n(A).n(B)

Inicio de página
Ejemplos

1. Sea S el conjunto de todos naipes en una baraja estándar (inglés; es decir, 13 naipes de cada palo) y sea

D = conjunto de diamantes;   n(D) = 13
T = conjunto de treces;   n(T) = 4
C = conjunto de corazones   n(C) = 13.

Entonces

n(D C) = n(D) + n(C)   pues D C =
= 13 +13 = 26
n(D T) = n(D) + n(T) - n(D T)
= 13+4-1 = 16
n(D') = n(S) -n(D)
= 52-13 = 39.

2. Sea

P = conjunto de palos = {picas, corazones, diamantes, tréboles}
D = conjunto de denominaciones = {2, 3, 4, 5, 6, 7, 8, 9, J, Q, K, A}
Entonces n(P×D) = 4×13 = 52, representando todos los naipes en la baraja.

Inicio de página
Algoritmo decisión

Un algoritmo decisión es un procedimiento con reglas precisas para cada paso.

Podemos utilizar algoritmos decisiones para ayudarnos contar el número de elementos posibles en cualquier conjunto como sigue:

A. Formule un algoritmo decisión
Si está preguntado cuantos elementos posibles hay, imagine que está contruyendo tal elemento, y describa un procedimiento paso a paso --- es decir, un algoritmo decisión --- para hacerlo. Enumere los pasos, mostrando el número de elecciones en cada paso.

B. Aplique la siguiente "prueba de fuego"
Pregúntese la siguiente: "¿Suponga siguiera el algoritmo dos veces, pero eligiera una o más que una distinta elecciones la segunda vez. Entonces llegara a un resultado distinto? Si la respuesta es siempre "si," entonces su algoritmo es válido. Si no es válido su algoritmo, necesita buscar un otro.

Inicio de página
Ejemplo

Aquí son dos algoritmos decisiones para contar el núero de distintas secuencias de cinco letras conteniendo dos "a"s, una "i", una "e", y una "d". El primero algoritmo no será válido, y no cumple la "prueba de fuego," y el segundo es válido.

Algoritmo decisión 1 (No válido)
Imagine que esté construyendo tal secuencia por meter las cinco letras, una a una, en cinco ranuras vacías:
Resultado posible
1. Meta la primera "s."
(5 ranuras vacías de la que escoger)
    s
2. Meta la segunda "s."
(4 ranuras sobrando de la que escoger)
s   s
3. Meta la "i."
(3 ranuras sobrando de la que escoger)
si  s
4. Mea la "e."
(2 ranuras sobrando de la que escoger)
si es
5. Meta la "d."
(1 ranura sobrando de la que escoger)
sides

Prueba de fuego
Puedes obtener la misma secuencia "sides" por intercambiar las elecciones de pasos 1 y 2. Entonces, este algoritmo no cumple con la prueba de fuego, y no es válido por consiguiente.

Algoritmo decisión 2 (Válido)
Imagine que esté construyendo tal secuencia por asignar grupos de ranuras vacías a las cuatro letras distintas (comenzando con las letras que ocurren una vez por sencillez):
Resultado posible
1. Asigne una ranura para la "i."
(5 ranuras vacías de la que escoger)
    i
2. Asigne una ranura para la "e."
(4 ranuras sobrando de la que escoger)
e   i
3. Asigne una ranura para la "d."
(3 ranuras sobrando de la que escoger)
ed  i
4. Asigne un par de ranuras para las "s".
(1 par de ranuras sobrando de la que escoger)
edssi

Prueba de fuego
Cambiando una o más que una elección en cualquier paso dará una secuencia distinta. Entonces este algoritmo cumple con la prueba de fuego y por consiguiente es válido.

Inicio de página
Principio multiplicativo

Si un algoritmo decisión requiere varios pasos, tal que Paso 1 tiene n1 resultados, Paso 2 tiene n2 resultados, ... , Paso r tiene nr resultados, entonces el numero de resultados del algoritmo es n1 × n2 × ... × nr.

Inicio de página
Ejemplo

Mire otra vez al segundo algoritmo decisión más arriba. El número de resultados de cada paso es como sigue:

Paso 1:   5 resultados posibles
Paso 2:   4 resultados posibles
Paso 3:   3 resultados posibles
Paso 4:   1 resultados posibles
Entonces, el número total de resultados es
5×4×3×1 = 60. En otras palabras, hay un total de 60 distintas secuencias de cinco letras conteniendo dos "a"s, una "i", una "e", y una "d".

Inicio de página
Principio aditivo

Si un algoritmo decisión requiere una elección entre varias alternativas, entonces se obtiene el número de resultados del algoritmo por sumar los números de resultados de cada alternativa.

Inicio de página
Ejemplo

En este ejemplo, combinamos los principios multiplicativo y aditivo para calcular el número total de comidas con dos platos posible del siguiente menú:

Menú

Sopa Du Joir
Crema de la Crema

Crema de Tomate

Platos Principales
Rosbif con Papas o Coles de Bruselas

Lomo de cerdo con Manzana, Mango, o Papaya

Que tenga un buen día

Algoritmo decisión:

Paso 1: Escoja una sopa: 2 elecciones
Paso 2: Escoja un plato principal:

    Alternativa 1: Rosbif: 2 elecciones de acompañamiento
    Alternativa 2: Cerdo: 3 elecciones de acompañamiento
El principio aditivo da un total de 2+3 = 5 elecciones para Paso 2. El principio multiplicativo ya da 2×5 = 10 elecciones de comidas.

Inicio de página
Permutaciones y combinaciones

Una permutación de r objetos tomados de entre n objetos es una lista ordenada de r objetos escogido de un conjunto de n objetos. El número de permutaciones de r objetos tomados de entre n objetos se expresa por

    P(n, r)=n × (n-1) × (n-2) × . . . × (n-r+1)
    =
    n!

    (n-r)!
    .
En la formua más arriba,
n! = 1×2×3×...×(n-1)× n
se llama "n factorial."

Una combinación de r objetos tomados de entre n objetos es un conjunto (no ordenado) de r objetos escogido de un conjunto de n objetos. El número de combinaciones de r objetos tomados de entre n objetos se expresa por

    C(n, r)=
    P(n, r)

    r!
    =
    n!

    r! (n-r)!
    .
    =
    n×(n-1)×...×(n-r+1)

    r×(r-1) ×...×2×1
    .

Notas

0! = 1   Cero factorial equivale 1.
Por lo tanto se puede decir que C(n, 0) =
n!

0! n!
=
n!

n!
= 1
Si a y b suman n, entonces
    C(n ,a) = C(n, b)
  Vea los ejemplos

Inicio de página
Ejemplos
    P(7, 3)=7×6×5=210.
    C(7, 3)=
    7×6 ×5

    3×2×1
    =35.

Pues 5 y 2 suman 7, tenemos

    C(7, 5) = C(7, 2) =
    7×6

    2×1
    =21.

P(4, 1) =    
P(4, 4) =    
C(4, 2) =    
C(4, 0) =    
C(4, 4) =    
C(100, 98) =    

Preube la Calculador pop-up de factoriales, permutaciones y combinaciones para practicar más.

Inicio de página
Ultima actualización: abril 2009
Derechos de autor © Stefan Waner

Inicio de página