Konbinazio (konbinatoria)

Wikipedia(e)tik
Hona jo: nabigazioa, Bilatu

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[aldatu | aldatu iturburu kodea]

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

A,B A,C A,D A,E A,F
B,C B,D B,E B,F
C,D C,E C,F
D,E D,F
E,F

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[aldatu | aldatu iturburu kodea]

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[aldatu | aldatu iturburu kodea]

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[aldatu | aldatu iturburu kodea]

Identitatea Azalpena
{n \choose 1}=n n elementuko multzo batetik elementu bat n eratara aukera daiteke, multzoan dauden elementuetako bakoitza aukeratuz hain zuzen.
{n \choose 0}=1 n elementuko multzo batetik 0 elementu era bakar batean aukera daiteke, inongo elementurik aukeratu gabe hain zuzen.
{n \choose k}={n \choose n-k} n elementuko multzo batetik k elementu aukeratzen badira, n-k elementu aukeratu gabe geratzen dira. Beraz, k elementu aukeratzeko erak, n-k elementu ez aukeratzeko erak dira.
{n \choose k}={n-1 \choose k}+{n-1 \choose k-1} Pascalen identitatea: n elementuko multzo batetik k elementuren aukeraketa bi eratara egin daiteke, x elementu jakin bati buruz: x elementua aukeratuz nahiz x elementua aukeratu gabe. x elementua aukeratuz, beste k-1 elementuak beste n-1 elementuen artean aukera daitezke; x elementua aukeratu gabe, berriz, beste n-1 elementuetatik k aukeratu behar dira.
{m+n \choose k}=\sum_{i=0}^k{m \choose k}{n \choose r-k} Vandermonderen identitatea: m+n elementuko multzo batetik k elementuren aukeraketa k eratara egin daiteke: m elementutik 0 elementu eta n elementutik k elementu hartuz, m elementutik 1 elementu eta n elementutik k-1 elementu hartuz, m elementutik 2 elementu eta n elementutik k-2 elementu hartuz, ..., m elementutik k-1 elementu eta n elementutik 1 elementu hartuz eta azkenik m elementutik k elementu eta n elementutik 0 elementu hartuz.
\sum_{k=0}^n{n \choose k}=2^n Adierazpenean agertzen den konbinazioen batura n elementuko multzo bateko azpimultzo guztien kopurua da. Hain zuzen, multzo bat bertatik k=0, 1, 2, ..., n elementu erauziz zatitu daiteke.
n{n-1 \choose k-1}=k{n \choose k} Adibidez, n pertsona aukeran daudelarik, k kideko talde batean, burua ere aukeratu behar bada, talde kopurua bi era hauetako batean eman daiteke: lehenik burua (n aukera) eta gainerako k-1 kideak aukeratzeko n-1 pertsona daude aukeran edota lehenik talde osoa osaturik (n elementutik k kide), gero horietan burua aukeratzeko k taldekide daude aukeran.[1]

Ikus, gainera[aldatu | aldatu iturburu kodea]

Erreferentziak[aldatu | aldatu iturburu kodea]

  1. (Ingelesez)   Cameron, Peter J., Notes on Combinatorics, 9. orrialdea, http://www.maths.qmul.ac.uk/~pjc/notes/comb.pdf .

Kanpo loturak[aldatu | aldatu iturburu kodea]

Commonsen badira fitxategi gehiago, gai hau dutenak: Konbinazio (konbinatoria) Aldatu lotura Wikidatan