Konbinatoria

Multzo finitu baten elementuekin irizpide baten arabera egin daitezkeen zerrendak kontatzeko eta eratzeko modua aztertzen duen matematikaren atala.

Konbinatoria kontaketa-ebazkizunak aztertzen dituzten teknika matematikoen multzoa da. Zehatzago, konbinatoria multzo finituen kardinalen inguruko propietate eta ezaugarriak aztertzen arduratzen da, propietate berdinak dituzten elementuak zenbatu eta hauen arteko eraikuntzak ikasten dituelarik.

Biderketa konbinatorian maiz erabiltzen den teknika bat da, horren bitartez aukera ezberdinetarako emaitza posibleen kopurua kalkulatzen baita. Irudian, ebazkizun sinple bat: 2 praka pare eta 3 alkandora edukita, guztira 2×3=6 eratara jantzi naiteke.

Zenbaketa eta zerrendatze hutsaz arduratzen den arloari konbinatoria zerrendatzaile deritzo (adibidez, 10 pertsonako talde batean zenbat bikote ezberdin osa daitezke?); ezaugarri bati buruz multzoko elementu hobezina aurkitzeaz arduratzen den arloari, berriz, optimizazio edo hobereneratze konbinatorio deritzo (adibidez, 10 puntu harturik, puntu batetik bestera egiten diren ibilbide guztietatik zein da laburrena?).

Konbinatoria aljebra abstraktuan, geometrian, grafo teorian eta probabilitateen kalkuluan erabiltzen da. Praktikan, informatikan eta ikerketa operatiboan aplikazio zuzenak ditu.

Printzipio batukorra aldatu

Baldin eta   multzo finituak binaka disjuntoak badira, orduan  .

Multzoak binaka disjuntoak dira   bada,   guztietarako. Ez da gauza bera multzo guztien ebakidura hutsa izatea. Adibidez,   ren ebakidura osoa hutsa da, baina ez dira binaka disjuntuak, eta beraien bilduraren kardinala ez da 6, 4 baizik.

Frogapena aldatu

Indukzio metodoa erabiliko dugu. Baldin eta   bada eta   eta   badira. Orduan   eta   bijekzioak existitzen dira. Horietan oinarrituz, apliazio hau definitu dezakegu:

 , non  

Multzoak disjuntuak direnez, ondo definitta dago aplikazioa eta bistakoa da bijekzio bat dela. Beraz,  .

Demagun,  -rako eta ikus dezagun  -rako egia dela.   definituko dugu. Ohartuko gara   eta   disjuntuak direla,   multzo hutsa delako. Beraz,   kasua aplikatu diezaiokegu   eta  -ri, eta   lortuko dugu. Bina induzkioagatik,   denez,  -rako frogatuta geratzen da.

Printzipio biderkakorra aldatu

Baldin eta r luzerako zerrenda ordenatua osatu nahi badugu, non zerrendaren lehen tokirako   objekturen artean aukera daitekeen, bigarrenerako   objekturen artean eta, antzera, r-garren tokian   objektuen artean aukera daiteke. Orduan, zerrenda posible guztien kopurua   da.

Adibideak aldatu

  • Zenbat zenbaki osa daitezke 3 zifraz osatuta daudenak zifra bakoitzean 0tik 9rako zenbakiak jar badaitezke? Zerrendaren luzera 3 izango litzateke eta leku bakoitzean 10 elementu jar daitezke. Beraz, horrelako zenbaki desberdinen kopurua   izango litzateke.


  • zenbat matrikula posible daude espainiar kotxeetarako? 4 zenbakiz eta 3 letraz osaturik daude (― ― ― ― ― ― ―), zenbaki bakoitza [0-9] tartean egongo da, beraz, 10 elementu posible daude posizio bakoitzeko → 10 * 10 * 10 * 10 = 104 aukera posible. Bestalde, letrei dagokionez 21 elementu posible egongo dira posizio bakoitzeko (soilik kontsonanteak erabiltzen dira matrikuletan) → 21 * 21 * 21 = 213. Hortaz matrikula posible guztien kopurua 104 * 213 = 92.610.000 izango da.

Historia aldatu

Konbinatoriari buruzko oinarrizko kontzeptuak eta zerrenda-emaitzak antzinako munduan zehar agertu dira. K.a. VI. mendean, antzinako Indian, Sushruta medikuak Susruta-samhita-n ziurtatzen zuen 63 konbinazio osa daitezkeela 6 zapore desberdinetatik abiatuta, banan-banan, binaka eta abar hartuta, horrela aukera guztiak kalkulatuz. Plutarko historialari greziarrak Krisipo Solosekoarekin (K. a. III. mendea) eta Hiparco de Nicea (K. a. II. mendea) eztabaidatu zuen zerrenda-arazo zail bati buruz, aurrerago frogatuko zena Schröder–Hiparcos.12 zenbakiarekin zerikusia zuela.

Erdi Aroan, konbinatoria ikasten jarraitu zen, batez ere Europako zibilizaziotik kanpo. Indiar matematikaria MahuVra (k. 850) permutazio eta konbinazio kopururako formula bat sortu zuen, eta posibleena zen formula horiek jada matematikari indiarren ezagutzetan ezagunak izatea VI. mendearen hasieran. Rabbi Abraham ibn Ezra filosofo eta astronomoak (1140. k.) koefiziente binomialen simetria ezarri zuen, eta Gersonides talmudista eta matematikariak, berriz, formula zehatz bat aurkitu zuen aurrerago, 1321.an. Triangelu aritmetikoa (koefiziente binomialen arteko erlazioak erakusten dituen diagrama grafiko bat) X. mendetik agertzen zen matematika-tratatuetan, eta denborarekin hobeto ezagutuak izango ziren, hala nola, Pascalen triangeluarekin gertatutakoa.

Errenazimenduan, gainerako matematika eta zientziekin batera, konbinatoriak berpizkundeaz gozatu zuen. Pascal, Newton, Jacob Bernoulli eta Eulerren lanak funtsezkoak bihurtu ziren eremu sortu berrian. Garai modernoetan, J. J. Sylvesterren (XIX. mendearen amaieran) eta Percy MacMahonen (XX. mendearen hasieran) lanak lagungarri izan ziren zerrenda eta konbinatoria aljebraikoaren oinarriak finkatzeko. Grafoen teoriak ere eztanda interesgarri bat izan zuen aldi berean, bereziki lau koloreen teoremarekin lotuta.

XX. mendearen bigarren erdian, konbinatoriak hazkunde azkarra izan zuen, eta, horren ondorioz, dozenaka liburu, artikulu berri egin ziren eta gai horri buruzko hitzaldiak sustatu ziren. Neurri batean, beste eremu batzuetako konexio eta aplikazio berriek sustatu zuten hazkundea, aljebratik probabilitateetara, analisi funtzionaletik zenbakien teoriara arte, eta abar. Konexio horiek, azkenean, hautsi egin zituzten matematikaren eta informatika teorikoaren konbinatoriaren eta zatien arteko ertzak, baina, aldi berean, nolabaiteko zatiketa eragin zuten eremuaren barruan.

Konbinatoriak aldatu

Aukeraketa: Multzo batetik elementu batzuk aukeratzeko zenbat modu ezberdin dauden jakitea izango da helburua. Aukeraketa horretan aukeratutako elementuen multzoak soilik du garrantzia, eta beraz, elementuak zein ordenetan aukeratu diren ez da garrantzitsua izango.

Antolaketa: Multzo batetik objektu batzuk aukeratu eta antolatzea eskatzen du. Hau da, hautatzeaz gain, gero multzokatu, ordenatu edo dena delako moduan antolatu beharko dira aukeratutako objektu horiek.

Banaketa: Multzo bateko elementuak zenbat modu desberdinetan bana daitezke beste azpimultzo batzuetan


Zer konbinatoria kasu aztertzen ari garen jakiteko, hiru ezaugarri zehaztu behar dira:

  • Elementuen ordenak eraginik duen ala ez.
  • Multzoan (n) erabilgarri dauden elementuen kopurua hasieran daudenen berdina edo txikiagoa den (r).
  • Gertaeran errepikapenik gertatzen den ala ez.Ikusi eskuineko diagrama. Honako hauek bereiz daitezke:

C: errepikapenik gabeko konbinazioak.

V: errepikapenik gabeko aldakuntzak.

P: permutazioak errepikapenik gabe.

Cr: errepikapena duten konbinazioak.

VR: errepikatutako aldakuntzak.

PR: errepikapen bidezko permutazioak.

Konbinatoria errepikapenik gabe aldatu

Konbinatoriak elementu finituak dituzten hiru kasu mota aztertzen ditu: konbinazioak, aldakuntzak eta permutazioak, kasu honetan errepikapenik gabe, elementu bakoitza behin bakarrik ager baitaiteke gertaera bakoitzean. Hiru kasu daude:

- Errepikapenik gabeko konbinazioak

- Errepikapenik gabeko aldaketak

- Errepikapenik gabeko permutazioak

Errepikapenik gabeko konbinazioak

Demagun n elementuko multzo bat dugula. Bertatik   elementu aukeratzeko dauden moduei konbinazio esaten zaie. n elementuko multzo batetik k aukeratzeko modu desberdin kopuruari n-multzo baten gaineko k-konbinazio esaten zaio eta konbinazio desberdinen kopurua honela kalkulatzen da:   Kalkulagailuan kCr   (n r-ren gainean irakurtzen da)

Adibidez, 8 laguneko bilera batean, horietako bik osatutako batzorde bat izendatu behar da. Zenbat batzorde desberdin izenda litezke?

Soluzioa:

 

Konbinazio-zenbakiak:

  badira eta   bada, k-naka hartutako n elementuko konbinazioen kopurua ematen duen zenbakia   idazten da eta konbinazio-zenbakia deitzen da.  

Aldaketak errepikapenik gabe

R -tik hartutako n elementuen aldaketak r -tan: n elementu multzo batetik atera daitezkeen r elementu desberdinen lagin ordenatu posibleak; r < n.

Zenbakia:

 

(n-tik hasita, ondoz-ondoko r faktore oso beherakor)

Kalkulagailuan: nPr teklarekin kalkulatzen da:  

Beraz,  

Adibidez,

6 atleta dituen lasterketa batean, zenbat modutan bana daitezke urrezko eta zilarrezko dominak?

Soluzioa:

 

Permutazioak errepikapenik gabe

Multzo batek n elementu badauzka, elementuak ordenatzeko modu bakoitzari permutazio deritzo.

Izan bedi   multzoa n elementu dauzkana eta 1 < k < n.   multzotik k elementu aukeratu eta ordenatzeari k-permutazio esaten zaio.

Demagun n elementuko multzo batetik k elementu aukeratu eta ordenatu nahi ditugula eta hori egiteko zenbat modu dauden jakin nahi dugula.

  bidez adierazten da eta honela kalkulatzen da:   edo beste modu honetara adierazi dezakegu ere;  

Permutazio denen kopurua  

Kalkulagailuan: x! Teklarekin x -ko faktoriala kalkulatzen da, x zenbaki oso ez-negatiboa izanik.

Adibidea: 4 zifrako zenbat zenbaki idatz daitezke 2, 3, 5 eta 8 digituekin?

Soluzioa:

 

Konbinatoria errepikapenarekin aldatu

Errepikapena duen konbinatoriak gertaera batean elementu batzuk behin baino gehiagotan ager daitezkeen konbinatoria kasuak aztertzen ditu, aurreko kasuan bezala: konbinazioak, bariazioak eta permutazioak:

Hiru motatakoak daude:- Errepikapenezko konbinazioak

-Errepikapenezko bariazioak

-Errepikapenezko permutazioak

Errepikapena duten konbinazioak

R en r -tik hartutako n elementuen birperizazioarekin egindako konbinazioak: n elementu multzo batetik atera daitezkeen eta nahitaez desberdinak ez diren r elementuen ordenatu gabeko lagin posibleak. Zenbakia:

 Ohar gaitezen hemen r > n izan daitekeela. Adibidez Banku batek opari bat eskaintzen du kartilla bakoitzeko 5 opariren artean. Banku horretan hiru kartilla dituen gizon batek zenbat modutan aukera dezake hiru opariren sorta, opariak errepikatzea axola ez bazaio? Soluzioa:  

Aldaketak errepikapenarekin

R en r -tik hartutako n elementu errepikatuz egindako aldaketak: n elementu multzo batetik atera daitezkeen eta nahitaez desberdinak ez diren r elementuen lagin ordenatu posibleak.

Zenbakia:

 

Ohar gaitezen hemen r > n izan daitekeela.

Adibidea: 3 zifrako zenbat zenbaki desberdin idazten dira 1, 2, 5 eta 8 zifrak bakarrik erabiliz?

Soluzioa:

 

Errepikatutako permutazioak

n zeinu-sekuentzia baten ordenazio posibleak dira, eta horien artean errepikatutako batzuk daude (bat x aldiz errepikatzen da, beste bat aldiz eta beste bat z aldiz...).

Zenbakia:

 

Ohartu,

 

Adibidez,

6 zifrako zenbat zenbaki desberdin idatz daitezke hiru bat, bi bost eta zortzi bat erabiliz?

Soluzioa:

 

Konbinatoriako elementuak aldatu

Printzipio batukorra aldatu

Printzipio batukorra bi gertaera disjuntuen arteko kontaketan oinarritzen da. Demagun, A eta B gertaerak aldi berean, betetzen ez direla. Orduan, baldin eta A gertaera a modu desberdinetan gertatzen bada, eta B gertaera b desberdinetan gertatzen bada, A edo B gerta daitekeen modu desberdinen kopurua a + b da.

  

Printzipio biderkakorra aldatu

Kontaketa problemak ebazteko biderketan oinarritzen den zenbaketa-erregela sinple bat (ikus irudia) erabiltzen da askotan. Kasu honetan, baldin eta A gertaera bat a modu desberdinetan gertatzen bada eta, independenteki, bigarren B gertaera, b modu desberdinetan gertatzen bada, orduan A eta B gerta daitezkeen modu desberdinen kopurua ab da. Beste modu batean esanda, baldin eta r luzerako zerrenda bat non lehenengo posiziorako   aukera ditudan, bigarrenerako   eta r-garren tokirako   objektuen artean aukera daiteke, orduan zerrenda posible guztien kopurua   da.

Adibidez, bazkari batean lehenengo plater moduan 4 aukera eta bigarrenerako 3 aukera badira, guztira bazkaria egiteko 4×3=12 aukera izango dira.

Gauza bi M eta N eratara egin badaitezke hurrenik hurren, bi gauzak batera M × N eratara egin daitezke

Usategiaren printzipioa aldatu

Kontaketa printzipio hau honako egoeran oinarritzen da: usategi batean uso kopurua habien kopurua baino handiagoa bada, orduan existitzen da gutxienez bi uso dituen habi bat.

Beste era batean esanda, m objektu n multzotan banatu nahi baditugu, m>n bada, orduan gutxienez multzoetako batean bi objektu daude. Bestalde, m>nk bada, orduan multzo batean gutxienez k+1 objektu daude.

Usategiaren printzipioak egunerokotasunean emantzat hartzen den idea bati formaltasun matematikoa ematen dio.

Adibidez, demagun pertsona talde bat aztertzen ari garela eta honen barruan gutxienez biren urtebetetzeak berdinak direla ziurtatu nahi dugula, taldearen tamaina baino ez jakinda. Hau ziurtatuko duen pertsona-kopuru txikiena 367 litzateke, 366 egun ezberdin existitzen direlako. Beraz, talde batek 367 kide edo gehiago baditu, usategiaren printzipioa jarraituz, ziur egon gaitezke gutxienez taldeko bik urtebetetze berdina dutela.

Aukeraketa-problemak: aldakuntzak eta konbinazioak aldatu

Konbinatorian maiz kalkulatu behar dira zenbat multzo osatu diren, k elementukoak, guztira aukeran dauden elementuak n direlarik. Adibidez, a, b, c eta d letrak aukeran direlarik, zenbat 2-kote osa daitezke? Erantzuna elementuak errepikatu eta 2-koteetan ordena kontuan hartu behar den izango da:


a, b, c, d elementuetatik
sor daitezkeen 2-koteak
ordena bai ordena ez
errepikatu ez aldakuntza arruntak:
ab, ac, ad, ba, ca, da,
bc, bd, cd, cb, db, dc
.
konbinazio arruntak:
ab, ac, ad
bc, bd, cd
.
errepikatu bai errepikatuzko aldakuntzak:
ab, ac, ad, ba, ca, da,
bc, bd, cd, cb, db, dc
aa, bb, cc, dd
.
multikonbinazioak:
ab, ac, ad
bc, bd, cd
aa, bb, cc, dd
.


Biderketa-erregela erabiliz, multzo horietako kopuruak kalkula daitezke, ordena kontuan hartzen den eta elementuen errepikapena posible den formula desberdinak erabiliz, zeinetan faktoriala maiz agertzen den:

  • aldakuntza arruntak: n elementuko multzo batetik zenbat k-kote ezberdin osa daitezkeen kalkulatzeko erabiltzen dira, k-kote bakoitzean ordena kontuan hartuz eta elementurik errepikatu gabe. Adibidez, 2 letrako zenbat 2-kote osa daitezke a, b, c eta d letrekin letrarik errepikatu gabe ordena kontuan hartuz (ab eta ba ezberdinak dira, alegia)?


 


  • errepikatuzko aldakuntzak: n elementuko multzo batetik zenbat k-kote ezberdin osa daitezkeen kalkulatzeko erabiltzen dira, k-kote bakoitzean ordena kontuan hartuz eta elementuak errepika daitezkeela. Adibidez, zenbat 2-kote osa daitezke a, b, c eta d letrekin letrak errepikatuz?


 


  • konbinazioak, n elementu ezberdinetatik osaturiko k-kote posibleen kopurua kalkulatzeko erabiltzen dira, ordena kontuan hartu gabe. Adibidez, a, b, c eta d 4 letretatik zenbat 2-kote osa daitezke ordena kontuan hartu gabe:


 


  • errepikatuzko konbinazioak edo multikonbinazioak, n elementu ezberdinetatik osaturiko k-kote posibleen kopurua kalkulatzeko erabiltzen dira, ordena kontuan hartu gabe eta elementuak errepika daitezkeela. Adibidez, a, b, c, d 4 letretatik osa daitezke zenbat multikonbinazio osa daitezke?


 

Ordenatze-problemak: permutazioak aldatu

Konbinatorian elementu zenbait zenbait eratara ordenatu daitezkeen kalkulatu behar izaten da. Multzo bateko elementuak ordenatzeko modu bakoitzari permutazioa esaten zaio.

a, b, c eta d elementuen 24 permutazioak
abcd abdc acbd acdb adcb adbc

bacd badc bcad bcda bdac bdca
cabd cadb cbad cbda cdab cdba

dabc dacb dbac dbca dcab dcba

* permutazioak: n elementu ezberdin zenbat eratara ordena daitezkeen kalkulatzeko erabiltzen dira. Adibidez, a, b, c eta d letrak zenbat eratara ordean daitezke?


 


  • errepikatuzko permutazioak, n elementu zenbat eratara ordena daitezkeen kalkulatzeko erabiltzen dira, elementu zenbait berdinak izan daitezkeelarik. Adibidez, a, a, b elementuak zenbat eratara ordena daitezke? 3 dira ordenatzeko moduak: aab, aba, baa.


 

Banaketa problemak aldatu

Problema hauek multzo bateko elementuk zenbat modu derberdinetan bana daitezkeen beste azpimultzo batzuetan adierazten dute.

Formula konplexuak aldatu

Problema konplexuagoetarako formulak ere garatu dira:

  • bigarren motako Stirling zenbakiak, n elementuko multzo bat k azpimultzoetan zatitzeko era kopurua kalkulatzeko erabiltzen dira. Adibidez, a, b, c eta d elementuetako multzoa 2 azpimultzoetan zenbat eratara zatitu daiteke?


 


7 zatiketak hauek dira: aa-cd, ac-bd, ad-cb, abc-d, abd-c, acd-b, bcd-a.


  • zatiketak, n zenbaki oso bat k zenbaki osoko batura moduan kalkulatzeko erak kontatzeko erabiltzen dira. Adibidez, 7 zenbakia zenbat batuketa ezberdinen emaitza moduan kalkula daiteke, batugaiak 2 izanik (orden ezberdineko batuketak berdintzat joaz)?

Kalkulatu beharreko zatiketa kopuru horri   deritzo eta 4 da: 7=7+0=6+1=5+2=3+4. Zatiketa kopurua kalkulatzeko formula zuzenik ez dago eta formula errepikari bat erabili behar da,   eta  betetzen direla kontuan harturik:


 

Kanpo estekak aldatu

Wikiztegian orri bat dago honi buruz: konbinatoria .