Kezdőlap


Cím:	Az ismétléses variációkról
Szerző(k):	Dr. Jordan Károly
Füzet:	1939/május, 189 - 194. 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.

Tekintettel arra, hogy az ismétléses variációkra vonatkozó képletek kevéssé ismeretesek, talán nem lesz fölösleges velök foglalkozni. Bevezetésül legyen szabad a differencia-számítás alapjairól néhány szót szólni.
Valamely $f (x)$ függvény első differenciája alatt az alábbi kifejezést értjük:

\begin{matrix} Δ f (x) = f (x + 1) - f (x) . \end{matrix}

(1)

A függvény második differenciája pedig az első differenciának differenciája. Vagyis

\begin{matrix} Δ^{2} f (x) = Δ f (x + 1) - Δ f (x) = f (x + 2) - 2 f (x + 1) + f (x) . \end{matrix}

Ezt folytatva, hasonlóképpen megkapjuk a függvény

ν

-edik differenciáját:

\begin{matrix} Δ^{ν} f (x) = f (x + ν) - (\binom{ν}{1}) f (x + ν - 1) + (\binom{ν}{2}) f (x + ν - 2) - ... + {(- 1)}^{ν} (\binom{ν}{ν}) f (x) . \end{matrix}

Ezt rövidebben a következőkép írhatjuk:

\begin{matrix} Δ^{ν} f (x) = Σ {(- 1)}^{i} (\binom{ν}{i}) f (x + ν - i), \end{matrix}

(2)

a baloldali összeg

i = 0, 1, 2, ..., ν

-re értendő.
Megjegyzendő, hogy viszont ha ismerjük az

f (x)

függvény

ν

-edik differenciáját, akkor ezzel meghatároztuk a jobb oldali összeget. Ez az eljárás gyakran hasznosnak bizonyul.
Vannak ugyanis függvények, melyek differenciája igen egyszerűen fejezhető ki így:

\begin{matrix} Δ (\binom{x}{n}) = (\binom{x + 1}{n}) - (\binom{x}{n}) = (\binom{x}{n - 1}) vagy Δ a^{x} = a^{x} (a - 1) . \end{matrix}

(3)

Ebből azonnal következik, hogy

\begin{matrix} Δ^{ν} (\binom{x}{n}) = (\binom{x}{n - ν}) és Δ^{ν} a^{x} = a^{x} {(a - 1)}^{ν} . \end{matrix}

Ennélfogva például a (2) formula következtében

\begin{matrix} (\binom{x}{n - ν}) = Σ {(- 1)}^{i} (\binom{ν}{i}) (\binom{x + ν - i}{n}) . \end{matrix}

A hatványok magasabb differenciái már nem ilyen egyszerűek. Azt azonban azonnal láthatjuk, hogy

x^{n}

első differenciája

n - 1

fokú; tehát

n

-edik differenciája konstans és

n + 1

-edik differenciája nulla.
A hatványok differenciáinak kiszámítására célszerű bevezetni Stirling nyomán az úgynevezett másodfajú Stirling-féle számokat

S_{n}^{ν}

-vel jelölve az

\frac{x^{n}}{ν!}

mennyiség

ν

-edik differenciáját az

x = 0

helyen

\begin{matrix} S_{n}^{ν} = {[Δ^{ν} \frac{x^{n}}{ν!}]}_{x = 0} . \end{matrix}

Ennélfogva ha a (2) képletben

f (x) = x^{n} / ν!

írunk és ha a

ν

-edik differenciában

x

-et nullával tesszük egyenlővé, akkor

\begin{matrix} S_{n}^{ν} = Σ {(- 1)}^{i} (\binom{ν}{i}) \frac{{(ν - i)}^{n}}{ν!} \end{matrix}

(4)

eredményre jutunk.
Ebből azonnal következik, hogy

S_{n}^{0} = 0

és

S_{n}^{1} = 1

; továbbá az előzőkből láthatjuk, hogy

S_{n}^{n + k} = 0

. A másodfajú Stirling-féle számokat a (4) egyenlettel kiszámíthatjuk bármely

ν

és

n

értékre.
Ha azonban e számok táblázatát kívánjuk összeállítani, akkor célszerűbb, ha úgy járunk el, mint a Pascal-féle háromszög számainak kiszámításánál, amidőn tudvalevőleg legjobb, a

(\binom{0}{0}) = 1

és

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

értékekből kiindulva) a számokat az alábbi ,,differencia''-egyenlettel határozni meg:

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

(Ez az egyenlet azonos a (3) egyenletek közül az elsővel.)
A (4) egyenletből kiindulva kimutatható, hogy

S_{n}^{ν}

eleget tesz a következő differencia-egyenletnek:

\begin{matrix} S_{n + 1}^{ν} = S_{n}^{ν - 1} + ν S_{n}^{ν} \end{matrix}

(5)

S_{1}^{1} = 1

és

S_{1}^{0} = 0

-ból kiindulva, ez megadja lépésről-lépésre a többi másodfajú Stirling-féle számot.
Az (5) egyenletből következik,

S_{n}^{n + k} = 0

tekintetbevételével, hogy

S_{n}^{n} = 1

. Az egyenlet az alábbi táblázatra vezet:

\begin{matrix} n / ν & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 1 & 1 \\ 2 & 1 & 1 \\ 3 & 1 & 3 & 1 \\ 4 & 1 & 7 & 6 & 1 \\ 5 & 1 & 15 & 25 & 10 & 1 \\ 6 & 1 & 31 & 90 & 65 & 15 & 1 \\ 7 & 1 & 63 & 301 & 350 & 140 & 21 & 1 \\ 8 & 1 & 127 & 966 & 1701 & 1050 & 266 & 28 \end{matrix}

A Stirling-féle számok rendkívül hasznosak és a legkülönbözőbb problémák esetén felhasználhatók.
Ezek után áttérhetünk az ismétléses variáció tanulmányozására. Ismeretes, hogy

m

-elem ismétléses

n

-edrendű variációinak száma

\begin{matrix} W (m, n) = m^{n} . \end{matrix}

Jelöljük a variációk közül azokat, melyekben csak egyféle elem szerepel,

\begin{matrix} W (m, n, 1) -gyel. \\ Evidens, hogy & W (m, n, 1) = m . \end{matrix}

m

elem azon

n

-edrendű ismétléses variációinak száma, melyekben 2 különböző elem szerepel

\begin{matrix} W (m, n, 2) = (\binom{m}{2}) (2 n - 2) . \end{matrix}

Ugyanis

m

elemből két elemet

(\binom{m}{2})

-félekép választhatunk ki; e két elem

n

-ed rendű ismétléses variációinak száma

2^{n}

; de ezek között két oly variáció van, melyek csak egy elemet tartalmaznak, vagyis minden elempár

2^{n} - 2

számú

n

-edrendű oly ismétléses variációt ad, melyekben mind a két elem szerepel.
Azoknak az

n

-edrendű variációknak a száma, melyekben 3 különböző elem van

\begin{matrix} W (m, n, 3) = (\binom{m}{3}) [3^{n} - (\binom{3}{2}) W (3, n, 2) - (\binom{3}{1}) W (3, n, 1)] . \end{matrix}

Tényleg

(\binom{m}{3})

félekép választhatunk ki

m

elemből hármat; három elem

n

-ed rendű ismétléses variációinak száma

3^{n}

; ezekből azonban le kell vonni elsősorban azokat, melyekben csak két elem van; miután három elemből kettőt

(\binom{3}{2})

-félekép lehet kiválasztani és e két elem oly

n

-ed rendű variációinak száma, melyekben mind a kettő szerepel,

2^{n} - 2

. Le kell vonni továbbá azokat is, melyekben csak egy elem szerepel.
Az előző egyenletet még úgy is írhatjuk:

\begin{matrix} W (m, n, 3) = (\binom{m}{3}) [3^{n} - (\binom{3}{1}) 2^{n} + (\binom{3}{2}) 1^{n}] . \end{matrix}

Ezt folytatva, megkaphatjuk

m

elem azon

n

-ed rendű ismétléses variációinak számát, melyekben

ν

különféle elem szerepel:

\begin{matrix} W (m, n, ν) = (\binom{m}{ν}) Σ (- 1)^{i} (\binom{ν}{i}) {(ν - i)}^{n} . \end{matrix}

ahol

i = 0, 1, 2, ..., ν

.
A (4) képletből következik, hogy a jobb oldali összeg

ν! S_{n}^{ν}

-nel egyenlő, úgy hogy

\begin{matrix} W (m, a, ν) = (\binom{m}{ν}) ν! S_{n}^{ν} = m (m - 1) ... (m - ν + 1) S_{n}^{ν}; \end{matrix}

(6)

ez adja tehát

m

elem azon

n

-edrendű variációinak számát, melyekben

ν

különböző elem szerepel.

Megjegyzések. 1. Miután

m

elem

n

-edrendű ismétléses variációi vagy egy, vagy kettő, vagy három, és így tovább vagy

m

elemet tartalmaznak, következőleg

\begin{matrix} W (m, n) = Σ W (m, n, ν) . \end{matrix}

Vagyis

\begin{matrix} m^{n} = Σ m (m - 1) (m - 2) ... (m - ν + 1) S_{n}^{ν}, \end{matrix}

a differencia-számítás ismert kifejtésére jutunk. Ezen összegben

ν = 1, 2, ..., m .

2. Az előzőkben láttuk, hogy két elem oly

n

-edrendű variációinak száma, melyekben mind a két elem szerepel:

2^{n} - 2

; másrészt a (6) képletből folyik, hogy

\begin{matrix} W (2, n, 2) = 2 S_{n}^{2}, \end{matrix}

ami az

\begin{matrix} S_{n}^{2} = 2^{n - 1} - 1 \end{matrix}

képletet adja.

Nevezetes különleges esetek. 1.

m

elem azon

n

-edrendű ismétléses variációinak számát,

(n \geq m)

, melyek valamennyi elemet tartalmazzák, megkapjuk (6)-ból, ha abban

ν = m

-et írunk.

\begin{matrix} W (m, n, m) = m! S_{n}^{m} . \end{matrix}

Ha ezenkívül még

n = m

akkor

W (m, m, m) = m! S_{m}^{m} = m!

ami különben evidens, mert ez esetben a kérdéses variációkat az

m

elem permutációi alkotják.
2.

m

elem oly

n

-edrendű ismétléses variációinak számát, melyekben

m - 1

különböző elem szerepel, (6) adja, ha

ν = m - 1

-et írunk:

\begin{matrix} W (m, n, m - 1) = m! S_{n}^{m - 1} . \end{matrix}

Ha ezenkívül még

n = m

, akkor

\begin{matrix} W (m, m, m - 1) = m! S_{m}^{m - 1} (\binom{m}{2}) . \end{matrix}

Kimutatható ugyanis, hogy

S_{m}^{m - 1} = (\binom{m}{2})

. Ez a táblázatban ellenőrizhető.
3.

m

elem oly

n

-edrendű ismétléses variációinak számát

(m \geq n)

, melyekben csupa különböző elem szerepel, (6)-ból kapjuk

ν = n

helyettesítéssel:

\begin{matrix} W (m, n, n) = m (m - 1) ... (m - n + 1) S_{n}^{n} = m (m - 1) (m - 2) ... (m - n + 1) . \end{matrix}

Valószínűségszámítási példák. Egy urnában van

m

szám, még pedig

1, 2, ..., m

;

n

-szer húzunk oly formán, hogy minden húzás után a kihúzott számot visszatesszük az urnába. Határozzuk meg annak a valószínűségét, hogy a kihúzott

n

szám között

ν

különböző szám legyen. Az összes lehető esetek száma egyenlő

m

elem

n

-edrendű ismétléses variációinak számával, vagyis

m^{n}

-nel. A kedvező esetek száma pedig

W (m, n, ν)

úgy, hogy a keresett valószínűség:

\begin{matrix} P = \frac{m (m - 1) ... (m - ν + 1)}{m^{n}} S_{n}^{ν} . \end{matrix}

(7)

Annak a valószínűsége, hogy a kihúzott

n

szám között valamennyi

m

szám jelen legyen,

\begin{matrix} P = \frac{m! S_{n}^{m}}{m^{m}} . \end{matrix}

(8)

Továbbá annak a valószínűsége, hogy

m

kihúzott szám között az urnában levő

m

számból csak egy hiányozzék

\begin{matrix} P = \frac{m! (\binom{m}{2})}{m^{m}} . \end{matrix}

(9)

Ugyanis

\begin{matrix} S_{m}^{m - 1} = (\binom{m}{2}) . \end{matrix}

Végre annak a valószínűsége, hogy a kihúzott számok mind különbözők legyenek:

\begin{matrix} P = \frac{m (m - 1) (m - 2) ... (m - n + 1)}{m^{n}} \end{matrix}

(10)

Ugyanis

\begin{matrix} S_{n}^{n} = 1. \end{matrix}

Példák. 1. Valamely csokoládégyár kis csokoládés csomagokat hoz forgalomba, melyek mindegyikében van egy kép. Összesen

m

-féle képet raknak a csomagokba; minden képből ugyanannyit használva fel; a csomagokat jól összekeverik. A gyártás tovább folyik. A gyár díjat tűz ki annak, aki valamennyi képet megszerzi. Ha valaki

n

csomagot vesz, mi a valószínűsége annak, hogy a díjat megnyerje? E valószínűséget a (8) képlet adja. Ha pl.

m = 6

féle kép van összesen és ha 12 csomagot vesszünk, akkor miután

S_{12}^{6} = 1323652

, tehát

P = 0, 43782

.
2.

n

kockával dobunk; annak a valószínűségét, hogy az

1, 2, 3, 4, 5, 6

számokat mind megkapjuk, ugyancsak a (8) képlet adja, ha abban

m = 6

írunk. Ha például

n = 7

-szer dobunk, akkor miután

S_{7}^{6} = 21

, tehát

P = 35 / 648

.
Továbbá annak a valószínűsége, hogy 6 kockával dobva a számok közül csak egy hiányozzék, (9) értelmében

\begin{matrix} P = \frac{6! (\binom{6}{2})}{6^{6}} = \frac{50}{216} . \end{matrix}

3. Egy csomag francia kártyából (52 lap) ötször húzunk visszatevéssel; annak a valószínűsége, hogy színre való tekintet nélkül mind az öt különböző legyen, (10)-ből folyik, ha benne

m = 13

és

n = 5

írunk. Tehát

\begin{matrix} P = \frac{13 \cdot 12 \cdot 11 \cdot 10 \cdot 9}{13^{5}} = 0, 41595. \end{matrix}

Megjegyzés. Valószínűségi meggondolások gyakran érdekes eredményre vezetnek. Például könnyen beláthatjuk, hogy az előző urna problémában minél többször húzunk, annál nagyobb lesz a valószínűsége annak, hogy valamennyi számot megkapjuk; úgy hogy

n

növelésével tetszőlegesen megközelíthetjük a bizonyosságot. A valószínűségszámításban azonban a bizonyosság

P = 1

-nek felel meg. Következőleg

\begin{matrix} {lim}_{n = \infty}^{} \frac{m! S_{n}^{m}}{m^{n}} = 1 vagyis {lim}_{n = \infty}^{} \frac{S_{n}^{m}}{m^{n}} = \frac{1}{m!}, \end{matrix}

(11)

ami, ha

n

nagy

m

-hez képest,

S_{n}^{m}

megközelítő (aszimptotikus) értékét adja:

\begin{matrix} S_{n}^{m} \sim \frac{m^{n}}{m!} \end{matrix}

(12)

m = 1

, akkor a (12) képlet pontosan adja

S_{n}^{1} = 1

értékét. Ha

m = 2

, akkor a képlet

S_{n}^{2} = 2^{n - 1} - 1

helyett

S_{n}^{2} \sim 2^{n - 1}

értéket ad.
A (11) határértéket a (4) formulából kiindulva közvetlenül is bebizonyíthatjuk.

Dr. Jordan Károly