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 batukorraAldatu

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.

Printzipio biderkakorraAldatu

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.

Adibidez, zenbat zenbaki osa ditzakegu 3 zifraz osatuta daudenak zifra bakoitzean 0tik 9rako zenbakiak jar baditzazkegu? Zerrendaren luzera 3 izango litzateke eta leku bakoitzean 10 elementu jar ditzakegu. Beraz, horrelako zenbaki desberdinen kopurua   izango litzateke.

KonbinatoriakAldatu

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 gabeAldatu

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 errepikapenarekinAldatu

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 elementuakAldatu

Printzipio batukorraAldatu

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 biderkakorraAldatu

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 printzipioaAldatu

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 konbinazioakAldatu

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: permutazioakAldatu

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 problemakAldatu

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

Formula konplexuakAldatu

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 estekakAldatu

Wikiztegian orri bat dago honi buruz: konbinatoria .