Apunte 0 - Teoría de conjuntos y Técnicas de conteo

Vista previa del material en texto

Teoría de conjuntos
➔ Fórmulas de los complementos: A∪A=Ω ; A∩A=∅ ; Ω=∅
➔ Fórmula de la partición: ∀ B , A=( A∩B )∪( A∩B )
➔ Fórmulas de DeMorgan: A∪B=A∩B ; A∩B=A∪B
➔ Propiedades permutativas: A∪B=B∪A ; A∩B=B∩A
➔ Propiedades asociativas: {( A∪B )∪C = A∪( B∪C ) = A∪B∪C( A∩B )∩C = A∩( B∩C ) = A∩B∩C}
➔ Propiedades distributivas: {( A∪B )∩C = ( A∩C )∪( B∩C )( A∩B )∪C = ( A∪C )∩( B∪C )}
Técnicas de conteo
Principio(s) fundamental(es) del conteo:
Ley del producto: Si un cierto evento
puede suceder de m formas , y otro
cierto evento puede suceder de n formas
independientes del primero, entonces la
cantidad de formas en que puede suceder
los dos eventos simultáneamente es m⋅n
. ''y''⇔∩⇔⋅
Ley de la suma: Si un cierto evento puede
suceder de m formas , y otro cierto evento
puede suceder de n formas distintas al
primero, entonces la cantidad de formas en
que puede suceder alguno de los dos eventos
(o bien uno, o bien el otro) es m+n .
 ''o''⇔∪⇔+
Con n elementos todos distinguibles en tre si se forman arreglos de r
elementos cada uno: (modelo urna-arreglo)
No se pueden repetir elementos Se pueden repetir elementos
Im
po
rt
a
el
 o
rd
en
Permutaciones
(Variaciones)
(Ordenaciones)
Pr
n= n !
(n−r)!
=n⋅(n−1)⋅…⋅(n−(r−1))⏟
r factores
{(AB);(AC);(BA);(BC);(CA);(CB)} nPr
P'r
n=nr
xy
{(AA);(AB);(AC);…
…(BA);(BB);(BC);…
…(CA);(CB);(CC)}
Permutaciones
(r=n)
Pn=n! ! 
{(ABC);(ACB);…
…;(BAC);(BCA);…
…;(CAB);(CBA)}
P'n=nn
xy
{(AAA);(AAB);(AAC);(ABA);…
…;(ABB);(ABC);(ACA);(ACB);…
…;(ACC);(BAA);(BAB);(BAC);…
…;(BBA);(BBB);(BBC);(BCA);…
…;(BCB);(BCC);(CAA);(CAB);…
…;(CAC);(CBA);(CBB);(CBC);…
…;(CCA);(CCB);(CCC)}
N
o
im
po
rt
a
el
 o
rd
en
Combinaciones
Cr
n=(nr )= n !(n−r )!⋅r ! =
Pr
n
Pr
 
{{AB};{AC};{BC}} nCr
C'r
n=((nr ))=(r+(n−1)(n−1) )=(n+r−1)!r !⋅(n−1)!
{{AA};{AB};{AC};{BB};{BC};{CC}}
Permutaciones con categorías o clases: Si se tienen n1 elementos de una clase, n2 de
otra clase,..., nk de la última clase, y elementos de la misma clase son indistinguibles entre
si; entonces la cantidad de permutaciones distinguibles que se pueden contar son:
Pn
(n1 ;n2;…;nk)= n !
(n1 !)⋅(n2 !)⋅…⋅(nk !)
 donde n=n1+n2+…+nk es #(elementos totales)
Repartición de elementos indistinguibles: Si se tienen r elementos indistinguibles
entre si, la cantidad de forma en que estos pueden ser repartidos entre n categorías
diferentes es equivalente a la cantidad de formas de ordenar en línea r elementos
indistinguibles con (n−1) separadores. Estas formas son ((nr ))=P r+n−1( r ;n−1)
Apuntes de aula (no reemplaza la bibliografía correspondiente) Sergio QUINTEROS Reportar cualquier error a 6106tl@gmail.com