Post on 03-Feb-2015
1
Saber Contar
• Regla de Laplace (Definición clásica)
posibles casos de Número
favorables casos de Número)( AP
A)(AP
• Ejemplo: Espacio muestral discreto y finito, con n sucesos simples:
¿cúantos subconjuntos (sucesos compuestos?) pueden formarse?
2
Principio multiplicativo (ilustración gráfica)
El primer elemento puede escogerse de dos formas distintas: a1 y a2.
El segundo de tres maneras distintas: b1, b2 y b3. El tercer elemento puede escogerse en dos modos distintos: c1 y c2.
El total de posibilidades será: 2 . 3 . 2 = 12
c1c2 c1 c2 c1 c2 c1
c2 c1c2 c1 c2
b1 b2b3 b1 b3b2
a1 a2
3
= {a,b,c} Espacio muestral discreto y finito, con n=3 sucesos simples
Sucesos compuestos: Principio multiplicativo
El total de subconjuntos posibles será: 2 . 2 . 2 = 8para n elementos : 2n
b no-b
a no_a
b no-b
c no-c c no-c c no-c c no-c
{a,b,c} {a,b} {a,c} {a} {b,c} {b} {c} {Ø}
4
Alfabeto Braille
¿Cuántos símbolos distintos pueden representarse?
6364222222654321
5
“La combinatoria trata, ante todo, de contar el número de maneras en que unos objetos dados pueden organizarse de una determinada forma.”
Introducción a la combinatoria
Ian Anderson
CombinatoriaEl arte de contar
6
Combinatoria-I (simple)Número de formas de “colocar” n objetos distintos en una fila de r posiciones (...o “extraer” r elementos de un conjunto de n objetos)Ejemplo: colocar tres objetos {a,b,c} (n=3) en r=2 posiciones
Permutaciones/Variaciones: El orden importa• ”ab” es distinto a “ba”
Combinaciones: El orden no importa• ”ab” se considera igual a “ba”
Tanto las Permutación, Variaciones como las Combinaciones pueden o no considerar la repetición (o reposición) de los objetos o elementos: ”aa” ”bb”
Permutaciones/Variaciones/Combinacionescon/sin repetición
7
Combinatoria-II (simple)Variaciones: El orden importa
Variaciones sin repetición: escoger r elementos distintos de entre un total de n según un determinado orden.
Para escoger el primer elemento hay (n) posibilidades, para el segundo (n-1),.... para el elemento r (n-r+1) = n(n-1).....(n-r+1)
{a,b,c} escoger r=2 de n=3 {ab,ba,ac,ca,bc,cb} 3!/(3-2)!=6
{a,b,c} r=2 de n=3 con repetición {ab,ba,ac,ca,bc,cb,aa,bb,cc} 32=9
123 ... )1()(
123 ...)2()1(
rnrn
nnn
r)!(n
n!n
rV
Variaciones con repetición: escoger r elementos distintos de entre un total de n según un determinado orden, y pudiendo repetirse.
Ahora hay n posibilidades para escoger cada uno de los r elementos r
nn
rVR
8
Combinatoria-III (simple)
Permutaciones sin repetición (recordad 0! = 1):
!123)2()1( nnnnPn
Permutaciones con repetición:
nn nPR
{a,b,c} Permutaciones sin repetición {abc,acb,bac,bca,cab,cba} 3!=6
{a,b,c} Permutaciones con repetición {abc,acb,bac,bca,cab,cba,aaa,bbb,ccc,aab,aba,baa,aac,aca,caa,bba,bab,abb,bbc,bcb,cbb,cca,cac,acc,ccb,cbc,bcc} 33=27
Permutaciones con n=r : (Permutaciones/Variaciones)
9
Combinatoria-IV (simple)
Combinaciones: El orden no importa
Combinaciones sin repetición: escoger r elementos distintos de entre un total de n sin que importe el orden
{a,b,c} escoger r=2 de n=3 –sin que importe el orden- {ab,ac,bc} 3!/2!(3-2)!=3
En las Combinaciones, al no importar el orden, el número de Variaciones se reduce en un factor igual al número de “ordenaciones” de los r elementos:
)!(!
!),(
rnr
n
r
nrnC
rnC
10
Combinatoria-V (simple)
Combinaciones: El orden no importa
{a,b,c} r=2 de n=3 con repetición {ab,ac,bc,aa,bb,cc} 4!/(2!.2!)=6
Combinaciones con repetición: escoger r elementos distintos de entre un total de n sin que importe el orden, y pudiendo repetirse.
11
Ejemplos
12
Si se producen aleatoriamente n accidentes de coche en n días, ¿cuál es la probabilidad de que cada día se produzca un accidente?
(Sucesos equiprobables)Nº casos posibles:El accidente 1 puede ocurrir en n posibles días. El accidente 2 en n días, idem el 3, etc... De modo que existen nn maneras posibles de que sucedan n accidentes en n días (casos posibles).
Nº casos favorables:Número de formas de colocar n accidentes en n días, un accidente cada día....
13
Si se producen aleatoriamente n accidentes de coche en n días, ¿cuál es la probabilidad de que cada día se produzca un accidente?
nnn
np!
)(
Para siete accidentes de tráfico en una semana:p(7) = 7! / 77 = 0.00612 (anti-intuitivamente baja)
Nº casos posibles: nnEl accidente 1 puede ocurrir en n posibles días. El accidente 2 en n días, idem el 3, etc...
De modo que existen nn maneras posibles de que sucedan n accidentes en n días (casos posibles).
Nº casos favorables:Número de formas de colocar n bolas en n celdas, una bola por celda.... Permutaciones sin repetición de n-elementos tomados de n en n: n!
14
¿Cuál es el número de posibles ordenaciones de una baraja de póker de 52 cartas?
El resultado es 52!, que es aproximadamente 8 × 1067. Observa que a partir de una simple baraja obtenemos un número enorme, superior, por ejemplo, al cuadrado del número de Avogadro: 6,02 × 1023.
Explosión combinatoria
Nota: 0! = 1
15
Fórmula de Stirling
nnenn 2
1
2~!
La demostración de la fórmula de Stirling puede encontrarse en la mayoría de textos de análisis. Vamos a verificar la bondad de la aproximación usando el programa StirlingApproximations, que imprime: (a) n!, (b) la aproximación de Stirling y (c) el cociente de ambos valores. Observemos como ese cociente se acerca a 1 a medida que n crece. Se dice entonces que la aproximación es asintótica.A veces, al resolver un problema de combinatoria, es mejor encontrar una aproximación asintótica formada por funciones cuyo comportamiento es fácil de comprender que la solución exacta, cuyo comportamiento escapa a nuestra intuición.
James Stirling presentó su fórmula en “Methodus Differentialis” publicado en 1730.
16
Un ascensor sube con 7 pasajeros y se detiene al cabo de 10 pisos. ¿Cuál es la probabilidad de que dos pasajeros no bajen en el mismo piso? (Supongamos que todas las posibles maneras de descender son igualmente probables).
Casos posibles: VR10,7 = 107
Casos favorables: V10,7 = 10987654
06048,010
45...9107 p
n objetos : 10 pisos escogidos de 7 en 7El orden importa – VariacionesFavorables: Dos no en el mismo piso -> no repetición
17
Algunas Propiedades
El binomio de Newton(a + b)2 = (a + b) (a + b). Todos los posibles productos son: aa, ab, ba, bb.(a + b)2 = a2 + 2ab + b2.
(a + b)3 = (a + b) (a + b) (a + b).Todos los posibles productos son: aaa, aab, aba, baa, abb, bab, bba, bbb.(a + b)3 = a3 + 3a2b + 3ab2 + b3.
(a + b)4 = a4 + 4a3b + 6a2b2 + 4ab3 + b4. C(4,0) = 1; C(4,1) = 4; C(4,2) = 6; C(4,3) = 4; C(4,4) = 1
10
N
mN
N
m
N
18
Teorema del binomio
jjnn
j
n yxj
nyx
0
nnnnn yn
nyx
n
nyx
nyx
nx
n
11221
1...
210
kn
k
kknn
k
n
k
n
k
n111110
00
010
k
nn
k
kDemostrar: nn
k k
n2
0
n
k
kknn
k
nn
k
n
k
n
00
11112