2013. október 5., szombat

A Pascal-háromszög és a kombináció

Az előző bejegyzésben már esett szó a Pascal-háromszögről, illetve annak elemei közötti összefüggésekről, valamint az egyik lehetséges felhasználásáról.
Az alábbiakban egy másik felhasználási módról lesz szó, mégpedig arról, hogy miképpen kapcsolódik a Pascal-háromszög a kombinatorika témaköréhez, azon belül is az (ismétlés nélküli, illetve az ismétléses) kombinációhoz.

A kombinatorikában mikor beszélünk kombinációról?
A kombináció kifejezést akkor használjuk, ha adott (különböző) elemek közül kell valamennyit kiválasztani úgy, hogy a kiválasztott elemek sorrendje nem számít.

Két esetet kell már most külön kezelnünk:
Az 'n' különböző elem közül
1.) 'k' különböző elemet választunk ki, illetve
2.) 'k' nem feltétlen különböző elemet választunk ki.

Az első esetben ismétlés nélküli, míg a második esetben ismétléses kombinációról beszélünk.

Nézzük ezeket tehát külön-külön, egy-egy példán keresztül bemutatva.

Ismétlés nélküli kombináció
1. feladat:
Egy öttagú társaságból hányféleképpen tudunk kiválasztani két embert?
Mivel – szándékosan – kis elemszámról van szó a feladatban, ezért el tudjuk végezni a kísérletet a gyakorlatban is, illetve csak papíron, betűkkel jelölve az egyes személyeket.

Tehát legyenek a társaság tagjai: A, B, C, D és E, akik közül az alábbiak szerint tudunk kiválasztani kettőt:
A – B; A – C; A – D; A – E;
B – C; B – D; B – E;
C – D; C – E;
D – E;

Vegyük észre, hogy a fenti esetekben nem szerepel pl. a 'B – A' lehetőség, hiszen csak a kiválasztott személyek számítanak, a sorrendjük nem.
Így az 'A – B' eset megegyezik a 'B – A' esettel, ezért azt csak egyszer számoljuk.

Most számoljuk meg, hogy hányféleképpen tudtunk két személyt kiválasztani!
A végeredmény: 10 lehetőség. (4+3+2+1 = 10)

Mivel nagyobb elemszám esetén a fenti módszer nem alkalmazható, ezért felmerülhet Önben a kérdés, hogy "Mi a hozzá tartozó képlet?"

Ha az összes elem száma 'n', a kiválasztott elemek száma pedig 'k', akkor az összes lehetséges eset száma megegyezik a Pascal-háromszög 'n'-edik sorának a 'k'-adik elemével. (A sorok, valamint azon belül az elemek száma nullától indul.)
Most pedig jöhet az ellenőrzés, azaz a fenti képletbe helyettesítsünk az 'n' helyére 5-öt, a 'k' helyére pedig 2-őt. Elvégezve a szükséges számításokat ('n!' jelentése 'n' faktoriális, azaz a pozitív egész számok szorzata 1-től 'n'-ig), ugyancsak a 10-et kapjuk eredményül.

Most nézzünk olyan esetet, amikor a kiválasztott elemek között lehet egyforma!

Ismétléses kombináció
2. feladat:
Öt betűkártyából hányféleképpen tudunk betűpárokat kiválasztani, ha egy ilyen betűpárban ugyanaz a betű többször (itt: kétszer) is szerepelhet, továbbá nem lényeges a kiválasztott betűk sorrendje?
Mivel itt is kis elemszámról van szó, nézzük meg részletesen a feladat megoldását, lépésről-lépésre:

A felhasználható betűk legyenek – a "változatosság kedvéért" ;-) – az A, B, C, D és E, melyekből az alábbi módokon tudunk betűpárokat kiválasztani:
A – A; A – B; A – C; A – D; A – E;
B – B; B – C; B – D; B – E;
C – C; C – D; C – E;
D – D; D – E;
E – E;

Most is számoljuk meg a fenti lehetőségek számát!
A végeredmény: 15 lehetőség (5+4+3+2+1 = 15)

Természetesen ezt is ki tudjuk számítani képlet segítségével is:
A módszer ugyanaz, mint az előbb: az 'n' helyére 5-öt, a 'k' helyére pedig 2-őt helyettesítve a 6 alatt a 2-t kell kiszámítanunk (az 'n alatt a k' képlet segítségével, ahol az n=6, a k=2).
Ennek eredménye pedig 15 lesz, ami megegyezik a "kézi" számítási módszerünk eredményével.

VIGYÁZAT!
A fenti feladatok talán azt a következtetést engedik levonni, hogy a pozitív egész számokat kell összeadni 'n–1'-ig, illetve 'n'-ig (attól függően, hogy ismétlés nélküli vagy ismétléses kombinációról van szó), ám ez csak a látszat, hiszen mindkét feladatban két-két elemet kellett kiválasztani. Ilyen esetekben (a Pascal-háromszög tulajdonsága alapján is mondhatjuk, hogy) valóban megegyezik az előbb említett összeggel, DE csak ekkor, azaz, ha két elemet kell kiválasztanunk!
Amennyiben 2-nél több elem kiválasztásáról szól a feladat, abban az esetben már nem lesz érvényes ez az összefüggés, így marad az alapos odafigyelést igénylő "kézi" számítás, illetve javaslom inkább a kombinációhoz kapcsolódó két képlet megtanulását és azok alkalmazását.

Ezek után egy kombinatorikai feladatot látva már "csak" azt kell tudnunk eldönteni, hogy a kapott feladat kombináció-e, illetve, hogy azon belül ismétlés nélküli, vagy pedig ismétléses kombináció?
Ennek a gyors felismeréséhez – mint általában a matematikában – csak a sok-sok feladat hibátlan megoldása segíthet hozzá...
A félreértések elkerülése végett: a sok legalább 30 feladatot jelent – feladattípusonként!

Ehhez kívánok Önnek türelmet, kitartást!


--------------------------------------------------
Annak érdekében, hogy az Önt is érintő témákban mihamarabb megoldást nyújthassak, (amennyiben még nem tette) kérem töltse ki a kérdőívet az alábbi linkre klikkelve:
Problémát okozó matematika témakörök összegyűjtése - kérdőív
--------------------------------------------------

Nincsenek megjegyzések:

Megjegyzés küldése