Konbinatoria

Artikulu hau "Kalitatezko 2.000 artikulu 12-16 urteko ikasleentzat" proiektuaren parte da
Wikipedia, Entziklopedia askea

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.

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.

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 | aldatu iturburu kodea]

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 | aldatu iturburu kodea]

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 | aldatu iturburu kodea]

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.

Konbinatoriak[aldatu | aldatu iturburu kodea]

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 | aldatu iturburu kodea]

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 | aldatu iturburu kodea]

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 | aldatu iturburu kodea]

Printzipio batukorra[aldatu | aldatu iturburu kodea]

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 | aldatu iturburu kodea]

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 | aldatu iturburu kodea]

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 | aldatu iturburu kodea]

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 | aldatu iturburu kodea]

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 | aldatu iturburu kodea]

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

Formula konplexuak[aldatu | aldatu iturburu kodea]

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 | aldatu iturburu kodea]

Wikiztegian orri bat dago honi buruz: konbinatoria .