Konbinatoria

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 eta probabilitateen kalkuluan erabiltzen da besteak beste. Praktikan, informatikan eta optimizazioan aplikazio zuzenak ditu.

Konbinatoria zenbatzailea

Formula sinpleak

Konbinatoria zenbatzailean multzo bateko elementuen kopurua kalkulatzen dira. Horretarako, formula ezberdinak asmatu dira, ebatzi beharreko problema zein den. Zenbaketa problema sinpleenak osatu beharreko multzoak elementuak errepika daitezkeen eta horien ordena kontuan hartu behar den sailkatzen dira, taula honetan erakusten den bezala:

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, dd, ee.

Zenbaketa problema horiek ebazteko formulak biderketan oinarritzen den zenbaketa-erregela sinple bat (ikus irudia) erabiltzen da:

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

Horrela, biderketa-erregelatik konbinatoriako formula arrunt hauek eratortzen dira:

• 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, d eta e 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, d eta e letrekin letrak errepikatuz?

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

a, b, d eta e elementuen 24 permutazioak

abde abed adbe adeb aedb aebd

bade baed bdae bdea bead beda
dabe daeb dbae dbea deab deba

eabd eadb ebad ebda edab edba

• permutazioak: n elementu ezberdin zenbat eratara ordena daitezkeen kalkulatzeko erabiltzen dira. Adibidez, a, b, d eta e 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.

$P_3^{2,1}=\frac{3!}{2!1!}=3\,$

• konbinazioak, n elementu ezberdinetatik osaturiko k-kote posibleen kopurua kalkulatzeko erabiltzen dira, ordena kontuan hartu gabe. Adibidez, a, b, d eta e 4 letretatik 6 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, d, e 4 letretatik osa daitezke zenbat multikonbinazio osa daitezke?

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

Formula konplexuak

Problema konplexuagoetarako formaulak ere asmatu dira:

• bigarren motako Stirling zenbakiak, n elementuko multzo bat k azpimultzoetan zatitzeko era kopurua kalkulatzeko erabiltzen dira. Adibidez, a, b, d eta e elementuko 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)\,$