Cím: Variáczió, permutáczió, kombináczió 1.
Szerző(k):  Antal Márkus 
Füzet: 1901/október, 31 - 34. oldal  PDF file
Témakör(ök): Szakmai cikkek

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Adva van n különböző elem, melyeket rendre 1,2,3,...(n-1),n-nel vagy az abc betűivel jelölünk.
Ha kiválasztunk k(kn) elemet és ezeket egymás mellé írjuk, akkor az n adott elem egy k-ad osztályú csoportját kapjuk. Ha az egyes csoportokat nemcsak a bennük előforduló elemek, hanem azok elhelyezése szerint is megkülönböztetjük, akkor a csoport az n adott elem k-ad osztályú variáczióját képezi, melyet k=n esetében permutáczió-csoportnak nevezünk.

  12,13,14,...  21,23,24,...   
tehát különböző variáczió-csoportok.
Ha ellenben az elemek sorrendjére tekintettel nem vagyunk, akkor a kérdéses csoport az n adott elem k-ad osztályú kombinácziója.
123,132,213,231,312,321,

tehát identikus kombináczió-csoportok, mert ugyanazon elemeket -különböző sorrendben is- tartalmazzák.
Jelöljük az n adott elemből alakítható k-ad osztályú variácziók számát Vk(n)-nel, a k-ad osztályú kombinácziók számát Ck(n)-nel és az n elemből alakítható permutácziók számát P(n)-nel. A következőkben czélunk oda irányul, hogy ezeket kiszámíthassuk.
Az n adott elemből alakítható 1-ső osztályú variácziók:1,2,3,...n, vagyis
V1=n.
A másodosztályú variációkat az első osztályúból alakíthatjuk; általában a k-ad osztályút a (k-1)-ed osztályúból, még pedig a következőképpen.
Képzeljük el, hogy az n elemből alakítható (k-1)-ed osztályú variácziók már mind fel vannak írva és jelöljük ezen variácziók egyikét x-szel, akkor még n-(k-1)=n-k+1 oly elem van, a melyet az x nem tartalmaz. Ha ezen n-k+1 elem bármelyikét x-hez függesztjük, akkor csupa k-ad osztályú csoportot kapunk. Ily módon x-ből n-k+1, tehát Vk-1(n)-ből új csoportot kapunk.
Már most kimutathatjuk, hogy az (n-k+1)Vk-1(n) csoport mind különbözik egymástól. Ha ugyanis két k-ad osztályú csoportot ugyanazon x-ből képeztünk, akkor az utolsó elemben különböznek, ha pedig különböző (k-1)-ed osztályú variációból alakítottuk őket, akkor eo ipso különböznek egymástól.
Másodszor kimutatjuk, hogy az összes k-ad osztályú variácziót felírtuk ily módon. Ha ugyanis y egy tetszésszerinti k-ad osztályú variáczió, akkor utolsó elemét elhagyva egy (k-1)-ed osztályú variácziót kapunk, a mely a Vk-1(n)-ben minden esetre előfordul; legyen ez pl. a. Ámde a-hoz az összes benne elő nem forduló n-k+1 elemet hozzákapcsoltuk, tehát y-t csakugyan képeztük. Tehát
Vk(n)=(n-k+1)Vk-1(n)(1)
éppígy
Vk-1(n)=(n-k+2)Vk-2(n)
...
V3(n)=(n-2)V2(n)
V2(n)=(n-1)V1(n)
V1(n)=n.
Ezen egyenleteket összeszorozva, kapjuk, hogy
Vk(n)=(n-k+1)(n-k+2)...(n-1)n(2)

Az n elemből alakítható k-ad osztályú variácziók számát tehát az n-től (n-k+1)-ig terjedő egész számok szorzata adja.
Minthogy
P(n)=Vn(n),
azért
P(n)=123...n,
a mit még így is szoktunk írni:
P(n)=123...n=n!(3)
Az n elemből alakítható permutácziók számát tehát megkapjuk, ha a természetes számsor számait 1-től n-ig egymással megszorozzuk.
Végül számítsuk ki Ck(n)-et. Képzeljük el e végből, hogy az összes k-ad osztályú kombinációkat felírtuk; akkor minden egyes kombináczió- csoportból az elemek permutálása által más és más, vagyis összesen P(k) variácziót nyerünk. Ezen variácziók között nincsenek identikusak. Ha ugyanis x és y két tetszőleges variáczió, akkor ezek vagy egy és ugyanazon kombináczió-csoport permutácziójából keletkeztek és ekkor az elemek nem lehetnek ugyanazon sorrendben, tehát a csoportok különbözők; vagy különböző kombináczió-csoportokból származtak, s ekkor különböző elemeket is tartalmaznak, tehát szintén különbözők.
Másodszor ilyen módon minden képzelhető variáczió-csoportot előállítottunk, a mi nem is szorul bizonyításra.
Fennáll tehát ama összefüggés, hogy:
Vk(n)=Ck(n)P(k),(4)
miből
Ck(n)=Vk(n)P(k)=n(n-1)...(n-k+1)123...k=(nk).(5)
Az n elemből alkotható k-ad osztályú kombinácziók száma oly tört alakjában írható fel, melynek számlálója k darab n-től lefelé menő egymásután következő szám szorzatából, nevezője pedig ugyancsak k darab 1-től felfelé menő szám szorzatából áll.
A Ck(n)-et más alakban is előállíthatjuk, ha az (5) számlálóját és nevezőjét 123...(n-k)=(n-k)!-sal szorozzuk.
Ck(n)=n(n-1)...(n-k+1)(n-k)...321123...123...(n-k)=n!k!(n-k)!(6)
ámde éppígy
Cn-k(n)=n!(n-k)k!
s így
Ck(n)=Cn-k(n)vagy(nk)=(nn-k).(7)
Azt is könnyen kimulathatjuk; hogy:
Ck(n)+Ck-1(n)=Ck(n+1).(8)
Ugyanis:
Ck(n)+Ck-1(n)=n!k!(n-k)!+n!(k-1)!(n-k+1)!=n!(k-1)!(n-k)![1k+1n-k+1]=
=n!(k-1)!(n-k)!n+1k(n-k+1)=(n+1)!k!(n-k+1)!=Ck(n+1).
Tehát
(nk)+(nk-1)=(n+1k).(9)
Az eddigiek szerint C0(n)=(n0)-nek nincs értelme. Ha azonban a (7) érvényességét minden esetben fenn akarjuk tartani, akkor (n0)-t úgy értelmezzük, hogy
(n0)=(nn)=1.
A V0(n)-t úgy értelmezzük, hogy (1) a k=0 esetében is érvényes legyen, vagyis hogy:
V1(n)=nV0(n)=n,
miért is tehát akkor
V0(n)=1.
Ha pedig a (3) érvényességét is biztosítani akarjuk a k=0 esetére is, akkor:
V0(n)=C0(n)P(0),
miből
P(0)=V0(n)C0(n)=1,
tehát
0!=1.