Ugrás a tartalomhoz

A biostatisztika matematikai alapjai

Sándor János (2011)

Debreceni Egyetem

5. Kombinatorika (K)

5. Kombinatorika (K)

A kombinatorika a diszkrét matematika egyik ága, véges halmazok numerikus problémáival foglalkozik. Három alapfejezete a permutációk; a kombinációk és a variációk témaköre. Ezek a konstrukciók sok más területen részproblémaként, a megoldás egyik mozzanataként jelentkeznek. Ilyen területek: az algebra, a gráfelmélet, a valószínűségszámítás, stb. Ebben a részmodulban célunk a kombinatorika alapjainak átismétlése és bővítése.A részmodul eredményes elvégzésével a kombinatorika alapfogalmaival kell tisztába kerülnie az olvasónak.

A részmodul feldolgozásának ajánlott lépései:

  1. Olvassa el a K1-4. Kombinatorikai összefoglaló részt. Itt az alapvető fogalmak tömör összefoglalását találja. K1. Permutációk. K2. Kombinációk. K3. Variációk. K4. Binomiális együtthatók és összefüggéseik.

  2. Tekintse át ezután a K1-4. Gyakorló feladatok megoldással részt. Itt feladatokat talál, amelyek megoldása adott. Hasonló feladatokra számíthat az ellenőrző teszt esetén is.

  3. Az alkalmazási példák részbe olyan esettanulmányokat, bemutató anyagokat gyűjtöttünk össze, amely a fejezet fogalmainak, eljárásainak elmélyítését szolgálják. A részmodul feldolgozása nem kerül számonkérésre, de mindezek kitekintést nyújtanak az elsajátított matematikai fogalma gyakorlati alkalmazásába.

  4. Ezután kérjen le a rendszerből egy önellenőrző tesztet - K. Önellenőrző teszt (több feladatból válogat a rendszer, a válaszokat cseréli!). Oldja meg a feladatokat. Amennyiben eredményesen válaszolt a tesztkérdésekre (80% felett), akkor lépjen tovább az éles tesztre. Amennyiben nem éri el a megadott százalékos eredményt, úgy térjen vissza a kombinatorikai alapfogalmak ismétléséhez és a gyakorló feladatok átnézéséhez, majd próbálja újra az önellenőrző tesztet. Az önellenőrző tesztek megoldásai nem számítanak bele a végső értékelésbe, azok a felkészülést szolgálják, a tanulmányok eredményességének mérőeszközei.

  5. Amikor tehát úgy érzi, hogy megfelelő szinten elsajátította a részmodul ismereteit, úgy lépjen tovább a K - Ellenőrző teszt megoldására. Figyeljen! Az Ellenőrző teszt megoldása már a modul értékelésének része! A modul eredményes elvégzéséhez sikeresen kell teljesítenie a K - Ellenőrző teszt részt!

  6. Az Ellenőrző teszt sikeres teljesítése után lépjen a következő részmodulra.Ahogy a modul bevezető ismertetőjében már szerepelt, és többször is ismétlésre kerül ezután is: ha nehézségei támadnak a részmodul egyes elemeivel, akkor használja a Hírfórumot, elektronikus levélben keresse meg a modul oktatóját problémáival!

  7. Bővebb, a modulban szereplő tömör összefoglalónál lényegesen hosszabb leírást talál a következő forrásokban:

    Ezek a források kisegíthetik a részmodul ismereteinek feldolgozásában és elsajátításában, valamint sok esetben bővebb ismeretalapot is szolgáltatnak.

5.1. Kombinatorikai összefoglaló (K1-4)

K1. Permutációk

K1.1. Ismétlés nélküli permutáció.

n egymástól különböző elem egy meghatározott sorrendjét az n elem egy permutációjának nevezzük. Az n egymástól különböző elem összes lehetséges permutációinak száma:

Az n! szimbólum olvasata: „n faktoriális”:

K1.1. 1.Példa - ismétlés nélküli permutáció.

Papírlapokra írjuk fel 1-től 4-ig a természetes számokat. Rakjuk le ezután sorba a lapokat. Hányféle sorrendben tudjuk ezt megtenni? Írjuk fel a lehetséges számsorokat. Megoldás: Az első lap, amit leteszünk 4 lap közül kerülhet ki. Ezután a második lap 3 lap közül választható, a harmadik lap a 2 maradék lapból kerül ki, végül utóljára a maradék 1 lapot rakhatjuk le.

Ez összeszámolva: 4 * 3 * 2 * 1 = 24 = P(n) = P(4) = n! = 4! eset.

Az esetek: (1; 2; 3; 4); (1; 2; 4; 3); (1; 3; 2; 4); (1; 3; 4; 2); (1; 4; 2; 3); (1; 4; 3; 2) (2; 1; 3; 4); (2; 1; 4; 3); (2; 3; 1; 4); (2; 3; 4; 1); (2; 4; 1; 3); (2; 4; 3; 1) (3; 1; 2; 4); (3; 1; 4; 2); (3; 2; 1; 4); (3; 2; 4; 1); (3; 4; 1; 2); (3; 4; 2; 1) (4; 1; 2; 3); (4; 1; 3; 2); (4; 2; 1; 3); (4; 2; 3; 1); (4; 3; 1; 2); (4; 3; 2; 1)

K1.1. 2.Példa - ismétlés nélküli permutáció.

Egy szabályos dobókockával hatszor dobunk egymás után. Határozzuk meg azoknak a dobássorozatoknak a számát, amelyekben nincs azonos pontszámú dobás.

Megoldás: A feladat megoldása ismétlés nélküli permutációra vezet. A lehetséges 6 pontszámot ismétlés nélkül kell minden lehetséges sorrendben felírnunk. Ezt P(6) = 6! módon tehetjük meg. Úgy is gondolkodhatunk, hogy a lehetséges hatféle pontszámot kell sorbaraknunk. A sorrend kialakításakor az első helyre még hat pontszám közül válaszhatunk. A második helyre már egyel kevesebb, öt pontszám marad. Továbbgondolva, az utolsó helyre egyetlen pontszám marad. Összesítve: 6 * 5 * 4 * 3 * 2 * 1 eset lehet. Ez éppen P(6).

K1.2. Ismétléses permutáció.

n elem között legyen k1; k2, ..., kl darab megegyező. Ezen elemek egy meghatározott sorrendjét az n elem egy ismétléses permutációjának nevezzük. A megegyező elemek egymás közötti felcserélésével nem kapunk az előzőtől különböző permutációt. Az n elem összes lehetséges ismétléses permutációinak száma:

K1.2. 1.Példa - ismétléses permutáció.

Papírlapokra írjuk fel 1, 1, 2, 3 a természetes számokat. Rakjuk le ezután sorba a lapokat. Hányféle sorrendben tudjuk ezt megtenni? Írjuk fel a lehetséges számsorokat.

Megoldás: Az ismétléses permutáció (K1.2.) képletét alkalmazva eset lehetséges.

Megkülönböztetve a két 1-es értéket (1 és 1′), a következő lehetséges sorrendeket kapjuk: (1; 2; 3; 1′); (1; 2; 1′; 3); (1; 3; 2; 1′); (1; 3; 1′; 2); (1; 1′; 2; 3); (1; 1′; 3; 2) (2; 1; 3; 1′); (2; 1; 1′; 3); (2; 3; 1; 1′); (2; 3; 1′; 1); (2; 1′; 1; 3); (2; 1′; 3; 1) (3; 1; 2; 1′); (3; 1; 1′; 2); (3; 2; 1; 1′); (3; 2; 1′; 1); (3; 1′; 1; 2); (3; 1′; 2; 1) (1′; 1; 2; 3); (1′; 1; 3; 2); (1′; 2; 1; 3); (1′; 2; 3; 1); (1′; 3; 1; 2); (1′; 3; 2; 1)

Áthúzva az azonos eseteket (1 = 1//) 12 eset marad: (1; 2; 3; 1); (1; 2; 1; 3); (1; 3; 2; 1); (1; 3; 1; 2); (1; 1; 2; 3); (1; 1; 3; 2) (2; 1; 3; 1); (2; 1; 1; 3); (2; 3; 1; 1); (2//;/3//;/1/;//1); (2//;/1//;/1/;//3); (2//;/1//;/3/;//1) (3; 1; 2; 1); (3; 1; 1; 2); (3; 2; 1; 1); (3//;/2//;/1/;//1); (3//;/1//;/1/;//2); (3//;/1//;/2/;//1) (1//;/1//;/2/;//3); (1//;/1//;/3/;//2); (1//;/2//;/1/;//3); (1//;/2//;/3/;//1); (1//;/3//;/1/;//2); (1//;/3//;/2/;//1)

K1.2. 2.Példa - ismétléses permutáció.

Egy dobozba 15 golyót teszünk. A golyók között 9 piros, 4 fehér és 2 zöld van. A dobozból sorban (visszatevés nélkül) kivesszük a golyókat. Hányféle sorrend lehetséges, ha az egyszínű golyókat nem különböztetjük meg?

Megoldás: Ismétléses permutáció 9, 4 és 2 megegyező elemmel. P(15;9;4;2) = 15!/(9!4!2!) = 5 * 13 * 7 * 15 = 6825.

K1.3. Ciklikus permutáció. Tekintsük n különböző elem összes ismétlés nélküli permutációt. Ezután ezek közül ne különböztessük meg azokat a permutációkat, amelyek egymásból „eltolással” származtathatók (az eltolás jelentse azt, hogy az első elem a második elem helyére, a második elem a harmadik elem helyére, az utolsó elem pedig az első elem helyére kerül). Ezt a konstrukciót ciklikus permutációnak nevezzük. Ekkor az összes lehetséges sorrendek száma:

K1.3. 1.Példa - ciklikus permutáció.

Papírlapokra írjuk fel 1, 2, 3, 4 a természetes számokat. Rakjuk le kör alakban a számokat. Hányféle larakás lehetéges, ha a köralakú lerakás körbeforgatásait nem tekintjük különbözőnek?

Megoldás: A ciklikus permutáció (K1:3.) képletét alkalmazva Pc(n) = n! / n = 4! / 4 = (1 *2 * 3 * 4 ) / 4 = 6 .

Az esetek, felsorolva a körbeforgatásokat is:

1. (1; 2; 3; 4) -> (2; 3; 4; 1) -> (3; 4; 1; 2) -> (4; 1; 2; 3)

2. (1; 2; 4; 3) -> (2; 4; 3; 1) -> (4; 3; 1; 2) -> (3; 1; 2; 4)

3. (1; 3; 2; 4) -> (3; 2; 4; 1) -> (2; 4; 1; 3) -> (4; 1; 3; 2)

4. (1; 3; 4; 2) -> (3; 4; 2; 1) -> (4; 2; 1; 3) -> (2; 1; 3; 4)

5. (1; 4; 2; 3) -> (4; 2; 3; 1) -> (2; 3; 1; 4) -> (3; 1; 4; 2)

6. (1; 4; 3; 2) -> (4; 3; 2; 1) -> (3; 2; 1; 4) -> (2; 1; 4; 3)

K2. Kombinációk

K2.1. Ismétlés nélküli kombináció.

Tekintsünk n egymástól különböző elemet. Alkossunk az n elemből választva k () elemű csoportokat úgy, hogy a k elem sorrendjére nem vagyunk tekintettel, és egy elem nem szerepelhet többször a csoportban. Egy csoportot n elem egy k-adosztályú kombinációjának nevezzük. n elem összes lehetséges k-adosztályú kombinációinak száma:

Az szimbólum (binomiális együttható) olvasata: „n alatt a k”.

K2.1. 1.Példa - ismétlés nélküli kombináció.

Papírlapokra írjuk fel 1, 2, 3, 4 a természetes számokat. Válasszunk véletlenül, visszatevés nélkül két lapot úgy, hogy a sorrendre nem vagyunk tekintettel. Hányféle pár alakítható így ki. Írjuk fel ezeket a párokat.

Megoldás: Az ismétlés nélküli kombináció (K2.1.) képletét alkalmazva C(4;2) = 4! / (2!(4-2)!) = 6

Amennyiben a sorrend is számít, úgy a lehetséges párok a következők:

(1; 2); (1; 3); (1; 4);

(2; 1); (2; 3); (2; 4);

(3; 1); (3; 2); (3; 4);

(4; 1); (4; 2); (4; 3)

Amennyiben a sorrend nem számít, úgy a

(1; 2); (2; 1);

(1; 3); (3; 1);

(1; 4); (4; 1);

(2; 3); (3; 2);

(2; 4); (4; 2);

(3; 4); (4; 3)

párok egyformáknak tekinthetők. A párok száma 6.

K2.1. 2.Példa - ismétlés nélküli kombináció.

A hagyományos ötös lottó sorsolásakor 90 számból választanak 5 számot. Hány szelvényt kellene kitöltenünk, hogy biztosan közöttük legyen a nyertes szelvény?

Megoldás: 90 különböző elemből kell 5 elemű csoportokat képeznünk. Ismétlés nélküli kombináció: C(90; 5) = "90 alatt az 5" = 90! / (5! 85!) = 43 949 268.

K2.2. Ismétléses kombináció.

Tekintsünk n egymástól különböző elemet. Alkossunk az n elemből választva k () elemű csoportokat úgy, hogy a k elem sorrendjére nem vagyunk tekintettel, és egy elem többször is szerepelhet a csoportban. Egy csoportot n elem egy k-adosztályú ismétléses kombinációjának nevezzük. n elem összes lehetséges k-adosztályú ismétléses kombinációinak száma:

K2.2. 1.Példa - ismétléses kombináció.

Papírlapokra írjuk fel 1, 2, 3, 4 a természetes számokat. Válasszunk véletlenül, visszatevéssel két lapot úgy, hogy a sorrendre nem vagyunk tekintettel. Hányféle pár alakítható így ki. Írjuk fel ezeket a párokat.

Megoldás: Az ismétléses kombináció (K2.2.) képletét alkalmazva: Ci(4;2) = 5! / (2! 3!) = ... = 10.

A lehetséges párok a következők: (1; 2); (1; 3); (1; 4); (2; 3); (2; 4); (3; 4); (1; 1; ); (2; 2; ); (3; 3); (4; 4).

K2.2. 2.Példa - ismétléses kombináció.

Négy szabályos dobókockát dobunk fel. Hányféle dobássorozat alakulhat ki, ha a kockákat nem különböztetjük meg?

Megoldás: A lehetséges hatféle dobásértékből negyedosztályú ismétléses kombinációkat kell képeznünk. Ci(6;4) = ... = 126.

K3. Variációk

K3.1. Ismétlés nélküli variáció.

Tekintsünk n egymástól különböző elemet. Alkossunk az n elemből választva k () elemű csoportokat úgy, hogy a k elem sorrendjére tekintettel vagyunk, és egy elem nem szerepelhet többször a csoportban. Egy csoportot n elem egy k-adosztályú variációjának nevezzük. n elem összes lehetséges k-adosztályú variációinak száma:

K3.1. 1.Példa - ismétlés nélküli variáció.

Papírlapokra írjuk fel 1, 2, 3, 4 a természetes számokat. Válasszunk véletlenül, visszatevés nélkül két lapot úgy, hogy a sorrend számít. Hányféle pár alakítható így ki. Írjuk fel ezeket a párokat.

Megoldás: Az ismétlés nélküli variáció (K3.1.) képletét alkalmazva: V(4;2) = ... = 12.

A lehetséges párok a következők: (1; 2); (1; 3); (1; 4); (2; 1); (2; 3); (2; 4); (3; 1); (3; 2); (3; 4); (4; 1); (4; 2); (4; 3).

K3.1. 2.Példa - ismétlés nélküli variáció.

Egy versenyen 12 fő vesz részt. Körmérkőzésket vívnak úgy, hogy egy versenyző kétszer mérkőzik meg ellenfelével („odavágó” és „visszavágó”), majd következik az újabb ellenfél. Hány mérkőzést játszanak a versenyen?

Megoldás: A feladat 12 elemből párok (2 elem) képzését vizsgálja úgy, hogy a párok sorrnedje számít: V(12;2) = ... = 132.

Tehát 132 mérkőzést játszanak.

K3.2. Ismétléses variáció.

Tekintsünk n egymástól különböző elemet. Alkossunk az n elemből választva k () elemű csoportokat úgy, hogy a k elem sorrendjére tekintettel vagyunk, és egy elem többször szerepelhet a csoportban. Egy csoportot n elem egy k-adosztályú ismétléses variációjának nevezzük. n elem összes lehetséges k-adosztályú ismétléses variációinak száma:

K3.2. 1.Példa - ismétléses variáció.

Papírlapokra írjuk fel 1, 2, 3, 4 a természetes számokat. Válasszunk véletlenül, visszatevéssel két lapot úgy, hogy a sorrend számít. Hányféle pár alakítható így ki. Írjuk fel ezeket a párokat.

Megoldás: Az ismétléses variáció (K3.2.) képletét alkalmazva: Vi(4;2) = 4^2 = 16.

A lehetséges párok a következők: (1; 2); (1; 3); (1; 4); (2; 1); (2; 3); (2; 4); (3; 1); (3; 2); (3; 4); (4; 1); (4; 2); (4; 3) (1; 1); (2; 2); (3; 3); (4; 4).

K3.2. 2.Példa - ismétléses variáció.

A totón 13 + 1 mérkőzésre lehet tippelni. 1 a hazai csapat, 2 a vendégcsapat győzelmét jelöli, x a döntetlent. Hány szelvényt kell kitölteni, hogy a kitöltött szelvények között legyen olyan, amelyen az első 13 mérkőzés eredményét eltaláljuk.

Megoldás: A szelvény egyes rubikáiba az 1, 2, x jeleket írjuk, újra felhasználva a jeleket. Az elemek sorrendje számít, így az ismétléses variáció összefüggéseit kell alkalmaznunk. Tehát Vi(13;3) = 3^13 = 1 594 323 totószelvényt kell kitöltenünk a 13 biztos találathoz.

K4. Binomiális együtthatók és összefüggéseik.

A binomiális együtthatók néhány tulajdonsága:

K4.1. 1. A binomiális együtthatók érétkei mindig természetes számok.

K4.2. 2.

K4.3. 3.

K4.4. 4.

K4.5. 5. Az n-elemű halmaz összes részhalmazainak száma:

K4.6. 6. Kéttagú kifejezés első hatványa:

Ez felírható binomiális együtthatókkal:

K4.8. 7. Kéttagú kifejezés második hatványa (négyzete):

Ez felírható binomiális együtthatókkal:

K4.12. 8. A kéttagú kifejezések hatványai tovább sorolhatók, a kapcsolat a binomiális együtthatókkal hasonló alakba írható:

Az együtthatók rendezett felírásával az úgynevezett Pascal háromszöghöz jutunk, amelynek igen sok érdekes tulajdonsága van.

(Gyakorló feladatok megoldásssal)

(Alkalmazási példa: Jearl Walkler: Íme, a karikavarázs. Tudomány, 1987.12.)

(Önellenőrző teszt)

(Kombinatorika fejezet - Ellenőrző, számonkérő teszt)