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 $V_n^k:k\to H$ függvényt n elem k-ad osztályú ismétléses variációjának nevezzük. Ha a függvény bijekció,Sablon:Jegyzet* akkor a variáció ismétlés nélküli. Utóbbi esetben értelemszerűen $k\le n$.

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.Sablon:Jegyzet*

Ismétléses variációk

Az ismétléses variációk száma n elem és k hossz esetén:

$V_{n,i}^k=n^k$

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 V⁶_5,i=Sablon:Szám 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,Sablon:Jegyzet* akkor a lehetőségek száma:

$V_n^k=\frac{n!}{(n-k)!}.$

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 V³₆=6!/3!=720/6=120.

Források

• Sablon:Cite book
• Sablon:Cite book

Kapcsolódó szócikkek

• Kombináció
• Permutáció