Kezdőlap


Cím:	Variáczió, permutáczió, kombináczió 1.
Szerző(k):	Antal Márkus
Füzet:	1901/október, 31 - 34. oldal	PDF \| MathML
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 $a b c$ betűivel jelölünk.
Ha kiválasztunk $k (k ≦ n)$ 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.

\begin{matrix} 12, & 13, & 14, & ... \\ 21, & 23, & 24, & ... \end{matrix}

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.

\begin{matrix} 123, 132, 213, 231, 312, 321, \end{matrix}

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

V_{k} (n)

-nel, a

k

-ad osztályú kombinácziók számát

C_{k} (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

\begin{matrix} V_{1} = n . \end{matrix}

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

V_{k - 1} (n)

-ből új csoportot kapunk.
Már most kimutathatjuk, hogy az

(n - k + 1) V_{k - 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

V_{k - 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

\begin{matrix} V_{k} (n) = (n - k + 1) \cdot V_{k - 1} (n) \end{matrix}

(1)

éppígy

\begin{matrix} V_{k - 1} (n) = (n - k + 2) \cdot V_{k - 2} (n) \end{matrix}

\begin{matrix} ... \end{matrix}

\begin{matrix} V_{3} (n) = (n - 2) \cdot V_{2} (n) \end{matrix}

\begin{matrix} V_{2} (n) = (n - 1) \cdot V_{1} (n) \end{matrix}

\begin{matrix} V_{1} (n) = n . \end{matrix}

Ezen egyenleteket összeszorozva, kapjuk, hogy

\begin{matrix} V_{k} (n) = (n - k + 1) (n - k + 2) ... (n - 1) n \end{matrix}

(2)

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

\begin{matrix} P (n) = V_{n} (n), \end{matrix}

azért

\begin{matrix} P (n) = 1 \cdot 2 \cdot 3 ... n, \end{matrix}

a mit még így is szoktunk írni:

\begin{matrix} P (n) = 1 \cdot 2 \cdot 3 ... n = n! \end{matrix}

(3)

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

C_{k} (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:

\begin{matrix} V_{k} (n) = C_{k} (n) \cdot P (k), \end{matrix}

(4)

miből

\begin{matrix} C_{k} (n) = \frac{V_{k} (n)}{P (k)} = \frac{n (n - 1) ... (n - k + 1)}{1 \cdot 2 \cdot 3 ... k} = (\binom{n}{k}) . \end{matrix}

(5)

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

C_{k} (n)

-et más alakban is előállíthatjuk, ha az

(5)

számlálóját és nevezőjét

1 \cdot 2 \cdot 3 ... (n - k) = (n - k)!

-sal szorozzuk.

\begin{matrix} C_{k} (n) = \frac{n (n - 1) ... (n - k + 1) (n - k) ... 3 \cdot 2 \cdot 1}{1 \cdot 2 \cdot 3 ... 1 \cdot 2 \cdot 3 ... (n - k)} = \frac{n!}{k! (n - k)!} \end{matrix}

(6)

ámde éppígy

\begin{matrix} C_{n - k} (n) = \frac{n!}{(n - k) k!} \end{matrix}

s így

\begin{matrix} C_{k} (n) = C_{n - k} (n) vagy (\binom{n}{k}) = (\binom{n}{n - k}) . \end{matrix}

(7)

Azt is könnyen kimulathatjuk; hogy:

\begin{matrix} C_{k} (n) + C_{k - 1} (n) = C_{k} (n + 1) . \end{matrix}

(8)

Ugyanis:

\begin{matrix} C_{k} (n) + C_{k - 1} (n) = \frac{n!}{k! (n - k)!} + \frac{n!}{(k - 1)! (n - k + 1)!} = \frac{n!}{(k - 1)! (n - k)!} [\frac{1}{k} + \frac{1}{n - k + 1}] = \end{matrix}

\begin{matrix} = \frac{n!}{(k - 1)! (n - k)!} \cdot \frac{n + 1}{k (n - k + 1)} = \frac{(n + 1)!}{k! (n - k + 1)!} = C_{k} (n + 1) . \end{matrix}

Tehát

\begin{matrix} (\binom{n}{k}) + (\binom{n}{k - 1}) = (\binom{n + 1}{k}) . \end{matrix}

(9)

Az eddigiek szerint

C_{0} (n) = (\binom{n}{0})

-nek nincs értelme. Ha azonban a

(7)

érvényességét minden esetben fenn akarjuk tartani, akkor

(\binom{n}{0})

-t úgy értelmezzük, hogy

\begin{matrix} (\binom{n}{0}) = (\binom{n}{n}) = 1. \end{matrix}

V_{0} (n)

-t úgy értelmezzük, hogy

(1)

k = 0

esetében is érvényes legyen, vagyis hogy:

\begin{matrix} V_{1} (n) = n V_{0} (n) = n, \end{matrix}

miért is tehát akkor

\begin{matrix} V_{0} (n) = 1. \end{matrix}

Ha pedig a

(3

) érvényességét is biztosítani akarjuk a

k = 0

esetére is, akkor:

\begin{matrix} V_{0} (n) = C_{0} (n) \cdot P (0), \end{matrix}

miből

\begin{matrix} P (0) = \frac{V_{0} (n)}{C_{0} (n)} = 1, \end{matrix}

tehát

\begin{matrix} 0! = 1. \end{matrix}