Aldakuntza (konbinatoria)

Txantiloi:HezkuntzaPrograma Konbinatorian, aldakuntzak n elementu ezberdineko multzo batetik k elementu aukeratzeko erak dira, aukeratutako elementuen ordena kontuan hartuz. Aukeraketan elementuak ezin badira errepikatu, aldakuntza arruntak sortzen dira; aukeratutako elementuak errepikatzen ahal badira, errepikapenezko aldakuntzak edo errepikatuzko aldakuntzak izango dira. Adibidez, (1,2,3) elementuen binakako aldakuntza arruntak (12,21,13,31,23,32) dira eta (12,21,13,31,23,32,11,22,33) errepikapenezkoak. Ekibalentziaz, funtzio partzial bat hedatu daiteke permutazio bat izateko.

1-2-3-4-5 elementuak aukeran, 3 elementuko aldakuntza arruntak. 5 zifra horietatik 3 elementuak aukeratu ondoren, ordena posible guztiak zehaztu behar dira, aldakuntza guztien zerrenda osatzeko.

Aldakuntzen kopurua

Aldakuntza arruntak

n elementuko multzo batean, k-nakako aldakuntza arrunten kopurua honela kalkulatzen da:

$A_n^k=n(n-1)(n-2)...(n-k+1)=\frac{n!}{(n-k)!}$

Adibidez, 3 elementuko multzo batetik 2 elementuko aldakuntzak osatzeko era kopurua hau izango da:

$A_3^2=\frac{3!}{(3-2)!}=6$

Konbinatorian ohizkoa den biderkaketa erregela erabiliz, aise ulertzen da formula: aldakuntzaren lehenengo elementua n eratara aukera daiteke, bigarrena (n-1) eratara (elementuak errepika ezin daitezkeenez, lehenengoa baztertuz), ...; eta horrela aldakuntza osatzeko guztizko era kopurua :$n\cdot (n-1)\cdot (n-2)\cdots (n-k+1)$ izango da.

Aldakuntza arruntek honako erlazio hau dute koefiziente binomialekin:

$(\genfrac{}{}{0ex}{}{n}{k})=\frac{A_n^k}{k!}$

Izan ere, aldakuntza arruntetan ordena kontuan hartzen denez, ordena kontuan hartzen ez duten koefiziente binomial edo konbinazioen kopurua lortzeko k elementuak ordenatzeko era kopuruaz, k!-z alegia, zatitu behar da.

Errepikapenezko aldakuntzak

n elementuko multzo batean, k-nakako errepikatuzko aldakuntzen kopurua honela kalkulatzen da:

$E{A}_n^k=n^k$

Arestiko adibidean, 3 elementuko multzotik 2 elementuko errepikatuzko aldakuntzen kopurua, multzo ordenatuak elementuak errepikatu daitezkeela alegia, hau da:

$E{A}_3^2=3^2=9$.

Formula erraz ulertzen da, errepikatuzko aldakuntzak diren k-koteetan, leku bakoitzean n elementu baitaude aukeran eta horrela, hurrenez hurren biderkatuz $n\cdot n\cdots n=n^k$ k-kote izango dira guztira.

Ikus, gainera

• Permutazio