MATEMATIKA DISKRETUAMara Merino Maestre
UNIBERTSITATEKO ESKULIBURUAKMANUALES UNIVERSITARIOS
MATEMATIKA DISKRETUA
Mara Merino Maestre
Mara Merino MaestreMatematika Aplikatua eta Estatistika eta Ikerkuntza OperatiboaZientzia eta Teknologia [email protected]
http://www.ehu.es/mae/html/prof/Maria.html
UPV/EHUko Euskararen Arloko Errektoreordetzak sustatutako argitalpena
Servicio Editorial de la Universidad del Pas Vasco Euskal Herriko Unibertsitateko Argitalpen Zerbitzua
ISBN:978-84-9082-438-2
CIP. Unibertsitateko Biblioteka
Merino Maestre, Mara
Matematika diskretua [Recurso electrnico] / Mara Merino Maestre. Datos. - Bilbao : Universidad del Pas Vasco / Euskal Herriko Unibertsitatea, Argitalpen Zerbitzua = Servicio Editorial, [2016]. 1 recurso en lnea : PDF. Modo de acceso: World Wide Web ISBN: 978-84-9082-438-2.
1. Anlisis combinatorio. 2. Grafos, Teora de.519.1(0.034)
http://www.ehu.es/mae/html/prof/Maria.html
Jesus de la Cal Aguadoren omenez
Estos textos quieren contribuir humildemente a mantener vivo el recuerdo del catedrico Jess de la Cal Aguado, tristemente fallecido el 25 de agosto de 2011.
En el curso 2010-11 comenzaron los nuevosplanes de titulacion en la Facultad de Cien-cia y Tecnologa de la UPV/EHU y portanto, un curso despues nos enfrentamos alreto de impartir por primera vez la asignaturaMatematica Discreta de segundo curso del Gradoen Matematicas. Las ultimas conversaciones conJesus y los apuntes de la asignatura Combinato-ria del plan academico anterior fueron realmenteutiles para facilitar dicho trabajo.
Por medio de estos textos queremos rendirle un pequeno homenaje. Jesus fue sin duda un pro-fesor e investigador sobresaliente, pero ademas fue una persona cercana, generosa, muy humana y con un gran sentido del humor. Por lo que sin duda, ha dejado un recuerdo imborrable a quienes tuvimos la suerte de poder conocerle.
Ikasmaterial honen bidez, apalki lagundu nahidugu, Jesus de la Cal Aguado katedradunaren,tamalez 2011ko abuztuaren 25ean zendua,oroimenari bizirik eustera.
2010-11 ikasturtean, UPV/EHUko Zientzia etaTeknologia Fakultateko titulazio plan berriakhasi ziren. Beraz, ikasturte bete bat geroago,Matematika Graduko bigarren mailako Matem-atika Diskretua izeneko irakasgaia lehenengoaldiz emateko erronka izan genuen. Lanaerrazteko izugarri baliagarriak izan ziren Je-susekin izandako azken elkarrizketak eta aurrekoirakaskuntza-planaren Konbinatoria izenekoirakasgaiaren apunteak.
Ikasmaterial honen bidez, berari omenaldi txikibat egin nahi diogu. Jesus, irakasle eta ikertzailebikaina izateaz gain, oso pertsona hurbila, eskuz-abala, bihozbera eta umore-sen handikoa izanzen. Hori dela eta, zalantza barik, oroigarri ez-abaezina utzi digu bera ezagutzeko zortea izangenuen guztioi.
Larraitz Aranburu, Silvia Marcaida, Mara Merino eta Eduardo Sainz de la Maza
Matematika Diskretuaren irakasleak
Aurkibidea
Hitzaurrea 1
KONBINATORIA 5
1. Oinarrizko konbinatoria 11
1.1. Konbinatoria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2. Zenbaketa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3. Lurra eta sabaia izeneko funtzioak . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.4. Zuhaitz-diagramak . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.5. Potentzia faktorialak . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.6. Sailkapenak . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.7. Inklusio-esklusio printzipioa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.8. Itzulpenak . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.9. Usategia eta agurrak . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
1.10. Oinarrizko konbinatoriaren ariketa-zerrendak . . . . . . . . . . . . . . . . . . . . . . 27
Lehenengo ariketa-zerrenda: lur eta sabai funtzioak . . . . . . . . . . . . . . . . . . . 27
Bigarren ariketa-zerrenda: oinarrizko konbinatoriako problemak . . . . . . . . . . . . 28
Hirugarren ariketa-zerrenda: oinarrizko konbinatoriako beste zenbait problema . . . 30
Laugarren ariketa-zerrenda: olinpiada matematikoetako problemak . . . . . . . . . . 33
i
2. Konbinazio-identitateak 35
2.1. Konbinazio-identitateak . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.2. Binomioaren formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.3. Koefiziente multinomialak . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.4. Binomio orokortuaren formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.5. Konbinazio-identitateen ariketa-zerrendak . . . . . . . . . . . . . . . . . . . . . . . . 44
Bosgarren ariketa-zerrenda: zenbaki konbinatorioak . . . . . . . . . . . . . . . . . . . 44
Seigarren ariketa-zerrenda: Newtonen binomioa . . . . . . . . . . . . . . . . . . . . . 47
Zazpigarren ariketa-zerrenda: koefiziente multinomialak . . . . . . . . . . . . . . . . 49
3. Funtzio sortzaileak eta errepikapenak 51
3.1. Funtzio sortzaileak . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.2. Funtzio sortzaileak eta konbinazio-problemen erabilerak . . . . . . . . . . . . . . . . 54
3.3. Errepikapenak . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.4. Funtzio sortzaileak eta errepikapenen ariketa-zerrenda . . . . . . . . . . . . . . . . . 60
Zortzigarren ariketa-zerrenda: funtzio sortzaileak eta errepikapenak . . . . . . . . . . 60
4. Zenbait zenbaki-familia garrantzitsu 63
4.1. Fibonacciren zenbakiak . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.2. Catalanen zenbakiak . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.3. Zenbaki arrunten partiketak . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.4. Multzoen partiketak eta Bellen zenbakiak . . . . . . . . . . . . . . . . . . . . . . . . 70
4.5. Lehen motako Stirlingen zenbakiak . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.6. Bigarren motako Stirlingen zenbakiak . . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.7. Zenbait zenbaki-familia garrantzitsuren ariketa-zerrendak . . . . . . . . . . . . . . . 79
Bederatzigarren ariketa-zerrenda: Fibonacciren zenbakiak . . . . . . . . . . . . . . . 79
ii
Hamargarren ariketa-zerrenda: zenbaki-partiketak . . . . . . . . . . . . . . . . . . . 81
Hamaikagarren ariketa-zerrenda: Stirlingen eta Catalanen zenbakiak . . . . . . . . . 81
GRAFO-TEORIA 85
5. Grafo-teoria 85
5.1. Oinarrizko kontzeptuak . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.2. Bideak eta ibilbideak . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
5.3. Zuhaitzak . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
5.4. Planotasuna . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
5.5. Koloratzea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
5.6. Grafo-teoriaren ariketa-zerrenda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
Hamabigarren ariketa-zerrenda: grafo-teoria . . . . . . . . . . . . . . . . . . . . . . . 101
ARIKETAK 107
A. Zenbait ariketaren ebazpenak 107
A.1. Lehenengo ariketa-zerrendako ebazpenak: lur- eta sabai-funtzioak . . . . . . . . . . . 107
A.2. Bigarren ariketa-zerrendako ebazpenak: oinarrizko konbinatoriako problemak . . . . 111
A.3. Hirugarren ariketa-zerrendako ebazpenak: konbinatoriako beste zenbait problema . . 114
A.4. Laugarren ariketa-zerrendako ebazpenak: olinpiada matematikoetako problemak . . 121
A.5. Bosgarren ariketa-zerrendako ebazpenak: zenbaki konbinatorioak . . . . . . . . . . . 127
A.6. Seigarren ariketa-zerrendako ebazpenak: Newtonen binomioa . . . . . . . . . . . . . 134
A.7. Zazpigarren ariketa-zerrendako ebazpenak: koefiziente multinomialak . . . . . . . . . 138
A.8. Zortzigarren ariketa-zerrendako ebazpenak: funtzio sortzaileak eta errepikapenak . . 140
A.9. Bederatzigarren ariketa-zerrendako ebazpenak: Fibonacciren zenbakiak . . . . . . . 141
iii
A.10.Hamargarren ariketa-zerrendako ebazpenak: zenbaki-partiketak . . . . . . . . . . . . 144
A.11.Hamaikagarren ariketa-zerrendako ebazpenak: Stirlingen eta Catalanen zenbakiak . 145
A.12.Hamabigarren ariketa-zerrendako ebazpenak: grafo-teoria . . . . . . . . . . . . . . . 149
B. Ariketen zenbakizko soluzioak 151
B.1. Oinarrizko konbinatoriaren ariketa-zerrenden soluzioak . . . . . . . . . . . . . . . . . 151
B.2. Konbinazio-identitateen ariketa-zerrenden soluzioak . . . . . . . . . . . . . . . . . . 153
B.3. Funtzio sortzaileak eta errepikapenen ariketa-zerrendaren soluzioak . . . . . . . . . . 155
B.4. Zenbaki-familia garrantzitsuen ariketa-zerrenden soluzioak . . . . . . . . . . . . . . . 156
B.5. Grafo-teoriaren ariketa-zerrendaren soluzioak . . . . . . . . . . . . . . . . . . . . . . 156
Bibliografia 157
iv
Irudien zerrenda
1.1. 5 erradiodun zirkulu-laurdenerako bikote arruntak . . . . . . . . . . . . . . . . . . . 14
1.2. 10 erradiodun zirkulu-l