Camino.
Es una sucesión de lados que van de un nodo x a un nodo w (dichos lados se pueden repetir).
Circuito o ciclo.
Es un camino del nodo w al nodo w, esto es, un camino que regresa al mismo nodo de donde salió.
Circuito simple de longitud n.
Es aquel camino del nodo w al nodo w que solamente tiene un ciclo en la ruta que sigue.
Camino simple de longitud n.
Es una sucesión de lados que van de un nodo x a un nodo w, en donde los lados que componen dicho camino son distintos e iguales a n. Esto significa que no se puede pasar dos veces por una misma arista.
Camino de Euler.
Es aquel camino que recorre todos los nodos pasando por todas las aristas solamente una vez. Una característica importante de los grafos que tienen camino de Euler es que siempre comienzan y terminan en nodos que terminan en valencia impar.
Circuito de Euler.
Es aquel ciclo que recorre todos los nodos pasando por todos las aristas solamente una vez.
Un grafo tiene un Circuito de Euler si y solo si es conexo y todos sus nodos tienen valencia par.
Algoritmo de Fleury.
Nos permite determinar un circuito de Euler:
1)Verificar que el grafo sea conexo y que todos los nodos tengan valencia par. Si no cumple el grafo no tiene circuito de Euler y finalizar.
2)Si cumple con la condición anterior, seleccionar un nodo arbitrario para iniciar el recorrido.
3)Escoger una arista a partir del nodo actual. Esa arista seleccionada no debe de ser “lado puente”, a menos que no exista otra opción.
4)Desconectar los nodos que están unidos por la arista seleccionada.
5)Si todos los nodos del grafo ya estan desconectados, ya se tiene un circuito de Euler y finalizar. De otra manera continuar con el paso 3.
miércoles, 6 de mayo de 2009
Representación matricial de grafos
Matriz de adyacencia.
Es una matriz cuadrada en la cual los nodos del grafo se indican como renglones y como columnas. El orden de los nodos es el mismo que guardan los renglones y las columnas de la matriz. Se coloca 1 como elemento de la matriz cuando existe una relación entre uno y otro vertice, o bien un 0 cuando no exista relación alguna.
Nota: en una matriz de adyacencia no es posible representar lados paralelo.
Matriz de incidencia.
En esta matriz se colocan los nodos del grafo como renglones y las aristas como columnas. En esta matriz si es posible representar lados paralelos. Al sumar los elementos de cada una de los renglones se obtiene la valencia de los nodos, al sumar las columnas es posible distinguir cuando se trata de un lazo ya que su suma es 1.
Es una matriz cuadrada en la cual los nodos del grafo se indican como renglones y como columnas. El orden de los nodos es el mismo que guardan los renglones y las columnas de la matriz. Se coloca 1 como elemento de la matriz cuando existe una relación entre uno y otro vertice, o bien un 0 cuando no exista relación alguna.
Nota: en una matriz de adyacencia no es posible representar lados paralelo.
Matriz de incidencia.
En esta matriz se colocan los nodos del grafo como renglones y las aristas como columnas. En esta matriz si es posible representar lados paralelos. Al sumar los elementos de cada una de los renglones se obtiene la valencia de los nodos, al sumar las columnas es posible distinguir cuando se trata de un lazo ya que su suma es 1.
martes, 5 de mayo de 2009
Grafos.
Grafo.
Los grafos son representaciones de redes y por medio de ellos se pude expresar en forma visual y sencilla la relación entre elementos.
En computación los grafos se utilizan para mostrar las relaciones entre archivos en una base de datos, entre registros en una estructura de datos, entre computadoras en una red.
Partes de un grafo.
Un grafo (G) es un diagrama que consta de un conjunto de nodos (Vértices) y un conjunto de aristas (lados).
Nodos. Se indican por medio de un pequeño circulo y se le asigna un numero o una letra.
Aristas. Son las lineas que unen un nodo con otro y se les asigna una letra un numero o una combinación de ambos.
Aristas paralelas. Son las aristas que tienen relación con un mismo par de nodos.
Lazo. Es aquella arista que sale de un nodo y regresa al mismo nodo.
Valencia de un nodo. Es el numero de aristas que salen o entran a un nodo.
Tipos de grafos.
Grafos simples. Son aquellos grafos que no tienen lazos ni aristas paralelas.
Grafo completo de orden N. Es el grafo en donde cada nodo esta relacionado con todos los demas, sin lazos ni lados paralelos. Se indica Kn en donde n es el numero de nodos. La valencia de cada uno de los nodos de los grafos completos esta dada por la expresión:
numero de aristas= n(n-1)/2
en donde n es el numero de nodos.
Grafo bipartito completo. Es el grafo que esta compuesto por dos conjuntos de nodos, uno de ellos A={a1, a2, a3, ....., an} y otro B={b1, b2, .....,bm} y en el que cada nodo de A esta unido con todos los nodos de B, pero entre los nodos del mismo conjunto no existe ninguna arista que los una. Se indica como Kn,m en donde n y m es el numero de nodos de cada uno de los conjuntos.
Grafo dirigido. Es el grafo en donde las aristas tienen asociadas una dirección.
Complemento de un grafo. Es el grafo que le falta al grafo G, de forma que entre ambos forman un grafo completo de n vertices. Este grafo no tiene lazos ni ramas paralelas.
Los grafos son representaciones de redes y por medio de ellos se pude expresar en forma visual y sencilla la relación entre elementos.
En computación los grafos se utilizan para mostrar las relaciones entre archivos en una base de datos, entre registros en una estructura de datos, entre computadoras en una red.
Partes de un grafo.
Un grafo (G) es un diagrama que consta de un conjunto de nodos (Vértices) y un conjunto de aristas (lados).
Nodos. Se indican por medio de un pequeño circulo y se le asigna un numero o una letra.
Aristas. Son las lineas que unen un nodo con otro y se les asigna una letra un numero o una combinación de ambos.
Aristas paralelas. Son las aristas que tienen relación con un mismo par de nodos.
Lazo. Es aquella arista que sale de un nodo y regresa al mismo nodo.
Valencia de un nodo. Es el numero de aristas que salen o entran a un nodo.
Tipos de grafos.
Grafos simples. Son aquellos grafos que no tienen lazos ni aristas paralelas.
Grafo completo de orden N. Es el grafo en donde cada nodo esta relacionado con todos los demas, sin lazos ni lados paralelos. Se indica Kn en donde n es el numero de nodos. La valencia de cada uno de los nodos de los grafos completos esta dada por la expresión:
numero de aristas= n(n-1)/2
en donde n es el numero de nodos.
Grafo bipartito completo. Es el grafo que esta compuesto por dos conjuntos de nodos, uno de ellos A={a1, a2, a3, ....., an} y otro B={b1, b2, .....,bm} y en el que cada nodo de A esta unido con todos los nodos de B, pero entre los nodos del mismo conjunto no existe ninguna arista que los una. Se indica como Kn,m en donde n y m es el numero de nodos de cada uno de los conjuntos.
Grafo dirigido. Es el grafo en donde las aristas tienen asociadas una dirección.
Complemento de un grafo. Es el grafo que le falta al grafo G, de forma que entre ambos forman un grafo completo de n vertices. Este grafo no tiene lazos ni ramas paralelas.
sábado, 28 de febrero de 2009
Solución a los ejercicios del dia jueves 26 de febrero
1.- Una señora desea invitar a cenar a 5 de 11 amigos que tiene.
a) ¿Cuántas maneras tiene de invitarlos?
b) ¿Cuántas maneras tiene si entre ellos está una pareja de recién casados y no asisten el uno sin el otro. c) ¿Cuántas maneras tiene de invitarlos si Rafael y Arturo no se llevan bien y no van juntos?
Solucion:
a) 462 maneras de invitarlos
b) 210 maneras de invitarlos
c) 378 maneras de hacer la invitación.
2.- Cuantas cadenas de 8 bits contienen exactamente cuatro unos?
Solución:
70 cadenas.
3.- Una baraja de 52 cartas consta de 4 palos: Tréboles, diamantes, corazones y espadas; con 13 denominaciones cada uno as, 2-10, jack, reina y rey.
a) Cuantas manos de póquer de 5 cartas (no ordenadas) puede elegirse de una baraja ordinaria de 52 cartas.
b) Cuantas manos de póquer de 5 cartas tienen todas las cartas del mismo palo.
c) Cuantas manos de póquer de 5 cartas tienen 3 cartas de una denominación y 2 cartas de una segunda denominación.
Solución:
a) 2,598,960
b) 5,148
c)3,744
4.- De cuantas maneras se puede formar una fila con cinco marcianos distintos y ocho jupiterianos distintos si ningún par de marcianos debe de estar junto.
Solución:
33,868,800
5.- a) ¿Cuántas maneras hay de asignar las 5 posiciones diferentes de juego de un equipo de básquetbol, si el equipo consta de 12 integrantes?
b) ¿Cuántas maneras hay de asignar las posiciones de juego si una de ellas solo puede ser ocupada por Uriel José Esparza?
c) ¿Cuántas maneras hay de que se ocupen las posiciones de juego si es necesario que en una de ellas este Uriel José Esparza y en otra Omar Luna?
Solución:
a) 95,040
b) 7,920
c) 720
6.- a) Cuántas claves de acceso a una computadora será posible diseñar, si debe constar de dos letras, seguidas de cinco dígitos, las letras serán tomadas del abecedario y los números de entre los dígitos del 0 al 9.
Considere que se pueden repetir letras y números.
b) Considere que no se pueden repetir letras y números.
c) ¿Cuántas de las claves del inciso b empiezan por la letra A y terminan por el número 6?
d) ¿Cuántas de las claves del inciso b tienen la letra R seguida de la L y terminan por un número impar?
Solución:
a) 67,600,000 claves de acceso
b) 19,656,000 claves de acceso
c) 75,600 claves de acceso que empiezan por la letra A y terminan por el número 6
d) 15,120 claves de acceso
7.- Con las letras de la palabra “libro”, ¿cuántas ordenaciones distintas se pueden hacer que empiecen por vocal?
Solución:
48
8.- De cuantas maneras 3 americanos, 4 franceses, 4 daneses y 2 italianos pueden sentarse en una fila de forma que los de la misma nacionalidad se sienten juntos.
Solución:
165,888
ESTUDIENLE MUCHO NOS VEMOS EN EL EXAMEN!!!!
a) ¿Cuántas maneras tiene de invitarlos?
b) ¿Cuántas maneras tiene si entre ellos está una pareja de recién casados y no asisten el uno sin el otro. c) ¿Cuántas maneras tiene de invitarlos si Rafael y Arturo no se llevan bien y no van juntos?
Solucion:
a) 462 maneras de invitarlos
b) 210 maneras de invitarlos
c) 378 maneras de hacer la invitación.
2.- Cuantas cadenas de 8 bits contienen exactamente cuatro unos?
Solución:
70 cadenas.
3.- Una baraja de 52 cartas consta de 4 palos: Tréboles, diamantes, corazones y espadas; con 13 denominaciones cada uno as, 2-10, jack, reina y rey.
a) Cuantas manos de póquer de 5 cartas (no ordenadas) puede elegirse de una baraja ordinaria de 52 cartas.
b) Cuantas manos de póquer de 5 cartas tienen todas las cartas del mismo palo.
c) Cuantas manos de póquer de 5 cartas tienen 3 cartas de una denominación y 2 cartas de una segunda denominación.
Solución:
a) 2,598,960
b) 5,148
c)3,744
4.- De cuantas maneras se puede formar una fila con cinco marcianos distintos y ocho jupiterianos distintos si ningún par de marcianos debe de estar junto.
Solución:
33,868,800
5.- a) ¿Cuántas maneras hay de asignar las 5 posiciones diferentes de juego de un equipo de básquetbol, si el equipo consta de 12 integrantes?
b) ¿Cuántas maneras hay de asignar las posiciones de juego si una de ellas solo puede ser ocupada por Uriel José Esparza?
c) ¿Cuántas maneras hay de que se ocupen las posiciones de juego si es necesario que en una de ellas este Uriel José Esparza y en otra Omar Luna?
Solución:
a) 95,040
b) 7,920
c) 720
6.- a) Cuántas claves de acceso a una computadora será posible diseñar, si debe constar de dos letras, seguidas de cinco dígitos, las letras serán tomadas del abecedario y los números de entre los dígitos del 0 al 9.
Considere que se pueden repetir letras y números.
b) Considere que no se pueden repetir letras y números.
c) ¿Cuántas de las claves del inciso b empiezan por la letra A y terminan por el número 6?
d) ¿Cuántas de las claves del inciso b tienen la letra R seguida de la L y terminan por un número impar?
Solución:
a) 67,600,000 claves de acceso
b) 19,656,000 claves de acceso
c) 75,600 claves de acceso que empiezan por la letra A y terminan por el número 6
d) 15,120 claves de acceso
7.- Con las letras de la palabra “libro”, ¿cuántas ordenaciones distintas se pueden hacer que empiecen por vocal?
Solución:
48
8.- De cuantas maneras 3 americanos, 4 franceses, 4 daneses y 2 italianos pueden sentarse en una fila de forma que los de la misma nacionalidad se sienten juntos.
Solución:
165,888
ESTUDIENLE MUCHO NOS VEMOS EN EL EXAMEN!!!!
jueves, 26 de febrero de 2009
Combinaciones y permutaciones.
Combinación: Es todo arreglo de elementos en donde no nos interesa el lugar o posición que ocupa cada uno de los elementos que constituyen dicho arreglo.
Permutación: Es todo arreglo de elementos en donde nos interesa el lugar o posición que ocupa cada uno de los elementos que constituyen dicho arreglo.
Se plantea el siguiente ejemplo:
Suponga que un salón de clase está constituido por 35 alumnos.
a) El maestro desea que tres de los alumnos lo ayuden en actividades tales como mantener el aula limpia o entregar material a los alumnos cuando así sea necesario.
b) El maestro desea que se nombre a los representantes del salón (Presidente, Secretario y Tesorero).
Solución:
a) Suponga que por unanimidad se ha elegido a Daniel, Arturo y a Rafael para limpiar el aula o entregar material, (aunque pudieron haberse seleccionado a Rafael, Daniel y a Enrique, o pudo haberse formado cualquier grupo de tres personas para realizar las actividades mencionadas anteriormente).
¿Es importante el orden como se selecciona a los elementos que forma el grupo de tres personas?
Reflexionando al respecto nos damos cuenta de que el orden en este caso no tiene importancia, ya que lo único que nos interesaría es el contenido de cada grupo, dicho de otra forma, ¿quiénes están en el grupo? Por tanto, este ejemplo es una combinación, quiere decir esto que las combinaciones nos permiten formar grupos o muestras de elementos en donde lo único que nos interesa es el contenido de los mismos.
b) Suponga que se han nombrado como representantes del salón a Daniel como Presidente, a Arturo como secretario y a Rafael como tesorero, pero resulta que a alguien se le ocurre hacer algunos cambios, los que se muestran a continuación:
Presidente: Daniel
Secretario: Arturo
Tesorero: Rafael
Presidente:Daniel
Secretario: Rafael
Tesorero: Arturo
Presidente:Rafael
Secretario: Daniel
Tesorero: Arturo
Presidente:Rafael
Secretario: Arturo
Tesorero: Daniel
Ahora tenemos cuatro arreglos, ¿se trata de la misma representación?
La respuesta sería no, ya que el cambio de función que se hace a los integrantes de la representación original hace que definitivamente cada una de las representaciones trabaje de manera diferente, ¿importa el orden de los elementos en los arreglos?. La respuesta definitivamente sería sí, luego entonces las representaciones antes definidas son diferentes ya que el orden o la forma en que se asignan las funciones sí importa, por lo tanto es este caso estamos tratando con permutaciones.
La formula para las permutaciones es: nPr = n! / (n-r)!
Esta fórmula nos permitirá obtener todos aquellos arreglos en donde el orden es importante y solo se usen parte (r) de los n objetos con que se cuenta, además hay que hacer notar que no se pueden repetir objetos dentro del arreglo, esto es, los n objetos son todos diferentes.
Ejemplos:
1) ¿Cuantas representaciones diferentes serán posibles formar, si se desea que consten de Presidente, Secretario, Tesorero, Primer Vocal y Segundo Vocal?, sí esta representación puede ser formada de entre 25 miembros del sindicato de una pequeña empresa.
Solución:
n = 25, r = 5
25P5 = 25!/ (25 –5)! = 25! / 20! = (25 x 24 x 23 x 22 x 21 x....x 1) / (20 x 19 x 18 x ... x 1)=
= 6,375,600 maneras de formar la representación
2) a. ¿Cuántas maneras diferentes hay de asignar las posiciones de salida de 8 autos que participan en una carrera de fórmula uno? (Considere que las posiciones de salida de los autos participantes en la carrera son dadas totalmente al azar) b. ¿Cuántas maneras diferentes hay de asignar los primeros tres premios de esta carrera de fórmula uno?
Solución:
n = 8, r = 8
8P8= 8! = 8 x 7 x 6 x 5 x 4 x......x 1= 40,320 maneras de asignar las posiciones de salida ......etc., etc.
b. Por principio multiplicativo:
8 x 7 x 6 = 336 maneras de asignar los tres primeros lugares de la carrera
Por fórmula:
n =8, r = 3
8P3 = 8! / (8 – 3)! = 8! / 5! = (8 x 7 x 6 x 5 x ........x1)/ (5 x 4 x 3 x......x1) = 336 maneras de asignar los tres primeros lugares de la carrera
La formula de las combinaciones es: nCr = n! / (n-r)! r!
Ejemplos:
1) a. Si se cuenta con 14 alumnos que desean colaborar en una campaña pro limpieza del Tec, cuantos grupos de limpieza podrán formarse si se desea que consten de 5 alumnos cada uno de ellos, b.si entre los 14 alumnos hay 8 mujeres, ¿cuantos de los grupos de limpieza tendrán a 3 mujeres?, c.¿cuántos de los grupos de limpieza contarán con 4 hombres por lo menos?
Solución:
a. n = 14, r = 5
14C5 = 14! / (14 – 5 )!5! = 14! / 9!5!
= 14 x 13 x 12 x 11 x 10 x 9!/ 9!5!
= 2002 grupos
Entre los 2002 grupos de limpieza hay grupos que contienen solo hombres, grupos que contienen solo mujeres y grupos mixtos, con hombres y mujeres.
n = 14 (8 mujeres y 6 hombres), r = 5
En este caso nos interesan aquellos grupos que contengan 3 mujeres y 2 hombres
8C3*6C2 = (8! / (8 –3)!3!)*(6! / (6 – 2)!2!)
= (8! / 5!3!)*(6! / 4!2!)
= 8 x7 x 6 x 5 /2!
= 840 grupos con 3 mujeres y 2 hombres, puesto que cada grupo debe constar de 5 personas
c. En este caso nos interesan grupos en donde haya 4 hombres o más
Los grupos de interés son = grupos con 4 hombres + grupos con 5 hombres
= 6C4*8C1 + 6C5*8C0 = 15 x 8 + 6 x 1 = 120 + 6 = 126
Combinación: Es todo arreglo de elementos en donde no nos interesa el lugar o posición que ocupa cada uno de los elementos que constituyen dicho arreglo.
Permutación: Es todo arreglo de elementos en donde nos interesa el lugar o posición que ocupa cada uno de los elementos que constituyen dicho arreglo.
Se plantea el siguiente ejemplo:
Suponga que un salón de clase está constituido por 35 alumnos.
a) El maestro desea que tres de los alumnos lo ayuden en actividades tales como mantener el aula limpia o entregar material a los alumnos cuando así sea necesario.
b) El maestro desea que se nombre a los representantes del salón (Presidente, Secretario y Tesorero).
Solución:
a) Suponga que por unanimidad se ha elegido a Daniel, Arturo y a Rafael para limpiar el aula o entregar material, (aunque pudieron haberse seleccionado a Rafael, Daniel y a Enrique, o pudo haberse formado cualquier grupo de tres personas para realizar las actividades mencionadas anteriormente).
¿Es importante el orden como se selecciona a los elementos que forma el grupo de tres personas?
Reflexionando al respecto nos damos cuenta de que el orden en este caso no tiene importancia, ya que lo único que nos interesaría es el contenido de cada grupo, dicho de otra forma, ¿quiénes están en el grupo? Por tanto, este ejemplo es una combinación, quiere decir esto que las combinaciones nos permiten formar grupos o muestras de elementos en donde lo único que nos interesa es el contenido de los mismos.
b) Suponga que se han nombrado como representantes del salón a Daniel como Presidente, a Arturo como secretario y a Rafael como tesorero, pero resulta que a alguien se le ocurre hacer algunos cambios, los que se muestran a continuación:
Presidente: Daniel
Secretario: Arturo
Tesorero: Rafael
Presidente:Daniel
Secretario: Rafael
Tesorero: Arturo
Presidente:Rafael
Secretario: Daniel
Tesorero: Arturo
Presidente:Rafael
Secretario: Arturo
Tesorero: Daniel
Ahora tenemos cuatro arreglos, ¿se trata de la misma representación?
La respuesta sería no, ya que el cambio de función que se hace a los integrantes de la representación original hace que definitivamente cada una de las representaciones trabaje de manera diferente, ¿importa el orden de los elementos en los arreglos?. La respuesta definitivamente sería sí, luego entonces las representaciones antes definidas son diferentes ya que el orden o la forma en que se asignan las funciones sí importa, por lo tanto es este caso estamos tratando con permutaciones.
La formula para las permutaciones es: nPr = n! / (n-r)!
Esta fórmula nos permitirá obtener todos aquellos arreglos en donde el orden es importante y solo se usen parte (r) de los n objetos con que se cuenta, además hay que hacer notar que no se pueden repetir objetos dentro del arreglo, esto es, los n objetos son todos diferentes.
Ejemplos:
1) ¿Cuantas representaciones diferentes serán posibles formar, si se desea que consten de Presidente, Secretario, Tesorero, Primer Vocal y Segundo Vocal?, sí esta representación puede ser formada de entre 25 miembros del sindicato de una pequeña empresa.
Solución:
n = 25, r = 5
25P5 = 25!/ (25 –5)! = 25! / 20! = (25 x 24 x 23 x 22 x 21 x....x 1) / (20 x 19 x 18 x ... x 1)=
= 6,375,600 maneras de formar la representación
2) a. ¿Cuántas maneras diferentes hay de asignar las posiciones de salida de 8 autos que participan en una carrera de fórmula uno? (Considere que las posiciones de salida de los autos participantes en la carrera son dadas totalmente al azar) b. ¿Cuántas maneras diferentes hay de asignar los primeros tres premios de esta carrera de fórmula uno?
Solución:
n = 8, r = 8
8P8= 8! = 8 x 7 x 6 x 5 x 4 x......x 1= 40,320 maneras de asignar las posiciones de salida ......etc., etc.
b. Por principio multiplicativo:
8 x 7 x 6 = 336 maneras de asignar los tres primeros lugares de la carrera
Por fórmula:
n =8, r = 3
8P3 = 8! / (8 – 3)! = 8! / 5! = (8 x 7 x 6 x 5 x ........x1)/ (5 x 4 x 3 x......x1) = 336 maneras de asignar los tres primeros lugares de la carrera
La formula de las combinaciones es: nCr = n! / (n-r)! r!
Ejemplos:
1) a. Si se cuenta con 14 alumnos que desean colaborar en una campaña pro limpieza del Tec, cuantos grupos de limpieza podrán formarse si se desea que consten de 5 alumnos cada uno de ellos, b.si entre los 14 alumnos hay 8 mujeres, ¿cuantos de los grupos de limpieza tendrán a 3 mujeres?, c.¿cuántos de los grupos de limpieza contarán con 4 hombres por lo menos?
Solución:
a. n = 14, r = 5
14C5 = 14! / (14 – 5 )!5! = 14! / 9!5!
= 14 x 13 x 12 x 11 x 10 x 9!/ 9!5!
= 2002 grupos
Entre los 2002 grupos de limpieza hay grupos que contienen solo hombres, grupos que contienen solo mujeres y grupos mixtos, con hombres y mujeres.
n = 14 (8 mujeres y 6 hombres), r = 5
En este caso nos interesan aquellos grupos que contengan 3 mujeres y 2 hombres
8C3*6C2 = (8! / (8 –3)!3!)*(6! / (6 – 2)!2!)
= (8! / 5!3!)*(6! / 4!2!)
= 8 x7 x 6 x 5 /2!
= 840 grupos con 3 mujeres y 2 hombres, puesto que cada grupo debe constar de 5 personas
c. En este caso nos interesan grupos en donde haya 4 hombres o más
Los grupos de interés son = grupos con 4 hombres + grupos con 5 hombres
= 6C4*8C1 + 6C5*8C0 = 15 x 8 + 6 x 1 = 120 + 6 = 126
lunes, 23 de febrero de 2009
Métodos de conteo.
En muchos problemas discretos nos enfrentamos situaciones que implican conteos. El conteo también tiene un papel crucial en la teoría de la probabilidad.
Analicemos el siguiente ejemplo:
Restaurante Ronald
Entradas:
Nachos (N) .........$15
Ensaladas (E)......$20
Platos principales:
Hamburguesa (H).$40
Harburgesa
con queso (Q).....$50
Filete (F).............$50
Bebidas:
Te (T)...................$5
Leche (L).............$5
C. Cola (C)..........$5
Vino (V)..............$10
Cuantas comidas diferentes constan de un plato principal y una bebida?
Si enumeramos las comidas posibles que constan de un plato principal y una bebida obtenemos:
HT,HL,HC,HV,QT,QL,QC,QV,FT,FL,FC,FV
vemos que hay 12 comidas diferentes, observen que hay 3 comidas principales y 4 bebidas, y que 3*4=12.
Cuantas comidas diferentes constan de una entrada, un plato principal y una bebida?
NHT,NHL,NHC,NHV,NQT,NQL,NQC,NQV,NFT,NFL,NFC,NFV,EHT,EHL,EHC,EHV,EQT,EQL,EQC,EQV,EFT,EFL,EFC,EFV
vemos que hay 24 comidas diferentes, observen que hay 2 entradas, 3 comidas principales y 4 bebidas, y que 2*3*4=12.
Principio de multiplicación.
Si una actividad puede construirse en t pasos sucesivos y el paso 1 puede realizarse de n1 formas; el paso 2 de n2 formas; y el paso t puede realizarse de nt formas entonces el numero de diferentes actividades posibles es n1*n2*.....*nt.
Cuantas comidas diferentes constan de una entrada, un plato principal y una bebida?
Existen 3 formas de elegir un plato principal (Hamburguesa, hamburguesa con queso, filete) y 5 formas de escoger una bebida opcional (te, leche, c.cola, vino, ninguna), por lo tanto:
por el principio de multiplicación 3*5=15 comidas.
Cuantas cadenas de 8 bits comienzan con 101 o con 111?
cadenas con 101 2*2*2*2*2=32
cadenas con 111 2*2*2*2*2=32
por lo tanto las cadenas que comienzan con 101 o con 111 son 32+32=64
Principio de la suma.
Supongamos que X1 y X2 son conjuntos y que el numero de elementos de X1 es n1 y el numero de elementos de X2 es n2. Si X1 ∩ X2 =∅ el numero de elementos posibles que pueden elegirse de X1 o X2 es:
n1 + n2
Si estamos contando objetos que se construyen por pasos, utilizamos el principio de la multiplicación. Si tenemos conjuntos ajenos de objetos y queremos conocer la cantidad de objetos, utilizamos el principio de la suma.
En muchos problemas discretos nos enfrentamos situaciones que implican conteos. El conteo también tiene un papel crucial en la teoría de la probabilidad.
Analicemos el siguiente ejemplo:
Restaurante Ronald
Entradas:
Nachos (N) .........$15
Ensaladas (E)......$20
Platos principales:
Hamburguesa (H).$40
Harburgesa
con queso (Q).....$50
Filete (F).............$50
Bebidas:
Te (T)...................$5
Leche (L).............$5
C. Cola (C)..........$5
Vino (V)..............$10
Cuantas comidas diferentes constan de un plato principal y una bebida?
Si enumeramos las comidas posibles que constan de un plato principal y una bebida obtenemos:
HT,HL,HC,HV,QT,QL,QC,QV,FT,FL,FC,FV
vemos que hay 12 comidas diferentes, observen que hay 3 comidas principales y 4 bebidas, y que 3*4=12.
Cuantas comidas diferentes constan de una entrada, un plato principal y una bebida?
NHT,NHL,NHC,NHV,NQT,NQL,NQC,NQV,NFT,NFL,NFC,NFV,EHT,EHL,EHC,EHV,EQT,EQL,EQC,EQV,EFT,EFL,EFC,EFV
vemos que hay 24 comidas diferentes, observen que hay 2 entradas, 3 comidas principales y 4 bebidas, y que 2*3*4=12.
Principio de multiplicación.
Si una actividad puede construirse en t pasos sucesivos y el paso 1 puede realizarse de n1 formas; el paso 2 de n2 formas; y el paso t puede realizarse de nt formas entonces el numero de diferentes actividades posibles es n1*n2*.....*nt.
Cuantas comidas diferentes constan de una entrada, un plato principal y una bebida?
Existen 3 formas de elegir un plato principal (Hamburguesa, hamburguesa con queso, filete) y 5 formas de escoger una bebida opcional (te, leche, c.cola, vino, ninguna), por lo tanto:
por el principio de multiplicación 3*5=15 comidas.
Cuantas cadenas de 8 bits comienzan con 101 o con 111?
cadenas con 101 2*2*2*2*2=32
cadenas con 111 2*2*2*2*2=32
por lo tanto las cadenas que comienzan con 101 o con 111 son 32+32=64
Principio de la suma.
Supongamos que X1 y X2 son conjuntos y que el numero de elementos de X1 es n1 y el numero de elementos de X2 es n2. Si X1 ∩ X2 =∅ el numero de elementos posibles que pueden elegirse de X1 o X2 es:
n1 + n2
Si estamos contando objetos que se construyen por pasos, utilizamos el principio de la multiplicación. Si tenemos conjuntos ajenos de objetos y queremos conocer la cantidad de objetos, utilizamos el principio de la suma.
Ejercicios:
1.- Un investigador ha sido contratado para determinar que proporción de personas de una población dada prefiere tequila, cuantas brandy y cuantas whisky. El investigador decidió que no se incluirían personas que no gustaran de ningún licor y entrevisto a 1,000 personas que gustaban de al menos una de las bebidas. Días después presento su informe informando que:
729 gustan tequila (T)
814 gustan brandi (B)
628 gustan whisky(W)
592 gustan tequila y brandy ( T y B)
465 gustan tequila y whisky (T y W)
411 gustan brandy y whisky (B yW)
300 gustan de los tres (T, B y W)
La empresa que contrato la investigación duda de el resultado y dados los resultado se debe de comprobar que efectivamente la población entrevistada es igual a 1,000 personas.
Solución:
|T U B U W|=|T| + |B| + |W| - |T ∩ B| - |T ∩ W|-|B ∩ W| + |T ∩ B ∩ W |
= 729 + 814 + 628 – 529 – 465 – 411 + 300 = 1,003
2.- El departamento de publicidad del “palacio de bronce” efectúa una encuesta a un grupo de 1,000 clientes que abrieron una cuenta de crédito el mes de diciembre. Se les pregunta si su crédito fue utilizado para comprar artículos para el hogar, artículos de vestir o juguetes. Los resultados de la encuesta son:
Artículos para el hogar 275 |A|=275
Artículos de vestir 400 |B|=400
Juguetes 550 |C|=550
Artículos para el hogar y de vestir 150 |A ∩ B|=150
Artículos para el hogar y juguetes 110 |A ∩ C|=110
Artículos de vestir y juguetes 250 |B ∩ C|
Artículos de vestir, del hogar y juguetes 100 |A ∩ B ∩ C|=100
Se pregunta:
a) Cuantas personas no usaron su crédito en ninguna de esas 3 mercancías?
b) Cuantas personas utilizaron su crédito solo para comprar artículos de vestir?, solo para artículos del hogar?, solo para juguetes?
3.- Un investigador de mercado efectúa una encuesta sobre los hábitos de lectura de periódicos de la ciudad de Córdoba con los siguientes resultados:
9.8% leen el Clarín
22.9% leen el Mercurio
12.1% leen la Sensación
5.1 % leen el Clarín y el Mercurio
3.7% leen el Clarín y la Sensación
6.0% leen el Mercurio y la Sensación
32.4% leen al menos uno de los 3 periódicos
Calcular el porcentaje de personas que:
a) no le ningún periódico
b) le exactamente 2 de los periódicos.
1.- Un investigador ha sido contratado para determinar que proporción de personas de una población dada prefiere tequila, cuantas brandy y cuantas whisky. El investigador decidió que no se incluirían personas que no gustaran de ningún licor y entrevisto a 1,000 personas que gustaban de al menos una de las bebidas. Días después presento su informe informando que:
729 gustan tequila (T)
814 gustan brandi (B)
628 gustan whisky(W)
592 gustan tequila y brandy ( T y B)
465 gustan tequila y whisky (T y W)
411 gustan brandy y whisky (B yW)
300 gustan de los tres (T, B y W)
La empresa que contrato la investigación duda de el resultado y dados los resultado se debe de comprobar que efectivamente la población entrevistada es igual a 1,000 personas.
Solución:
|T U B U W|=|T| + |B| + |W| - |T ∩ B| - |T ∩ W|-|B ∩ W| + |T ∩ B ∩ W |
= 729 + 814 + 628 – 529 – 465 – 411 + 300 = 1,003
2.- El departamento de publicidad del “palacio de bronce” efectúa una encuesta a un grupo de 1,000 clientes que abrieron una cuenta de crédito el mes de diciembre. Se les pregunta si su crédito fue utilizado para comprar artículos para el hogar, artículos de vestir o juguetes. Los resultados de la encuesta son:
Artículos para el hogar 275 |A|=275
Artículos de vestir 400 |B|=400
Juguetes 550 |C|=550
Artículos para el hogar y de vestir 150 |A ∩ B|=150
Artículos para el hogar y juguetes 110 |A ∩ C|=110
Artículos de vestir y juguetes 250 |B ∩ C|
Artículos de vestir, del hogar y juguetes 100 |A ∩ B ∩ C|=100
Se pregunta:
a) Cuantas personas no usaron su crédito en ninguna de esas 3 mercancías?
b) Cuantas personas utilizaron su crédito solo para comprar artículos de vestir?, solo para artículos del hogar?, solo para juguetes?
3.- Un investigador de mercado efectúa una encuesta sobre los hábitos de lectura de periódicos de la ciudad de Córdoba con los siguientes resultados:
9.8% leen el Clarín
22.9% leen el Mercurio
12.1% leen la Sensación
5.1 % leen el Clarín y el Mercurio
3.7% leen el Clarín y la Sensación
6.0% leen el Mercurio y la Sensación
32.4% leen al menos uno de los 3 periódicos
Calcular el porcentaje de personas que:
a) no le ningún periódico
b) le exactamente 2 de los periódicos.
Suscribirse a:
Entradas (Atom)