Notas de álgebra superior

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 quepermiten determinar
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 contarlesa
las patas, haremos una 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 estrivial pero que
nos ense˜a la clave b´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 se puede 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 observarque 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 de hasta 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. Muchasdemostraciones de propiedades y f´rmulas de n´meros
o
u
naturales se basan en ´l. En la secci´n 4 se 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 puederealizarse
de n maneras distintas, entonces las dos tareas juntas pueden realizarse (en ese orden) de
mn 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

······

aaa

b

······

aab

a

······

aba

b

······

abb

a

······

baa

b

······

bab

a

······

bba

b

······

bbb

a
a
b

a
b
b

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

§1. Matem´ticas discretas
a...