Matematicas discretas el conteo

Matemáticas Discretas
Unidad II: Conteo

Conteo
Trata el área de las matemáticas que estudia “lo que  es posible”. Hay esencialmente dos tipos de problemas:
 Existe el problema de hacer una lista de todo lo 

que puede suceder en un situación determinada.

✔ Se tiene el problema de determinar cuántas cosas  diferentes pueden suceder (sin que en realidad se  haga una lista completa).  2Matemáticas Discretas ­Semestre B­2006

Principios Básicos del Conteo
 Regla de la Suma:

Si un evento se puede realizar de m formas,  mientras que un segundo evento puede realizarse  de n formas, y no es posible que ambos eventos se  realicen de manera simultánea, entonces para llevar  a cabo cualquiera de los eventos pueden utilizarse  cualquiera de m + n formas. 
3Matemáticas Discretas ­Semestre B­2006

Principios Básicos del Conteo
 Regla de la Suma:

Si A ∩ B =  , entonces |A ∪ B| = |A| + |B|

A

B

Matemáticas Discretas ­Semestre B­2006

4

Regla de la Suma
Por Ejemplo:  Para  escoger  el  presidente  de  una  comisión  se  puede elegir entre mujeres y hombres. ¿Si hay 25  mujeres  y  20  hombres  de  cuántas  formas  se  puede escoger el presidente?Por la regla de la suma hay 25 + 20 = 45 formas  diferentes de escoger el presidente de la  comisión.
Matemáticas Discretas ­Semestre B­2006 5

Regla de la Suma
Puede ampliarse a más de dos eventos,  siempre y cuando ninguna pareja de eventos  pueda ocurrir de forma simultánea. 

Por ejemplo:  Una  tienda  deportiva  sólo  tiene  15  modelos  de zapatos puma, 10 modelos de zapatos nike y 10  modelos  de  zapatos  adidas.  Por  lo  tanto,  un  cliente puede escoger entre 35 modelos, si desea  comprar un par de zapatos deportivos. 
Matemáticas Discretas ­Semestre B­2006 6

Principios Básicos del Conteo
 Regla del Producto:

Si una selección consta de dos pasos, de los  cuales el primero se puede efectuar de m  maneras y para cada una de éstas, la segunda se puede realizar de n maneras, entonces la  selección total se puede hacer de m.n formas.

Matemáticas Discretas ­Semestre B­2006

7

Regla del Producto
Por ejemplo: Para ir de Mérida a Caracas se puede viajar en  carro, en bus o en avión y para ir de Caracas a  Buenos Aires se puede ir en avión o en barco. Por la regla del producto, se puede ir de Mérida a  Buenos Aires de 6 formas diferentes (3x2)Matemáticas Discretas ­Semestre B­2006

8

Regla del Producto
 Este tipo de problemas se puede manejar  sistemáticamente trazando un diagrama de árbol:  
Caracas
c rro a
avión

Buenos Aires Buenos Aires Buenos Aires Buenos Aires Buenos Aires Buenos Aires
9

barco

Mérida

bus
av ión

n avió

Caracas

barco
n avió

Caracas

barco

Matemáticas Discretas ­Semestre B­2006Regla del Producto
Generalización:  Supongamos que una tarea requiere realizar  sucesivamente los pasos T1, T2,...Tm . Si la tarea Ti  realizado las tareas T1, T2,...Ti­1, entonces hay   n1 x n2 x ... x nm formas de hacer la tarea.  puede hacerse de ni formas después de haber 

Matemáticas Discretas ­Semestre B­2006

10

Regla del Producto
Si para formar la placa de un automóvil se requieren cuatro letras (L) y dos dígitos (D), agrupados de la  siguiente manera: LLL – DDL. ¿Cuántas placas  diferentes son posibles? Hay 26 posibilidades para cada una de las letras y  10 posibilidades para cada dígito. Por lo tanto son  posibles: 26 x 26 x 26 x 10 x 10 x 26 = 45.697.600 placas 
Matemáticas Discretas ­Semestre B­2006 11

Principios Básicos del Conteo La tercera regla del conteo incluye el cálculo del 

número de formas en que se pueden colocar en  orden un grupo de objetos: Por ejemplo:

Si se van a colocar en una repisa un grupo de seis  libros  ¿Cómo se puede determinar el número de  formas en que se pueden colocar los seis libros?   

                

Matemáticas Discretas ­Semestre B­2006

12

Principios Básicos del Conteo
Se  comienza ...