CAP 1 MAT

1.- Principios fundamentales del conteo
La enumeración, o conteo, puede parecer un proceso obvio que un estudiante aprende al estudiar aritmética por primera vez. Pero luego, según parece, se presta poca atención en lo que se refiere a un desarrollo más amplio del conteo conforme el estudiante pasa a áreas “más difíciles” de las matemáticas, como el álgebra, la geometría, la trigonometría y elcálculo. En consecuencia, este primer capítulo deberá servir como advertencia acerca de la seriedad y dificultad del “mero” conteo.

La enumeración no termina con la aritmética. También tiene aplicaciones en áreas como la teoría de códigos, la probabilidad y estadística (en matemáticas), y el análisis de algoritmos (en ciencias de la computación). Los capítulos posteriores mostraran algunosejemplos específicos de estas aplicaciones.
A medida que vayamos entrando en este fascinante campo de las matemáticas, nos encontraremos con muchos problemas que se pueden enunciar en forma sencilla pero que son “duros” de resolver. Así, asegúrese de aprender y comprender las formulas básicas, pero no confié demasiado en ellas, ya que, sin el análisis de cada problema, el mero conocimiento de lasformulas es casi inútil. En vez de ello, acepte el reto de resolver problemas poco usuales o diferentes de los problemas que ha visto en el pasado. Busque soluciones con base en su propio análisis sin importar si es exactamente la que proporciona el autor. Con frecuencia existen varias vías para resolver un problema dado.

1.1.- Reglas de la suma y el producto

Nuestro estudio de las matemáticasdiscreta y combinatoria comienza con dos principios básicos del conteo: las reglas de la suma y del producto. Los enunciados y aplicaciones iníciales de estas reglas parecen sencillos. Al finalizar problemas más complejos, a menudo podemos descomponerlos en partes que pueden resolverse mediante estos principios básicos. Queremos desarrollar la capacidad de “descomponer” dichos problemas y acomodarnuestras soluciones parciales para llegar a la respuesta final. Una buena forma de hacerlo consiste en analizar y resolver muchos problemas distintos de enumeración, tomando nota, todo el tiempo, de los principios utilizados en la solución. Este es el método que seguiremos.
Nuestro primer principio del conteo puede expresase de la forma siguiente:

REGLA DE LA SUMA: Si una primera tarea puederealizarse de m formas, mientras que una segunda tarea puede realizarse de n formas, y no es posible realizar ambas tareas de manera simultánea, entonces, para llevar a cabo cualquiera de ellas pueden utilizarse cualquiera de formas.

Observe que cuando decimos que una ocurrencia particular, como una primera tarea, puede realizarse de m formas, se supone que estas m formas son distintas, a menos que seindique lo contrario. Esto será así a lo largo de todo el texto.

Ejemplo 1.1 La biblioteca de una universidad tiene 40 libros de texto de sociología y 50 de antropología. Por la regla de la suma, un estudiante de esta universidad puede elegir entre 40 +50 = 90 libros de texto para aprender acerca de alguno de éstos dos temas.

Ejemplo 1.2 La regla puede ampliarse a más de dos tareas, siempreque ninguna pareja de tareas pueda ocurrir en forma simultanea. Por ejemplo, un instructor de ciencias de la computación que tiene, digamos, cinco libros de nivel introductorio acerca de APL, BASIC, FORTRAN y Pascal puede recomendar cualquiera de estos 20 libros a un estudiante interesado en aprender un primer lenguaje de programación.

Ejemplo 1.3 El instructor de ciencias de la computación delejemplo 1.2 tiene dos colegas. Uno de ellos tiene tres libros de texto acerca del análisis de algoritmos y el otro cuenta con cinco libros. Si n denota el número máximo de libros diferentes sobre el tema que el instructor puede pedirles prestados, entonces , ya que ambos profesores podrían tener copias del mismo libro (o libros).

El siguiente ejemplo presenta nuestro segundo principio de...