28-01-2013, 11:19 PM
Análisis combinatorio
Cardinal de un conjunto finito:
Es el número de elementos de dicho conjunto.
Ejemplo:
Sea el conjunto \( A = \left\{ a, b, c \right\} \), su cardinal será: \( card(A) = 3 \).
Propiedades:
· Producto de cardinales:
Dados dos conjuntos finitos \( A \) y \( B \), se cumple que el cardinal del producto cartesiano \( A × B \), es igual a la multiplicación de los cardinales de \( A \) y \( B \).
$$ card(A×B) = card(A) · card(B) $$
Ejemplo:
Sean dos conjuntos \( A = \left\{ a, b, c \right\}, B = \left\{ x, y \right\} \).
Nótese lo siguiente: \( card(A) = 3, card(B) = 2 ⇒ card(A·B) = 3·2 = 6 \).
De hecho: \( A·B = \left\{ (a,x),(a,y),(b,x),(b,y),(c,x),(c,y) \right\} \).
· Regla del producto:
Si una situación u objeto \( A \), puede elegirse de \( m \) formas distintas, y otro objeto o situación \( B \), puede elegirse posteriormente de \( p \) formas distintas, entonces, la elección de \( A \) y \( B \) (en el orden indicado), se puede realizar de \( m·p \) maneras.
· Cardinal de la unión de dos conjuntos:
Dados dos conjuntos finitos \( A \) y \( B \), que además son disjuntos ( \( A∩B=∅ \) ), se cumple que el cardinal del conjunto unión ( \( A∪B \)), es igual a la suma de los cardinales \( A \) y \( B \).
$$ si: A∩B=∅ → card(A∪B) = card(A) + card(B) $$
$$ si: A∩B≠∅ → card(A∪B) = card(A) + card(B) - card(A∩B) $$
Arreglos:
Sea \( A \) un conjunto de \( m \) elementos, y un número natural \( k \), tal que \( 1 ≤ k ≤ m \), se denomina arreglo de orden \( k \), a cada k-upla conformada por \( k \) elementos distintos del conjunto \( A \).
Ejemplo:
Sea el conjunto \( A = \left\{ a, b, c \right\} \).
Son arreglos de primer orden del conjunto \( A : (a), (b), ( c ) \).
Son arreglos de segundo orden del conjunto \( A : (a,b), (b,a), (a,c), ... \).
Son arreglos de tercer orden del conjunto \( A : (a,b,c), (b,a,c), (a,c,b), ... \).
Número de arreglos:
Se denomina número de arreglos de orden \( k \), de un conjunto \( A \) de \( m \) elementos, denotado: \( A_{k}^m \), al cardinal del conjunto de arreglos.
Teorema sobre el número de arreglos:
El número de arreglos de orden \( k \), de un conjunto \( A \) de \( m \) elementos, está dado por la expresión.
$$ A_{k}^{m} = \frac {m!}{(m-k)!} $$
Cardinal de un conjunto finito:
Es el número de elementos de dicho conjunto.
Ejemplo:
Sea el conjunto \( A = \left\{ a, b, c \right\} \), su cardinal será: \( card(A) = 3 \).
Propiedades:
· Producto de cardinales:
Dados dos conjuntos finitos \( A \) y \( B \), se cumple que el cardinal del producto cartesiano \( A × B \), es igual a la multiplicación de los cardinales de \( A \) y \( B \).
$$ card(A×B) = card(A) · card(B) $$
Ejemplo:
Sean dos conjuntos \( A = \left\{ a, b, c \right\}, B = \left\{ x, y \right\} \).
Nótese lo siguiente: \( card(A) = 3, card(B) = 2 ⇒ card(A·B) = 3·2 = 6 \).
De hecho: \( A·B = \left\{ (a,x),(a,y),(b,x),(b,y),(c,x),(c,y) \right\} \).
· Regla del producto:
Si una situación u objeto \( A \), puede elegirse de \( m \) formas distintas, y otro objeto o situación \( B \), puede elegirse posteriormente de \( p \) formas distintas, entonces, la elección de \( A \) y \( B \) (en el orden indicado), se puede realizar de \( m·p \) maneras.
· Cardinal de la unión de dos conjuntos:
Dados dos conjuntos finitos \( A \) y \( B \), que además son disjuntos ( \( A∩B=∅ \) ), se cumple que el cardinal del conjunto unión ( \( A∪B \)), es igual a la suma de los cardinales \( A \) y \( B \).
$$ si: A∩B=∅ → card(A∪B) = card(A) + card(B) $$
$$ si: A∩B≠∅ → card(A∪B) = card(A) + card(B) - card(A∩B) $$
Arreglos:
Sea \( A \) un conjunto de \( m \) elementos, y un número natural \( k \), tal que \( 1 ≤ k ≤ m \), se denomina arreglo de orden \( k \), a cada k-upla conformada por \( k \) elementos distintos del conjunto \( A \).
Ejemplo:
Sea el conjunto \( A = \left\{ a, b, c \right\} \).
Son arreglos de primer orden del conjunto \( A : (a), (b), ( c ) \).
Son arreglos de segundo orden del conjunto \( A : (a,b), (b,a), (a,c), ... \).
Son arreglos de tercer orden del conjunto \( A : (a,b,c), (b,a,c), (a,c,b), ... \).
Número de arreglos:
Se denomina número de arreglos de orden \( k \), de un conjunto \( A \) de \( m \) elementos, denotado: \( A_{k}^m \), al cardinal del conjunto de arreglos.
Teorema sobre el número de arreglos:
El número de arreglos de orden \( k \), de un conjunto \( A \) de \( m \) elementos, está dado por la expresión.
$$ A_{k}^{m} = \frac {m!}{(m-k)!} $$