0 Prob1

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