matematika diskretua - web- · pdf fileariketak 107 a. zenbait ariketaren ebazpenak 107 a.1....
TRANSCRIPT
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