Matematica Discreta

MATEMATICAS
DISCRETA
y
COMBINATORIA
Una introducci6n con aplicaciones
TERCERA-EDICI6N
RALPH P. GRIMALDI
Rose-Hulman Institute of Technology
PEARSON EDUCACION DE MEXICO
C.IEMPLAR PAlM CVALUACION
PROHIBIDA SU VENT A
~======-=-- --. -~-J
PEARSON
Educaci6n
Mexico • Argentina • Brasil • Colombia • Cost~ Rica • Chile • Ecuador
Esp·afta • Guatemala • Panama • PerU • Puerto Rico • Uruguay• Venezuela
This one
7W7B-K94-FSTJ
Versi6n en espallol de Ia obra Discrete and Combinatorial Mathemalics. An applied inlroduction.
de Ralph P. Grimaldi, publicada originalmente en ingl6s por Addison-Wesley Publishing
Company, Inc., Reading, Massachusetts@ 1994, por Addison-Wesley Compaoy, lnc.
Esta ed.ici6n en cspallol es Ia unica autorizada.
C 1997 por Addl•on Wesley lberoamericana, S.A.Primer• relmpr .. l6n, 1998
D.R. Cl 1998 por Addl•on Wesley Longman de M6xlco, S.A. de C.V.
Atlacomulco Ndm. 500·5° Piso
• Col. l.ndustrial Atoto
53519, Naucalpan de Ju~rez, Edo. de Mexjco
CNIEM 1031
Reservados todos los derechos. Ni Ia totalidad ni parte de esta
poblicaci6n pueden reprodudrse, registrarse o transmltirse. por un
sistema de recuperad6n de informaci6n, de ninguna forma. nl porningun rnedlo, sea electronico, mecanico. fotoqulmico, magn6tico o
electto6pUco. por fotocopia. grabaci6n o cualquier otro. sin permlso
previo por escrito del edito(. El pr~tamo. alquiler o cualquier otra
forma de oes•6n de uso de este ejemplar requerir~ tambi~ Ia
autortzacl6n del editor ode sus representantes.
ISBN 968 444 324 2
lmpreso en Mexico. Printed In Mexico
l. opynghted material1
Principios
fundamentales
del
L a enumeraci6n, o conteo. pucde parecer un proceso obvio que un cstudiante aprende al
e-~tudiar aritmetica por primera vez. Pero luego, segun parece, se presta poca atenci6n
en lo que se refiere a un desarrollo mas amplio del conteo conforrne el estudiante pasa a
areas "mas diffciles" de las matematicas, como el algebra, Ia g~ometrfa, Ia trigonometrfa y
elc:Uculo. En consecuencia, este primer capitulo debera servir como advertencia acerca
de Ia seriedad y dificultad del "mero" conteu.
La enumcraci6n no terrnina con Ia ariunetica. Tambien tiene aplicaciones en areas como
Ia leoria de c6digos,la probabilidad y estadistica (en matem:iticas), y el amilisis de algoriunos
(en ciencias de Ia computaci6n). Los capftulos posteriores mostraran algunosejemplos
especificos de estaS aplicaciones.
A medida que vayamos entrando en este fascinante campo de las matematicas, nos
encontraremos con muchos problemas que se pucden enunciar en forma sencilla pero que
son "duros" de resolver. Asf, asegurese de aprender y comprender Ia~ f6rmulas basicas,
pero 110 conffe demasiado en elias, ya que, sin el amiUsis de cada problema, el mcro
conocimicnto delas f6rrnulas es casi inutil. En vez de ello, acepte el reto de resolver
problemas poco usuales o diferent.es de los problemas que ha vista en el pasado. Busque
soluciones con base en su propio anaUsis sin importar si es exact.amcntc Ia que proporciona
el autor. Con frecuencia existen varias v!as para resolver uo problema dado.
1.1
Reglas de Ia suma y del producto
NuestrO estudio de lasmatematicas discreta y combinatoria comienza con dos principios
basicos del conteo: las reglas de Ia suma y del producto. Los enunciados y aplicacioncs
iniciales de estas reglas parecen sencillos. Alanalizar problemas mas cornplcjos, a rnenudo
podemos descomponerlos en partes que pueden resolvcrse mediante estos principios basi·
cos. Queremos desarrollar Ia capacidad de "descomponer" dichosproblemas y acornodar
• En este texlo se han utiliUJdo los tl!nninos •·conteo". "*recuemo" y .. contar .. pnra traducir cl tt!rmino
counting. (N. dd T.)
Copyrighted material
You have either reached a page that is unavailable for viewing or reached your viewing limit for this
book.
•
1 . 1 Reg las de Ia su rna y del producto 5
bro del comitt! A ellunes y el martes con un miembro del comite B....