¿Otra vez?

Actualización 3: Es 2^n, (1+1)^n

(1-1)^n, 2^(n-1)

1. Conteo

Uno de los conceptos matem´aticos abstractos m´as primitivos que conocemos es el de

n´umero y, dentro de los n´umeros, el de los n´umeros naturales enteros positivos: 1, 2,

3, 4, etc. Con ellos representamos las cantidades de objetos que se nos presentan en la vida

cotidiana. En esta secci´on desarrollaremos algunas t´ecnicas que permiten determinar con

facilidad cantidades. Comencemos por ilustrar la necesidad de aprender estas t´ecnicas de

conteo con unos ejemplos: Si se nos ense˜na un pu˜nado de canicas y se nos pregunta cu´antas

son, un vistazo nos bastar´a para contarlas y dar la respuesta; sin embargo si se nos pregunta

cu´antas patas tienen 100 perros, en lugar de buscar los 100 animales y contarles las patas,

haremos una abstracci´on, y la operaci´on: 4×100 = 400 nos dir´a la respuesta; utilizamos aqu´ı

una t´ecnica muy simple de multiplicaci´on. Desde luego hay preguntas que necesitan t´ecnicas

m´as elaboradas. Estudiaremos estas t´ecnicas mediante ejemplos que iremos complicando

gradualmente.

Analicemos primero con cuidado un ejemplo que a primera vista es trivial pero que nos

ense˜na la clave b´asica del conteo.

1.1 Ejemplo. ¿Cu´antos n´umeros enteros de tres o menos cifras hay?

Soluci´on. La respuesta a esta pregunta es f´acil: Hay 1000 pues son todos los n´umeros

enteros del 0 al 999. Esta soluci´on no nos ense˜na gran cosa. Retomemos ahora el problema

buscando una soluci´on constructiva; esto es, para cualquier n = 1, 2, 3, . . ., la cantidad de

n´umeros de hasta n + 1 cifras se puede obtener de la cantidad de n´umeros de hasta n cifras:

simplemente se multiplica por 10. Vamos a describir con detalle este procedimiento:

N´umeros de a lo m´as una cifra hay 10, a saber, 0, 1, 2, 3, 4, 5, 6, 7, 8 y 9. Para contar 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 cada uno de

´estos hay 10 terminaciones distintas; por ejemplo, los n´umeros de dos cifras 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´alogo:

Para contar los n´umeros de hasta tres cifras hay que agregar un d´ıgito (posiblemente 0) a

cada uno de los 100 n´umeros de 2 o menos cifras; como hay diez posibilidades la respuesta

ser´a 10 × 100 = 1000. ♦

Este procedimiento de “construir sobre lo ya construido” que hemos utilizado se llama

procedimiento inductivo . Muchas demostraciones de propiedades y f´ormulas de n´umeros

naturales se basan en ´el. M´as adelante se estudiar´a esto con detalle. El principio 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

1

n maneras distintas, entonces las dos tareas juntas pueden realizarse (en ese orden) de mn

formas diferentes.

1.3 Ejemplo. ¿Cu´antas palabras de tres letras se pueden formar si se dispone de un

alfabeto con dos letras: a y b. (Nota: Son permisibles palabras como bba.)

Soluci´on. Procederemos como en el ejemplo anterior. En este caso conviene ilustrarlo

haciendo un “diagrama ´arbol”