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ó szerkesztés

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 szerkesztés

  • 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 szerkesztés

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 szerkesztés

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

 

Bizonyítás szerkeszté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 szerkesztés

Ö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 szerkesztés

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 szerkeszté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 szerkesztés

Ha hat fiú versenyez, akkor a lehetséges dobogós helyezések száma V36=6!/3!=720/6=120.

Források szerkesztés

  • 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) 

Megjegyzések szerkesztés

  1. Azaz kölcsönösen egyértelmű hozzárendelés.
  2. Előfordulhat, hogy ez nem is lehetséges.
  3. Azaz kivesszük és nem tesszük vissza a halmazba

Kapcsolódó szócikkek szerkesztés