Konbinazio (konbinatoria)

Konbinatorian, **konbinazioak** *n* elementuko multzo batetik *k* elementu aukeratzeko erak dira, era bakoitzean elementuen ordena kontuan hartu gabe. **Konbinazio arruntak** eta **errepikatuzko konbinazioak** bereizten dira, aukeratutako elementuak errepika daitezkeen.

## Konbinazio arruntak 
thumb| *(1,2,3,4,5)* multzotik hartutako 3 elementuren **konbinazio arruntak**: *C(n=5,k=3)=10*, 10 eratara aukera baitaitezke 3 elementu (gorriz) *(1,2,3,4,5)* multzotik; eskuin aldean konbinazio arrunt horien zerrenda zehazten da.

Konbinazio arrunta *n* elementu ezberdineko multzo batetik *k* elementu aukeratzeko era bakoitza da, *ordena kontuan hartu gabe eta elementurik errepikatu gabe*. *n* eta *k* zenbakiak osoak eta ez negatiboak izan behar dira. Gainera n \geq k betetzen da, ezin baitira aukeratu daude *n* elementuak baino gehiago.

Adibidez {A,B,C,D,E,F} multzoa harturik, 6 elementu dituena, 2 elementu aukeratu behar dira. Konbinazio arrunten kopurua 15 da:

Konbinazio arrunten kopurua adierazteko  C(n,k)\, , n\, C\, k\,,  C^n_k\,  notazioak erabil daitezke. Honela kalkulatzen da horien kopurua (ikus koefiziente binomiala eta faktoriala):

::C(n,k)={n\choose k}=\frac{n!}{k!(n-k)!}.

Honela bada, aurreko adibidea harturik C(6,2)=6!/(2!4!)=6*5/2=15 eta beraz, zerrendan ikus daitekeen bezala, 15 dira 2 elementu 6 elementuko multzo batetik aukeratzeko erak.

### Frogapena 
*n* elementuko multzo batetik *k* elementu, *modu ordenatuan* eta *elementurik errepikatu gabe*, osatzeko era kopurua (ikus aldakuntza (konbinatoria)) honela kalkulatzen da:

* lehen elementua *n* eratara aukera daiteke;
* bigarren elementua *n-1* eratara aukera daiteke, aurreko elementua ezin baita aukeratu;
...
* azken elementua *n-(k-1)* eratara aukera daiteke
* beraz, *k* elementuak *(n)r=n×(n-1)×(n-2)×...×(n-(k-1))* eratara aukera daitezke.

*(n)r* kopuruan aukeratutako elementuen ordena hartzen da kontuan (adibidez, 123 eta 321 ez dira bat bera balira bezala kontatzen). *k* elementuko aukeraketa bakoitzak, beraz, *n!* permutazio izango ditu *n(r)* kopuruan . Beraz, ordena kontuan hartu gabe *k* elementuen aukeraketa, konbinazio arrunten kopurua alegia, hau izango da: *n(r)/k!*. Hots,

:\begin{align}
C(n,k)=&\frac{(n)_k}{k!}=\frac{n \times (n-1) \times \ldots \times (n-(k-1))}{k!}\\
=&\frac{n \times (n-1) \times \ldots \times (n-(k-1)) \times (n-k) \times (n-(k+1)) \times \ldots 1}{k! \times (n-k) \times (n-(k+1)) \times \ldots 1}\\
=&\frac{n!}{k!(n-k)!}
\end{align}

## Errepikatuzko konbinazioak 
**Errepikatuzko konbinazioa**, multikonbinazioa ere deitua, *n* elementu ezberdineko multzo batetik *k* elementu aukeratzeko era bakoitza da, *ordena kontuan hartu gabe eta elementuak errepika daitezkeela*. Adibidez, 1-2-3 elementuen binakako errepikatuzko konbinazioak hauek dira, 6 guztira: 11-12-13-22-23-33

*n* elementuko multzo batetik *k*-nakako errepikatuzko konbinazioen kopurua honela izendatu eta kalkulatzen da, koefiziente binomial baten bitartez:

:Cr(n,k)=C(n+k-1,k)={n+k-1\choose k}=\frac{(n+k-1)!}{k!\cdot(n-1)!}.

Arestiko adibidea hartuz, errepikatuzko konbinazioen kopurua honela kalkulatzen da:

:Cr(n=3,k=2)={3+2-1\choose 2}=\frac{(3+2-1)!}{2!\cdot(3-1)!}=6.

Frogapen intuitibo moduan, (1,2,3,4) multzoa hartu eta 3 elementuren errepikatuzko konbinazioak osatuko dira eta errepikatuzko konbinazio bakoitzari, *(n-1)* "0" eta *k* "X" elementu berdinen errepikatuzko permutazio bat dagokio, modu honetan:

 112 -----> XX0X00
 233 -----> 0X0XX0
 234 -----> 0X0X0X
 .................

Bihurketa hau honela interpretatzen da: lehenengo 0 ikurraren ezkerrera dagoen X ikur kopurua permutazioan 1 elementuen kopurua da errepikatuzko konbinazioan, bigarren 0 ikurraren ezkerrera dagoen X ikur kopurua permutazioan 2 elementuen kopurua da errepikatuzko konbinazioan, ... Azken 0 ikurra jartzea ez da beharrezkoa: 4 elementuen kopurua konbinazioan hirugarren 0 ikurraren *eskuinera* dagoen X ikur kopurua izango da. Horrela 4 elementuen 3-nakako errepikatuzko konbinazioak 4-1 "0" eta 3 "X" elementuen errepikatuzko permutazioak izango dira:

:Cr(n,k)=\frac{(n+k-1)!}{k!\cdot(n-1)!}.

## Konbinazioei buruzko identitate jakingarriak 
:

## Ikus, gainera 
* Aldakuntza (konbinatoria)

## Erreferentziak 
## Kanpo estekak