Modelos EstocásticosModelos Estocásticos
Métodos Combinatorios y Métodos Combinatorios y Números AleatoriosNúmeros Aleatorios
SESIÓN 01SESIÓN 01
Métodos Combinatorios 1Métodos Combinatorios 1• Teorema 1.1 (Regla de multiplicación de posibilidades) Si
una operación consta de dos pasos, de los cuales el primero puede efectuarse en n1 formas y para cada una de éstas el segundo puede realizarse en n2 formas, entonces toda la operación se lleva a cabo de n1*n2 maneras.
• ¿De cuántas formas se puede viajar entre Italia, Alemania, Suiza, Francia y España si podemos viajar en autobús, tren o avión?
Rpta. n1 = 5, n2 = 3 El viaje puede hacerse de 15 formas
• ¿Cuántos productos posibles existen cuando se tira un dado rojo y uno verde?
Rpta. 6*6 = 36 formas
Métodos Combinatorios 2Métodos Combinatorios 2• Teorema 1.2 Si una operación consta de “k” pasos, de los cuales el
primero puede efectuarse en n1 formas, para cada una de éstas el segundo puede realizarse en n2 maneras, para cada una de éstas el tercero puede realizarse en n3 formas, etc., entonces toda la operación puede llevarse a cabo en n1*n2 *...* nk formas.
* ¿Cuántos almuerzos diferentes son posibles, si se componen de una sopa, un emparedado, un postre y una bebida y puede elegirse entre cuatro sopas, tres tipos de emparedados, cinco postres y cuatro bebidas? Rpta. 4*3*5*4 = 240
• ¿En cuántas formas puede marcarse una prueba de verdadero y falso que consta de 20 preguntas? Rpta. 2*2*2*…*2*2 (20 factores) = 1.048.576 formas (1 solo caso correcto)
• Teorema 1.3 El número de permutaciones de n objetos distintos es: Pn = n!
¿Cuántas permutaciones hay de las letras a, b y c? Rpta. 6• Teorema 1.4 El número de r permutaciones con repetición, sobre un
conjunto de n elementos es: nr
Métodos Combinatorios 3Métodos Combinatorios 3
• Teorema 1.5 (Variaciones) El numero de permutaciones de n objetos diferentes tomados r a la vez es
para r = 0, 1, 2, …,n• ¿Cuál es el número de permutaciones de las letras a, b, c
y d, tomadas de dos en dos? Rpta. 12 *Se toman 4 nombres de los 24 miembros de un club para
ocupar los cargos de presidente, vicepresidente, tesorero y secretario. ¿En cuantas formas diferentes puede hacerse? Rpta. 255.024
• ¿En cuántas formas se puede programar a 3 oradores para 3 reuniones diferentes, si todos están disponibles en cualquiera de 5 fechas posibles? Rpta. 60
)!(
!
rn
nVP nrrn
Métodos Combinatorios 4Métodos Combinatorios 4
• Teorema 1.6 (Permutaciones circulares) El número de permutaciones de n objetos distintos ordenados en un círculo en (n-1)!
* ¿Cuántas permutaciones circulares hay de cuatro personas que juegan q-negra? Rpta. 3! = 6 arreglos
• Teorema 1.7 El número de permutaciones de n objetos de los cuales n1 son de un tipo, n2 son de un segundo tipo,…,nk son de un k-ésimo tipo, y n1+n2+…+nk = n, es
!!...!
!
21 knnn
n
Métodos Combinatorios 5Métodos Combinatorios 5
* ¿Cuántas permutaciones hay en la palabra book?
Rpta. 24/2 = 12
*¿Cuántas permutaciones hay en la palabra receive?
Rpta. 7!/3! = 840
*¿En cuántas formas se puede ordenar 2 robles, 3 pinos y 2 arces en una línea recta si no se hace distinción entre árboles de la misma clase?
Rpta. 7!/(2!3!2!) = 210
Métodos Combinatorios 6Métodos Combinatorios 6
• Teorema 1.8 (Combinaciones) El número de combinaciones de r objetos seleccionados de un conjunto de n objetos distintos es
para r = 0, 1, 2, …, n
* ¿En cuántas formas puede entrevistar una persona que recolecta datos para una empresa a tres de las 20 familias que viven en cierta casa de apartamentos?
Rpta. 1.140 formas
)!(!
!
rnr
n
r
nC nr
Métodos Combinatorios 7Métodos Combinatorios 7
* ¿En cuántas formas diferentes pueden producir 6 lanzamientos al aire de una moneda, dos caras y cuatro cruces? Rpta. 15
* ¿Cuántos comités de dos químicos y un físico pueden formarse con cuatro químicos y tres físicos? Rpta. 18
• Teorema 1.9 (Combinaciones con repetición) El número de combinaciones de r objetos tomados entre n, con repetición es
1'
)!1(!
)!1(
rnr
nr C
nr
rnC
Métodos Combinatorios 8Métodos Combinatorios 8
• Teorema 1.10 El número de maneras de dividir o partir un conjunto de n objetos distintos en k subconjuntos con n1 objetos en el primer subconjunto, n2 objetos en el segundo, …, y nk en el k-ésimo subconjunto, es
* ¿En cuántas formas puede dividirse un conjunto de cuatro objetos en tres subconjuntos que contengan, 2, 1 y 1 de los objetos?
Rpta. 12 particiones* ¿En cuántas formas pueden asignarse 7 científicos a un cuarto
triple y dos dobles de un hotel?Rpta. 210 formas
!!...!
!
,...,, 2121 kk nnn
n
nnn
n
Métodos Combinatorios 9Métodos Combinatorios 9
• Distribución de Fermi-Dirac: Se considera N objetos idénticos (N = n1 + n2 + … nm), m cajas, divididas en m celdas (g1, g2, … gm)
),...,(),...,(
),...,(
)!(!
!),...,(
11
1
11
mm
Nm
iii
im
im
nnnnP
nn
ngn
gnn
Métodos Combinatorios 10Métodos Combinatorios 10
• Distribución de Bose - Einstein: Se considera N objetos idénticos (N = n1 + n2 + … nm), m cajas, divididas en m celdas (g1, g2, … gm)
),...,(),...,(
),...,(
)!1(!
)!1(),...,(
11
1
11
mm
Nm
ii
iim
im
nnnnP
nn
gn
gnnn
Métodos Combinatorios 11Métodos Combinatorios 11
• Aproximación de Stirling: Cuando n es muy grande, la aproximación es la siguiente:
• En forma de integral (función Gamma):
n
e
nnx
2!
0
)1(! dttexx xt
Coeficientes Binomiales 1Coeficientes Binomiales 1
• Teorema 1.11 La fórmula del binomio es:
para cualquier entero positivo n
rrnn
r
n yxr
nyx
0
)(
Coeficientes Binomiales 1Coeficientes Binomiales 1
• Teorema 1.12 Para dos enteros positivos cualquiera n y r = 0, 1, 2, …, n,
* ¿En cuántas formas puede dividirse un conjunto de cuatro objetos en tres subconjuntos que contengan, 2, 1 y 1 de los objetos?
Rpta. 12 particiones* ¿En cuántas formas pueden asignarse 7 científicos a un cuarto
triple y dos dobles de un hotel?Rpta. 210 formas
rn
n
r
n
Coeficientes Binomiales 2Coeficientes Binomiales 2
• Teorema 1.13 Para cualquier entero positivo n y r = 1, 2, …, n,
• Teorema 1.14
1
11
r
n
r
n
r
n
k
nm
rk
n
r
nk
r 0
Coeficientes Binomiales 3Coeficientes Binomiales 3
• Teorema 1.15 El coeficiente multinomial del término x1
r1x2r2*…*xk
rk en la expansión de (x1+x2+…+xk)n es
!!...!
!
,...,, 2121 kk rrr
n
rrr
n
ProbabilidadProbabilidad
• Teorema 1.16: Probabilidad es la razón entre el evento que sucede, partido para el número total de eventos
N
k
Card
ACardAP
)(
)(
totaleseventos
favorables eventos)(
tricaHipergeomé
n
n-nn
)( 1
1
1
1
k
kkkAP
binomial :Bernoulli
)1(n
)( knk ppk
AP
Números Aleatorios 1Números Aleatorios 1
• Números aleatorios: Quien intente generar números aleatorios mediante medios deterministas esta evidentemente viviendo en pecado (Von Neuman)
• Experimento aleatorio: En el lanzamiento de una moneda: Cara (C) o Sello (S): CCSSSSCSS: 6 S y 4 C: p = 0.6 y q = 0.4
• Por el Teorema del Límite Central y la Ley de los Grandes Números: p = q = 0.5
Números Aleatorios 2Números Aleatorios 2
• Generador de números aleatorios:• Excel: = aleatorio ()
(número aleatorio entre 0 y 1) = aleatorio.entre (a;b)(número aleatorio entre los números a y b)
• Matlab: c = randint(4,4,[1,10])(matriz 4x4 de aleatorios entre 1 y 10)
• Mathematica: Table[Random[Integer,{10,20}],{10}](vector de números aleatorios enteros entre 10 y 20)
Comentarios HistóricosComentarios HistóricosCombinatoriaCombinatoria
• En 1730 N. L. Biggs (1979) s métodos combinatorios
Comentarios HistóricosComentarios HistóricosExperimentos AleatoriosExperimentos Aleatorios
• Buffon realizó 4040 lanzamientos de una moneda, resultando C: 2048 y S: 1992
• En 1927, L. H. C. Tippett publicó una lista de 41,600 números aleatorios
• En 1955, la RAND Corporation publicó la table de 1,000,000 números aleatorios generados por ruido electrónico