Fisico Matematico

Secci´n 1 o

Matem´ticas discretas a
Conteo
Uno de los conceptos matem´ticos abstractos m´s primitivos que conocemos es el de a a n´mero y, dentro de los n´meros, el de los n´meros naturales o enteros positivos: 1, 2, u u u 3, 4, etc. Con ellos representamos las cantidades de objetos que se nos presentan en la vida cotidiana. En esta secci´n desarrollaremos algunas t´cnicas que permitendeterminar o e con facilidad cantidades. Comencemos por ilustrar la necesidad de aprender estas t´cnicas e de conteo con unos ejemplos: Si se nos ense˜a un pu˜ado de canicas y se nos pregunta n n cu´ntas son, un vistazo nos bastar´ para contarlas y dar la respuesta; sin embargo si se nos a a pregunta cu´ntas patas tienen 100 perros, en lugar de buscar los 100 animales y contarles a las patas, haremosuna abstracci´n, y la operaci´n: 4 × 100 = 400 nos dir´ la respuesta; o o a utilizamos aqu´ una t´cnica muy simple de multiplicaci´n. Desde luego hay preguntas que ı e o necesitan t´cnicas m´s elaboradas. Estudiaremos estas t´cnicas mediante ejemplos que e a e iremos complicando gradualmente. Analicemos primero con cuidado un ejemplo que a primera vista es trivial pero que nos ense˜a la claveb´sica del conteo. n a [1.1] Ejemplo. ¿Cu´ntos n´meros enteros de tres o menos cifras hay? a u Soluci´n. La respuesta a esta pregunta es f´cil: Hay 1000 pues son todos los n´meros o a u enteros del 0 al 999. Esta soluci´n no nos ense˜a gran cosa. Retomemos ahora el problema o n buscando una soluci´n constructiva; esto es, para cualquier n = 1, 2, 3, . . ., la cantidad de o n´meros de hasta n+1 cifras sepuede obtener de la cantidad de n´meros de hasta n cifras: u u simplemente se multiplica por 10. Vamos a describir con detalle este procedimiento: N´meros de a lo m´s una cifra hay 10, a saber, 0, 1, 2, 3, 4, 5, 6, 7, 8 y 9. Para contar u a los de hasta dos cifras (del 0 al 99) no necesitamos escribirlos todos; basta con observar que la primera cifra puede ser cualquiera de los 10 d´ ıgitos 0, 1,2, 3, 4, 5, 6, 7, 8, 9, y por

§1. Matem´ticas discretas a cada uno de ´stos hay 10 terminaciones distintas; por ejemplo, los n´meros de dos cifras e u que empiezan con 4 son: 40, 41, 42, 43, 44, 45, 46, 47, 48 y 49, diez en total; lo mismo para cada una de las otras decenas. As´ la cantidad de enteros entre 0 y 99 es 10 × 10 = 100. ı El siguiente paso es an´logo: Para contar los n´meros dehasta tres cifras hay que agregar a u un d´ ıgito (posiblemente 0) a cada uno de los 100 n´meros de 2 o menos cifras; como hay u diez posibilidades la respuesta ser´ 10 × 100 = 1000. a Este procedimiento de “construir sobre lo ya construido” que hemos utilizado se llama procedimiento inductivo. Muchas demostraciones de propiedades y f´rmulas de n´meros o u naturales se basan en ´l. En la secci´n 4se estudiar´ esto con detalle. El principio e o a combinatorio que manejamos en el ejemplo anterior (y que manejaremos en los siguientes) es: [1.2] Principio Fundamental de Conteo. Si una cierta tarea puede realizarse de m maneras diferentes y, para cada una de esas formas, una segunda tarea puede realizarse de n maneras distintas, entonces las dos tareas juntas pueden realizarse (en ese orden) demn formas diferentes. [1.3] Ejemplo. ¿Cu´ntas palabras de tres letras se pueden formar si se dispone de un a alfabeto con dos letras: a y b. (Nota: Son permisibles palabras como bba.) Soluci´n. Procederemos como en el ejemplo anterior. En este caso conviene ilustrarlo o haciendo un “diagrama ´rbol”: a
letra inicial letra central letra final palabra formada

a a b a a b b a a b b a b b

············ ······ ······ ······ ······ ······ ······

aaa aab aba abb baa bab bba bbb

Resolvamos ahora el ejemplo utilizando nuestro Principio Fundamental de Conteo.
2

§1. Matem´ticas discretas a Consideremos tres casillas: — — — , la primera para la letra inicial, la segunda para la letra central y la tercera para la letra final. En cada casilla hay dos elecciones posibles: la letra a o...