i i “Kovic” — 2016/5/11 — 7:38 — page 38 — #1 i i i i i i NOVE KNJIGE Miklós Bóna, A Walk Through Combinatorics, World Scientific Publishing Co. Ptc. Ltd. 2013, 550 strani. Učbenikov kombinatorike je, tako kot to da- nes velja že skoraj za vsako področje ma- tematike, zelo veliko, in čeprav dostikrat obravnavajo zelo podobne teme, niso vsi enako zanimivi in vredni pozornega branja. Knjiga »Sprehod po kombinatoriki« s pod- naslovom Uvod v preštevanje in teorijo gra- fov je bila od prve izdaje 2011 že dvakrat ponatisnjena, kar samo po sebi zgovorno priča o njeni uporabnosti pri pouku kom- binatorike. K njenemu uspehu je zagotovo pripomoglo več dejavnikov, od katerih je morda najpomembneǰsi posrečena kombina- cija strokovnosti in berljivosti oziroma lepo uravnotežena tehtnost vsebine in zanimi- vost idejne, jezikovne in slikovne prezenta- cije obravnavane tematike, pri kateri teorijo (definicije, izreke, dokaze, formule, metode, itd.) lepo dopolnjujejo številni primeri in naloge, ki kažejo, kako na kom- binatorične probleme pogosto naletimo ne le v matematiki, ampak tudi v vsakdanjem življenju. Vsako od 20 poglavij se začne z duhovitim naslovom, ki gre v srž dolo- čene teme, npr.: 1. poglavje: Sedem je več kot šest. Dirichletovo načelo, 2. poglavje: En korak naenkrat. Metoda matematične indukcije, 8. poglavje: Funkcija je vredna veliko števil. Rodovne funkcije, 16. poglavje: Vsaj ne- kaj reda. Delne urejenosti in mreže, 19. poglavje: Čim prej, tem bolje. Kombinatorični algoritmi, itd. Na kratko preletimo vsebino posameznih poglavij. Knjiga se začne z obravnavo Dirichletovega načela, za katerega avtor pravi, da uteleša eno od najprivlačneǰsih lastnosti kombinatorike, in sicer možnost, da dobimo zelo močne rezultate z zelo preprostimi sredstvi. Primer uporabe tega načela je dokaz (s protislovjem!) presenetljive trditve, da je imel vsak danes živeči človek v obdobju zadnjih 1000 let nekega prednika A, za katerega je obstajala neka oseba P, ki je bila hkrati prednik tako očeta kot mame osebe A. Primer zanimive naloge s tega področja pa je npr. tale: 38 Obzornik mat. fiz. 63 (2016) 1 i i “Kovic” — 2016/5/11 — 7:38 — page 39 — #2 i i i i i i A Walk Through Combinatorics »Na našem dvorǐsču so štirje kupi kamenja. Kamne preložimo na pet kupov. Dokaži, da sta vsaj dva kamna na manǰsem kupu kot prej.« V drugem poglavju, posvečenem matematični indukciji, so zanimive predvsem naloge s področja t. i. močne indukcije, kjer pri dokazu indukcij- skega koraka oziroma veljavnosti trditve pri n+ 1 upoštevamo njeno veljav- nost pri vseh številih 1, 2, . . . , n. Preprost primer uporabe tega algoritma je naslednja naloga: »Naj bo f(0) = 1, f(1) = 2, in naj bo f(n + 1) = f(n− 1) + 2f(n), če je n ≥ 1. Pokaži, da je potem f(n) ≤ 3n.« Bralce, ki so se v srednji šoli mučili z različnimi formulami za prešte- vanje, bo razveselila tabela v 3. poglavju, v kateri so lepo urejene formule za permutacije, kombinacije in variacije. A ko že mislǐs, da ti je končno vse jasno, že trenutek zatem v grozi spoznaš, da si v svojem učenju že spet na začetku (tipična frustracija v matematiki na vseh nivojih!), ko ti avtor zastavi nalogo: poǐsči število H3(r) vseh magičnih kvadratov 3 × 3 z vsoto elementov v vsaki vrstici in stolpcu enako r oziroma (kot da bi to bilo kaj bistveno lažje!) dokaži, da je to število enako vsoti nekih treh binomskih simbolov! Kdor se vseeno prebije do četrtega poglavja, je za svoj trud bogato nagrajen, saj tam najde binomski izrek in podobne identitete, katerih dokazi so, kot pravi avtor, morda še pomembneǰsi kot identitete same, v katerih leva in desna stran enačbe pomenita dva različna načina, na katera lahko preštejemo isto množico objektov; prav o takšne vrste argumentu sanjajo kombinatoriki, ko dokazujejo razne identitete. Bralca, ki pozna binomski izrek, bo zagotovo navdušila njegova posplošitev: multinomski izrek, pa tudi posplošitev binomskega izreka za izraz (1 + x)m, kjer je m poljubno realno število. Peto poglavje, posvečeno particijam, se začne s problemom, na koliko načinov lahko razdelimo 20 žog 4 otrokom. Potem spoznamo Ferrerjeve diagrame (ki jim drugi avtorji pravijo tudi Youngovi tableauxi), nazoren način za predstavitev particij. S preprostim trikom zrcaljenja teh diagramov prek glavne diagonale zlahka vidimo, da je število particij števila n v največ k delov enako številu particij števila n v dele, ki niso večji od k. Pregledna tabela s formulami olaǰsa spoznavanje različnih vrst enumeracij in olaǰsa reševanje ustreznih nalog. V šestem poglavju so obravnavane permutacije kot funkcije, to pa omo- goča preučevanje ciklov v njih. Spoznamo tudi Stirlingova števila prve in druge vrste. Sedmo poglavje je posvečeno pravilu vključitve in izključitve, z upo- rabo katerega lahko rešimo znani problem, na koliko načinov lahko n go- stov po zabavi v temi izbere napačen klobuk oziroma koliko je permuta- Obzornik mat. fiz. 63 (2016) 1 39 i i “Kovic” — 2016/5/11 — 7:38 — page 40 — #3 i i i i i i Nove knjige cij n elementov brez fiksnih točk; za to število D(n) dobimo lepo formulo D(n) = Σni=0(−1)i n!i! . Osmo poglavje predstavi eno najmočneǰsih orodij enumerativne kombi- natorike: tehniko rodovnih funkcij (ki jo je med prvimi uporabljal že Eu- ler!). Rodovna funkcija zaporedja a0, a1, a2, . . . je formalna potenčna vrsta G(x) = Σ∞n=0anx n. Če so členi zaporedja podani z začetnim členom in neko rekurzivno enačbo, npr. a0 = 50, an+1 = 4an − 100, potem lahko tako enačbo pomnožimo z xn+1 in seštejemo, kar nam da neko enačbo za rodovno funkcijo, v gornjem konkretnem primeru dobimo G(x)−a0 = 4xG(x)− 100x1−x oziroma G(x) = a01−4x− 100x (1−x)(1−4x) , od koder po razcepu na parcialne ulomke dobimo koeficient pri xn, v konkretnem primeru an = 50 · 4n − 100 · (4 n−1) 3 . V devetem poglavju spoznamo osnove teorije grafov le toliko, kolikor je potrebujemo za nekatere preproste kombinatorične probleme. V desetem poglavju najdemo nekaj dokazov Cayleyeve formule, da je število dreves na n vozlǐsčih v1, v2, . . . , vn enako n n−2. V enem od dokazov odigra pomembno vlogo (n − 1) × (n − 1) matrika L0, katere elementi li,j imajo vrednost stopnje vi, če je i = j, vrednost −1, če je i 6= j in sta vozlǐsči vi in vj povezani, ter vrednost 0 sicer, kjer je 1 ≤ i, j ≤ n. Izkaže se, da je število vpetih dreves polnega grafa na n vozlǐsčih Kn enako det L0 = n n−2. Enajsto poglavje lepo ponazori problem barvanja vozlǐsč grafa s prime- rom iz vsakdanjega življenja, kjer telefonska družba načrtuje gradnjo oddaj- nikov, kjer morata vsaka dva, ki sta si bliže od 50 milj, delovati na različnih frekvencah. Spoznamo pojem kromatičnega števila in dvodelnih grafov (ti imajo kromatično število 2) ter pojem prirejanja. Dvanajsto poglavje obravnava planarne grafe, Eulerjevo poliedrsko for- mulo in Spernerjevo lemo. Trinajsto poglavje predstavi osnove Ramseyjeve teorije, ki se je začela s preprostim opažanjem, da so v množici šestih ljudi vselej trije, ki se med seboj vsi poznajo, ali pa trije, ki se med seboj ne poznajo. Določitev Ram- seyjevih števil R(k, l), to je minimalnih števil, za katera velja, da če pobar- vamo vsako od povezav polnega grafa Kn z rdečo ali modro barvo, potem je v tem grafu neki monokromatski podgraf Kk s samimi rdečimi poveza- vami ali neki monokromatski podgraf Kl s samimi modrimi povezavami, je v splošnem precej težek problem. Eksistenca teh števil je sicer zagotovljena (pri pogoju k, l ≥ 2), niso pa znana niti za nekatere pare majhnih števil k, l. Vseeno pa se da iz rekurzivne zveze R(k, l) ≤ R(k, l − 1) + R(k − 1, l) izpeljati npr. oceno za simetrična Ramseyjeva števila R(k, k) ≤ 4k−1. V štirinajstem poglavju je obravnavan problem števila permutacij Sn(q) dolžine n brez določenih vzorcev, npr. brez vzorcev tipa q = 132 (kjer je prvi element manǰsi od tretjega, ta pa manǰsi od drugega). Dokazane so 40 Obzornik mat. fiz. 63 (2016) 1