lunes, 5 de enero de 2009

6.1 Principios básicos de conteo.

Hay dos principios básicos en combinatoria:

Principio de la adición. Si se desea escoger un objeto que puede tener r tipos distintos, y para el primer tipo hay t1 opciones, para el segundo tipo hay t2 opciones, para el tercer tipo t3 opciones, y así sucesivamente hasta tr opciones para el ultimo tipo, entonces el objeto puede escogerse de t1 +t2 ...+tr maneras.
Lo que el principio anterior dice, es que el total de opciones es la suma del número de opciones en cada tipo. Como por ejemplo, supongamos que hay que escoger un libro de entre tres materias: matemáticas, historia y biología. Hay seis libros de matemáticas, 9 de historia y 4 de biología . Entonces tenemos 6+9+4 = 19 opciones.

Principio de la multiplicación. Si una tarea se ha de realizar en n etapas, y si la primera etapa tiene k1 maneras de realizarse, la segunda tiene k2 maneras, y así sucesivamente hasta kn , maneras de realizar la ultima, entonces el numero de formas de realizar la tara es k 1× k2 ×...×kn.

Si una persona ha de escoger como vestirse, teniendo 4 camisas, 6 pantalones, 5 pares de calcetines y 2 pares de zapatos, entonces tiene 4 × 6 × 5 ×2 = 240 formas de vestirse, ya que cada elección de la camisa (4 opciones) tiene 6 opciones para el pantalón, lo que da 4 × 6 = 24 opciones para la camisa y pantalón. Para cada una de esas 24 tiene 5 pares de calcetines, totalizando 120 formas, y para cada una de esas tiene dos opciones de los zapatos, de modo que se duplica el total y al final tiene 240 formas de vestirse. El principio de la multiplicación puede visualizarse mediante un diagrama de árbol
Veamos algunos ejercicios que usan estos principios.
Ejemplo ¿cuántos números de 5 cifras están formados únicamente de cuatros y doses (ejemplos:44242, 24422)? Nos están pidiendo números de cinco cifras, es decir nos piden llenar con doses y cuatros las cinco rayitas _ _ _ _ _ . En la primera rayita podemos poner un dos o un cuatro (2 opciones), en la segunda podemos poner un dos o un cuatro (2 opciones), lo mismo en la tercera, cuarta y quinta rayita. El principio de la multiplicación dice que el total es 2× 2 × 2× 2 × 2= 25 = 32. Así la respuesta es que hay 32 números pedidos.
Ejemplo ¿Cuántos números de cinco cifras no tienen cincos ni treses?
Como en el ejemplo anterior, tenemos que llenar cinco espacios _ _ _ _ _.En el primer espacio, de los diez dígitos, no podemos usar el 3 ni el cinco, pero tampoco podemos usar un cero ya que si ponemos cero, el numero tendría menos de cinco cifras. Entonces tenemos 7 opciones para el primer espacio. En las restantes 4 posiciones podemos poner cualquier digito excepto el 3 y el 5, es decir 8 opciones en cada caso. El principio de la multiplicación nos da un total de 7 × 84 = 28672.
Ejemplo. Si hay que escoger un número de cuatro cifras que tenga todas sus cifras pares excepto cuatros y ochos, o todas sus cifras impares, excepto cincos y sietes, ¿De cuantas formas puede hacerse?
Hay dos tipos de números que queremos contar: los que tienen dígitos pares y los que tienen dígitos impares. El principio de la adición dice que el total lo obtenemos sumando el total de cada caso.
Cuando todos son pares, hay cuatro posiciones _ _ _ _. En la primera posición tenemos que poner un número par que no sea 4 ni 8, pero tampoco cero (porque de lo contrario, el número ya no tendría cuatro cifras). Entonces tenemos dos opciones (2,6). Para las demás posiciones tenemos 3 opciones siempre (2,6,0). El total es 2 ×33 = 54.
Cuando todos son impares, como no podemos poner cincos ni sietes, tenemos 3 opciones para cada espacio: 1,3,9. En total hay 34 = 81 números de esta forma.

Entonces, el total pedido (usando el principio de la suma) es 54 + 81 = 135.

Ejemplo ¿Cuántos números de seis cifras hay que no tienen sus dígitos repetidos ?
Tenemos seis espacios a llenar _ _ _ _ _ _ . En el primero, tenemos 9 opciones, porque no podemos poner al cero. En la segunda posición también tenemos 9 opciones, porque, aunque ya no podemos usar el numero que escogimos antes, ahora si podemos usar el cero. Para la tercera posición tenemos 8 opciones (de los 10 dígitos, ya usamos dos), para la cuarta posición hay 7 opciones, para la quinta 6 y para la ultima 5. En total hay 9 ×9×8×7×6×5= 136080 números de seis cifras sin dígitos repetidos.
Aunque los principios básicos de conteo pueden usarse en la gran mayoría de los casos, usualmente hay formulas(basadas en esos principios) que nos permiten hacer los cálculos de manera más rápida. En las siguientes secciones estudiaremos las principales.