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

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

Á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.

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

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

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?

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

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

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

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

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

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

Director: Juan, Auxiliar: Tomás

Director: Juan, Auxiliar: María

Director: Juan, Auxiliar: María

Director: Tomás, Auxiliar: Juan

Director: Tomás, Auxiliar: María

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

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

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

Director: Juan, Auxiliar: Tomás

Director: Juan, Auxiliar: María

Director: Juan, Auxiliar: María

Director: Tomás, Auxiliar: Juan

Director: Tomás, Auxiliar: María

Se tienen 5 posibles configuraciones.

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

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

Principio de la Multiplicación

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

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

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

Principio de la Multiplicación

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

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

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

Principio de la Multiplicación

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,

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

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

Principio de la Multiplicación

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,■ . . .

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

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

Principio de la Multiplicación

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.

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

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

Principio de la Multiplicación

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.

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

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

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?

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

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

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

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

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

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

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

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

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),

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

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

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).

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

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

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á:

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

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

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

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

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

Ejemplo

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

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

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

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

Ejemplo

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

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

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

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

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

Ejemplo

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

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

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

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

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

Ejemplo

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

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; . . . ;

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

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

Ejemplo

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

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.

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

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

Ejemplo

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

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.

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

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

Ejemplo

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

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

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

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

Ejemplo

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

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

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

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:

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

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

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

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

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

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■ Escoger la tercera letra: 4 posibilidades (para no

repetir A ni B)

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

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

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■ Escoger la tercera letra: 4 posibilidades (para no

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

repetir A ni B ni la 3a letra)

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

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

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■ Escoger la tercera letra: 4 posibilidades (para no

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.

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

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

Ejemplo

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

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

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

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)

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

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

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).

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

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

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:

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

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

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)

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

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

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)

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

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

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

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

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

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;

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

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

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.

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

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

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

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

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

Ejemplo

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

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

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

Ejemplo

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

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

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

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

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

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

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■ T2: Elegir los 4 siguientes bits: que por el mismo

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

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

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

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■ T2: Elegir los 4 siguientes bits: que por el mismo

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

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

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

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

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■ T2: Elegir los 4 siguientes bits: que por el mismo

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

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

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

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

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

Permutaciones

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

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

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

Permutaciones

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

Ejemplo

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

XYZ, XZY, YXZ, YZX, ZXY, ZYX

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

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

Permutaciones

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

Ejemplo

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

XYZ, XZY, YXZ, YZX, ZXY, ZYX

Resultado:

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

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

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

Permutaciones

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

Ejemplo

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

XYZ, XZY, YXZ, YZX, ZXY, ZYX

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

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

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

Ejemplo

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

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

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

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.

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

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

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

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

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

r−Permutación

Una r−permutación de un conjunto con n

elementos es una secuencia ordenada de r

elementos escogidos en el conjunto.

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

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

r−Permutación

Una r−permutación de un conjunto con n

elementos es una secuencia ordenada de r

elementos escogidos en el conjunto.

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)

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

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

r−Permutación

Una r−permutación de un conjunto con n

elementos es una secuencia ordenada de r

elementos escogidos en el conjunto.

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)!

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

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

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?

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

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

Ejemplo

Determine:■ P (5, 2)

P (5, 2) =5!

(5 − 2)!=

5 · 4 · 3 · 2 · 1

3 · 2 · 1= 20

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

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

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

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

Ejemplo

Determine:■ P (5, 2)

P (5, 2) =5!

(5 − 2)!=

5 · 4 · 3 · 2 · 1

3 · 2 · 1= 20

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

P (7, 4) =7!

(7 − 4)!=

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

3 · 2 · 1= 840

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

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

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

Ejemplo

Determine:■ P (5, 2)

P (5, 2) =5!

(5 − 2)!=

5 · 4 · 3 · 2 · 1

3 · 2 · 1= 20

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

P (7, 4) =7!

(7 − 4)!=

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

3 · 2 · 1= 840

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

P (5, 3) =5!

(5 − 3)!=

5 · 4 · 3 · 2 · 1

2 · 1= 60