5 Principios basicos ‣ Parte II Combinatoria ‣ Matemática discreta

Proposición II.1 (Principio del producto).

Sea $\mathcal{{A}}$ una actividad que se puede realizar en $t\geq 2$ pasos secuenciales, de manera que el paso 1 se puede hacer de $n_{1}$ fofrmas distintas, el paso 2 se puede hacer de $n_{2}$ formas distintas, …, y el paso $t$ se puede hacer de $n_{t}$ formas distintas.

Entonces el numero de posibles formas de realizar la actividad $\mathcal{{A}}$ es $n_{1}\cdot n_{2}\cdots n_{t}$ .

Ejemplo II.1.

Sean $B_{1},B_{2},\ldots,B_{t}$ conjuntos finitos no vacios.

Calcula $|B_{1}\times B_{2}\times\cdots\times B_{t}|$ .

$B_{1}\times B_{2}\times\cdots\times B_{t}=\left\{(b_{1},b_{2},\ldots,b_{t})% \mid\forall b_{i}\exists B_{i}\right\}$ .

Por tanto, habra $|B_{1}|$ opciones de la primera coordenada, $|B_{2}|$ opciones de la segunda, …, $|B_{t}|$ opciones de la t-esima.

$|B_{1}\times B_{2}\times\cdots\times B_{t}|=B_{1}\cdot B_{2}\cdots B_{t}$ .

Ejemplo II.2.

El alfabeto español consta de 27 letras de las cuales 5 son vocales. Cuantas palabras (con o sin sentido) de 7 letras se pueden formar de manera que empiecen por vocal y que nunca tengan dos vocales ni dos consonantes seguidas?

Solucion: se pueden formar $5^{4}\cdot 22^{3}$ palabras.

Ejemplo II.3.

Se lanzan simultaneamente dos dados de 6 caras, uno de color rojo y otro de color azul. Despues se suman los resultados. De cuantas formas se puede obtener un resultado total de 10 o mas?

Consideramos varios casos dependiendo de la suma de los dos dados:

Caso 1: suma 12. Se puede sacar con un 6 en ambos dados (1 forma).
Caso 2: suma 11. Se puede sacar un 6 en el rojo y 5 en el azul o 6 en el azul y 5 en el rojo (2 formas).
Caso 3: suma 10. 5 rojo y 5 azul, 4 rojo y 6 azul, 6 rojo y 4 azul (3 formas).

La solucion es $1+2+3=6$ formas de obtener 10 o mas.

Proposición II.2.

Sea $\mathcal{{A}}$ una actividad tal que las distintas formas de realizarla son los elementos de un conjunto finito $B$ . Supongamos que $B$ se puede escribir como union de subconjuntos disjuntos dos a dos, es decir,

B=B_{1}\cup B_{2}\cup\cdots\cup B_{t}\text{, y si }i\neq j\text{ entonces }B_{% i}\cap B_{j}=\varnothing

Supongamos tambien que $|B_{j}|=n_{j}$ .

Entonces el numero de posibles formas de realizar la actividad $\mathcal{{A}}$ es $n_{1}+n_{2}+\cdots+n_{t}$ .

(Es decir, $|B|=|B_{1}\cup B_{2}\cup\cdots\cup B_{t}|=|B_{1}|+|B_{2}|+\cdots+|B_{t}|$ ).

Ejemplo II.4.

El alfabeto español consta de 27 letras de las cuales 5 son vocales. Cuantas palabras de 4 letras se pueden formar de manera que empiecen por “D” y acaben en consonante o que empiecen por “F” y acaben en vocal?

Caso 1: $1\cdot 27^{2}\cdot 22$ .
Caso 2: $1\cdot 27^{2}\cdot 5$ .

Todos los casos posibles son $27^{2}\cdot 22+27^{2}\cdot 5=27^{3}$ (como son casos disjuntos puedo aplicar la regla de la suma).

Ejemplo II.5.

Cuantas palabras de 4 letras se pueden formar de manera que empiecen por “D” o acaben en “F”?

Caso 1: $1\cdot 27^{3}$
Caso 2: $1\cdot 27^{3}$

En este caso, no son disjuntos (por ejemplo, DEEF esta en ambos).

Debemos restar la interseccion, que será $1\cdot 27^{2}\cdot 1=27^{2}$ .

La solucion final es $27^{3}+27^{3}-27^{2}$ .

Teorema II.1.

Sean $B,B_{1},B_{2}$ conjuntos finitos tales que $B=B_{1}\cup B_{2}$ . Entonces

|B|=|B_{1}|+|B_{2}|-|B_{1}\cap B_{2}|\mathchar 46\relax

Ejemplo II.6.

Se lanzan dos dados de 6 caras, uno rojo y otro azul. Despues se suman los resultados. De cuantas formas se puede obtener un resultado total de 4 o mas?

Lo contrario de sacar $\geq 4$ es sacar $<4$ , que es lo mismo que sacar $2$ o $3$ .

Para que sume 2, el azul sera 1 y el rojo 1 (1 forma).

Para que sume 3, hay dos posibilidades: azul 1 y rojo 2, azul 2 y rojo 1.

En total, hay 4 formas. Podemos sacar el numero de opciones de $\geq 4$ restando del total ( $6\cdot 6=36$ ). $36-3=33$ .

Proposición II.3 (Principio del complementario).

Sea $\mathcal{{A}}$ una actividad tal que las distintas formas de realizarla son los elementos de un conjunto finito $B$ . Supongamos que $D$ es otro conjunto finito tal que $B\subseteq D$ y sabemos que $|D|=n$ y que $|D\setminus B|=m$ .

Entonces el numero de posibles formas de realizar la actividad $\mathcal{{A}}$ es $n-m$ . Es decir, $|B|=|D|-|D\setminus B|$ .

Observación II.1.

El principio del complementario es un corolario del principio de la suma.

|B|+|D\setminus B|=|D|\Rightarrow|B|=|D|-|D\setminus B|\mathchar 46\relax

Ejemplo II.7.

Cuantas palabras de 6 letras se pueden formar de manera que contengan al menos una vocal?

Como tiene que haber $\geq 1$ vocales, lo contrario es que no haya ninguna vocal, que es lo mismo que “todo consonantes”. En ese caso, hay $22^{6}$ posibilidades y el total es $27^{6}$ .

La solucion sera $27^{6}-22^{6}$ .