Eseményalgebra, kombinatorika
Eseményalgebra Definíció. Véletlen kísérletnek nevezünk minden olyan megfigyelést, melynek több kimenetele lehetséges, és a véletlentől függ, (azaz az általunk figyelembevett feltételek nem határozzák meg egyértelműen), hogy a lehetséges kimenetelek közül melyik következik be. Definíció. A kísérlet lehetséges kimeneteleit elemi eseményeknek, az elemi események halmazát pedig eseménytérnek nevezzük. Az eseményteret Ω-val, az elemi eseményeket pedig ω-val jelöljük. Példa:
Kockadobás két különböző kockával Ω = {(i, j) : 1 ≤ i, j ≤ 6}
Eseményalgebra Definíció. A véletlen esemény az Ω eseménytér egy részhalmaza. Egy esemény akkor következik be, ha a kísérlet során adódó elemi esemény a szóban forgó részhalmaz eleme. Példa: Két különböző kockával történő kockadobás esetén legyen az A esemény az, hogy a dobásösszeg nem nagyobb, mint 6. Ekkor A = {(i, j): i + j ≤ 6}. Az eseményeket általában A, B, C,... betűkkel fogjuk jelölni. Definíció. Biztos esemény az az esemény, amely a kísérlet kimenetelétől függetlenül mindig bekövetkezik. Nyilván a biztos esemény megfelel az Ω halmaznak, ezért a biztos eseményt is szokás Ω-val jelölni. Lehetetlen esemény (∅) az az esemény, amely a kísérlet kimenetelétől függetlenül sohasem következik be. Az A esemény ellentett eseménye (vagy komplementer eseménye) az az esemény, amely akkor és csak akkor következik be, ha A nem.
Műveletek események között Definíció. Az A és B események összege az A + B-vel jelölt esemény, amely akkor és csak akkor következik be, ha A és B közül legalább az egyik bekövetkezik. Az A és B események szorzata az A·B-vel jelölt esemény, amely akkor és csak akkor következik be, ha A is és B is bekövetkezik. Az A és B események különbsége az A - B-vel jelölt esemény, amely akkor és csak akkor következik be ha A bekövetkezik, de B nem. Az A és B események egymást kizárják, ha A·B = ∅. Az
A1 , A2 , ..., An , ... események teljes eseményrendszert alkotnak, ha Ai ≠ ∅ (i = 1, 2,..., n,...) és 1./
Ai ⋅ A j = ∅, ha i ≠ j, továbbá ∞
2./
∑A
k
k= 1
= Ω
Kombinatorika A kombinatorika a véges halmazok elméletével foglalkozik. Az általunk vizsgált problémák két fő területre oszthatók: 1./ 2./
különböző sorrendben való elhelyezés, különböző módon való kiválogatás.
Az első kérdéskör a permutációk, a második a kombinációk, a kettő együtt pedig a variációk témaköréhez vezet.
Permutációk Ismétlés nélküli permutációk Definíció. Adott n db különböző elem. Ezen elemek egy lehetséges sorrendjét az n elem egy permutációjánaknak nevezzük. Tétel. n különböző elem összes lehetséges permutációinak száma:
Pn = n!
Példa: 1./ A 0, 1, 2, 3, 4, 5 számjegyek felhasználásával hány olyan hatjegyű számot írhatunk fel, amelyben minden számjegy csak egyszer fordul első? 2./ Tíz regény közül az egyik háromkötetes, a többi egykötetes. Hányféleképpen tehetjük fel a könyveket a könyvespolcra, ha a háromkötetes regény könyveinek egymás mellett kell lenniük? 3./ 10 házaspárt szeretnénk leültetni egy egyenes asztal mellé. Hányféle sorrend lehetséges, ha a házaspárok egymás mellett ülnek?
Ismétléses permutációk Definíció. Az olyan permutációt, amelyben a permutálandó elemek között egyenlők is vannak ismétléses permutációknak nevezzük. Tétel. Ha n elemből k egyenlő, a többi pedig ezektől és egymástól is különböző, akkor ezen elemek ismétléses permutációinak a száma:
n! P = k! k n
Általánosan: Ha n elemből k egyenlő, majd újabb l egyenlő, melyek az előzőektől különböznek, stb., akkor ezen elemek ismétléses permutációinak a száma: Tétel.
k , l , m, ...
Pn
=
n! k !⋅ l !⋅ m!⋅...
Példa: 1./ Határozzuk meg az 1, 2, 2, 3, 3, 3, 4, 4 elemek permutációinak számát! Ezek között hány olyan van, amelyben az első helyen a 2-es számjegy áll? 2./ Hány hatjegyű páros szám alkotható a 2, 2, 3, 5, 6, 6 számjegyekből? 3./ Hányféleképpen tölthetünk ki egy TOTÓ szelvényt - ha 13 mérkőzésre tippelünk - úgy, hogy 8 darab 1-es, 2 darab x-es és 3 darab 2-es tipp legyen rajta?
Variációk Ismétlés nélküli variációk Definíció. Legyen adott n különböző elem. Válasszunk ki közülük k darabot (k ≤ n) és képezzük ezek egy permutációját. Ezt n elem k-ad osztályú variációjának nevezzük. Tétel. n különböző elem k-ad osztályú variációinak a száma:
Vnk = n ⋅ (n − 1) ⋅ (n − 2) ⋅ ... ⋅ (n − k + 1) Példa: 1./ Hány olyan ötjegyű szám van amelynek számjegyei különbözőek? 2./ Hány 5-tel osztható ötjegyű számot írhatunk fel a 0, 1, 2, 3, 4, 5, 6, 7 számjegyek felhasználásával?
Ismétléses variációk Definíció. Legyen adott n különböző elem. Ha ezen elemek k-d osztályú variációinak képzésénél egy elemet nemcsak egyszer, hanem többször is kiválaszthatunk, akkor az ily módon nyert variációt n elem k-ad osztályú ismétléses variációjának nevezzük. k, i
Tétel. n különböző elem k-ad osztályú ismétléses variációinak a száma: Vn
= n
Példa: 1./ Hány olyan negyedosztályú ismétléses variáció készíthető az 1, 2, 3, 4, 5, 6, 7 számjegyek felhasználásával, melynek első jegye 1-es? 2./ Hány ötjegyű szám írható fel a 0, 1, 2 számjegyek felhasználásával? 3./ Hányféleképpen lehet különböző módon kitölteni egy egyhasábos TOTO szelvényt?
k
Kombinációk Ismétlés nélküli kombinációk Definíció. Ha n különböző elemből kiválasztunk k darabot oly módon, hogy a kiválasztott elemek sorrendjére nem vagyunk kíváncsiak, n elem k-ad osztályú kombinációjáról beszélünk.
n k
Tétel. n elem k-ad osztályú kombinációinak a száma: Cnk =
Példa: 1./ A „ hatos ”, vagy az „ ötös ” LOTTÓ szelvényből kell többet különböző módon kitölteni, hogy biztosan legyen egy hatos, vagy egy ötös találatunk? 2./ A 32 lapos magyar kártyából kiválasztunk 10 lapot. Hányféleképpen fordulhat elő ilyen kiosztásban, hogy a 4 ász a 10 lap között legyen?
Ismétléses kombinációk Definíció. Ha n különböző elem k-d osztályú kombinációit úgy képezzük, hogy az elemeket többször is, mégpedig akárhányszor felhasználhatjuk, akkor ismétléses kombinációkat kapunk. Tétel. n különböző elem k-d osztályú ismétléses kombinációinak a száma:
C
k,i n
n + k − 1 = k
Példa: 1./ Egy gyerek 5 különböző fagylaltból választhat egy háromgombócos adagot. Hányféle lehetősége van a választásra? A tölcsérben a gombócok sorrendjére nem vagyunk tekintettel. 2./ Egy piaci árusnak háromféle almája van. 10 darab almát szeretnénk vásárolni. Hányféleképpen tehetjük ezt meg?
Gyakorló feladatok 1./ A 0, 1, 2, 3, 4 számjegyekből hány ötjegyű szám készíthető, ha minden számjegyet csak egyszer használunk fel? Ezek között hány olyan szám van, amelyben a 0 a második helyen szerepel? 2./ Hány olyan permutációja van az 1, 2, 3, 4, 5, 6, 7, 8 elemeknek, amelyben az első három helyet a 6, 7, 8 elemek foglalják el valamilyen sorrendben, s az utolsó helyen az 5-ös áll? 3./ Egy 34 fős szervezet 5-tagú vezetőséget választ: 1 titkárt és 4 vezetőségi tagot. Hányféle kimenetele lehet a választásnak? (A titkárt a vezetőségi tagoktól megkülönböztetjük, de a 4 vezetőségi tag között nem teszünk különbséget.) 4./ Magyarországon a 80-as években a gépkocsik rendszáma két betűből és utána 4 számjegyből állt. 26 betű és 10 számjegy áll rendelkezésünkre. Hány gépkocsit lehetett megkülönböztetni, ha a 0000 számnégyes nem fordulhat elő? 5./ Egy pályázatra 10 pályamunka érkezett, és 6 egyenlő díj van. Hányféleképpen lehet a díjakat kiadni, ha a díjak felezése, vagy megosztása tilos?
Gyakorló feladatok 6./ 100 csavar közül, amelyek között 10 darab selejtes, kiválasztunk 5-öt. a./ Hányféleképpen lehetséges ez? b./ Hány olyan eset van, amelyben a kiválasztottak mind 1hibátlan csavarok? c./ Hány olyan választás létezik, amelyben 3 csavar jó és 2 selejtes? 7./ Egy futóversenyen 14 futó vesz részt. a./ Hány különböző befutási sorrend lehetséges? b./ Hány olyan különböző befutási sorrend lehetséges, amelyben két kiszemelt versenyző valamilyen sorrendben, de az első két helyen ér célba? 8./ Egy szabályos dobókockát kétszer feldobva egymás után hány esetben fordulhat elő, hogy a a./ dobott számok összege 6? b./ dobott számok összege legalább 7? c./ dobott számok összege legfeljebb 6?
