Variáció (matematika)
A variáció a kombinatorikában használt fogalom. Egy véges halmaz elemeinek egy variációját úgy kapjuk, hogy néhány nem feltétlenül különböző elemet kiválasztunk, és sorrendbe rakjuk őket: egy ilyen elemsorrend képez egy variációt. A variációk fő osztályozása azon alapul, hogy egy-egy elem egynél többször előfordulhat-e, ennek megfelelően van ismétlés nélküli és ismétléses variáció.
Definíció
Legyen H véges halmaz, aminek elemszáma n, k pedig egész szám. Ekkor egy függvényt n elem k-ad osztályú ismétléses variációjának nevezzük. Ha a függvény bijekció,[* 1] akkor a variáció ismétlés nélküli. Utóbbi esetben értelemszerűen .
Ez annyit jelent, hogy ha a halmaz elemiből k darabot sorban egymás után felírunk, akkor variációnak nevezzük az így kapott sorozatot. Ha az elemeket ki is emeljük a halmazból, akkor lesz a variáció ismétlés nélküli.
Példa
- Hat fiú versenyt fut. A lehetséges dobogós helyezések egy-egy (ismétlés nélküli) variációját alkotják a futóknak.
- Öt betűből alkotható hárombetűs "szavak" egy-egy (ismétléses) variációt alkotnak.
- Az előbbi példában öt betűből akár hétbetűs "szavak" is alkothatóak. Ez tulajdonképpen az írások, különösen a hangjelölő írások mögött meghúzódó alapgondolat.
A variációk száma
A variációk száma pusztán a halmaz elemszámának és a sorozat hosszának ismeretében is megadható, ehhez nem szükséges az összes lehetőséget felírni.[* 2]
Ismétléses variációk
Az ismétléses variációk száma n elem és k hossz esetén:
Bizonyítás
Az első helyre n elemből választhatunk. De azt visszatesszük, így újra választhatjuk, tehát a következő tag megint n féle lehet. Ezt k alkalommal tesszük meg, így adódik az állítás.
Példa
Öt betűből hatbetűs szót összesen V65,i=15 625 darabot tudunk alkotni.
Ismétlés nélküli variációk
Ha n elemből k hosszú sorozatokat alkotunk olyan módon, hogy egy elem csak egyszer szerepelhet,[* 3] akkor a lehetőségek száma:
Bizonyítás
Ha egy elemet csak egyszer választhatunk ki, akkor a sorozat nem lehet hosszabb n-nél, ez kézenfekvő.
Az n elemet sorba rakva csak az első k elem sorrendjével foglalkozunk, a többi elemét nem különböztetjük meg. Az összes sorrend tehát az n elem permutációinak a száma, a végső elemek pedig (n-k) számban vannak, az ő sorrendjük, ami a permutációik száma azonos, tehát ezzel le kell osztani.
Ez a hányados biztosan egész szám, mivel n!-nak osztója minden n-nél kisebb szám, így az (n-k)! minden tényezője is.
Másképpen gondolkodva az első helyre n, a második helyre n-1, stb. elemet választhatunk ki, egészen n-k+1-ig. Ha ezt megszorozzuk a maradék n-k elem sorrendjeivel - (n-k)!-sal, akkor az összes elem lehetséges sorrendjeit kapjuk, ami éppen n!. Ez esetben egész számok szorzatáról van szó, így az eredmény biztosan egész szám. QED
Példa
Ha hat fiú versenyez, akkor a lehetséges dobogós helyezések száma V36=6!/3!=720/6=120.
Források
- I. N. Bronstejn, K. A. Szemengyajev, G. Musiol, H. Mühlig. Matematikai kézikönyv. TypoTeX (2000). ISBN 963-9132-59-4
- Simon, Béla. Matek érettségi. Shannon Iroda (1995)