matemáticas discretas tc1003cb.mty.itesm.mx/tc1003/lecturas/tc1003-062.pdfejemplo 3 ejemplo 4...

Conteo: Principio de la Multiplicación Matemáticas Discretas - p. 1/15

Matemáticas DiscretasTC1003

Conteo: Principio de la MultiplicaciónDepartamento de Matemáticas / Centro de Sistema Inteligentes

ITESM

Arboles dePosibilidadesEjemplo 1PrincipioMultiplicativoEjemplo 2Ejemplo 3Ejemplo 4Ejemplo 5Ejemplo 6PermutacionesEjemplo 7r−PermutacionEjemplo 8


Árboles de Posibilidades

Un árbol de posibilidades es una representacióngráfica de todas las posibilidades en la toma desituaciones de una serie de tareas consecutivas.



Ejemplo

Se desean eligir los puestos de Director y Auxiliar de Director entreLucía, María, Tomás y Juan. Se tiene que ni Lucía ni María seráneligidas para director. También se sabe que habiendo elegido aTomás como director Lucía no debería ser auxiliar suyo. ¿Cuántasposibilidades existen de elección?



Ejemplo

Se desean eligir los puestos de Director y Auxiliar de Director entreLucía, María, Tomás y Juan. Se tiene que ni Lucía ni María seráneligidas para director. También se sabe que habiendo elegido aTomás como director Lucía no debería ser auxiliar suyo. ¿Cuántasposibilidades existen de elección?Soluci on

Inicio

Juan

Tomás

Tomás

Lucía

María

Juan

María

Director Auxiliar Selección

María

Lucía

Lucía



Ejemplo


Inicio

Juan

Tomás

Tomás

Lucía

María

Juan

María


María

Lucía

Lucía

Director: Juan, Auxiliar: Tomás

Director: Juan, Auxiliar: María


Director: Tomás, Auxiliar: Juan

Director: Tomás, Auxiliar: María



Ejemplo


Inicio

Juan

Tomás

Tomás

Lucía

María

Juan

María


María

Lucía

Lucía

Director: Juan, Auxiliar: Tomás



Director: Tomás, Auxiliar: Juan

Director: Tomás, Auxiliar: María

Se tienen 5 posibles configuraciones.



Principio de la Multiplicación

Si una actividad se puede construir en t pasosdiferentes e independientes entre si y




Si una actividad se puede construir en t pasosdiferentes e independientes entre si y■ el paso 1 se puede hacer de n1 maneras,




Si una actividad se puede construir en t pasosdiferentes e independientes entre si y■ el paso 1 se puede hacer de n1 maneras,■ el paso 2 se puede hacer de n2 maneras,




Si una actividad se puede construir en t pasosdiferentes e independientes entre si y■ el paso 1 se puede hacer de n1 maneras,■ el paso 2 se puede hacer de n2 maneras,■ . . .




Si una actividad se puede construir en t pasosdiferentes e independientes entre si y■ el paso 1 se puede hacer de n1 maneras,■ el paso 2 se puede hacer de n2 maneras,■ . . .■ y el paso t se puede hacer de nt maneras.




Si una actividad se puede construir en t pasosdiferentes e independientes entre si y■ el paso 1 se puede hacer de n1 maneras,■ el paso 2 se puede hacer de n2 maneras,■ . . .■ y el paso t se puede hacer de nt maneras.Entonces el número de actividades posiblesdiferentes es

n1 · n2 · · ·nt.



Ejemplo

El menú de El Sobrino consta de:■ Entremés:

◆ Queso fundido◆ Guacamole

■ Plato fuerte:◆ Hamburguesa◆ Carne asada◆ Pechuga de pollo a la parrilla

■ Bebida:◆ Limonada◆ Cerveza◆ Coca◆ Té

¿Cuántas comidas diferentes se pueden obtenerescogiendo un entremés, un plato fuerte, y unabebida?



Soluci onLa tarea de elegir una comida en este caso constade 3 pasos:



Soluci onLa tarea de elegir una comida en este caso constade 3 pasos: escoger un entremés (2 opciones),



Soluci onLa tarea de elegir una comida en este caso constade 3 pasos: escoger un entremés (2 opciones),escoger un plato fuerte (3 opciones),



Soluci onLa tarea de elegir una comida en este caso constade 3 pasos: escoger un entremés (2 opciones),escoger un plato fuerte (3 opciones), y escogeruna bebida (4 opciones).



Soluci onLa tarea de elegir una comida en este caso constade 3 pasos: escoger un entremés (2 opciones),escoger un plato fuerte (3 opciones), y escogeruna bebida (4 opciones).Suponiendo independencia en la selección, elnúmero total de comidas diferentes será:



Soluci onLa tarea de elegir una comida en este caso constade 3 pasos: escoger un entremés (2 opciones),escoger un plato fuerte (3 opciones), y escogeruna bebida (4 opciones).Suponiendo independencia en la selección, elnúmero total de comidas diferentes será:

2 · 3 · 4 = 24



Ejemplo

Use el principio de la multiplicación para encontrarel número de subconjuntos del conjunto

A = {x1, x2, . . . , xn}



Ejemplo


A = {x1, x2, . . . , xn}

Soluci onPodemos pensar que un subconjunto de A seconstruye en n pasos sucesivos:



Ejemplo


A = {x1, x2, . . . , xn}

Soluci onPodemos pensar que un subconjunto de A seconstruye en n pasos sucesivos: se elige o no seelige x1;



Ejemplo


A = {x1, x2, . . . , xn}

Soluci onPodemos pensar que un subconjunto de A seconstruye en n pasos sucesivos: se elige o no seelige x1; se elige o no se elige x2; . . . ;



Ejemplo


A = {x1, x2, . . . , xn}

Soluci onPodemos pensar que un subconjunto de A seconstruye en n pasos sucesivos: se elige o no seelige x1; se elige o no se elige x2; . . . ; se elige ono se elige xn.



Ejemplo


A = {x1, x2, . . . , xn}

Soluci onPodemos pensar que un subconjunto de A seconstruye en n pasos sucesivos: se elige o no seelige x1; se elige o no se elige x2; . . . ; se elige ono se elige xn. Cada paso se puede realizar dedos maneras.



Ejemplo


A = {x1, x2, . . . , xn}

Soluci onPodemos pensar que un subconjunto de A seconstruye en n pasos sucesivos: se elige o no seelige x1; se elige o no se elige x2; . . . ; se elige ono se elige xn. Cada paso se puede realizar dedos maneras. Entonces el número de conjuntosdiferentes contruidos será:

2 · 2 · · · 2︸︷︷︸

n factores

= 2n



Ejemplo

¿Cuántas cadenas de longitud 4 se pueden formarcon las letras ABCEDF que incien con AB y queno tengan repeticiones de letras?



Ejemplo

¿Cuántas cadenas de longitud 4 se pueden formarcon las letras ABCEDF que incien con AB y queno tengan repeticiones de letras?Soluci onPodemos imaginarnos que la contrucción de lascadenas se puede descomponer en tres pasos:



Ejemplo

¿Cuántas cadenas de longitud 4 se pueden formarcon las letras ABCEDF que incien con AB y queno tengan repeticiones de letras?Soluci onPodemos imaginarnos que la contrucción de lascadenas se puede descomponer en tres pasos:■ Poner las dos primeras letras que deben ser AB:

1 sola posibilidad



Ejemplo


1 sola posibilidad■ Escoger la tercera letra: 4 posibilidades (para no

repetir A ni B)



Ejemplo



repetir A ni B)■ Escoger la cuarta letra: 3 posibilidades (para la

repetir A ni B ni la 3a letra)



Ejemplo



repetir A ni B)■ Escoger la cuarta letra: 3 posibilidades (para la

repetir A ni B ni la 3a letra)Total de cadenas : 1 · 4 · 3 = 12.



Ejemplo

Sea X un conjunto con n elementos. ¿Cuántospares de subconjuntos (A,B) que cumplanA ⊆ B ⊆ X se pueden formar?



Ejemplo

Sea X un conjunto con n elementos. ¿Cuántospares de subconjuntos (A,B) que cumplanA ⊆ B ⊆ X se pueden formar?Soluci onPara que se cumpla A ⊆ B se requiereB = A ∪ (B − A)



Ejemplo

Sea X un conjunto con n elementos. ¿Cuántospares de subconjuntos (A,B) que cumplanA ⊆ B ⊆ X se pueden formar?Soluci onPara que se cumpla A ⊆ B se requiereB = A ∪ (B − A) y para que B ⊆ X queX = B ∪ (X − B).



Ejemplo

Sea X un conjunto con n elementos. ¿Cuántospares de subconjuntos (A,B) que cumplanA ⊆ B ⊆ X se pueden formar?Soluci onPara que se cumpla A ⊆ B se requiereB = A ∪ (B − A) y para que B ⊆ X queX = B ∪ (X − B). Por tanto, para que se cumplaA ⊆ B ⊆ X se requerira:



Ejemplo

Sea X un conjunto con n elementos. ¿Cuántospares de subconjuntos (A,B) que cumplanA ⊆ B ⊆ X se pueden formar?Soluci onPara que se cumpla A ⊆ B se requiereB = A ∪ (B − A) y para que B ⊆ X queX = B ∪ (X − B). Por tanto, para que se cumplaA ⊆ B ⊆ X se requerira:■ B = A ∪ (B − A)



Ejemplo

Sea X un conjunto con n elementos. ¿Cuántospares de subconjuntos (A,B) que cumplanA ⊆ B ⊆ X se pueden formar?Soluci onPara que se cumpla A ⊆ B se requiereB = A ∪ (B − A) y para que B ⊆ X queX = B ∪ (X − B). Por tanto, para que se cumplaA ⊆ B ⊆ X se requerira:■ B = A ∪ (B − A)

■ X = B ∪ (X − B)



Por tanto, todo elemento x de X está en sólo 1 delos conjuntos A, B − A, o X − B.



Por tanto, todo elemento x de X está en sólo 1 delos conjuntos A, B − A, o X − B. Cada pareja deconjuntos (A,B) se construirá eligiendo cadaelemento x de X en algunos de los tres conjuntosanteriores;



Por tanto, todo elemento x de X está en sólo 1 delos conjuntos A, B − A, o X − B. Cada pareja deconjuntos (A,B) se construirá eligiendo cadaelemento x de X en algunos de los tres conjuntosanteriores; es decir, cada elemento de X tiene 3posibilidades.



Por tanto, todo elemento x de X está en sólo 1 delos conjuntos A, B − A, o X − B. Cada pareja deconjuntos (A,B) se construirá eligiendo cadaelemento x de X en algunos de los tres conjuntosanteriores; es decir, cada elemento de X tiene 3posibilidades.Por tanto, el número de posibles parejas (A,B) desubconjuntos cumpliendo A ⊆ B ⊆ X será:

3 · 3 · · · 3︸︷︷︸

n factores

= 3n



Ejemplo

¿Cuántas cadenas de 8 bits inician con 11 yterminan con 00?



Ejemplo

¿Cuántas cadenas de 8 bits inician con 11 yterminan con 00?Soluci onPodemos imaginar que la tarea se puede construiren tres pasos:



Ejemplo

¿Cuántas cadenas de 8 bits inician con 11 yterminan con 00?Soluci onPodemos imaginar que la tarea se puede construiren tres pasos:■ T1: Elegir los dos primeros bits que deben ser

11: 1 posibilidad



Ejemplo


11: 1 posibilidad■ T2: Elegir los 4 siguientes bits: que por el mismo

principio de la multiplicación tendrá 24 = 16posibilidades,



Ejemplo




■ T3: Elegir los 2 últimos bits que deben ser 00: 1posibilidad



Ejemplo




■ T3: Elegir los 2 últimos bits que deben ser 00: 1posibilidad

El número de posibles cadenas es: 1 · 16 · 1 = 16.



Permutaciones

Una permutación de un conjunto de objetos es unordenamiento de los mismos en una secuencia.



Permutaciones


Ejemplo

El conjunto {X,Y,Z} tiene 6 permutaciones:

XYZ, XZY, YXZ, YZX, ZXY, ZYX



Permutaciones


Ejemplo



Resultado:

Para cualquier entero n con n ≥ 1, el númerode permtaciones de los elementos de conconjunto con n elementos direfentes es n!



Permutaciones


Ejemplo



Resultado:

Para cualquier entero n con n ≥ 1, el númerode permtaciones de los elementos de conconjunto con n elementos direfentes es n!

Donde:

n! = n · (n − 1) · (n − 2) · · · 2 · 1



Ejemplo

Calcule el número de posibles combinaciones delas letras en la palabra ABIERTO.



Ejemplo

Calcule el número de posibles combinaciones delas letras en la palabra ABIERTO.Soluci onEl conjunto de letras en la palabra es{A,B,I,E,R,T,O} y tiene 7 elementos diferentes.



Ejemplo

Calcule el número de posibles combinaciones delas letras en la palabra ABIERTO.Soluci onEl conjunto de letras en la palabra es{A,B,I,E,R,T,O} y tiene 7 elementos diferentes. Portanto, el número de posibles permutaciones es:

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



r−Permutación

Una r−permutación de un conjunto con n

elementos es una secuencia ordenada de r

elementos escogidos en el conjunto.



r−Permutación




Resultado:

Si n y r son enteros y 1 ≤ r ≤ n, entonces elnúmero de r-permutaciones de un conjuntocon n elementos está dado por la fórmula:

P (n, r) = n · (n − 1) · (n − 2) · · · (n − r + 1)



r−Permutación




Resultado:

Si n y r son enteros y 1 ≤ r ≤ n, entonces elnúmero de r-permutaciones de un conjuntocon n elementos está dado por la fórmula:

P (n, r) = n · (n − 1) · (n − 2) · · · (n − r + 1)

O equivalentemente:

P (n, r) =n!

(n − r)!



Ejemplo

Determine:■ P (5, 2)

■ ¿Cuántas 4-permutaciones hay en un conjuntocon 7 objetos?

■ ¿De cuántas maneras se pueden cadenas de 3letras tomadas de la palabra LIBRE?



Ejemplo


P (5, 2) =5!

(5 − 2)!=

5 · 4 · 3 · 2 · 1

3 · 2 · 1= 20





Ejemplo


P (5, 2) =5!

(5 − 2)!=

5 · 4 · 3 · 2 · 1

3 · 2 · 1= 20


P (7, 4) =7!

(7 − 4)!=

7 · 6 · 5 · 4 · 3 · 2 · 1

3 · 2 · 1= 840




Ejemplo


P (5, 2) =5!

(5 − 2)!=

5 · 4 · 3 · 2 · 1

3 · 2 · 1= 20


P (7, 4) =7!

(7 − 4)!=

7 · 6 · 5 · 4 · 3 · 2 · 1

3 · 2 · 1= 840


P (5, 3) =5!

(5 − 3)!=

5 · 4 · 3 · 2 · 1

2 · 1= 60

matemáticas discretas tc1003cb.mty.itesm.mx/tc1003/lecturas/tc1003-062.pdfejemplo 3 ejemplo 4...

Documents