Konbinatoria

Konbinatoria kontaketa-ebazkizunak aztertzen dituzten teknika matematikoen multzoa da. Zehatzago, konbinatoriak propietate berdinak dituzten elementuak zenbatu eta elementu hauen multzoen ezaugarriak aztertzen ditu. 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.

Konbinatoria zenbatzailea

Biderketa erregela

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

Aukeraketa-problemak: aldakuntzak eta konbinazioak

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\,

Ordenatze-problemak: permutazioak

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

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: