Aldakuntza (konbinatoria)

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].

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)={\dfrac {n!}{(n-k)!}}

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

A_{3}^{2}={\dfrac {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:

{n \choose k}={\dfrac {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:

EA_{n}^{k}=n^{k}

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

EA_{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

Erreferentziak

↑ (Ingelesez) Straubing, Howard. (1983-01-01). «A combinatorial proof of the Cayley-Hamilton theorem» Discrete Mathematics 43 (2): 273–279. doi:10.1016/0012-365X(83)90164-4. ISSN 0012-365X. (Noiz kontsultatua: 2022-12-12).
↑ (Ingelesez) Ku, C. Y.; Leader, I.. (2006-01-28). «An Erdős–Ko–Rado theorem for partial permutations» Discrete Mathematics 306 (1): 74–86. doi:10.1016/j.disc.2005.11.007. ISSN 0012-365X. (Noiz kontsultatua: 2022-12-12).