Konbinatoria

Wikipedia(e)tik
Hona jo: nabigazioa, Bilatu
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, konbinatoriak propietate berdinak dituzten elementuak zenbatu eta elementu hauen multzoen ezaugarriak aztertzen ditu. Zenbaketa hutsaz arduratzen den arloari konbinatoria zenbatzaile 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.


Konbinatoria zenbatzailea[aldatu | aldatu iturburu kodea]

Biderketa erregela[aldatu | aldatu iturburu kodea]

Zenbaketa problemak ebazteko biderketan oinarritzen den zenbaketa-erregela sinple bat (ikus irudia) erabiltzen da askotan. 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




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)?


A_4^2=\frac{4!}{(4-2)!}=4 \times 3=12\,


  • 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?


EA_4^2=4^2=4 \times 4=16\,


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


K_4^2={4 \choose 2}=\frac{4!}{2!(4-2)!}=6\,


  • 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?


EK_4^2={4+2-1 \choose 2}={5 \choose 2}=\frac{5!}{3!2!}=10\,

Elementu zenbaiten ordenatze kopurua: permutazioak[aldatu | aldatu iturburu kodea]

Konbinatorian elementu zenbait zenbait eratara ordenatu daitezkeen kalkulatu behar izaten da. Elementuak ordenatzeko era bakoitza permutazio bat da.

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?


P_4=4!=4 \times 3 \times 2 \times 1=24\,


  • 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.


EP_3^{2,1}=\frac{3!}{2!1!}=3\,

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?


S(4,2)=\left\{{4\atop 2}\right\}=\frac{1}{2!}\sum_{j=0}^{2}(-1)^{2-j}{2 \choose j} j^4=7.


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 p(n=7,k=2)\, 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, p(n,k)=0, k>n\, eta p(n,k)=1, k=n\,betetzen direla kontuan harturik:


p(n,k)=p(n,k+1)+p(n-k,k)\,

Kanpo loturak[aldatu | aldatu iturburu kodea]

Commonsen badira fitxategi gehiago, gai hau dutenak: Konbinatoria Aldatu lotura Wikidatan
Wikiliburuetan liburu bat dago honi buruz:
Konbinatoria ariketak
Wikiztegian orri bat dago honi buruz: konbinatoria .