Konbinatoria

[thumb|300px|[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 
Baldin eta A_1, A_2, A_3,...,A_n multzo finituak binaka disjuntoak badira, orduan Card (A_1\cup \ A_2\cup \ ... \ \cup \ A_n) = Card(A_1) + Card(A_2)+...+ Card(A_n).

Multzoak binaka disjuntoak dira A_i \ \cap \ A_j = \emptyset bada,  i\neq j guztietarako. Ez da gauza bera multzo guztien ebakidura hutsa izatea. Adibidez, A_1 = \begin{Bmatrix} 0,2 \\ \end{Bmatrix}  \ A_2= \begin{Bmatrix} 0,3 \\ \end{Bmatrix} \ eta\ A_3=\begin{Bmatrix} 3,4 \\\end{Bmatrix} ren ebakidura osoa hutsa da, baina ez dira binaka disjuntuak, eta beraien bilduraren kardinala ez da 6, 4 baizik. 

### Frogapena 
Indukzio metodoa erabiliko dugu. Baldin eta n=2 bada eta Card(A_1)=n eta Card(A_2)=m badira. Orduan f:A_1\longrightarrow \{1,2,...,n\} eta g:A_2\longrightarrow \{1,2,...,m\} bijekzioak existitzen dira. Horietan oinarrituz, apliazio hau definitu dezakegu:

h: A_1\cap A_2 \longrightarrow \{1,2,...,n+m\}, non h(x) = \begin{cases} f(x), & x \in A_1 \\ g(x)+n, & x \in A_2 \end{cases}

Multzoak disjuntuak direnez, ondo definitta dago aplikazioa eta bistakoa da bijekzio bat dela. Beraz, Card(A_1\cap A_2)=n+m.

Demagun, n-1\geq 2-rako eta ikus dezagun n-rako egia dela. B=A_1 \cup ...\cup A_{n-1} definituko dugu. Ohartuko gara B eta A_n disjuntuak direla, B \cap A_n  multzo hutsa delako. Beraz, n=2 kasua aplikatu diezaiokegu  B eta A_n-ri, eta Card(B \cup A_n)= Card(B)+Card(A_n) lortuko dugu. Bina induzkioagatik, Card(B)=Card(A_1)+...+Card(A_{n-1}) denez, n-rako frogatuta geratzen da.

## Printzipio biderkakorra 
Baldin eta r luzerako zerrenda ordenatua osatu nahi badugu, non zerrendaren lehen tokirako n_1 objekturen artean aukera daitekeen, bigarrenerako n_2 objekturen artean eta, antzera, r-garren tokian n_r objektuen artean aukera daiteke. Orduan, zerrenda posible guztien kopurua n_1n_2...n_r da.  

#### Adibideak
*Zenbat zenbaki osa daitezke 3 zifraz osatuta daudenak zifra bakoitzean 0tik 9rako zenbakiak jar badaitezke? Zerrendaren luzera 3 izango litzateke eta leku bakoitzean 10 elementu jar daitezke. Beraz, horrelako zenbaki desberdinen kopurua 10^3 izango litzateke.

*zenbat matrikula posible daude espainiar kotxeetarako? 4 zenbakiz eta 3 letraz osaturik daude (― ― ― ― ― ― ―), zenbaki bakoitza [0-9] tartean egongo da, beraz, 10 elementu posible daude posizio bakoitzeko → 10 * 10 * 10 * 10  = **104** aukera posible. Bestalde, letrei dagokionez 21 elementu posible egongo dira posizio bakoitzeko (soilik kontsonanteak erabiltzen dira matrikuletan) → 21 * 21 * 21 = **213.** Hortaz matrikula posible guztien kopurua 104 * 213 = 92.610.000 izango da.

## Historia 
Konbinatoriari buruzko oinarrizko kontzeptuak eta zerrenda-emaitzak antzinako munduan zehar agertu dira. K.a. VI. mendean, antzinako Indian, Sushruta medikuak Susruta-samhita-n ziurtatzen zuen 63 konbinazio osa daitezkeela 6 zapore desberdinetatik abiatuta, banan-banan, binaka eta abar hartuta, horrela aukera guztiak kalkulatuz. Plutarko historialari greziarrak Krisipo Solosekoarekin (K. a. III. mendea) eta Hiparco de Nicea (K. a. II. mendea) eztabaidatu zuen zerrenda-arazo zail bati buruz, aurrerago frogatuko zena Schröder–Hiparcos.12 zenbakiarekin zerikusia zuela.

Erdi Aroan, konbinatoria ikasten jarraitu zen, batez ere Europako zibilizaziotik kanpo. Indiar matematikaria MahuVra (k. 850) permutazio eta konbinazio kopururako formula bat sortu zuen,  eta posibleena zen formula horiek jada matematikari indiarren ezagutzetan ezagunak izatea VI. mendearen hasieran. Rabbi Abraham ibn Ezra filosofo eta astronomoak (1140. k.) koefiziente binomialen simetria ezarri zuen, eta Gersonides talmudista eta matematikariak, berriz, formula zehatz bat aurkitu zuen aurrerago, 1321.an. Triangelu aritmetikoa (koefiziente binomialen arteko erlazioak erakusten dituen diagrama grafiko bat) X. mendetik agertzen zen matematika-tratatuetan, eta denborarekin hobeto ezagutuak izango ziren, hala nola, Pascalen triangeluarekin gertatutakoa.

Errenazimenduan, gainerako matematika eta zientziekin batera, konbinatoriak berpizkundeaz gozatu zuen. Pascal, Newton, Jacob Bernoulli eta Eulerren lanak funtsezkoak bihurtu ziren eremu sortu berrian. Garai modernoetan, J. J. Sylvesterren (XIX. mendearen amaieran) eta Percy MacMahonen (XX. mendearen hasieran) lanak lagungarri izan ziren zerrenda eta konbinatoria aljebraikoaren oinarriak finkatzeko. Grafoen teoriak ere eztanda interesgarri bat izan zuen aldi berean, bereziki lau koloreen teoremarekin lotuta.

XX. mendearen bigarren erdian, konbinatoriak hazkunde azkarra izan zuen, eta, horren ondorioz, dozenaka liburu, artikulu berri egin ziren eta gai horri buruzko hitzaldiak sustatu ziren. Neurri batean, beste eremu batzuetako konexio eta aplikazio berriek sustatu zuten hazkundea, aljebratik probabilitateetara, analisi funtzionaletik zenbakien teoriara arte, eta abar. Konexio horiek, azkenean, hautsi egin zituzten matematikaren eta informatika teorikoaren konbinatoriaren eta zatien arteko ertzak, baina, aldi berean, nolabaiteko zatiketa eragin zuten eremuaren barruan.

## Konbinatoriak 
**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 
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 k\leq n 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: C_n^k =
   \binom{n}{k} =
   \frac{V_n^k}{P_{k}} =
   \frac{n  \cdot (n-1)  \cdot (n-2) ... (n-k+1)}{k!} =
   \frac{n!}{k!  \cdot (n-k)!}
Kalkulagailuan k**Cr**  \binom{n}{k} (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:

C_{8}^2 =
   \binom{8}{2} =
   \cfrac{8!}{2! \cdot (8-2)!} =
   \cfrac{8!}{2! \cdot 6!} =
   \frac{8 \cdot 7}{2 \cdot 1} =
   28

**Konbinazio-zenbakiak:**

k \ eta\ n \in \mathbb{N} badira eta k\leq n bada, k-naka hartutako n elementuko konbinazioen kopurua ematen duen zenbakia \binom{n}{k} idazten da eta konbinazio-zenbakia deitzen da. \binom{n}{k}=\frac{n!}{k!(n-k)!}

**Aldaketak errepikapenik gabe**

R -tik hartutako n elementuen aldaketak r -tan: n elementu multzo batetik atera daitezkeen r elementu desberdinen lagin ordenatu posibleak; r V_n^r =
   \cfrac{n!}{(n-r)!} =
   n  \cdot (n-1)  \cdot (n-2) \dots (n-r+1)

(n-tik hasita, ondoz-ondoko r faktore oso beherakor)

Kalkulagailuan: **nPr** teklarekin kalkulatzen da:   V_n^r \, , \; izaten \; r \leq n 

Beraz, V_n^n = P_n = n! 

Adibidez,

6 atleta dituen lasterketa batean, zenbat modutan bana daitezke urrezko eta zilarrezko dominak?

Soluzioa:

 V_{6}^2 =
   \cfrac{6!}{(6-2)!} =
   \cfrac{6!}{4!} =
   6 \cdot 5 =
   30

**Permutazioak errepikapenik gabe**

Multzo batek n elementu badauzka, elementuak ordenatzeko modu bakoitzari permutazio deritzo.

Izan bedi A multzoa n elementu dauzkana eta 1 A 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.

P(n,k) bidez adierazten da eta honela kalkulatzen da: P(n,k)= n (n-1)(n-2)...(n-k-1) edo beste modu honetara adierazi dezakegu ere; P(n,k)=\frac{n!}{(n-k)!}  

Permutazio denen kopurua  P(n,n)=n!

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:

P_4 =
   4! =
   4  \cdot 3  \cdot 2  \cdot 1 =
   24

### Konbinatoria errepikapenarekin 
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:

CR_n^r =
   \binom{n+r-1}{r}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:
CR_5^3 =
   \binom{5+3-1}{3} =
   \binom{7}{3} =
   35
   

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

VR_n^r =
   n^r
   

Ohar gaitezen hemen r > n izan daitekeela.

Adibidea: 3 zifrako zenbat zenbaki desberdin idazten dira 1, 2, 5 eta 8 zifrak bakarrik erabiliz?

Soluzioa:

  VR_4^3 =
   4^3 =
   64

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

PR_n^{x,y,z, \dots} =
   \frac{n!}{x!  \cdot y!  \cdot z!  \cdot \dots}

Ohartu,

PR_n^{x,n-x} =
   \binom{n}{x}

Adibidez,

6 zifrako zenbat zenbaki desberdin idatz daitezke hiru bat, bi bost eta zortzi bat erabiliz?

Soluzioa:

 PR_6^{3,2,1} =
   \frac{6!}{3!  \cdot 2!  \cdot 1!} =
   60

## Konbinatoriako elementuak 
### Printzipio batukorra 
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.

A\cap B=\phiCard (A\cup B)=Card A + CardB

### Printzipio biderkakorra 
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 n_1 aukera ditudan, bigarrenerako n_2 eta r-garren tokirako n_r objektuen artean aukera daiteke, orduan zerrenda posible guztien kopurua n_1n_2...n_r da. 

Adibidez, bazkari batean lehenengo plater moduan 4 aukera eta bigarrenerako 3 aukera badira, guztira bazkaria egiteko 4×3=12 aukera izango dira.

### Usategiaren printzipioa 
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 
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:

::

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. Multzo bateko elementuak ordenatzeko modu bakoitzari permutazioa esaten zaio.

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

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

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

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

## Kanpo estekak 
*  The Electronic Journal of Combinatorics, konbinatoria buruzko artikulu akademiko askeak.