Konbinatoria
Konbinatoria: elkarketak
Multzo bateko elementuak (m) hiru modutan elkartu eta aukeratu daitezke:
- Ezberdintzat joko da edozein azpitalde, baldin eta edozein desberdintasun badauka kopuruari (edukia) edo ordenari dagokionez. Mota honetako elkarketei aldakuntzak deitzen zaie.
- Azpimultzoak aintzat hartuko dira soilik m elementuak badituzte, baina berauek ordena desberdinean kokaturik (permutazioak).
- Soilik hartuko dira aintzat elementu desberdinen bat duten azpimultzoak, elementuen ordena edozein delarik ere (konbinazioak).
Sortutako azpimultzo guztietan elementuak behin bakarrik agertzen badira, azpimultzoei arruntak edo errepikatu gabeak esaten zaie; azpimultzo bakoitzean elementu bat behin baino gehiagotan ager badaiteke, ordea, errepikatuzko azpimultzoak esaten zaie, aldakuntzak, permutazioak edo konbinazioak badira ere.
Aldakuntzak
Multzo bateko n elementuak r-ren multzoka biltzen badira (r £ n izanik) aldakuntza arruntak (edo errepikatu gabeak) deituko zaie r elementurekin osatzen diren multzo guztiei, baldin eta berauek desberdinak badira, bai beren elementuengatik, bai elementuen kokapenagatik.
Multzo bateko n elementuak r-naka antolatuz gero, ondoko formularen bidez jakin ahalko da zenbat aldakuntza arrunt desberdin osa daitezkeen:
Alboko zuhaitz-diagramak erakusten du zenbat diren osatu daitezkeen aldakuntza arruntak (errepikatu gabeak), elementuak (A, B, C, D) binaka hartuz gero.
Permutazioak
n = r betetzen denean, n elementu r -naka hartzean osatutako aldakuntzei permutazioak esaten zaie. Elementuen ordena da, beraz, azpimultzo bakoitzaren bereizgarri bakarra, haietan guztietan baitaude multzoko elementu guztiak.
Alboko zuhaitz-diagramak erakusten du zenbat permutazio arrunt (errepikatu gabeak) osa daitezkeen elementuekin (A, B, C).
n elementurekin osatutako permutazio arruntak jakiteko:
Pn = n (n - 1) (n - 2) ... 1 = n!
Konbinazioak
n elementuen multzo batetik r -ren multzoak hartzerakoan, konbinazio izeneko elkarketa konbinatorioak eratuko dira; horrela, azpitalde bakoitza besteetatik desberdina izango da, baldin eta -eta soilik baldin eta- gutxienez elementu bat desberdin badu, elementuen ordena edozein delarik ere.
Multzo bateko n elementuak r -naka antolatuz gero, ondoko formularen bidez jakin ahalko da zenbat konbinazio arrunt desberdin (errepikatu gabeak) osa daitezkeen:
adierazpena «n gain r» irakurtzen da, eta konbinazio-zenbakia deitzen zaio.
n elementuak r -naka antolatuz gero zenbat konbinazio eratu daitekeen kalkulatzeko, zatiketa egingo da, zatikizuna modu berean eratutako aldakuntza-kopurua izanik eta zatitzailea azpitalde bakoitzeko r elementuekin osatutako permutazioak izanik:
Zuhaitz-diagrama honek erakusten du zenbat konbinazio arrunt (errepikatu gabeak) osa daitezkeen, elementuak (A, B, C, D) binaka harturik.
Zenbaki baten faktoriala
n zenbaki oso eta positibo baten faktorialaren ikurra n! da. Berez, ondoz ondoko faktoreen biderkadura da, 1etik hasita eta n zenbakiarekin bukatuta, biak barne:
n! = n × (n - 1) x (n - 2) × …× 1
Kasu berezi gisa, 0! = 1 dela definitu da.
Errepikatuzko aldakuntzak
Onartzen bada n elementu r -naka hartuz osatutako aldakuntzetan elementu errepikatuak egotea, errepikatuzko aldakuntzez ari gara. Adibidez, {A, B, C} multzoan ondoko errepikatuzko aldakuntzak onar litezke: AAA, AAB, BAA, AAC, ABB, etab. Ondoko formularekin kalkula daiteke zenbat errepikatuzko aldakuntza osa daitezkeen multzo bateko n elementuak r -naka hartuz gero:
VRn,r = nr.
Errepikatuzko permutazioak
Multzo bateko n elementuekin osa daitezkeen errepikatuzko permutazioak kalkulatzeko (hau da, elementu horien ordena bereizgarritzat duten azpimultzoak), hurrengo formulaz baliatuko gara. Horren arabera, lehenengo elementua k1 aldiz errepikatuko da, bigarrena k2 aldiz, hirugarrena k3 aldiz..., eta enegarren elementua kn aldiz:
Errepikatuzko konbinazioak
Elementuak errepikatzea onartzen bada konbinazioak osatzean, errepikatuzko konbinazioez ari gara, eta dagokion formula hauxe izango da:
