Sistemas Aleatorios: Técnicas de Conteo · Una forma de denotar el numero de combinaciones es C...

Sistemas Aleatorios: Tecnicas de Conteo

Computacion / Matematicas

MA2006

Computacion / Matematicas Sistemas Aleatorios: Tecnicas de Conteo

Primer Regla del Producto

Si el primer elemento u objeto de un par ordenado puede serseleccionado de n1 maneras y por cada una de estas n1 maneras elsegundo elemento del par puede ser seleccionado de n2 maneras,entonces el numero de pares es n1 · n2.


Ejemplo

El propietario de una casa que va a llevar a cabo una remodelacionrequiere los servicios tanto de un contratista de fontanerıa como deun contratista de electricidad. Si existen 12 contratistas defontanerıa y 9 contratistas electricistas disponibles en el area, ¿decuantas maneras pueden ser elegidos los contratistas?


Ejemplo

El propietario de una casa que va a llevar a cabo una remodelacionrequiere los servicios tanto de un contratista de fontanerıa como deun contratista de electricidad. Si existen 12 contratistas defontanerıa y 9 contratistas electricistas disponibles en el area, ¿decuantas maneras pueden ser elegidos los contratistas?Sean Pl , . . . , Pl2 los fontaneros y Ql , . . . ,Q9 los electricistas,entonces se desea el numero de pares de la forma (Pi ,Qj). Conn1 = 12 y n2 = 9, la regla de producto da N = (12)(9) = 108formas posibles de seleccionar los dos tipos de contratistas.


Ejemplo

Una familia se acaba de cambiar a una nueva ciudad y requiere losservicios tanto de un obstetra como de un pediatra. Existen dosclınicas medicas facilmente accesibles y cada una tiene dosobstetras y tres pediatras. La familia obtendra los maximosbeneficios del seguro de salud si se une a la clınica y seleccionaambos doctores de la clınica. ¿De cuantas maneras se puede haceresto?


Ejemplo

Una familia se acaba de cambiar a una nueva ciudad y requiere losservicios tanto de un obstetra como de un pediatra. Existen dosclınicas medicas facilmente accesibles y cada una tiene dosobstetras y tres pediatras. La familia obtendra los maximosbeneficios del seguro de salud si se une a la clınica y seleccionaambos doctores de la clınica. ¿De cuantas maneras se puede haceresto?Denote los obstetras por O1, O2, O3 y 04 y los pediatras por P1,. . . , P6. Entonces se desea el numero de pares (Oi ,Pj) para loscuales 0i y Pj estan asociados con la misma clınica. Como existencuatro obstetras, n1 = 4, y por cada uno existen tres opciones depediatras, por lo tanto n2 = 3. Aplicando la regla de producto seobtienen N = n1 · n2 = 12 posibles opciones.


Regla general del producto

Supongase que un conjunto se compone de conjuntos ordenados dek elementos (k-tuplas) y que existen n1 posibles opciones para elprimer elemento por cada opcion del primer elemento, existen n2posibles opciones del segundo elemento; . . . ; por cada posibleopcion de los primeros k − 1 elementos, existen nk opciones delelemento k-esimo. Existen entonces n1 · n2 · · · · · nk posiblesk-tuplas.


Ejemplo

(Continuacion del ejemplo inmediato anterior) Suponga que eltrabajo de remodelacion de la casa implica adquirir primero variosutensilios de cocina. Se adquiriran en la misma tienda y hay cincotiendas en el area.


Ejemplo

(Continuacion del ejemplo inmediato anterior) Suponga que eltrabajo de remodelacion de la casa implica adquirir primero variosutensilios de cocina. Se adquiriran en la misma tienda y hay cincotiendas en el area.Con las tiendas denotadas por D1, . . . , D5, existenN = n1 · n2 · n3 = (5)(12)(9) = 540 3-tuplas (triadas) de la forma(Di ,Pj ,Qk); ası que existen 540 formas de elegir primero unatienda, luego un contratista de fontanerıa y finalmente uncontratista electricista.


Ejemplo

Si cada clınica tiene dos especialistas en medicina interna y dosmedicos generales, existen n1 · n2 · n3 · n4 = (4)(3)(3)(2) = 72formas de seleccionar un doctor de cada tipo de tal suerte quetodos los doctores practiquen en la misma clınica.


Ejemplo

En el alfabeto Braile se construye cada sımbolo utilizando unamatriz (3× 2) de 6 puntos algunos de ellos en relieve o realzados ylos otros no. Determine el numero de caracteres que se puederepresentar si no se puede elegir la configuracion donde ningunoesta realzados. Son tan pocos que se requiere anteponer otrosımbolo para indicar como interpretar la matriz de puntos.Determine el numero de caracteres que se puede representar con 8puntos.


Ejemplo

Un restaurante ofrece una seleccion de 4 aperitivos, 14 entradas, 6postres y 5 bebidas. De cuantas maneras se puede disenar unacomida suponiendo que se tiene suficiente hambre para hacercualquier seleccion?


Ejemplo

Una octava contiene 12 notas distintas: en un piano 5 de esasnotas estan en teclas negras y 7 en teclas blancas. Cuantasdiferentes melodias de 8 notas se pueden construir con las notas deuna octava si solo deben usarse notas en teclas blancas?


Ejemplo

En el alfabeto o codigo Morse las letras o numeros sonrepresentados por puntos o rayas. Por ejemplo, S es tres puntos yO es tres rayas. Cuando se usa en telegrafıa la duracion del sonidoraya es aproximadamente 3 puntos. La distancia entre doscaractares de una palabra son aproximadamente 3 puntos, mientrasque la separacion entre dos palabras es el equivalente a 5 puntos.Cuantos caracteres se requerirıan para representar solo letras (29)y numeros (10)?


Ejemplo

Una pizerıa ofrece rapida ofrece una seleccion de 8 toppings paracada una de las pizas. De cuantas maneras se un cliente puedeescoger si la seleccion incluye de 1 a 4 toppings diferentes?


Ejemplo

Suponga que el formato de las placas de Nuevo Leon es de tresletras seguido de un numero de 3 dıgitos. La primera letra estaentre N y S. Determine el total de placas posibles para Nuevo Leon.


Ejemplo

Determine el numero de enteros entre 100 y 999 que tienen sustres dıgitos diferentes. ¿Cuantos de esos son impares?


Permutacion y Combinacion

Un subconjunto ordenado se llama permutacion. El numero depermutaciones de tamano r que se puede formar con los nindividuos u objetos en un grupo sera denotado por Pn,r (nPk).Un subconjunto no ordenado se llama combinacion. Una forma dedenotar el numero de combinaciones es Cn,r (nCr), pero en sulugar se utilizara una notacion que es bastante comun en libros de

probabilidad:

(nr

), que se lee de n se eligen r .


Formula de Pn,r

Pn,r =n!

(n − r)!


Ejemplo

Suponga que de 7 alumnos se va a elegir un comite: presidente,vicepresidente y tesorero. ¿Cuantos comites es posible formar?


Ejemplo

Suponga que de 7 alumnos se va a elegir un comite: presidente,vicepresidente y tesorero. ¿Cuantos comites es posible formar? Eneste caso n = tamano del grupo = 7 y r = tamano delsubconjunto = 3. El numero de permutaciones es

P7,3 =7!

(7− 3)!=

7!

4!= 7 · 6 · 5 = 210

Es decir, el total de comites que es posible formar es de 210.


Ejemplo

Continue con el ejemplo anterior y suponga que los comites sonigualmente probables y que Pedro es uno de los 7 alumnos.Responda:

En cuantos comites estara Pedro como presidente?

En cuantos comites estara Pedro?

En cuantos comites no estara Pedro?


Ejemplo

¿De cuantas maneras las letras de COMPUTER pueden serarreglas en una lınea?

¿De cuantas maneras las letras de COMPUTER pueden serarreglas en una lınea si la CO debe considerarse como unaunidad?


Ejemplo

Una reunion de 6 diplomaticos (digamos A, B, C, D, E y F) sellevara a cabo usando una mesa circular. A pesar de que la mesano tiene cabecera y no importa la posicion absoluta, sı importa larelativa.

¿De cuantas maneras se pueden sentarse los diplomaticos?

¿De cuantas manearas se pueden sentar para que A quedeentre B y F?


Ejemplo

Existen diez asistentes de profesor disponibles para calificarexamenes en un curso de calculo en una gran universidad. Elprimer examen se compone de cuatro preguntas y el profesor deseaseleccionar un asistente diferente para calificar cada pregunta (soloun asistente por pregunta). ¿De cuantas maneras se pueden elegirlos asistentes para calificar?


Ejemplo

Existen diez asistentes de profesor disponibles para calificarexamenes en un curso de calculo en una gran universidad. Elprimer examen se compone de cuatro preguntas y el profesor deseaseleccionar un asistente diferente para calificar cada pregunta (soloun asistente por pregunta). ¿De cuantas maneras se pueden elegirlos asistentes para calificar?En este caso n = tamano del grupo = 10 y r = tamano delsubconjunto = 4. El numero de permutaciones es

P10,4 =10!

(10− 4)!=

10!

6!= 10 · 9 · 8 · 7 = 5040

Es decir, el profesor podrıa aplicar 5040 examenes diferentes decuatro preguntas sin utilizar la misma asignacion de calificadores apreguntas.


Formula de Cn,k

Cn,r =

(nr

)=

n!

r ! · (n − r)!


Ejemplo

Suponga que se tiene un departamento con 10 empleados y que seelige el jefe del departamento de la siguiente manera. Hay unaseleccion interna de tres candidatos. De los cuales el jefe de lacomanıa selecciona uno. ¿Cual es el numero total de posiblesselecciones internas?. Suponga que Pedro es uno de los 10empleados, cual es el numero total de ternas donde Pedro estapresente?


Ejemplo

De 12 personas 5 seran seleccionadas para formar un grupo detrabajo. Suponga que 2 miembros insisten que en caso de serseleccionadas deben ir las dos. ¿De cuantas maneras se puedeformar los equipos? Si los equipos se forman al azar, ¿cual sera laprobabilidad de que queden juntas? Si tales miembros ahora noquieren ir juntos en caso se ser seleccionados, ¿de cuantas manerasse pueden formar los equipos?


Ejemplo

El almacen de una universidad recibio 25 impresoras, de las cuales10 son impresoras laser y 15 son modelos de inyeccion de tinta. Si6 de estas 25 se seleccionan al azar para que revise un tecnicoparticular, ¿cual es la probabilidad de que exactamente 3 de lasseleccionadas sean impresoras laser (de modo que las otras 3 seande inyeccion de tinta)?


Solucion

Sea D3 = {exactamente 3 de las 6 seleccionadas son impresoras deinyeccion de tinta}. Suponiendo que cualquier conjunto particularde 6 impresoras es tan probable de ser elegido como cualquier otroconjunto de 6, se tienen resultados igualmente probables, por lotanto P(D3) = N(D3)/N, donde N es el numero de formas deelegir 6 impresoras de entre las 25 y N(D3) es el numero de formasde elegir 3 impresoras laser y 3 de inyeccion de tinta. lo tantoN = C25,6. Para obtener N(D3), primero se piensa en elegir 3 delas 15 impresoras inyeccion de tinta y luego 3 de las impresoraslaser. Existen C15,2 formas de elegir las 3 impresoras de inyeccionde tinta y C10,3 formas de elegir las 3 impresoras laser; N(D3) es elproducto de estos dos numeros:

P(D3) =N(D3)

N=

(153

)(103

)(

266

) =


Ejemplo

Se tiene un equipo de 13 programadores.

1 ¿De cuantas maneras se pueden escoger 7 personas paratrabajar en un proyecto?

2 Suponga que en el equipo 7 son hombres y 6 son mujeres:

¿Cuantos grupos de 7 pueden ser escogidos para que 4 seanmujeres y 3 sean hombres?¿Cuantos grupos de 7 se pueden escoger con al menos 1hombre?¿Cuantos grupos de 7 se pueden escoger con a lo mas 3mujeres?

3 Suponga que hay dos personas (x y y) que se reusan atrabajar juntas, ¿cuantos equipos se pueden formar?


Ejemplo

Se tiene un equipo de 13 programadores.1 ¿De cuantas maneras se pueden escoger 7 personas para

trabajar en un proyecto?

NT =

(137

)=

13 · 12 · 11 · 10 · 9 · 8 · 7!

6 · 5 · 4 · 3 · 2 · 1 · 7!= 1716


¿Cuantos grupos de 7 pueden ser escogidos para que 4 seanmujeres y 3 sean hombres?¿Cuantos grupos de 7 se pueden escoger con al menos 1hombre?¿Cuantos grupos de 7 se pueden escoger con a lo mas 3mujeres?

3 Suponga que hay dos personas (x y y) que se reusan a trabajarjuntas, ¿cuantos equipos se pueden formar?


Ejemplo



NT =

(137

)=

13 · 12 · 11 · 10 · 9 · 8 · 7!

6 · 5 · 4 · 3 · 2 · 1 · 7!= 1716


¿Cuantos grupos de 7 pueden ser escogidos para que 4 seanmujeres y 3 sean hombres? N1 = Nnumw=4 · Nnumm=3

¿Cuantos grupos de 7 se pueden escoger con al menos 1hombre?¿Cuantos grupos de 7 se pueden escoger con a lo mas 3mujeres?



Ejemplo



NT =

(137

)=

13 · 12 · 11 · 10 · 9 · 8 · 7!

6 · 5 · 4 · 3 · 2 · 1 · 7!= 1716



¿Cuantos grupos de 7 se pueden escoger con al menos 1hombre? N2 = NT − Nnummen=0

¿Cuantos grupos de 7 se pueden escoger con a lo mas 3mujeres?



Ejemplo



NT =

(137

)=

13 · 12 · 11 · 10 · 9 · 8 · 7!

6 · 5 · 4 · 3 · 2 · 1 · 7!= 1716




¿Cuantos grupos de 7 se pueden escoger con a lo mas 3mujeres? N3 = Nnumw=0 + Nnumm=1 + Nnumw=2 + Nnumm=3



Ejemplo



NT =

(137

)=

13 · 12 · 11 · 10 · 9 · 8 · 7!

6 · 5 · 4 · 3 · 2 · 1 · 7!= 1716




¿Cuantos grupos de 7 se pueden escoger con a lo mas 3mujeres? N3 = Nnumw=0 + Nnumm=1 + Nnumw=2 + Nnumm=3

3 Suponga que hay dos personas (x y y) que se reusan a trabajarjuntas, ¿cuantos equipos se pueden formar?N4 = Nx esta + Ny esta + Nx,y no estan


Sistemas Aleatorios: Técnicas de Conteo · Una forma de denotar el numero de combinaciones es C...

Documents

Transcript of Sistemas Aleatorios: Técnicas de Conteo · Una forma de denotar el numero de combinaciones es C...