MD-liburua/Konbinatoria

6. Gaia: Konbinatoria

6.1 Sarrera

Konbinatoriaren helburua konfigurazioak aztertzea da. Konfigurazio bat objektuen antolaketa jakin bat da. Konfigurazio bat bilatzen da objektu batzuk aldez aurretik finkatutako murriztapen batzuk errespetatuz jarri nahi diren bakoitzean.

Adibidez, $O$ eta $X$ objektuak eta $K_{1}$ eta $K_{2}$ kaxak baditugu, bi objektuak bi kaxetan sartzeko modu bakoitza konfigurazio bat da.

${\begin{array}{cccc}{\begin{array}{||c|c||}K_{1}&K_{2}\\\hline O,X&\\\hline \end{array}}&{\begin{array}{||c|c||}K_{1}&K_{2}\\\hline X&O\\\hline \end{array}}&{\begin{array}{||c|c||}K_{1}&K_{2}\\\hline O&X\\\hline \end{array}}&{\begin{array}{||c|c||}K_{1}&K_{2}\\\hline &O,X\\\hline \end{array}}\end{array}}$

Demagun, orain, bidaiari batek $50$ herri bisitatu behar dituela, eta abiapuntura itzuli. Behin bakarrik bisitatu nahi du herri bakoitza. Ibilbide posible bakoitza konfigurazio bat da.

Konbinatorian lau alderdi hartu behar dira kontuan: existentzia, deskribapena, zenbaketa eta optimizazioa.

Existentzia: konfigurazio ezezagun baten bilaketaren problema da. Horrelako konfiguraziorik egongo al da?

Adibidez, bidaiariaren probleman, herri bakoitzetik behin pasatzen den ibilbiderik ba al dago?

Beste kasu batean, osa daiteke zenbaki oso positiboen $3\times 3$ matrize bat, haren errenkada, zutabe eta diagonal guztien batura $15$ izan dadin?

Deskribapena: Konfigurazio guztien deskribapena konfigurazio guztien zerrenda egitean datza.

Ikus dezagun zein diren bi objektu hiru kaxatan sartzeko moduak:

${\begin{array}{ccc}{\begin{array}{||c|c|c||}K_{1}&K_{2}&K_{3}\\\hline O,X&&\\\hline \end{array}}&{\begin{array}{||c|c|c||}K_{1}&K_{2}&K_{3}\\\hline &O,X&\\\hline \end{array}}&{\begin{array}{||c|c|c||}K_{1}&K_{2}&K_{3}\\\hline &&O,X\\\hline \end{array}}\\&&\\{\begin{array}{||c|c|c||}K_{1}&K_{2}&K_{3}\\\hline X&O&\\\hline \end{array}}&{\begin{array}{||c|c|c||}K_{1}&K_{2}&K_{3}\\\hline X&&O\\\hline \end{array}}&{\begin{array}{||c|c|c||}K_{1}&K_{2}&K_{3}\\\hline O&X&\\\hline \end{array}}\\&&\\{\begin{array}{||c|c|c||}K_{1}&K_{2}&K_{3}\\\hline &X&O\\\hline \end{array}}&{\begin{array}{||c|c|c||}K_{1}&K_{2}&K_{3}\\\hline O&&X\\\hline \end{array}}&{\begin{array}{||c|c|c||}K_{1}&K_{2}&K_{3}\\\hline &O&X\\\hline \end{array}}\\\end{array}}$

Bidaiariaren probleman, ibilbide guztien deskribapena.

Zenbaketa: konfigurazio guztien zenbaketaren problema konfigurazio posible guztien kopurua lortzen saiatzea da. Konbinatoriaren alderdirik ezagunena da. Gu alderdi horretaz baino ez gara arduratuko.

Adibidez, zenbat modu daude mahai-inguru batean $6$ pertsona esertzeko?

Bi objektu bi kaxatan jartzeko $4$ modu daude. Hiru kaxatan bi objektu jartzeko $9$ modu daude. Bidaiariaren arazoan, ibilbide kopurua.

Optimizazioa: $x$ konfigurazio bakoitzari $f(x)$ balio bat esleitzen zaio eta $f(x)$ minimoa egiten duen konfigurazioa bilatuko da. Hau da, $x_{0}$ konfigurazio bat bilatuko da, non $f(x_{0})\leq f(x)$ beteko den $x$ konfigurazio guztietarako.

Bidaiariaren problemari dagokionez, $x$ ibilbide bakoitzari $f(x)=x$-ren kilometro kopurua esleitzen zaio. Ibilbiderik laburrena bilatuko da.

6.2 Baturaren eta biderkaduraren arauak

Esperimentu deituko diogu hainbat emaitza behagarri dituen prozesu bati. Adibidez, dado bat jaurti ($6$ emaitza posible), txanpon bat eta dado bat batera jaurti ($12$ emaitza posible), bi objektu bi kaxatan sartu ($4$ emaitza posible), $300$ ikasleren artean ordezkari bat aukeratu ($300$ emaitza posible).

Esperimentu baten emaitza posibleen kopurua zenbatzeko, oinarrizko bi printzipio erabiliko ditugu: baturaren araua eta biderkaduraren araua. Arau horien enuntziatuak eta aplikazioak oso errazak dira. Problema konplexuenak aztertzean, oinarrizko ideia horien bidez ebatz daitezkeen zatietan banatzen dira.

Problema horiek deskonposatzeko eta gure soluzio partzialak egokitzeko gaitasuna garatu nahi dugu, azken erantzunera iristeko.

Baturaren araua: Esperimentu batek $m$ emaitza posible baditu eta beste esperimentu batek $n$ emaitza posible baditu, bi esperimentuetako edozein egiten dugunean (ez biak batera) $m+n$ emaitza posible daude.

Oharra. Esperimentu batek $m$ emaitza posible dituela diogunean, $m$ emaitza horiek desberdinak direla jotzen da, kontrakoa adierazten ez bada behintzat.

Biderkaduraren araua: Esperimentu batek $m$ emaitza posible baditu eta beste esperimentu batek $n$ emaitza posible baditu, bi esperimentuak egiten ditugunean, $m\cdot n$ emaitza posible daude.

Adibidea. Enpresa batean bi atal daude: $A$ atala $50$ langilerekin eta $B$ atala $30$ langilerekin. Zenbat aukera daude:

a) enpresaren ordezkari bat hautatzeko? $50+30=80$ forma daude.

b) atal bakoitzeko ordezkari bat hautatzeko? $50\cdot 30=1.500$ forma daude.

Arauak bi esperimentu baino gehiagotan aplika daitezke.

Adibidea. Akademia batek Logikako $3$ ikastaro, Konbinatoriako $5$ ikastaro eta Aljebrako $2$ ikastaro eskaintzen ditu. Zenbat aukera ditu pertsona batek

a) ikastaro batean izena emateko? $3+5+2=10$ aukera daude.

b) gai bakoitzeko ikastaro batean izena emateko? $3\cdot 5\cdot 2=30$ aukera daude.

Batzuetan, bi arauak konbinatu behar izaten dira problema bat ebazteko.

Adibidea. Matrikula-plaka batek $6$ digitu ditu edo $2$ letra eta jarraian $4$ digitu. Zenbat matrikula-plaka daude

a) letrak eta digituak ezin badira errepikatu? $10\cdot 9\cdot 8\cdot 7\cdot 6\cdot 5+26\cdot 25\cdot 10\cdot 9\cdot 8\cdot 7=3.427.200$ plaka daude.

b) letrak ezin badira errepikatu, baina digituak bai? $10^{6}+26\cdot 25\cdot 10^{4}=7.500.000$ plaka daude.

6.3 Aldakuntzak. Permutazioak

Biderkaduraren araua erabiliz, ordena edo diseinu jakin baten arabera jarritako objektuen antolamenduak zenbatuko dira.

Definizioa. $n$ objektu dituen bilduma bat emanda, $r$ tamainako aldakuntza deituko diogu $n$ objektuen artetik aukeratutako $r$ objekturen ordenazio bakoitzari. Adibidez, $a,b,c$ hiru objektuak baditugu:

a) $2$ tamainako aldakuntzak:

- errepikapenik ez badago: $ab,ac,ba,bc,ca,cb$.

- errepikapenak onartzen badira: $aa,ab,ac,ba,bb,bc,ca,cb,cc$.

b) $2$ tamainako aldakuntzak:

- errepikapenik ez badago: $abc,acb,bac,bca,cab,cba$.

- errepikapenak onartzen badira: $aaa,aab,aac,aba,abb,abc,\ldots$.

$n$ objektuko bilduma bateko errepikapenik gabeko $r$ tamainako aldakuntzen kopurua $V(n,r)$ adieraziko dugu. Kasu horretan, $0\leq r\leq n$ izan behar du.

$n$ objektuko bilduma bateko $r$ tamainako errepikatuzko aldakuntzen kopurua $V(n,r)$ adieraziko dugu. Kasu horretan, $0\leq r$ izan behar du.

$10$ objektu baditugu, $A,B,C,D,E,F,G,H,I$ eta $J$, $4$ tamainako aldakuntza kopurua zenbatzeko, posizioak eta posizio bat okupatzeko aukeratu daitezkeen objektuen kopurua hartuko ditugu kontuan. Posizio bat okupatzea esperimentu bat da.

- Errepikapenik onartzen ez bada: lehen posiziorako $10$ emaitza posible daude. Bigarren posiziorako $9$ daude, hirugarrenerako $8$ daude, eta laugarrenerako $7$. Biderkaduraren arauaren arabera, $4$ tamainako aldakuntza kopurua hau da: $V(10,4)=10\cdot 9\cdot 8\cdot 7=5.040$. (Emaitza bera lortzen da posizioak beste ordena batean betetzen badira)

- Errepikapenak onartzen badira: posizio bakoitzean $10$ emaitza posible daude. Biderkaduraren arauaren arabera, $4$ tamainako errepikatuzko aldakuntzen kopurua, orain, $VR(10,4)=10\cdot 10\cdot 10\cdot 10=10.000$ da.

Oro har, $n$ objektu $a_{1},\ldots ,a_{n}$ baldin baditugu, $r$ tamainako aldakuntza kopurua modu berean kalkulatzen da:

- Errepikapenik gabe ($r\leq n$ izan behar du): lehen posiziorako $n$ emaitza posible daude; bigarrenerako $n-1$ daude; hirugarrenerako $n-2$ daude; eta $r$. posiziorako $n-r+1$ daude. Biderkaduraren arauaren arabera, $n$ objektuko bilduma bateko errepikapenik gabeko $r$ tamainako aldakuntza kopurua hau da:

$r=0$ bada, errepikapenik gabeko $0$ tamainako aldakuntza kopurua da.

- Errepikapenekin ($r\geq n$ izan daiteke): posizio bakoitzean $n$ emaitza posible daude. Biderkaduraren arauaren arabera, $n$ objektuko bilduma bateko $r$ tamainako errepikatuzko aldakuntza kopurua honako hau da:

Definizioa. $n\geq 0$ zenbaki oso bat emanik, $n$-ren faktoriala, $n!$, honela definitzen da: ${\begin{array}{l}0!=1,\\n!=n\cdot (n-1)\cdot (n-2)\cdots 3\cdot 2\cdot 1,\quad n\geq 1.\end{array}}$

Ondorio gisa, edozein $n$ zenbaki osotarako: $(n+1)!=(n+1)\cdot n!$.

Faktorialen idazkera erabiliz, aurreko emaitzak honela idatziko ditugu: $V(n,r)=n\cdot (n-1)\cdots (n-r+1)={\frac {n\cdot (n-1)\cdots (n-r+1)\cdot (n-r)\cdots 3\cdot 2\cdot 1}{(n-r)\cdots 3\cdot 2\cdot 1}}=$ $={\frac {n!}{(n-r)!}},\quad 1\leq r\leq n.$

$r=0$ kasuan, $\displaystyle {V(n,0)={\frac {n!}{n!}}=1}$.

Hau da,

Definizioa. $r=n$ denean, $n$ tamainako aldakuntzei $n$ objektuen permutazio esaten zaie. Hau da, $n$ objektu desberdineko permutazioa $n$ objektuen antolamendua da.

Adibidea. $a$, $b$ eta $c$ hiru objektu desberdinen permutazioak $abc$, $acb$, $bac$, $bca$, $cab$ eta $cba$ dira.

$n$ objektu desberdinen permutazio kopurua objektu horien ordenazio kopurua da, eta $P(n)$ adieraziko dugu:

Adibideak.

1. $10$ laguneko talde bati argazkia atera nahi diogu banku batean.

   a) Nola eseri daitezke? $P(10)=10!=3.628.800$.

   b) $10$ lagunetatik $4$ren argazkia atera nahi badugu, nola egin daiteke?

   $V(10,4)={\dfrac {10!}{6!}}=10\cdot 9\cdot 8\cdot 7=5.040$.

2. (Permutazio zirkularrak) $5$ pertsona esertzen badira mahai zirkular baten inguruan, $A,B,C,D$ eta $E$, zenbat ordenazio zirkular desberdin egin daitezke?

   Bi ordenazio zirkular berdinak dira horietako bat biraketa bidez lor daitekeenean. Adibidez, $ABCDE=BCDEA=CDEAB=DEABC=EABCD$.

   Ordenazio (permutazio) zirkular bakoitzeko, $5$ permutazio lineal lortuko ditugu. Beraz, permutazio zirkularren kopuruari $PC(n)$ deitzen badiogu, hau izango dugu: $P(5)=5\cdot PC(5)$ eta hortik, $PC(5)={\dfrac {P(5)}{5}}={\dfrac {5!}{5}}=4!=24$.

   Kalkulatzeko beste modu bat $A$ posizioa finkatzea izango litzateke. Kasu horretan, $PC(5)=P(4)=4!$.

   Orokorrean, esan dezakegu dela.

3. Zenbat modutan eser daitezke $5$ lagun, $A,B,C,D$ eta $E$, mahai zirkular baten inguruan, $C$ lagunak $B$-ren eskuinean eseri nahi badu?

   Bi posizio finkatzen dira; beraz, erantzuna $P(3)=3!=6$ da.

4. Zenbat modutan ordena daitezke $LAPIKO$ hitzaren letrak? $P(6)=6!=720$.

Demagun, orain, $n$ objekturen ordenazioen kopurua kalkulatu nahi dugula, eta horietako batzuk errepikatuta daudela: lehen motako $n_{1}$ objektu daude, bigarren motako $n_{2}$ , ..., eta $r$. motako $n_{r}$, non $n_{1}+n_{2}+\cdots +n_{r}=n$ baita. Ordenazio kopurua $PR_{n_{1},n_{2},\ldots ,n_{r}}(n)$ adieraziko dugu.

Adibideak.

1. Zenbat modutan ordena daitezke $AMA$ hitzaren letrak?

   Si distinguimos las dos letras $A$, $A_{1}$ y $A_{2}$, tendremos $P(3)=3!=6$ formas: $A_{1}MA_{2}$, $A_{2}MA_{1}$, $A_{1}A_{2}M$, $A_{2}A_{1}M$, $MA_{1}A_{2}$ y $MA_{2}A_{1}$.

   $A$ letrak bereizten baditugu $A_{1}$ eta $A_{2}$, $P(3)=3!=6$ forma izango dugu: $A_{1}MA_{2}$, $A_{2}MA_{1}$, $A_{1}A_{2}M$, $A_{2}A_{1}M$, $MA_{1}A_{2}$ eta $MA_{2}A_{1}$.

   $A$ letrak bereizten ez baditugu, $A_{1}MA_{2}=A_{2}MA_{1}=AMA$, $A_{1}A_{2}M=A_{2}A_{1}M=AAM$ eta $MA_{1}A_{2}=MA_{2}A_{1}=MAA$ izango ditugu. $A$ letrak bereizten ez dituen permutazio bakoitzari A letrak bereizten dituen bi permutazio dagozkio. Hortaz,

   $P(3)\;(A_{1}MA_{2})=2\cdot PR_{2,1}(3)\;(AMA).$

   $PR_{2,1}(3)={\dfrac {P(3)}{2}}={\dfrac {3!}{2}}=3.$

2. Zenbat modutan ordena daitezke $ATAZA$ hitzaren letrak?

   $P(5)\;(A_{1}TA_{2}ZA_{3})=3!\cdot PR_{3,1,1}(5)\;(ATAZA).$

   $PR_{3,1,1}(5)={\dfrac {P(5)}{3!}}={\dfrac {5!}{3!}}=20.$

3. Zenbat modutan ordena daitezke $OROKOR$ hitzaren letrak?

   $P(6)\;(O_{1}R_{1}O_{2}KO_{3}R_{2})=2!\cdot PR_{2,1,1,1,1}(6)\;(O_{1}RO_{2}KO_{3}R)=$ $=2!\cdot 3!\cdot PR_{2,3,1}(6)\;(OROKOR).$

   $PR_{2,3,1}(6)={\dfrac {P(6)}{2!3!}}={\dfrac {6!}{2!3!}}=60.$

Oro har, $n$ objektu badaude, lehenengo motako $n_{1}$, bigarren motako $n_{2}$, ..., $r$. motako $n_{r}$, non $n_{1}+n_{2}+\cdots +n_{r}=n$ baita, $n$ objektuen errepikatuzko permutazio kopurua honako hau da:

Adibideak.

1. Zenbat mezu desberdin sor daitezke $3$ lerro eta $2$ puntuko segida batekin? $PR_{3,2}(5)={\dfrac {5!}{3!2!}}=10.$
2. Zenbat modutan margotu ditzakegu $12$ gela $3$ gela berde, $2$ gela arrosa, $2$ gela hori eta gainerakoak zuriak izateko moduan? $PR_{3,2,2,5}(12)={\frac {12!}{3!2!2!5!}}=166.320.$

6.4 Konbinazioak

Definizioa. Errepikapenik gabeko $r$ tamainako konbinazio deituko diogu, $n$ objektuen artean aukeratutako $r$ objekturen ordenazio bakoitzari, zein ordenatan aukeratzen diren kontuan hartu gabe. $n$ objekturen errepikapenik gabeko $r$ tamainako konbinazioen kopurua $C(n,r)$ adieraziko dugu.

Adibidez, $10$ kideko erakunde batean, $A,B,C,D,E,F,G,H,I$ eta $J$, lehendakaria, idazkaria eta diruzaina aukeratu behar baditugu, ordenazio kopurua honako hau izango da: $V(10,3)=10\cdot 9\cdot 8=720$. Kontuan hartzen dugu ez dela gauza bera lehendakaria izatea, diruzaina izatea edo idazkaria izatea.

Baina $3$ pertsonako batzorde bat aukeratzen badugu, non ez dagoen kargu desberdinik, beraz, hautaketa-ordenak ez du axola, $ABC$, $ACB$, $BAC$, $BCA$, $CAB$ eta $CBA$ desordenatutako hautapen bera da; hots, $ABC=ACB=BAC=BCA=CAB=CBA$. Eta gauza bera beste batzuekin. Beraz,

$V(10,3)=3!\cdot C(10,3).$

$C(10,3)={\dfrac {V(10,3)}{3!}}={\dfrac {10!}{3!7!}}=120.$

Oro har, $n$ objektuko bilduma bat emanda, $r$ tamainako konbinazio bakoitzeko (ordenak ez du axola) $r$ tamainako $r(r)=r!$ aldakuntza (ordenak garrantzia du) izango ditugu. Beraz, oro har, hau dugu:

$V(n,r)=P(r)\cdot C(n,r),$

eta hortik:

$C(n,r)={\dfrac {V(n,r)}{P(r)}}={\dfrac {n!}{r!(n-r)!}},\quad 0\leq r\leq n.$

$C(n,r)$ balioa $\left({\begin{array}{c}n\\r\end{array}}\right)$ eran ere idatzi ohi da eta $n$ gain $r$ zenbaki (edo koefiziente) binomial deitzen zaio.

$C(n,r)=\left({\begin{array}{c}n\\r\end{array}}\right)={\dfrac {n!}{r!(n-r)!}},\quad 0\leq r\leq n.$

Adibidea. Pertsona batek $20$ lagun ditu eta $5$ gonbidatu nahi ditu afaltzera. Zenbat modutan egin dezake hautaketa?

Ordena garrantzitsua ez denez, $C(20,5)=\left({\begin{array}{c}20\\5\end{array}}\right)={\dfrac {20!}{5!15!}}=15.504$.

Edozein zenbaketa-problemarekin aritzean, ordenak probleman duen garrantzia aztertu behar da. Ordenak garrantzia badu, aldakuntzak hartu behar dira kontuan eta, bestela, konbinazioak.

Adibideak.

1. Azterketa batean, $12$ galderako sorta batetik $8$ galderari erantzun behar die ikasle batek. Zenbat modutan erantzun diezaioke azterketari?

   a) Murrizketarik gabe: $\left({\begin{array}{c}12\\8\end{array}}\right)={\dfrac {12!}{8!4!}}=495.$

   b) Lehenengo $5$ galderetatik $2$ erantzun behar baditu, eta azken $7$ galderetatik $6$: $\left({\begin{array}{c}5\\2\end{array}}\right)\left({\begin{array}{c}7\\6\end{array}}\right)={\frac {5!}{2!3!}}{\frac {7!}{6!1!}}=10\cdot 7=70.$

   c) Lehenengo $5$ galderetatik gutxienez $2$ erantzun behar baditu (eta guztira $8$):

   - lehenengo $5$ galderetatik $2$ erantzuten baditu: $\left({\begin{array}{c}5\\2\end{array}}\right)\left({\begin{array}{c}7\\6\end{array}}\right)$.

   - lehenengo $5$ galderetatik $3$ erantzuten baditu: $\left({\begin{array}{c}5\\3\end{array}}\right)\left({\begin{array}{c}7\\5\end{array}}\right)$.

   - lehenengo $5$ galderetatik $4$ erantzuten baditu: $\left({\begin{array}{c}5\\4\end{array}}\right)\left({\begin{array}{c}7\\4\end{array}}\right)$.

   - lehenengo $5$ galderetatik $5$ erantzuten baditu: $\left({\begin{array}{c}5\\5\end{array}}\right)\left({\begin{array}{c}7\\3\end{array}}\right)$.

   Guztira, $\left({\begin{array}{c}5\\2\end{array}}\right)\left({\begin{array}{c}7\\6\end{array}}\right)+\left({\begin{array}{c}5\\3\end{array}}\right)\left({\begin{array}{c}7\\5\end{array}}\right)+\left({\begin{array}{c}5\\4\end{array}}\right)\left({\begin{array}{c}7\\4\end{array}}\right)+\left({\begin{array}{c}5\\5\end{array}}\right)\left({\begin{array}{c}7\\3\end{array}}\right)=70+210+165+35=490$.

   . c) kalkulatzeko, lehenengo $5$ galderen artean $2$ galdera hartzen baditugu, eta, gero, aukeratu ez diren $10$ galderen artean $6$ galdera hartzen baditugu, $\left({\begin{array}{c}5\\2\end{array}}\right)\left({\begin{array}{c}10\\6\end{array}}\right)=2.100$, zenbait aukera hainbat aldiz zenbatzen ari gara. Adibidez, $p_{1}$ eta $p_{2}$ aukeratzen baditugu lehenengo $5$ artean, eta gainerako $10$en artean $p_{4},p_{6},p_{7},p_{8},p_{9}$ eta $p_{10}$ azterketa hau izango dugu: $p_{1},p_{2},p_{4},p_{6},p_{7},p_{8},p_{9},p_{10}$. Baina, lehenengo $5$ galderen artean $p_{1}$ eta $p_{4}$ aukeratzen baditugu, eta $p_{2},p_{6},p_{7},p_{8},p_{9}$ eta $p_{10}$ gainerako $10$en artean, berriro ere $p_{1},p_{4},p_{2},p_{6},p_{7},p_{8},p_{9},p_{10}$ azterketa izango dugu.

2. $3$ digituko zenbat zenbaki daude?

   1. Digitu errepikaturik ez badute: $V(10,3)=10\cdot 9\cdot 8={\dfrac {10!}{7!}}=720$.

   2. Digitu errepikatuak izan baditzakete: $VR(10,3)=10^{3}=1.000$.

   3. Digitu errepikaturik ez badute eta $5$ zenbakiaz hasten badira:

      $V(9,2)=9\cdot 8={\dfrac {9!}{7!}}=72$.

   4. Digitu errepikaturik ez badute eta $0$ zenbakiaz ez badira hasten:

      $V(10,3)-V(9,2)=10\cdot 9\cdot 8-9\cdot 8=648$.

   5. Digitu errepikatuak izan baditzakete eta $5$ zenbakiaz hasten badira:

      $VR(10,2)=10^{2}=100$.

   6. Digitu errepikatuak izan baditzakete eta $0$ zenbakiaz ez badira hasten:

      $VR(10,3)-VR(10,2)=10^{3}-10^{2}=900$.

Problema batzuk bi ikuspuntutatik azter daitezke, permutazioenak edo konbinazioenak.

Adibidea. $21$ laguneko talde batetik $7$ laguneko $3$ batzorde eratu behar dira ($A,B$ eta $C$). Zenbat modutan egin daiteke?

Lehenengo batzorderako: $\left({\begin{array}{c}21\\7\end{array}}\right)$ aukera.

Bigarren batzorderako: $\left({\begin{array}{c}14\\7\end{array}}\right)$ aukera.

Hirugarren batzorderako: $\left({\begin{array}{c}7\\7\end{array}}\right)$ aukera.

Guztira, $\left({\begin{array}{c}21\\7\end{array}}\right)\left({\begin{array}{c}14\\7\end{array}}\right)\left({\begin{array}{c}7\\7\end{array}}\right)={\dfrac {21!}{7!14!}}{\dfrac {14!}{7!7!}}{\dfrac {7!}{7!0!}}={\dfrac {21!}{7!7!7!}}=399.072.960$.

Kalkulua honela ere egin genezakeen: $21$ pertsonak lerroan jartzen ditugu, eta bakoitzaren azpian dagokion batzordea: ${\begin{array}{cccccc}1&2&3&4&\ldots &21\\A&A&B&B&\ldots &B\end{array}}$ Horrela, $7A$, $7B$ eta $7C$ antolamenduak izan ditzakegu. Hau da: $PR_{7,7,7}(21)={\dfrac {21!}{7!7!7!}}=399.072.960.$

Problema batzuk ebazteko, permutazio eta konbinazio kontzeptuak behar dira.

Adibidea. Zenbat modutan ordena daitezke $ARABERAKOAN$ hitzaren letrak?

a) Murrizketarik gabe: $PR_{4,2,1,1,1,1,1}(11)={\dfrac {11!}{4!2!}}=831.600.$

b) $A$ horiek ezin badira ondoz ondoan agertu:

$A$ gabe ($RBERKON$), $PR_{1,2,1,1,1,1}(7)={\dfrac {7!}{2!}}=2.520$.

$A$ kokatzeko posizioak:

Lau posizio aukeratu behar dira $8$etatik: $C(8,4)=\left({\begin{array}{c}8\\4\end{array}}\right)=70$.

Hortaz, guztira: ${\dfrac {7!}{2!}}\left({\begin{array}{c}8\\4\end{array}}\right)=2520\cdot 70=176.400$. Propietateak.

1. $\left({\begin{array}{c}n\\0\end{array}}\right)=\left({\begin{array}{c}n\\n\end{array}}\right)=1$.
2. $\left({\begin{array}{c}n\\r\end{array}}\right)=\left({\begin{array}{c}n\\n-r\end{array}}\right),\quad 0\leq r\leq n$.
3. $\left({\begin{array}{c}n\\r\end{array}}\right)=\left({\begin{array}{c}n-1\\r-1\end{array}}\right)+\left({\begin{array}{c}n-1\\r\end{array}}\right),\quad 1\leq r\leq n-1$.

Froga.

Propietate bakoitzaren bi froga emango ditugu: lehenengoa koefiziente binomialen definizioa erabiliz; eta bigarrenean, koefiziente horiek interpretatuko ditugu.

1. a) Koefiziente binomialak

   $\left({\begin{array}{c}n\\0\end{array}}\right)={\dfrac {n!}{0!n!}}=1$. $\left({\begin{array}{c}n\\n\end{array}}\right)={\dfrac {n!}{n!0!}}=1$.

   b) Koefizienteen interpretazioa

   $\left({\begin{array}{c}n\\0\end{array}}\right)$ balioa $n$ objekturen artean $0$ objektu aukeratzeko moduen kopurua da. Hori modu bakarrean egin daiteke, bat ere aukeratu gabe.

   $\left({\begin{array}{c}n\\n\end{array}}\right)$ balioa $n$ objekturen artean $n$ objektu aukeratzeko moduen kopurua da. Hori modu bakarrean egin daiteke, denak aukeratuz.

2. a) Koefiziente binomialak

   $\left({\begin{array}{c}n\\r\end{array}}\right)={\dfrac {n!}{r!(n-r)!}}$. $\left({\begin{array}{c}n\\n-r\end{array}}\right)={\frac {n!}{(n-r)!(n-(n-r))!}}={\frac {n!}{(n-r)!r!}}$.

   b) Koefizienteen interpretazioa

   $n$ objekturen artean $r$ objektu hautatzeko moduen kopurua $n$ objektuen artean $n-r$ objektu baztertzeko moduen kopuru bera da.

3. a) Koefiziente binomialak

   $\left({\begin{array}{c}n\\r\end{array}}\right)={\dfrac {n!}{r!(n-r)!}}$.

   $\left({\begin{array}{c}n-1\\r-1\end{array}}\right)+\left({\begin{array}{c}n-1\\r\end{array}}\right)={\dfrac {(n-1)!}{(r-1)!((n-1)-(r-1))!}}+{\dfrac {(n-1)!}{r!(n-1-r)!}}=$

   $={\dfrac {(n-1)!}{(r-1)!(n-r)(n-r-1)!}}+{\dfrac {(n-1)!}{r(r-1)!(n-r-1)!}}=$

   $={\dfrac {(n-1)!r+(n-1)!(n-r)}{r(r-1)!(n-r)(n-r-1)!}}={\dfrac {(n-1)!(r+n-r)}{r!(n-r)!}}={\dfrac {(n-1)!n}{r!(n-r)!}}={\dfrac {n!}{r!(n-r)!}}$.

   b) Koefizienteen interpretazioa

   $n$ objektu, $a_{1},\ldots ,a_{n}$, emanda, horien $r$ tamainako ordenazio kopurua $\left(\left({\begin{array}{c}n\\r\end{array}}\right)\right)$ $a_{2},\ldots ,a_{n}$ objektuen $r-1$ tamainako ordenazioen kopurua $\left(\left({\begin{array}{c}n-1\\r-1\end{array}}\right)\right)$ gehi $a_{2},\ldots ,a_{n}$ objektuen $r$ tamainako ordenazioen kopurua $\left(\left({\begin{array}{c}n-1\\r\end{array}}\right)\right)$. Lehenengoak $a_{1}$ dutenak dira, eta bigarrenak, berriz, $a_{1}$ ez dutenak. $\Box$

Teorema. Teorema binomiala

$x,y$ bi zenbaki erreal badira eta $n$ zenbaki oso positibo bat bada: $(x+y)^{n}=\left({\begin{array}{c}n\\0\end{array}}\right)x^{0}y^{n}+\left({\begin{array}{c}n\\1\end{array}}\right)x^{1}y^{n-1}+\left({\begin{array}{c}n\\2\end{array}}\right)x^{2}y^{n-2}+\cdots +\left({\begin{array}{c}n\\n\end{array}}\right)x^{n}y^{0}=$ $=\sum _{k=0}^{n}\left({\begin{array}{c}n\\k\end{array}}\right)x^{k}y^{n-k}.$ Froga.

Teorema binomiala $n$-ren gaineko indukzioaren bidez frogatuko dugu.

$n=1$ denean, $(x+y)^{1}=x+y$.

Bestalde, $\displaystyle {\sum _{k=0}^{1}\left({\begin{array}{c}1\\k\end{array}}\right)x^{k}y^{1-k}=\left({\begin{array}{c}1\\0\end{array}}\right)x^{0}y^{1}+\left({\begin{array}{c}1\\1\end{array}}\right)x^{1}y^{0}=y+x=x+y.}$

Demagun berdintza $n=p\geq 1$ denean betetzen dela, hau da, $(x+y)^{p}=\sum _{k=0}^{p}\left({\begin{array}{c}p\\k\end{array}}\right)x^{k}y^{p-k}\quad {\mbox{(indukzio-hipotesia)}}$ betetzen dela.

Berdintza $n=p+1$ baliorako ere betetzen dela frogatu behar dugu. Hau da, frogatu behar dugu:

$(x+y)^{p+1}=\sum _{k=0}^{p+1}\left({\begin{array}{c}p+1\\k\end{array}}\right)x^{k}y^{p+1-k}.$ $(x+y)^{p+1}=(x+y)^{p}(x+y)=\left(\sum _{k=0}^{p}\left({\begin{array}{c}p\\k\end{array}}\right)x^{k}y^{p-k}\right)(x+y)=$ $=\left(\sum _{k=0}^{p}\left({\begin{array}{c}p\\k\end{array}}\right)x^{k}y^{p-k}\right)x+\left(\sum _{k=0}^{p}\left({\begin{array}{c}p\\k\end{array}}\right)x^{k}y^{p-k}\right)y=\sum _{k=0}^{p}\left({\begin{array}{c}p\\k\end{array}}\right)x^{k+1}y^{p-k}+\sum _{k=0}^{p}\left({\begin{array}{c}p\\k\end{array}}\right)x^{k}y^{p+1-k}.$ Alde batetik, $\sum _{k=0}^{p}\left({\begin{array}{c}p\\k\end{array}}\right)x^{k+1}y^{p-k}=\sum _{k=1}^{p+1}\left({\begin{array}{c}p\\k-1\end{array}}\right)x^{k}y^{p+1-k}=\sum _{k=1}^{p}\left({\begin{array}{c}p\\k-1\end{array}}\right)x^{k}y^{p+1-k}+\left({\begin{array}{c}p\\p\end{array}}\right)x^{p+1}y^{0}=$ $=\sum _{k=1}^{p}\left({\begin{array}{c}p\\k-1\end{array}}\right)x^{k}y^{p+1-k}+x^{p+1}.$ Beste aldetik, $\sum _{k=0}^{p}\left({\begin{array}{c}p\\k\end{array}}\right)x^{k}y^{p+1-k}=\left({\begin{array}{c}p\\0\end{array}}\right)x^{0}y^{p+1}+\sum _{k=1}^{p}\left({\begin{array}{c}p\\k\end{array}}\right)x^{k}y^{p+1-k}=y^{p+1}+\sum _{k=1}^{p}\left({\begin{array}{c}p\\k\end{array}}\right)x^{k}y^{p+1-k}.$ Eta biak elkartuz, $(x+y)^{p+1}=\sum _{k=1}^{p}\left({\begin{array}{c}p\\k-1\end{array}}\right)x^{k}y^{p+1-k}+x^{p+1}+y^{p+1}+\sum _{k=1}^{p}\left({\begin{array}{c}p\\k\end{array}}\right)x^{k}y^{p+1-k}=$ $=\sum _{k=1}^{p}\left[\left({\begin{array}{c}p\\k-1\end{array}}\right)+\left({\begin{array}{c}p\\k\end{array}}\right)\right]x^{k}y^{p+1-k}+x^{p+1}+y^{p+1}.$ Kontuan izanik $\left({\begin{array}{c}p\\k-1\end{array}}\right)+\left({\begin{array}{c}p\\k\end{array}}\right)=\left({\begin{array}{c}p+1\\k\end{array}}\right)$ dela eta $\left({\begin{array}{c}p+1\\p+1\end{array}}\right)=\left({\begin{array}{c}p+1\\0\end{array}}\right)=1$ dela, hau dugu: $(x+y)^{p+1}=\sum _{k=1}^{p}\left({\begin{array}{c}p+1\\k\end{array}}\right)x^{k}y^{p+1-k}+\left({\begin{array}{c}p+1\\p+1\end{array}}\right)x^{p+1}y^{0}+\left({\begin{array}{c}p+1\\0\end{array}}\right)x^{0}y^{p+1}=$ $=\sum _{k=0}^{p+1}\left({\begin{array}{c}p+1\\k\end{array}}\right)x^{k}y^{p+1-k}.$ $\Box$

Adibideak.

1. $\displaystyle {(x+y)^{2}=\sum _{k=0}^{2}\left({\begin{array}{c}2\\k\end{array}}\right)x^{k}y^{2-k}=\left({\begin{array}{c}2\\0\end{array}}\right)x^{0}y^{2}+\left({\begin{array}{c}2\\1\end{array}}\right)x^{1}y^{1}+\left({\begin{array}{c}2\\2\end{array}}\right)x^{2}y^{0}=y^{2}+2xy+x^{2}}$.

2. $\displaystyle {(x+y)^{3}=\sum _{k=0}^{3}}\left({\begin{array}{c}3\\k\end{array}}\right)x^{k}y^{3-k}=\left({\begin{array}{c}3\\0\end{array}}\right)x^{0}y^{3}+\left({\begin{array}{c}3\\1\end{array}}\right)x^{1}y^{2}+\left({\begin{array}{c}3\\2\end{array}}\right)x^{2}y^{1}+\left({\begin{array}{c}3\\3\end{array}}\right)x^{3}y^{0}=$

   $=y^{3}+3xy^{2}+3x^{2}y+x^{3}$.

3. $\displaystyle {(x+y)^{4}=\sum _{k=0}^{4}}\left({\begin{array}{c}4\\k\end{array}}\right)x^{k}y^{4-k}=\left({\begin{array}{c}4\\0\end{array}}\right)x^{0}y^{4}+\left({\begin{array}{c}4\\1\end{array}}\right)x^{1}y^{3}+\left({\begin{array}{c}4\\2\end{array}}\right)x^{2}y^{2}+\left({\begin{array}{c}4\\3\end{array}}\right)x^{3}y^{1}+\left({\begin{array}{c}4\\4\end{array}}\right)x^{4}y^{0}=$ $=y^{4}+4xy^{3}+6x^{2}y^{2}+4x^{3}y+x^{4}$.

Korolarioa. $x,y$ bi zenbaki erreal badira eta $n$ zenbaki oso positibo bat bada, $(x+y)^{n}=\sum _{k=0}^{n}\left({\begin{array}{c}n\\n-k\end{array}}\right)x^{k}y^{n-k}.$ Froga.

Nahikoa da kontuan izatea $\left({\begin{array}{c}n\\k\end{array}}\right)=\left({\begin{array}{c}n\\n-k\end{array}}\right)$ dela. $\Box$

Korolarioa. Edozein $n$ zenbaki oso positibotarako:

a) $\left({\begin{array}{c}n\\0\end{array}}\right)+\left({\begin{array}{c}n\\1\end{array}}\right)+\left({\begin{array}{c}n\\2\end{array}}\right)+\cdots +\left({\begin{array}{c}n\\n\end{array}}\right)=2^{n}$.

b) $\left({\begin{array}{c}n\\0\end{array}}\right)-\left({\begin{array}{c}n\\1\end{array}}\right)+\left({\begin{array}{c}n\\2\end{array}}\right)-\cdots +(-1)^{n}\left({\begin{array}{c}n\\n\end{array}}\right)=0$. Froga.

a) $2^{n}=(1+1)^{n}=\left({\begin{array}{c}n\\0\end{array}}\right)+\left({\begin{array}{c}n\\1\end{array}}\right)+\left({\begin{array}{c}n\\2\end{array}}\right)+\cdots +\left({\begin{array}{c}n\\n\end{array}}\right)$.

b) $0=(-1+1)^{n}=\left({\begin{array}{c}n\\0\end{array}}\right)(-1)^{0}+\left({\begin{array}{c}n\\1\end{array}}\right)(-1)^{1}+\left({\begin{array}{c}n\\2\end{array}}\right)(-1)^{2}+\cdots +\left({\begin{array}{c}n\\n\end{array}}\right)(-1)^{n}=$ $=\left({\begin{array}{c}n\\0\end{array}}\right)-\left({\begin{array}{c}n\\1\end{array}}\right)+\left({\begin{array}{c}n\\2\end{array}}\right)-\cdots +(-1)^{n}\left({\begin{array}{c}n\\n\end{array}}\right)$. $\Box$

Teorema. Teorema multinomiala

$n$ eta $t$ zenbaki oso positiboetarako eta $x_{1},\ldots ,x_{t}$ zenbaki errealetarako, $x_{1}^{n_{1}}x_{2}^{n_{2}}\cdots x_{t}^{n_{t}}$ gaiaren koefizientea $(x_{1}+x_{2}+\cdots +x_{t})^{n}$ garapenean hau da: ${\dfrac {n!}{n_{1}!n_{2}!\cdots n_{t}!}},$ non $n_{i}$ bakoitza zenbaki oso bat den, $0\leq n_{i}\leq n$, $i=1,\ldots ,t$ eta $n_{1}+n_{2}+\cdots +n_{t}=n$ izanik. Froga.

$n$-ren gaineko indukzioaren bidez frogatuko dugu.

$n=1$ denean, $n_{1}+n_{2}+\cdots +n_{t}=n$ denez, $0\leq n_{i}\leq 1$ izanik, $k\in \{1,\ldots ,t\}$ existituko da, non $n_{k}=1$ eta $n_{i}=0$, $i\neq k$. Hortaz, $x_{1}^{n_{1}}x_{2}^{n_{2}}\cdots x_{t}^{n_{t}}=x_{k}$.

$x_{k}$ gaiaren koefizientea $(x_{1}+x_{2}+\cdots +x_{t})^{1}=x_{1}+x_{2}+\cdots +x_{t}$ garapenean hau da: $1={\dfrac {1!}{0!\cdots 1!\cdots 0!}}={\dfrac {n!}{n_{1}!n_{2}!\cdots n_{t}!}}.$

Demagun $x_{1}^{n_{1}}x_{2}^{n_{2}}\cdots x_{t}^{n_{t}}$ gaiaren koefizientea $(x_{1}+x_{2}+\cdots +x_{t})^{p}$ berreturan ${\dfrac {p!}{n_{1}!n_{2}!\cdots n_{t}!}}$ dela (indukzio-hipotesia), $n_{1}+n_{2}+\cdots +n_{t}=p$ izanik.

Frogatu behar dugu $(x_{1}+x_{2}+\cdots +x_{t})^{p+1}$ berreturan $x_{1}^{n_{1}}x_{2}^{n_{2}}\cdots x_{t}^{n_{t}}$ gaiaren koefizientea ${\dfrac {(p+1)!}{n_{1}!n_{2}!\cdots n_{t}!}}$ dela, $n_{1}+n_{2}+\cdots +n_{t}=p+1$ izanik.

$(x_{1}+x_{2}+\cdots +x_{t})^{p+1}=(x_{1}+x_{2}+\cdots +x_{t})^{p}(x_{1}+x_{2}+\cdots +x_{t})=$

$=(x_{1}+x_{2}+\cdots +x_{t})^{p}x_{1}+(x_{1}+x_{2}+\cdots +x_{t})^{p}x_{2}+\cdots +(x_{1}+x_{2}+\cdots +x_{t})^{p}x_{t}$ denez,

$x_{1}^{n_{1}}x_{2}^{n_{2}}\cdots x_{t}^{n_{t}}$ gaiaren koefizientea $(x_{1}+x_{2}+\cdots +x_{t})^{p}x_{i}$ batugai bakoitzean duen koefizienteen batura izango da, $i=1,...,t$.

$x_{1}^{n_{1}}x_{2}^{n_{2}}\cdots x_{t}^{n_{t}}$ gaiaren koefizientea $(x_{1}+x_{2}+\cdots +x_{t})^{p}x_{i}$ batugaian $x_{1}^{n_{1}}\cdots x_{i}^{n_{i}-1}\cdots x_{t}^{n_{t}}$ gaiaren koefizientea da $(x_{1}+x_{2}+\cdots +x_{t})^{p}$ berreturan. Hau da,${\dfrac {p!}{n_{1}!n_{2}!\cdots (n_{i}-1)!\cdots n_{t}!}}$.

Ondorioz, $(x_{1}+x_{2}+\cdots +x_{t})^{p+1}$ berreturan $x_{1}^{n_{1}}x_{2}^{n_{2}}\cdots x_{t}^{n_{t}}$ gaiaren koefizientea hau da: $\sum _{i=1}^{t}{\dfrac {p!}{n_{1}!n_{2}!\cdots (n_{i}-1)!\cdots n_{t}!}}={\dfrac {p!}{(n_{1}-1)!n_{2}!\cdots n_{t}!}}+\cdots +{\dfrac {p!}{n_{1}!n_{2}!\cdots (n_{t}-1)!}}=$ $={\dfrac {p!n_{1}+p!n_{2}+\cdots +p!n_{t}}{n_{1}!n_{2}!\cdots n_{t}!}}={\dfrac {p!(n_{1}+n_{2}+\cdots +n_{t})}{n_{1}!n_{2}!\cdots n_{t}!}}={\dfrac {p(p+1)}{n_{1}!n_{2}!\cdots n_{t}!}}={\dfrac {(p+1)!}{n_{1}!n_{2}!\cdots n_{t}!}}.$ $\Box$

Adibideak.

1. $(x+y+z)^{8}$ berreturan, $x^{2}y^{3}z^{2}$ gaiaren koefizientea ${\dfrac {8!}{2!3!2!}}=1.680$ da.

2. a) Aurkitu $x^{3}y^{5}$ gaiaren koefizientea $(x+y)^{8}$ berreturan.

   b) Aurkitu $a^{3}b^{5}$ gaiaren koefizientea $(2a-3b)^{8}$ berreturan.

   a) Koefizientea $\left({\begin{array}{c}8\\3\end{array}}\right)=56$ da.

   b) $x=2a$ eta $y=-3b$ eginez $x^{3}y^{5}$ gaian, hau geratuko da: $\left({\begin{array}{c}8\\3\end{array}}\right)x^{3}y^{5}=\left({\begin{array}{c}8\\3\end{array}}\right)(2a)^{3}(-3b)^{5}=\left({\begin{array}{c}8\\3\end{array}}\right)2^{3}(-3)^{5}a^{3}b^{5}=56\cdot 8\cdot (-243)a^{3}b^{5}=-108.864a^{3}b^{5}.$

3. a) Aurkitu $x^{2}y^{2}z^{4}$ gaiaren koefizientea $(x+y+z)^{8}$ berreturan.

   b) Aurkitu $a^{2}b^{2}$ gaiaren koefizientea $(a+2b-3)^{8}$ berreturan.

   a) Koefizientea ${\dfrac {8!}{2!2!4!}}=420$ da.

   b) $x=a$, $y=2b$ eta $z=-3$ eginez $x^{2}y^{2}z^{4}$ gaian, hau geratuko da: ${\dfrac {8!}{2!2!4!}}x^{2}y^{2}z^{4}={\dfrac {8!}{2!2!4!}}a^{2}(2b)^{2}(-3)^{4}={\dfrac {8!}{2!2!4!}}2^{2}(-3)^{4}a^{2}b^{2}=$ $=420\cdot 4\cdot 81a^{2}b^{2}=136.080a^{2}b^{2}.$

6.5 Errepikatuzko konbinazioak

Definizioa. $r$ tamainako errepikatuzko konbinazio deituko diogu $n$ objektuen artean aukeratutako $r$ objekturen ordenazio bakoitzari, $r$ objektu horiek errepikatuta egon daitezkeelarik.

$E=\{a,b,c,d,e,f\}$ multzoa kontuan hartuta, $4$ tamainako errepikatuzko konbinazioak aztertuko ditugu. Hau da, $E$ multzotik $4$ elementu hautatuko ditugu, baina aukera bakoitzean elementu errepikatuak egon daitezke.

Horrela, $aabb=abab=abba=baab=baba=bbaa\neq aaab$ daukagu.

$E$ multzoa erabat ordenatuta dagoela jotzen dugu: $a<b<c<d<e<f$.

$4$ tamainako errepikatuzko konbinazioak ordena ditzakegu: $aaaa$, $aaab$, $aaac$, $aaad$, ...

Ordenazio kopurua zenbatzeko, beste modu batera adieraziko ditugu. Konbinazio bakoitzeko, agertzen diren letrak eta errepikatzen diren elementuak idatziko ditugu. Honela:

$aaaa$ konbinazioari $a123$ esleitzen diogu, $a$-k lehen posizioan $a$ agertzen dela adierazten du, $1$ak lehen elementua ($a$) errepikatu egiten dela adierazten du, $2$ak bigarren elementua ($a$) errepikatu egiten dela eta $3$ak hirugarren elementua ($a$) errepikatu egiten dela.

${\begin{array}{ll}aaab&ab12\\aacc&ac13\\abdf&abdf\\accc&ac23\end{array}}$

Beraz, $\{a,b,c,d,e,f\}$ elementuen $4$ tamainako errepikatuzko konbinazio bakoitzari $\{a,b,c,d,e,f,1,2,3\}$ elementuen errepikapenik gabeko $4$ tamainako konbinazio bat dagokio, eta alderantziz. Adibidez, $abe3$ konbinazioa $abee$ da, eta $af23$ konbinazioa $afff$.

Beraz, $\{a,b,c,d,e,f\}$ elementuen $4$ tamainako errepikatuzko konbinazioen kopurua ($CR(6,4)$) $\{a,b,c,d,e,f,1,2,3\}$ elementuen errepikapenik gabeko $4$ tamainako konbinazioen kopuruaren berdina da $\left(=C(6+3,4)=\left({\begin{array}{c}9\\4\end{array}}\right)\right)$. Kontuan izan behar da $6$ elementu ager daitezkeela eta $3$ posizio errepika daitezkeela.

Oro har, $n$ objektu ezberdin $a_{1},\ldots ,a_{n}$ izanik, objektu horien $r$ tamainako errepikatuzko konbinazio bakoitzari $\{a_{1},\ldots ,a_{n},1,2,\ldots ,r-1\}$ (objektuak + posizio errepikagarriak) objektuen errepikapenik gabeko $r$ tamainako konbinazio bat dagokio, eta alderantziz. Beraz,

$CR(n,r)=C(n+r-1,r)=\left({\begin{array}{c}n+r-1\\r\end{array}}\right),\quad r\geq 0.$

($r$ $n$ baino handiagoa izan daiteke errepikapenak onartzen direnean)

Adibideak.

1. Likore-denda batean $20$ ardo-marka daude. $12$ botila eskatu nahi baditugu, nola egin daiteke?

   Markak errepikatu daitezkeenez,

   $CR(20,12)=C(20+12-1,12)=\left({\begin{array}{c}31\\12\end{array}}\right)=141.120.525$.

2. $7$ txanpon banatu nahi dira $3$ lagunen artean. Nola egin daiteke hori?

   ${\begin{array}{ccccccc}1&2&3&4&5&6&7\\A&A&A&A&A&A&B\\A&A&B&A&A&A&A\end{array}}$

   Bi banaketa horiek desberdinak dira.

   Beraz, hau da soluzioa: $VR(3,7)=3^{7}=2.187$.

3. $7$ txanpon berdin $3$ lagunen artean banatu nahi dira. Nola egin daiteke, baldin eta

   1. murrizketarik ez badago? (onartzen da lagun batek edo gehiagok ez dutela ezer jasotzen)

      ${\begin{array}{ccccccc}1&2&3&4&5&6&7\\A&A&A&A&A&A&B\\A&A&B&A&A&A&A\end{array}}$

      Bi banaketa horiek berdinak dira.

      Beraz, hau da soluzioa: $CR(3,7)=\left({\begin{array}{c}3+7-1\\7\end{array}}\right)=\left({\begin{array}{c}9\\7\end{array}}\right)=36$.

   2. lagun bakoitzak txanpon bat jaso behar badu gutxienez?

      Txanpon bat ematen diogu lagun bakoitzari, eta gainerakoak banatuko ditugu. Hau da, $CR(3,4)=\left({\begin{array}{c}3+4-1\\4\end{array}}\right)=\left({\begin{array}{c}6\\4\end{array}}\right)=15.$

   3. lagun bakoitzak txanpon bat jaso behar du gutxienez, eta $A$ lagunak $3$ txanpon gutxienez?

      $A$-ri $3$ txanpon eta $B$ eta $C$-ri txanpon bana emango diegu, eta gainerakoa banatuko dugu: $CR(3,2)=\left({\begin{array}{c}3+2-1\\2\end{array}}\right)=\left({\begin{array}{c}4\\2\end{array}}\right)=6.$

Ikusten dugunez, $r$ objektu $n$ hartzaileren artean banatzeko moduak hauek dira:

- objektuak desberdinak badira, $VR(n,r)=n^{r}$.

- objektuak berdinak badira, $CR(n,r)=\left({\begin{array}{c}n+r-1\\r\end{array}}\right)$.

Adibideak.

1. Zenbat modutan banatu daitezke $8$ euro eta $6$ zentimo $4$ lagunen artean, lagun bakoitzak gutxienez euro bat jaso dezan?

   Euro bana emango diegu lau lagunei, eta gainerakoa honela banatuko dugu:

   $CR(4,4)CR(4,6)=\left({\begin{array}{c}7\\4\end{array}}\right)\left({\begin{array}{c}9\\6\end{array}}\right)=2.940.$

2. Zehaztu ondoko ekuazioaren soluzio osoen kopurua: $x_{1}+x_{2}+x_{3}+x_{4}=8,\quad x_{i}\geq 0,\quad i=1,2,3,4.$

   Soluzio bat, adibidez, hau da: $x_{1}=3,x_{2}=0,xartz=0,x_{4}=5$. Interpretazio bat izan daiteke $8$ objektu berdin banatzen direla $4$ hartzaileren artean (lehenak $x_{1}$ jasotzen ditu, bigarrenak $x_{2}$, ...). Hau da soluzio kopurua:

   $CR(4,8)=\left({\begin{array}{c}11\\8\end{array}}\right)=165.$

Era berean, $x_{1}+\cdots +x_{n}=r,\quad x_{i}\geq 0,\quad i=1,\ldots ,n,$ ekuazioaren soluzio osoen kopurua $r$ objektu berdin $n$ hartzaile artean banatzeko modu kopuruaren berdina da, eta hau da kopuru hori: $CR(n,r).$

Adibideak.

1. Zenbat soluzio oso ez-negatibo daude ondoko inekuaziorako? $x_{1}+x_{2}+x_{3}+x_{4}+x_{5}+x_{6}<10.$

   Soluzio kopurua kalkula dezakegu honako ekuaziorako soluzio kopurua kalkulatuz: $x_{1}+x_{2}+x_{3}+x_{4}+x_{5}+x_{6}=k,\quad 0\leq k\leq 9.$ Hortaz, guztira: $\sum _{k=0}^{9}CR(6,k).$

   Beste modu bat da $x_{1}+x_{2}+x_{3}+x_{4}+x_{5}+x_{6}+x_{7}=10,\quad x_{i}\geq 0,\quad i=1,\ldots ,6,\quad 1\leq x_{7},$ ekuazioaren soluzio osoen kopurua kalkulatzea da.

   $y_{7}=x_{7}-1,\quad y_{7}\geq 0$ aldaketa egiten badugu, honela geratzen zaigu: $x_{1}+x_{2}+x_{3}+x_{4}+x_{5}+x_{6}+y_{7}=9.$ Soluzio osoen kopurua, $x_{i}\geq 0,\quad i=1,\ldots ,6,\quad 0\leq y_{7}$ izanik, hau da: $CR(7,9)=\left({\begin{array}{c}15\\9\end{array}}\right)=5.005.$

2. Zenbat gai daude $(x+y)^{n}$ berreturaren garapen binomialean?

   Gai bakoitzak $\left({\begin{array}{c}n\\k\end{array}}\right)x^{k}y^{n-k}$ forma du. Beraz, gai kopurua $n_{1}+n_{2}=n$ ekuazioaren soluzio osoen kopurua da, $n_{1},n_{2}\geq 0$ izanik. Hau da,

   $CR(2,n)=\left({\begin{array}{c}2+n-1\\n\end{array}}\right)=\left({\begin{array}{c}n+1\\n\end{array}}\right)={\dfrac {(n+1)!}{n!1!}}=n+1.$

3. Zenbat gai daude $(x+y+z+w)^{10}$ berreturaren garapenean?

   Gai bakoitzak ${\dfrac {10!}{n_{1}!n_{2}!n_{3}!n_{4}!}}x^{n_{1}}y^{n_{2}}z^{n_{3}}w^{n_{4}}$ forma du, non $n_{1}+n_{2}+n_{3}+n_{4}=10$ baita, $n_{i}\geq 0$, $i=1,2,3,4$, izanik.

   Gai kopurua = $n_{1}+n_{2}+n_{3}+n_{4}=10$ ekuazioaren soluzio osoen kopurua, $n_{i}\geq 0$, $i=1,2,3,4$ izanik. $CR(4,10)=\left({\begin{array}{c}13\\10\end{array}}\right)=286.$