II. FEJEZET SZÁMLÁLÁSI FELADATOK. A KOMBINATORIKA ELEMEI II.1. Valószínűségszámítási feladatok

Fejezet tartalma

Vissza 36

Tartalomjegyzék

Számlálási feladatok. A kombinatorika elemei

II. FEJEZET SZÁMLÁLÁSI FELADATOK. A KOMBINATORIKA ELEMEI II.1. Valószínűségszámítási feladatok A klasszikus valószínűségszámítás néhány alapfogalmát már a VI. osztályban tanultátok. Eszerint, ha K véges számú kimenetellel rendelkező kísérlet1 és A egy vele kapcsolatos esemény, akkor az A valószínűségén az A-nak kedvező események és az összes események számának arányát értjük. II.1.1. Megoldott feladatok 1. Mennyi a valószínűsége annak, hogy egy dobókockával egy dobásból hatost dobjunk? Megoldás. A dobásnak hat különböző kimenetele lehetséges. Ezek közül egy eset 1 kedvező (amikor hatost dobunk), tehát a keresett valószínűség . 6 2. Mennyi a valószínűsége annak, hogy valamely véletlenszerűen választott kétjegyű természetes szám osztható legyen 7-tel? Megoldás. A kétjegyű számok 10, 11, 12, 13,..., 97, 98, 99 , tehát az összes esetek száma 90. Ezek közül a 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91 és 98 kedvező, 13 . tehát a keresett valószínűség 90 3. Válasszuk ki találomra egy konvex tízszög két csúcsát. Mennyi a valószínűsége annak, hogy az általuk meghatározott egyenes mindkét oldalán a sokszögnek négy csúcsa lesz? Megoldás. Számozzuk egytől tízig a csúcsokat trigonometrikus irányban, és jelöljük a kiválasztott csúcsoknak megfelelő eseményt a csúcsokba írt két számból alkotott halmazzal. A kísérletnek tehát a következő kimenetelei lehetségesek: {1, 2} {1, 3} {1, 4} {1, 5} {1, 6} {1, 7} {1, 8} {1, 9} {1, 10} {2, 3} {2, 4} {2, 5} {2, 6} {2, 7} {2, 8} {2, 9} {2, 10} {3, 4} {3, 5} {3, 6} {3, 7} {3, 8} {3, 9} {3, 10} {4, 5} {4, 6} {4, 7} {4, 8} {4, 9} {4, 10} {5, 6} {5, 7} {5, 8} {5, 9} {5, 10} {6, 7} {6, 8} {6, 9} {6, 10} {7, 8} {7, 9} {7, 10} {8, 9} {8, 10} {9, 10} Ezek közül az {1, 6}, {2, 7}, {3, 8}, {4, 9} és {5, 10} pontpároknak megfelelő 5 1 = . választás kedvező, tehát a keresett valószínűség 45 9 1

A kimenetelek közt nincsenek kitüntetettek, vagyis azok egyforma eséllyel következhetnek be.

Fejezet tartalma Számlálási feladatok. A kombinatorika elemei

Tartalomjegyzék 37

4. Egy tömör fakocka minden lapját befestjük fehérre, majd minden élét tíz részre osztjuk, és ezer egyforma nagyságú kis kockára daraboljuk. Mennyi a valószínűsége annak, hogy egy találomra választott kis kockának a) csak egy lapja van befestve, b) csak két lapja van befestve, c) három lapja van befestve, d) egyetlen lapja sincs befestve? Számítsd ki a négy valószínűség összegét! Mit tapasztalsz? Magyarázd meg, amit észleltél! Megoldás. Vizsgáljuk meg, hogy a nulla, egy, két vagy három befestett lappal rendelkező kis kockák az eredetiben hol helyezkedhettek el. Három lap csak akkor lehet befestve, ha az eredetivel közös csúcsa van a kockának. Az ilyen kockát sarokkockának nevezzük. Mivel az eredeti kockának nyolc csúcsa van, összesen nyolc 8 1 = . A kis kockának akkor van sarokkockánk lesz. Így a c) kérdésre a válasz: 1000 125 két lapja befestve, ha nem sarokkocka, de (a szétvágás előtt) volt az eredetivel közös éle. Az ilyen kockákat élkockáknak nevezzük. Minden élre nyolc darab élkocka illeszkedik, tehát összesen 12 ⋅ 8 = 96 élkocka van. Így a b) kérdésre a válasz: 96 12 = . Ha a kis kockának egy lapja van befestve, akkor nem sarokkocka és nem 1000 125 is élkocka, de az eredetivel volt közös lapja (a szétvágás előtt). Nevezzük ezeket a kockákat lapkockának. Minden lapra 100 − 4 − 4 ⋅ 8 = 64 ilyen kocka illeszkedik, tehát 384 48 = . Azok a kockák, összesen 6 ⋅ 64 = 384 kocka. Így az a) kérdésre a válasz 1000 125 amelyeknek egyetlen lapjuk sincs befestve, együttesen egy 8 × 8 × 8 -as kockát 512 64 = . A kapott alkotnak, tehát 512 ilyen kis kocka van. A d) kérdésre a válasz: 1000 125 valószínűségek összege 1. Ez azt fejezi ki, hogy egy kis kockának háromnál több lapja nem lehet befestve, tehát a kiválasztott kockával azonosan festett kockák számát valamelyik alpontnál megszámoltuk.2

Az itt megoldott feladatok mindegyikében sikerült megszámolni a kedvező, illetve az összes esetek számát. Láthatjuk azonban, hogy ez általános esetben speciális számlálási módszereket igényelhet (próbáld megoldani 2., 3. vagy 4. feladatot, ha nem a kétjegyű számok közül választasz, ha a tízszög helyett n-szög van, illetve ha a kocka lapjait n részre osztod). Gyakran előfordul, hogy a számlálási kísérleteink csődöt mondanak, vagy ha sikerül is megsejteni az eredményt, tanácstalanok vagyunk, amikor a megoldás leírásáról van szó. A megválaszolandó kérdések közben egyre érdekesebbeké és izgatóbbakká válnak. Lássunk néhány ilyen problémát! Mire érdemesebb fogadni: egy az egy ellen arra, hogy két egyforma kockával 24 dobásból lesz egy dupla hatosunk, vagy egy az öt ellen arra, hogy egy dobásból lesz egy dupla hatosunk? Hát arra érdemes-e fogadni, hogy egy érmének száz egymás utáni feldobását lejegyezve lesz egymás után legalább tíz fej vagy tíz írás? E kérdések megválaszolása előtt fejlesszük a számlálási technikánkat! 2

Ezt a belső kis kockák megszámolásakor is meggondolhattuk volna.

Fejezet tartalma

38

Tartalomjegyzék


II.2. Hány csapat van? A Descartes-szorzat alkalmazásai 2.1. Feladat. Egy táncverseny után az első három lány (Ica, Kata és Zsuzsa) és az első két fiú (Peti, Robi) közül szeretnénk a legjobban összeillő párt kiválasztani (minden pár egy lányból és egy fiúból áll). a) Hány olyan pár képzelhető el, amelynek a fiú tagja Peti? Hát olyan, amelynek a fiú tagja Robi? b) Összesen hány pár képzelhető el? c) Hogyan módosul az összes lehetséges párok száma, ha 1° négy lány és két fiú, 2° négy lány és három fiú, 3° hét lány és öt fiú közül kell kiválasztanunk a legjobban táncoló párt? d) Próbálj megfogalmazni egy általános eljárást az összes pár felsorolására! Megoldás a) Mivel az összes lehetséges párt ki kell próbálni, Peti (akárcsak Robi) mindhárom lánnyal egy-egy párt alkothat. Így a következő párok képzelhetők el: Peti – Ica Robi – Ica Peti – Kata Robi – Kata Peti – Zsuzsa Robi – Zsuzsa Az is látható, hogy több pár nem alkotható (mert minden párban kell lennie egy fiúnak, és az előbb felsoroltuk az összes olyan párt, amelyben valamelyik fiú szerepel). c) 1° Minden fiú négy párban szerepelhet (mert négy lány van), így összesen 2 ⋅ 4 = 8 pár képzelhető el. 2° Minden fiú négy párban szerepelhet (mert négy lány van), így összesen 3 ⋅ 4 = 12 pár képzelhető el. 3° Minden fiú hét párban szerepelhet (mert hét lány van), így összesen 5 ⋅ 7 = 35 pár képzelhető el. Jelöljük a 2° esetben szereplő lányokat A-val, B-vel, C-vel, illetve D-vel és a fiúkat Xszel, Y-nal, illetve Z-vel. A lehetséges párokat az alábbiak szerint rendezhetjük X-A Y-A Z-A X-B Y-B Z-B X-C Y-C Z-C X-D Y-D Z-D Itt az első oszlopban azok a párok szerepelnek, amelyeknek X a fiú tagja, a másodikban azok, amelyeknek Y, és a harmadikban azok, amelyeknek Z. Ez a csoportosítás az általános esetben is jó. Ha n lány és m fiú közül választunk, akkor a lehetséges párok m sort és n oszlopot tartalmazó táblázatba rendezhetőek, tehát összesen m ⋅ n lehetséges pár létezik. 2.2. Feladat. Egy cukrászdában zárás után megmaradt hat gombóc epres és négy gombóc csokis fagyi. A cukrász kisfia kikönyörögte, hogy ehessen egy adag fagyit, és maga dönthesse el, hogy melyik fagyiból hány gombócot eszik. Hány különböző lehetőség közül választhat a kisfiú? Vizsgáljuk meg az előbbi lehetőségekben szereplő adagok százalékos összetételét! Hány különböző összetételű adag van?

Tartalomjegyzék

Fejezet tartalma

39


Megoldás. A leírás egyszerűsítésének céljából jelöljük csak számpárokkal a különböző lehetséges adagokat. A számpár első tagja jelentse az epres, míg a második tag a csokis gombócok számát. A (3, 2) számpár a három epres és két csokis gombócot tartalmazó fagyiadagnak felel meg. Mivel egy fagylaltadagban az epres gombócok száma nullától hatig és a csokis gombócok száma nullától négyig változhat, 5 × 7 -es táblázatba rendezhetjük a számpárokat.

(0, 0) (0, 1) (0, 2) (0, 3) (0, 4)

(1, 0) (1, 1) (1, 2) (1, 3) (1, 4)

(2, 0) (2, 1) (2, 2) (2, 3) (2, 4)

(3, 0) (3, 1) (3, 2) (3, 3) (3, 4)

(4, 0) (4, 1) (4, 2) (4, 3) (4, 4)

(5, 0) (5, 1) (5, 2) (5, 3) (5, 4)

(6, 0) (6, 1) (6, 2) (6, 3) (6, 4)

A (0, 0) pár egy külön csoportot jelent, hisz ez esetben nem beszélhetünk a százalékos összetételről. Az első sor többi eleme ismét külön csoport (száz százalékban epres) akárcsak az első oszlop többi eleme (száz százalékban csokis). A többi pár esetén kiszámítjuk az első és második tag arányát, és két párt pontosan, akkor sorolunk egy csoportba, ha a nekik megfelelő arányok egyenlők. Felsoroljuk az előbbiektől különböző, legalább kételemű csoportokat: {(1, 1), (2, 2), (3, 3), (4, 4)} {(3, 1), (6, 2)}

{(1, 2), (2, 4)} {(3, 2), (6, 4)}

{(2, 1), (4, 2), (6, 3)}

A többi pár mindegyike meghatároz egy-egy csoportot, tehát összesen 19, százalékos összetétel szerint különböző adag létezik. 2.3. Jelölések és értelmezések. Legyen E és C két halmaz. 1. Rendezett elempáron egy E-beli és egy C-beli elem együttesét értjük, ha ismerjük az elemek sorrendjét is. Példa. A 2.2. feladat esetében E = { 0, 1, 2, 3, 4, 5, 6 } az epres gombócok lehetséges száma és C = { 0, 1, 2, 3, 4 } a csokis gombócok lehetséges száma. Az (1, 2) elempárt akkor tekintjük rendezettnek, ha rögzítjük, hogy melyik eleme tartozik E-hez és melyik C-hez. A 2.2. feladat esetében az első szám az E-hez tartozott, a második elem a C-hez. Így világos, hogy az (1, 2) elempár különbözik a (2, 1) elempártól. 2. Az összes olyan rendezett elempárok halmazát, amelynek az első eleme E-ből a második pedig C-ből származik, az E és C halmazok Descartes-szorzatának (vagy direkt szorzatának) nevezzük, és E × C -vel jelöljük. Példa. Ha E = {1, 2} és C = {1, 2, 3 } , akkor E × C = {(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3)} . Ha L={Ica, Kata, Zsuzsa} és F={Peti, Robi}, akkor L × F = {(Ica, Peti), (Ica, Robi), (Kata, Peti), (Kata, Robi), (Zsuzsa, Peti), (Zsuzsa, Robi)}. Ha A = { a, b, c, d } és B = { ∆, ℵ } , akkor A × B = {(a, ∆ ), (a, ℵ), (b, ∆ ), (b, ℵ), (c, ∆ ), (c, ℵ), (d , ∆ ), (d , ℵ)} .

Tartalomjegyzék

Fejezet tartalma

40


2.4. Feladat. Alapozz eddigi tapasztalataidra, és egészítsd ki a következő kijelentéseket úgy, hogy igaz állításokhoz jussál! a) Ha az A halmaz elemeinek száma a és a B halmaz elemeinek száma b, akkor az A × B halmaznak ……… és a B × A halmaznak ……… eleme van. b) Az A × B és B × A halmazok pontosan akkor egyenlők, ha ………. c) Az A × B halmaz pontosan akkor részhalmaza a B × A halmaznak, ha ……… 2.5. Feladat I. Egy akciócsoport két sofőrből (Rudi és Tóni), három rádiósból és négy mesterlövészből áll. Valamely akciójukban olyan háromtagú csapat vesz részt, amelyben van egy sofőr egy rádiós és egy mesterlövész. Hány olyan csapat képzelhető el, amelynek Rudi a sofőrje? Összesen hány csapat képzelhető el? II. Jelöljük S1-gyel és S2-vel a sofőröket, R1-gyel, R2-vel és R3-mal a rádiósokat és M1-gyel, valamint M2-vel a mesterlövészeket. Írd fel az összes elképzelhető csapatot! III. Ha a csoporthoz csatlakozik öt bombaszakértő és az akcióban részt vevő csapathoz bombaszakértő is kell, hányszorosára növekszik a lehetséges csapatok száma? IV. Próbálj általános eredményt megfogalmazni! Megoldás I. Ha Rudi a sofőr, akkor a három rádiós és négy mesterlövész közül kell kiválasztani egyet-egyet. Ez 3 ⋅ 4 = 12 módon érhető el, tehát 12 olyan csapatot lehet elképzelni, amelynek Rudi a sofőrje. Ha Tónit választjuk sofőrnek, szintén 12 csapatot tudunk elképzelni, tehát összesen 24 felállás lehetséges. II. A táblázatos reprezentáció itt nehezen használható, ezért más számlálást kell kitalálnunk. Készítsük el az alábbi ábrát: O

S1 R1

R2

S2 R3

R1

R2

R3

M1 M1 M2 M1 M2 M1 M 2 M1 M 2 M 2 M1 M 2 Ha az O pontból az alsó sorba akarunk eljutni a nyilak mentén, akkor minden lehetséges útvonal egy lehetséges csapatnak felel meg. Például a vastag nyilakkal jelzett útvonal az (S1 , R3 , M 2 ) csapat kiválasztását jelenti. Mivel az alsó sorban 12 érkezési lehetőség van, összesen 12 csapat képzelhető el. Ha alaposabban megfigyeljük az ábra szerkezetét, láthatjuk, hogy négy mesterlövész esetén az alsó sorban 6 ⋅ 4 = 24 érkezési lehetőség volna, tehát az I. kérdésre adott válaszunk megerősíthető és általánosítható. Ha a csoporthoz öt bombaszakértő csatlakozik, akkor az előbbi ábrát ki kell egészíteni még egy sorral oly módon, hogy minden M-mel jelzett csomópontból öt nyíl induljon ki. Ez azt jelenti, hogy az összes lehetőségek száma ötszöröződik. Így 120 négytagú csapat képzelhető el.

Fejezet tartalma

Tartalomjegyzék 41


IV. Fogalmazzuk meg általánosan is a feladatot és az eredményeinket. Legyen A1 , A2 , A3 ,..., An tetszőleges halmaz, és keressük az összes olyan rendezett, n elemű

halmazok számát, amelyeknek a k-adik eleme Ak -ban található minden k = 1, n -re. Ha a k az Ak halmaz elemeinek száma, minden k = 1, n -re, készítsünk az előbbihez hasonló ábrát úgy, hogy a k-adik sorba az Ak −1 elemei legyenek minden k = 2, n + 1 re. Így a k-adik sor minden elemétől pontosan a k darab nyíl indul, ha k = 1, n , tehát összesen a1 ⋅ a 2 ⋅ a3 ⋅ ... ⋅ a n olyan rendezett, n elemű halmaz létezik, amelynek a k-adik eleme Ak -ban található van minden k = 1, n -re. 2.6. Jelölések és értelmezések. Tekintsük az A1 , A2 , A3 ,..., An tetszőleges halmazokat. 1. Rendezett elemhármason egy A1 , egy A2 és egy A3 halmazbeli elem valamilyen rögzített sorrendben vett együttesét értjük. 2. k elemet tartalmazó rendezett elemrendszer alatt egy k elemű halmazt értünk, amelynek minden eleméről tudjuk, hogy az A1 , A2 , A3 ,..., Ak halmazok melyikéhez tartozik. 3. Az összes olyan rendezett elemhármasok halmazát, amelyek első eleme A1-ben, a második A2-ben és a harmadik A3-ban van az A1, A2 és A3 halmazok Descartes-szorzatának nevezzük, és A1 × A2 × A3 -mal jelöljük. 4. Az összes olyan k elemet taratlamzó rendezett elemrendszer halmazát, amelynek az i-edik eleme minden i = 1, k esetén Ai -ben van, az A1, A2,..., Ak-1 és Ak k

halmaz Descartes-szorzatának nevezzük, és A1 × A2 × A3 × ... × Ak = ∏ Ai i =1

vel jelöljük. 2.7. Példa. Ha Ai = {0, 1} ∀ i = 1, 4 , akkor az A1 × A2 × A3 × A4 halmaz elemei a következő számnégyesek: (0, 0, 0, 0), (0, 0, 0, 1), (0, 0, 1, 0), (0, 0, 1, 1), (0, 1, 0, 0), (0, 1, 0, 1), (0, 1, 1, 0), (0, 1, 1, 1), (1, 0, 0, 0), (1, 0, 0, 1), (1, 0, 1, 0), (1, 0, 1, 1), (1, 1, 0, 0), (1, 1, 0, 1), (1, 1, 1, 0), (1, 1, 1, 1). Minden négyelemű rendezett 0-1 jelsorozat tekinthető egy kettes számrendszerbeli számnak is, tehát az A1 × A2 × A3 × A4 halmaznak pontosan annyi eleme van, ahány legfeljebb négyjegyű kettes számrendszerbeli szám létezik. Az utóbbiak száma 16, tehát A1 × A2 × A3 × A4 -nek összesen 16 eleme van. 2.8. Feladat. Jelöljük rendre A-val, B-vel és C-vel az {1, 2, 3}, {a, b} és {M, N} halmazt. a) Írd fel az A × B , B × A , A × ( B × C ) , ( A × B) × C és A × B × C halmazokat! b) Hasonlítsd össze az előbbi alpont utolsó három halmazát, és egészítsd ki az alábbi kijelentéseket! Ha az A, B és C halmazok elemeinek száma rendre a, b és c, akkor az A × ( B × C ) , ( A × B) × C és A × B × C halmazok elemeinek száma ……… Az A × ( B × C ) , ( A × B) × C és A × B × C halmazok ……..

Fejezet tartalma

42

Tartalomjegyzék


Észrevételeinket tételben foglaltuk össze. 2.9. Tétel. Ha a k az Ak halmaz elemeinek száma minden k = 1, n esetén, akkor az n

A1 × A2 × A3 × ... × An = ∏ Ai i =1

halmaz elemeinek száma a1 ⋅ a 2 ⋅ a 3 ⋅ ... ⋅ a n , és a

halmazok összeszorzásakor a sorrend felcserélése nélkül bármilyen csoportosítást elvégezhetünk. A tétel (matematikailag) teljes bizonyítását a matematikai indukció módszerével adhatjuk meg. Úgy gondoljuk azonban, hogy aki megértette az előbbi feladatok megoldását, annak ez a bizonyítás semmiféle többletet nem adhat, ezért a bizonyítás részletezését az olvasóra bízzuk. 2.10. Feladat a) Sorold fel az N =22355 szám prímosztóit! b) Ha d természetes osztója N-nek, akkor milyen prímosztói lehetnek d-nek, és ezek milyen hatványon fordulhatnak elő a d prímtényezős felbontásában? c) Hány darab természetes osztója van N-nek? Megoldás. Az N prímosztói 2, 3 és 5, továbbá N egyetlen osztója sem tartalmazhat ezektől különböző prímtényezőt. A d prímtényezős felbontásában a 2 legfeljebb a második, a 3 legfeljebb az ötödik és az 5 legfeljebb az első hatványon fordulhat elő (ezt az ötödik osztályban tanultak alapján tudjuk). Tehát d = 2α ⋅ 3 β ⋅ 5γ , ahol α ∈ { 0, 1, 2 }, β ∈ { 0, 1, 2, 3, 4, 5 } és γ ∈ { 0, 1 } . Eszerint, az N osztóinak száma megegyezik a { 0, 1, 2 }× { 0, 1, 2, 3, 4, 5 } × { 0, 1 } Descartes-szorzat elemeinek számával. Mivel a szorzatnak 36 eleme van, az N is 36 természetes osztóval rendelkezik. 2.11. Feladat a) Hány természetes osztója van az M = 2 2 ⋅ 35 ⋅ 11 ⋅ 19 3 számnak? Hát a P = 2 7 ⋅ 35 ⋅ 53 ⋅ 119 számnak? b) Egészítsd ki a következő kijelentést úgy, hogy igaz állítást kapjál! Ha p1 , p 2 ,..., p k −1 és p k páronként különböző prímszámok, akkor az α

α

n = p1α1 ⋅ p α2 2 ⋅ p3 3 ⋅ ... ⋅ p k k szám természetes osztóinak száma ……….… ……………………….………………. Megoldás. Az előbbi feladathoz hasonlóan az M osztóinak száma megegyezik a { 0, 1, 2 } × { 0, 1, 2, 3, 4, 5 } × { 0, 1} × { 0, 1, 2, 3 } Descartes-szorzat elemeinek számával, tehát M-nek 144 osztója van. A P osztóinak száma egyenlő a { 0, 1,..., 7 } × { 0, 1,..., 5 } × { 0, 1, 2, 3} × { 0, 1,..., 9 } Descartes-szorzat elemeinek számával, vagyis P-nek 1920 osztója van.

II.2.1. Gyakorlatok és feladatok 1. Hány legfeljebb hatjegyű természetes szám létezik? 2. Hány olyan természetes szám létezik, amelynek a hetes számrendszerbeli reprezentációja pontosan hét számjegyet tartalmaz? 3. Egy helyőrség kétszáz közkatonája, tíz altisztje, négy rádiósa és három tisztje közül négytagú különítményt kell választanod, és ki kell jelölnöd a különítmény


Tartalomjegyzék 43

vezetőjét. A különítménynek egy közkatonát, egy rádióst, egy altisztet és egy tisztet kell tartalmaznia, a vezető csak a rádiós vagy a tiszt lehet. Hány különböző módon választhatod ki a különítményt? 4. Vizsgáld meg a következő egyenlőségek helyességét: a) ( A ∪ B ) × C = ( A × C ) ∪ (B × C ) ; b) ( A \ B ) × C = ( A × C ) \ (B × C ) ; c) ( A ∩ B ) × C = ( A × C ) ∩ (B × C ) . 5. Írd egyszerűbb alakba az ( A × A) ∩ ( A × C ) ∩ (B × A) ∩ (B × C ) kifejezést úgy, hogy csak egy direkt szorzat szerepeljen benne! 6. Egyszerre három, különböző színű dobókockával dobunk. Mi a valószínűsége annak, hogy a három szám közül az egyik a másik kettő összege? 7. Valamelyik Las Vegas-i kaszinó egy játékgépén három korong forog. Mindegyik korong oldalát 24 egyforma részre osztották, és minden részre ráfestették az alábbi hat rajz valamelyikét oly módon, hogy mindegyik négyszer szerepeljen mindegyik korongon.

A korongok egymástól függetlenül forognak, és a játékos minden korongról mindig csak egy-egy ábrát láthat. A játékos akkor nyer, ha mindhárom korongon ugyanazt az alakzatot látja. Mennyi a valószínűsége annak, hogy már az első játékban nyerünk? Ha 10 cent egy játék, megéri-e a kaszinónak, hogy négy dollárt fizessen egy nyereségért? 8. a) Valamely n elemű számhalmaz elemeiből hány különböző módon állíthatunk össze egy olyan számpárt, amelynek elemei különböznek? b) Egy n elemű számhalmaz elemei közül hány különböző módon állíthatunk össze olyan számpárt, amelynek elemei egyenlők is lehetnek? 9. Az űrhajós csoport tíz nőből és harminc férfiből áll. Ebből a csoportból hányféleképpen lehet kiválasztani olyan öttagú csapatot, amelyben két nő és három férfi van? 10. Igaz-e, hogy ha az n1 természetes számnak d1 természetes osztója van és az n2 természetes számnak d2, akkor az n1 ⋅ n2 számnak d1 ⋅ d 2 osztója van? Milyen feltételre van szükség ahhoz, hogy az állítás igaz legyen? 11. Egy börtönben 1000 cella van, ezek 1-től 1000-ig vannak megszámozva, és minden cellának az ajtajára olyan zárat szereltek, amelyen három betű látható (lásd a mellékelt ábrát). Az ajtó akkor nyílik ki, ha az a betű van legfelül. Miután a rabok elalszanak, a börtönőr 1000-szer körbejárja a cellákat A k-adik körútja alkalmával minden k-adik cella zárján fordít egyet (trigonometriai irányban 120°-ot). Hány zár lesz nyitva reggel? Melyek ezek?

Tartalomjegyzék

Fejezet tartalma

44


II.3. Rekurzív számlálások, avagy a „Lassan járj, tovább érsz” filozófiája A mellékelt ábrák mindegyikén az A pontból a B-be kell eljutnunk úgy, hogy mezőről mezőre és csak jobbra vagy felfele léphetünk. Tehát bármelyik mezőről csak a felső vagy a jobb oldali szomszédjára léphetünk. A kérdés az, hogy hány különböző módon tehetjük (mindegyik „tábla” esetében külön-külön) meg ezt? B

B

A

A

II.1. ábra II.2. ábra Látható, hogy ha kezdettől az A-ból B-be vezető utakat vizsgáljuk, akkor elég nehéz dolgunk van. Ez a helyzet rögtön megváltozik, ha a táblák mindegyik mezőjére ráírjuk, hogy A-ból hány különböző úton juthatunk az illető mezőre. Ez egy fontos ötlet, és a következőkben hasznunkra válhat. A lépésszabályok alapján egy mezőre csak a bal oldali vagy az alatta levő mezőről léphetünk, tehát minden mezőn e két szomszédos mezre írt szám összege áll. Ezt a szabályt használva próbáld folytatni, amit mi elkezdtünk! B

8 4 8 8 2 4 4 1 2 2 A 1

B

9 9 6 9 9 3 3 1

3 1 3 1 2 A 1 II.3. ábra II.4. ábra Az A és a B mező középpontjait összekötő szakasz által kettészelt mezőkre írt számokat tekintsük egy számsorozat kezdőértékeiként. Tudnád-e folytatni ezeket a sorozatokat? Általánosítva: ha az n darab egymásba ágyazott 2 × 2 -es négyzet jobb felső sarkában megjelenő szám a n és az n darab egymásba ágyazott 3 × 3 -as négyzet jobb

felső sarkában megjelenő szám bn , keressük meg az (a n )n∈N ∗ és (bn )n∈N ∗ sorozatok általános tagjának képletét.

Fejezet tartalma

Tartalomjegyzék 45


Ha az ábrák üres mezőire ráírjuk a megfelelő számokat, kapjuk: a1 = 2, a 2 = 4, a3 = 8, a 4 = 16, a5 = 32, a6 = 64, a7 = 128 és b1 = 6, b2 = 18, b3 = 54, b4 = 162, b5 = 486, b6 = 1458 . Látható, hogy mindkét sorozat mértani haladvány, az első kvóciense 2, a másodiké 3. Ezt figyelembe véve, megsejthetjük, hogy az általános tag képlete a n = 2 n , illetve

bn = 2 ⋅ 3 n . Az első ábra esetében ezt a sejtést indukcióval azonnal igazolhatjuk az alábbi diagramm alapján: 2n

2 n + 2 n = 2 n+1

2n

2n

A második esetben beláthatjuk, hogy nem elégséges a sejtésünk. Az alapján nem tudjuk bizonyítani az általános tag képletét. (Azt nem tudjuk bizonyítani, amit a legegyszerűbb észrevenni, vagyis azt, hogy a (bn )n∈N ∗ sorozat mértani haladvány.) Ez azért van így, mert sejtésünk semmit sem állít a bn fölött, illetve tőle jobbra elhelyezkedő számokról, pedig bn +1 kiszámításakor ezeket is kell használnunk. A számokat megvizsgálva észrevehetjük, hogy ezek a 3 hatványai, tehát az állítás, amit igazolni szeretnénk a következő: bn = 2 ⋅ 3n , ∀ n ≥ 1 , és bn fölött, illetve a tőle jobbra elhelyezkedő számok 3n -nel egyenlők. Észrevételünk alapján a fentihez hasonló diagramot készíthetünk. 3n

3 n + 2 ⋅ 3 n = 3 n+1

2 ⋅ 3 n +1

3n

2 ⋅ 3n

3 n + 2 ⋅ 3 n = 3 n+1

2 ⋅ 3n−1

3n

3n

A nagyobb számok a feltételezést tartalmazzák. A nyilak alapján látható, hogy ezek egyértelműen meghatározzák a többi számot, és a kapott értékek igazolják sejtésünket (n+1)-re, tehát a matematikai indukció elve alapján sejtésünk igaz. II.3.1. Permutációk 3.1.1. Feladat. Egy polcon az alábbi ábrán látható öt különböző trófeát kell elhelyeznünk. Hányféle sorrendbe helyezhetjük el?


Tartalomjegyzék 46

Megoldás. A feladat ismét becsapó, mert már ez az öt trófea is 120 különböző sorrendben helyezkedhet el, és ez elég sok ahhoz, hogy találgatás útján felírhassuk. Szükség van tehát egy számlálási módszerre, amely szerint generálhatjuk a lehetséges sorrendeket, és amely biztosítja azt, hogy valóban az összes sorrendet megtaláljuk. Ehhez vizsgáljunk meg egyszerűbb eseteket. Próbáljuk előállítani az összes lehetséges sorrendet 1, 2, 3, 4 és csak ezek után 5 trófea esetén. Jelöljük t1 , t 2 , t 3 , t 4 és t 5 -tel az 1, 2, 3, 4, illetve 5 trófea összes lehetséges sorrendjét. Ha egy trófeánk van, akkor ezt egyféleképpen tehetjük a polcra (a sorrendre gondolunk, és nem egyébre), tehát t1 = 1 . Két trófeát már két különböző sorrendben helyezhetünk el, tehát t 2 = 2 . Vizsgáljuk meg, hogy mi történik, ha az előbbi két sorrend valamelyikét kiegészítjük a harmadik trófeával.

Az előbbi ábra szerint ezt tehetjük a sor elejére, a két trófea közé vagy a sor végére, tehát az előbbi két sorrend mindegyikéből három különböző három trófeát tartalmazó sor készíthető. Ha egy hármas sorrendből elhagyjuk a harmadik trófeát, akkor egy kettes sorrendhez jutunk, tehát az előbbi szerkesztés az összes hármas sorrendet megadja, így t 3 = 6 . Az itt alkalmazott ötlet továbbra is használható. Egy három trófeát tartalmazó sorrend négy különböző négy trófeát tartalmazó sorrendet származtat, tehát a hat hármas sorrend összesen 6 ⋅ 4 = 24 darab lehetséges sorrendet határoz meg négy trófea esetén. Így t 4 = 24 . Egy négy trófeát tartalmazó sorba öt helyre tehetjük az ötödik trófeát, tehát minden négyes sorrend öt darab ötös sorrendet határoz meg. A 24 négyes sorrend összesen 24 ⋅ 5 = 120 sorrendet származtat az öt trófeára. Általánosítsuk az eredményeinket! Vizsgáljuk meg, hogy milyen összefüggés létezik n, illetve n+1 trófea összes lehetséges sorrendjének száma közt. Jelöljük t n -nel n trófea összes lehetséges sorrendjének a számát, ha n nullánál nagyobb természetes szám. Az n trófea közt összesen n-1 hely van, mivel a sor elejére, illetve a végére is helyezhetjük az (n+1)-edik trófeát, összesen n+1 különböző sorrendhez jutunk. Ennek (5) alapján érvényes a t n+1 = (n + 1) ⋅ t n összefüggés minden n ∈ N ∗ esetén. Az eddig vizsgált t n értékeket írhatjuk a következő alakban: t1 = 1, t 2 = 1 ⋅ 2 , t 3 = 1 ⋅ 2 ⋅ 3 , t 4 = 1 ⋅ 2 ⋅ 3 ⋅ 4 és t 5 = 1 ⋅ 2 ⋅ 3 ⋅ 4 ⋅ 5 , tehát t n az első n természetes szám szorzata, ha n ≤ 5 . A továbbiakban az (5) összefüggés segítségével igazoljuk, hogy ez minden természetes számra igaz. A leírás egyszerűsítésének céljából bevezetjük a következő jelöléseket:

Tartalomjegyzék

Fejezet tartalma

47


3.1.2. Jelölés. Az első n, nullától különböző természetes szám szorzatát az n ! szimbólummal jelöljük, és n-faktoriálisnak (vagy egyszerűen n-faktornak) olvassuk. 3.1.3. Példák és összefüggések: a) Számítsuk ki az első tíz számra az n-faktor értékét! 1! = 1, 2! = 2, 3! = 6, 4! = 24, 5! = 120, 6! = 720, 7! = 5040, 8! = 40320 10!= …………… 9!= …………… Látható, hogy az n-faktoriális nagyon gyorsan növekszik, ezért a kiszámítása már viszonylag kis kétjegyű n esetén is nehézséget okozhat. A tíz számjegyet kijelző zsebszámológép sem ad pontos értéket n = 16 esetén. Érdekességképpen kiszámoltuk a 25! -t és a 33! -t1: 25!= 1551121004330985984000000 33! = 8683317618811886495518194401280000000 b) Megegyezés szerint azt mondjuk, hogy 0!= 1 . c) Az értelmezést használva írjátok egyszerűbb alakba a következő kifejezéseket: (n + 2)! = n 2 + 3n + 2 ⋅ n != n ⋅ ( n + 1) ⋅ (n + 2) n! 1 ⋅ 3 ⋅ 5 ⋅ ... ⋅ (2n − 1) = = (n − 3)! 2 ⋅ 4 ⋅ 6 ⋅ ... ⋅ (2n) d) Feladatgyűjteményekben gyakran találkozhattok még a (2n)!! , illetve (2n − 1)!! szimbólumokkal is. Ezek az első n darab, nullától különböző páros, illetve páratlan természetes szám szorzatát jelölik, és nem tévesztendők össze a ((2n)!)! jelöléssel, amely a 2n-faktor faktoriálisát jelöli. Így (6)!!= 2 ⋅ 4 ⋅ 6 = 48 míg ((6)!)!= 720!

(

)

3.1.4. Értelmezés. Az A halmaz egy permutációján az A összes eleméből szerkesztett rendezett halmazt értjük. Ha az A halmaz n elemet tartalmaz, akkor A elemeiből úgy kaphatunk egy rendezett halmazt, hogy az A minden eleméhez hozzárendelünk az 1, 2, 3,…, n számok közül egyet oly módon, hogy különböző elemekhez különböző számok tartozzanak. (Minden elemhez hozzárendeljük a sorszámát.) Az elemekből és a hozzájuk rendelt számokból képzett párok alkotják a rendezett halmazt. Általában az elemeket a hozzájuk rendelt számok szerinti növekvő sorrendben szoktuk felírni, ezért magukat a számokat elhagyhatjuk. Képezzünk két rendezett halmazt az { a, c, 5, 3, t , ∆ } halmazból! Az alábbi táblázatokban azt láthatjuk, hogy az 1, 2, 3, 4, 5 és 6 számok a halmaz melyik eleméhez tartoznak. Az ezeknek megfelelő rendezett halmazok ( a, 5, 3, ∆, c, t ) és (3, 5, c, ∆, a, t ) .

1 a

1

2 5

3 3

4 ∆

5 c

6 t

1 3

2 5

A számolásokat egy Texas Instruments TI-92-es gépen végeztük.

3 c

4 ∆

5 a

6 t


Tartalomjegyzék 48

Az egyszerűbb írásmód kedvéért a táblázatot, ha csak lehet, mellőzzük. Például az {1, 2, 3 } halmazból képezhető összes rendezett halmaz (lásd a trófeákat): ( 1, 2, 3 ) ( 1, 3, 2 ) ( 2, 1, 3 ) ( 2, 3, 1 ) ( 3, 1, 2 ) és ( 3, 2, 1 ) . 3.1.5. Tétel. Egy n elemű halmaz permutációinak számát Pn -nel jelöljük, és Pn = n! , minden természetes n számra. Bizonyítás. Az (5) összefüggés alapján Pk +1 = (k + 1) ⋅ Pk , ∀ k ∈ N . A k-nak rendre az 1, 2, 3,…, n–1 értéket adjuk, majd összeszorozzuk a kapott egyenlőségeket. A P1 , P2 , P3 ,..., Pn −1 szám mindkét oldalon megjelenik, tehát a szorzatukban egyszerűsíthetünk velük. A bal oldalon az egyszerűsítés után az első n természetes szám szorzata áll, az alábbiak szerint: Pn = n ⋅ Pn−1 Pn−1 = (n − 1) ⋅ Pn− 2 Pn−2 = (n − 2) ⋅ Pn−3

.......................... P3 = 3 ⋅ P2 P2 = 2 ⋅ P1 Pn = n!

Tehát

Pn = n ! ∀ n∈ N -re. II.3.2. Variációk 3.2.1. Feladat. Egy hattagú társaság tagjai közül egy titkárt és egy írnokot kell kiválasszunk. Hány különböző módon tehetjük ezt meg? Megoldás. A titkárt hat ember közül kell kiválasztanunk, tehát erre hat lehetőségünk van. Minden kiválasztott titkárhoz a megmaradt öt tag közül bárkit választhatunk írnoknak, tehát összesen 6 ⋅ 5 = 30 lehetőségünk van. Számozzuk meg a társaság tagjait 1-től 6-ig. A lehetséges választásokat táblázatba foglaltuk össze: (1, 2) (2, 1) (3, 1) (4, 1) (5, 1) (6, 1) (1, 3) (2, 3) (3, 2) (4, 2) (5, 2) (6, 2) (1, 4) (2, 4) (3, 4) (4, 3) (5, 3) (6, 3) (1, 5) (2, 5) (3, 5) (4, 5) (5, 4) (6, 4) (1, 6) (2, 6) (3, 6) (4, 6) (5, 6) (6, 5) A számpárok első tagja a titkár számát, míg a második sorszám az írnok számát jelöli. 3.2.2. Feladat. Ha az írnok és a titkár mellé egy küldöncöt is kell választanunk, akkor ez hányszorosára növeli a lehetséges választások számát? Megoldás. A küldöncöt a titkár és az írnok minden lehetséges választása esetén a megmaradt négy tag közül kell kiválasztanunk, ez a négyszeresére növeli a lehetséges választások számát. 3.2.3. Feladat. Ha Vnk -val jelöljük egy n elemű halmaz összes k elemű rendezett

részhalmazainak a számát, mi az összefüggés Vnk és Vnk +1 közt? (Elemezd az előbbi feladat megoldását!)


Tartalomjegyzék 49

Megoldás. Jelöljük A-val az n elemű halmazunkat. Minden k elemű X rendezett részhalmazból pontosan (n − k ) darab (k + 1) elemű rendezett részhalmazt szerkeszthetünk, ha X-hez (k + 1) -edik elemként hozzáadjuk az A \ X valamelyik elemét (az utóbbi halmaznak pontosan (n − k ) eleme van). Világos, hogy így minden (k + 1) elemű rendezett részhalmazt megkapunk, és nem kaphatunk egyetlen (k + 1)

elemű rendezett részhalmazt sem két, különböző módon, tehát Vnk +1 = Vnk ⋅ (n − k ) . (6) 3.2.4. Értelmezés 1. Valamely halmaz elemeiből szerkesztett rendezett részhalmazt az illető halmaz egy variációjának nevezzük. 2. Bármely halmaz elemeiből szerkesztett k elemű rendezett részhalmazt a halmaz egy k-ad osztályú variációjának nevezzük. Egy n elemű halmaz k-ad osztályú variációinak számát V nk -val jelöljük (n,k∈N). 3.2.5. Példák a) A 3.2.1. feladatban egy hatelemű halmaz másodosztályú variációinak számát kellett meghatároznunk, és a táblázatban maguk a másodosztályú variációk szerepeltek. b) A 3.1. paragrafusban egy n elemű halmaz n-ed osztályú variációit számoltuk meg, és ezeket permutációknak neveztük. c) A 3.2.2. feladatban azt vizsgáltuk, hogy mi az összefüggés a hatelemű halmaz másod és harmadosztályú variációinak száma között, míg a 3.3.3. feladatban általános összefüggést találtunk egy n elemű halmaz k-ad és (k + 1) -ed osztályú variációinak száma közt. A 3.2.3. feladat megoldása alapján találjunk általános képletet valamely n elemű halmaz k-ad osztályú variációinak számára, vagyis a Vnk -ra. Akárcsak a permutációk esetében helyettesítsünk a (6) összefüggésbe k helyett rendre (k–1)-et, (k–2)-t,…, 3-at, 2-t és 1-et, majd szorozzuk össze a kapott egyenlőségeket: Vnk = (n − k + 1) ⋅Vnk −1 Vnk −1 = (n − k + 2) ⋅Vnk − 2

Vnk − 2 = (n − k + 3) ⋅Vnk − 3

........................................ Vn3 = (n − 2) ⋅Vn2 Vn2 = (n − 1) ⋅Vn1 Vn1 = n Vnk = (n − k + 1) ⋅ (n − k + 2 ) ⋅ ... ⋅ n Érvényes tehát a következő tétel: 3.2.6. Tétel. Ha 0 ≤ k ≤ n és k, n∈N, akkor egy n elemű halmaz k-ad osztályú variációinak száma Vnk = n ⋅ (n − 1) ⋅ (n − 2 ) ⋅ ... ⋅ (n − k + 2 ) ⋅ (n − k + 1) .

Fejezet tartalma

Tartalomjegyzék


50

3.2.7. Megjegyzés. k > n esetén a Vnk számot nullának tekintjük, hisz ebben az esetben egy n elemű halmaz elemeiből nem tudunk egyetlen m elemű rendezett részhalmazt sem szerkeszteni. Ha tömörebb felírást óhajtunk, az előbbi összefüggés jobb oldalán álló kifejen! képlethez jutunk. Az előbbi képletek zést bővítjük (n − k )! -sal, és így a V nk = (n − k )! lehetővé teszik, hogy gondolkodás nélkül válaszoljunk nagyon sok bonyolult kérdésre, a képlet megjegyzése azonban önmagában nem elégséges. Nagyon sok feladat megoldásakor könnyebben tudjuk majd hasznosítani a levezetés egy-egy részletét. 3.2.8. Példák a) Hány, csak különböző számjegyet tartalmazó öt- vagy hatjegyű természetes 10! szám létezik? A válasz a 3.2.6. tétel szerint = 10 ⋅ 9 ⋅ 8 ⋅ 7 ⋅ 6 ⋅ 5 = 151200 , 4! mert a tíz lehetséges számjegy közül egy rendezett hatelemű részhalmaz meghatároz egy öt- vagy hatjegyű természetes számot aszerint, hogy a rendezett részhalmaz első eleme nulla vagy sem. Így a megengedett öt- vagy hatjegyű számok száma tíz elem hatodrendű variációinak számával egyenlő. b) Hány olyan természetes szám létezik, amely a 0, 1, 3, 4, 5 és 7 számjegyeken kívül nem tartalmaz más számjegyeket, és ezek legfeljebb egyszer szerepelnek benne? A számokat a számjegyeik száma szerint csoportosítjuk, és az egyes csoportok elemeinek számát külön-külön határozzuk meg. Az adott hat számjegy összes lehetséges 6! sorrendje közül azok, amelyek nullával kezdődnek, nem származtatnak hatjegyű számot. Ezek száma megegyezik az 1, 3, 4, 5 és 7 számok összes lehetséges sorrendjének számával, tehát P5 -tel. Így a hatjegyű számok száma: P6 − P5 = 6!−5!= 720 − 120 = 600 . Ha az ötelemű rendezett részhalmazok számából kivonjuk azoknak az ötelemű rendezett halmazoknak a számát, amelyek 0-val kezdődnek, éppen az

ötjegyű számok számát kapjuk, tehát V65 − V54 = 6!−5! = 720 − 120 = 600 . Hasonló gondolatmenettel – a négyjegyű számok száma: V64 − V53 = 6 ⋅ 5 ⋅ 4 ⋅ 3 − 5 ⋅ 4 ⋅ 3 = 300 ; – a háromjegyű számok száma: V63 − V52 = 6 ⋅ 5 ⋅ 4 − 5 ⋅ 4 = 100 ; – a kétjegyű számok száma: V62 − V51 = 6 ⋅ 5 − 5 = 25 ; – az egyjegyű számok száma: V61 = 6 (a nulla is egyjegyű). Ez összesen 1+5+25+100+300+600+600=1631 szám. II.3.3. Kombinációk 3.3.1. Feladat. A terroristák hat túsz közül kettőt szabadon akarnak engedni. Hány különböző módon lehetséges ez? Ha a túszok közt két rendőr van, és a terroristák véletlenszerűen választják a két szabadon bocsátandó túszt, mi a valószínűsége annak, hogy egyik rendőr sem szabadul ki?

Fejezet tartalma

Tartalomjegyzék 51


Megoldás. Számozzuk meg a túszokat 1-től 6-ig. Mivel a túszokat egyszerre engedik szabadon itt nem a rendezett elempárokat kell megszámolnunk, hanem az {1, 2, 3, 4, 5, 6 } halmaz kételemű részhalmazait. Ezeket az alábbi táblázatba foglaltuk össze:

{1, 2} {1, 3} {1, 4} {1, 5} {1, 6}

{2, 3} {2, 4} {2, 5} {2, 6}

{3, 4} {3, 5} {3, 6}

{4, 5} {4, 6}

{5, 6}

Tehát az első kérdésre a válasz: 15. Ha a két rendőrt az 1-es, illetve a 2-es számmal jelöltük, akkor az előbbi táblázatból leolvasható a kedvező esetek száma is. Azoknak a részhalmazoknak a száma, amelyek nem tartalmazzák sem az 1-est, sem a 2-est, 6 2 = . pontosan 6. A keresett valószínűség tehát 15 5 Ellenőrizd, hogy az eredmény nem függ attól, hogy milyen számokkal jelöltük a rendőröket! Hasonlítsd össze ezt a táblázatot a 3.2.1. feladat megoldásában szereplő táblázattal! 3.3.2. Feladat. Hogyan változik a lehetőségek száma, ha a 3.3.1. feladatban három túszt engednek szabadon? Megoldás. Ha előbb kiválasztanak két embert (15 lehetőség) és a megmaradt 4 közül még egyet (4 lehetőség), akkor ez összesen15 ⋅ 4 = 60 lehetőség. Az így kapott hármas csoportok tagjai közül egy (akit utolsónak választottak) meg van jelölve. Az ilyen hármasokat úgy is megszámolhatjuk, hogy előbb létrehozzuk az összes háromtagú csoportot (ezek száma legyen c), majd minden csoportból az összes lehetséges módon kijelölünk egy-egy tagot. Így 3 ⋅ c csoportot kapunk. Mivel mindkét esetben ugyanazokat a csoportokat számláltuk, a két eredmény egyenlő, tehát 4 ⋅ 15 60 = 3 ⋅ c . Innen c = = 20 . 3 Ugyanezt megközelíthetjük másféleképpen is. Jelöljük A-val az {1, 2, 3, 4, 5, 6 } halmazt. Képzeljük el, hogy felírtuk egy nagy kartonlapra az A összes harmadrendű variációját és egy másik lapra az összes háromelemű részhalmazát. Ha egy harmadik kartonra minden részhalmaz helyett a belőle képezhető összes rendezett részhalmazt írjuk, akkor ugyanazokat a rendezett halmazokat kapjuk, amelyek az első lapon szerepelnek. Tehát, ha c darab háromelemű részhalmaz létezik, akkor a harmadik lapon 6 ⋅ c darab rendezett halmaz jelenik meg. A 3.2.6. tétel szerint az első lapon 6 ⋅ 5 ⋅ 4 = 120 rendezett halmaz van, tehát 120 = 6 ⋅ c . Akárcsak az előbb, innen is kifejezhetjük a c-t, és ugyanazt az értéket kapjuk, mint a másik módszerrel. Így V3 3 levezettük a variációk, kombinációk és permutációk közti összefüggést: C10 = 10 . P3 Látható, hogy mindkét ötlet hasznos lehet az általános probléma megoldásában is. Előbb fogalmazzuk meg az általános esetet, és vezessünk be néhány jelölést.

Fejezet tartalma

52

Tartalomjegyzék


3.3.3. Értelmezés és jelölés 1. Valamely n elemű halmaz k elemű részhalmazát a halmaz egy k-ad osztályú kombinációjának nevezzük. 2. Valamely n elemű halmaz k-ad osztályú kombinációinak (vagy k elemű részhalmazainak) számát C nk -val jelöljük (n, k∈N). 3.3.4. Feladat. Bizonyítsátok be a következő egyenlőségeket: a) C nk = Cnn − k , ha 0 ≤ k ≤ n (kiegészítő kombinációk képlete);

b) (k + 1) ⋅ C nk +1 = (n − k ) ⋅ C nk , ha 0 ≤ k ≤ n − 1 . Bizonyítás. a) A bal oldal egy n elemű X halmaz k elemű részhalmazainak száma. Minden R részhalmazhoz rendeljük hozzá a komplementerét ( X \ R -et). Így minden k elemű részhalmazhoz hozzárendelünk egyetlen n–k elemű részhalmazt. Az is látható, hogy különböző halmazokhoz különböző részhalmazokat rendelünk, tehát ugyanannyi

n–k elemű részhalmaz létezik, mint amennyi k elemű. Ezt éppen a C nk = Cnn − k összefüggés fejezi ki. b) Tekintsünk egy, n tagú társaságot, és válasszunk ki közülük egy k+1 tagú bizottságot, valamint a bizottságban egy elnököt. A pontosság kedvéért nevezzünk működésképtelennek egy bizottságot, ha még nincs elnöke, és működőképesnek, ha már megválasztották az elnököt is. Vizsgáljuk meg, hány különböző összetételű működőképes bizottság jöhet létre? (Elvben ugyanazt kell tennünk, mint a 3.3.3. feladatban.) A jelöléseink alapján C nk +1 működésképtelen bizottságot választhatunk. Mivel a k +1 tag közül bárki lehet elnök, minden ilyen bizottságból k +1 különböző működőképes bizottság jöhet létre, tehát a lehetséges működőképes bizottságok száma

(k + 1) ⋅ Cnk +1 .

Másrészt, egy ilyen bizottság úgy is kijelölhető, hogy előbb a

bizottságnak k tagját, majd az elnökét választjuk ki. A k tagot Cnk különböző módon választanunk ki és minden ilyen k taghoz a megmaradt (n − k ) közül kell egy elnököt válasszunk. Ez (n − k ) ⋅ C nk különböző működőképes bizottságot jelent. Mivel mindkét esetben ugyanazokat a bizottságokat számoltuk, a két eredménynek egyenlőnek kell lennie, tehát a kívánt egyenlőséget igazoltuk. Megjegyzés. Ha előbb a bizottság elnökét választjuk meg és csak ezután a tagokat, akkor az n ⋅ Cnk−1 eredményhez jutunk, tehát (k + 1) ⋅ C nk +1 = (n − k ) ⋅ C nk = n ⋅ C nk−1 .

Akárcsak a permutációk vagy a variációk esetén az általános képletet itt is azonnal levezethetjük az előbbi egyenlőség többszöri felhasználásával. Az eredményt a következő tételben foglaltuk: 3.3.5. Tétel. Ha 0 ≤ k ≤ n (n, k∈N), akkor n! C nk = k ! ⋅ (n − k )! Bizonyítás. A (3.3.4) összefüggésbe k helyett rendre az 1, 2, 3, 4,…, k–1 értéket helyettesítjük, majd a kapott egyenlőségeket összeszorozzuk:

Fejezet tartalma

Tartalomjegyzék


53

k ⋅ C nk = (n − k + 1) ⋅ C nk −1

(k − 1) ⋅ Cnk −1 = (n − k + 2) ⋅ Cnk − 2 (k − 2) ⋅ Cnk − 2 = (n − k + 3) ⋅ Cnk − 2 ........................................ 3 ⋅ C n3 = (n − 2 ) ⋅ C n2

2 ⋅ C n2 = (n − 1) ⋅ C n1 Cn1 = n

k!⋅C nk = (n − k + 1) ⋅ (n − k + 2) ⋅ ... ⋅ n Ha az utolsó egyenlőség jobb oldalán álló kifejezést bővítjük (n − k )! -sal és kifejezzük

a C nk számot, éppen a tételben szereplő kifejezéshez jutunk1. 3.3.6. Megjegyzés. A 3.3.2. feladat kartonlapos megoldását is általánosíthatjuk. Jelöljünk A-val egy n-elemű halmazt. Képzeljük el, hogy felírtuk egy nagy kartonlapra az A összes k-ad rendű variációját Vnk darab és egy másik lapra az összes k elemű

(

C nk

)

(

)

darab . Ha egy harmadik kartonra minden részhalmaz helyett a belőle részhalmazát képezhető összes rendezett részhalmazt (permutációt) írjuk, akkor ugyanazokat a rendezett halmazokat kapjuk, amelyek az első lapon szerepelnek. De egy részhalmaz pontosan k ! rendezett részhalmazt származtat, így a harmadik lapon k !⋅ C nk darab rendezett halmaz n! jelenik meg. A 3.2.6. tétel szerint az első lapon Vnk = rendezett halmaz van, tehát (n − k )!

Vnk n! = . Pk k !⋅ (n − k )! 3.3.7. Feladat. Bizonyítsuk be az alábbi összefüggéseket valamilyen számlálásra C nk =

hivatkozva, majd a C nm számokra felírt képleteket használva!

Cnm C nm++11 = m +1 n +1 Megoldás. a) Az egyenlőség bal oldala az {1, 2, 3,..., n } halmaz m elemű részhalmazainak a száma. Osszuk a részhalmazokat két csoportba: az első csoportba azok a részhalmazok kerüljenek, amelyek nem tartalmazzák n-et, és a másodikba azok, amelyek tartalmazzák. Az első csoportbeli halmazok minden elemét az 1, 2, 3,…, n–1 közül kell a) C nm = C nm−1 + C nm−−11 ;

b)

kiválasztanunk, tehát C nm−1 ilyen részhalmaz létezik. A második csoportbeli részhalmazoknak egy eleme rögzített (az n), és a többi (m–1)-et az 1, 2, 3,…, n–1 közül kell kiválasztanunk, tehát C nm−−11 ilyen részhalmaz van. Mivel minden m elemű részhalmaz csak az egyik csoportba tartozik, a két csoport elemeinek számát összeadva az összes m elemű részhalmazok számát kell kapnunk. Tehát igazoltuk a kért egyenlőséget. 1

Ha n < k , a C nk értéke nulla, hisz egy n elemű halmaznak nincs k elemű részhalmaza.

Fejezet tartalma

Tartalomjegyzék 54


Ha a C nm számok képletét használjuk, a bizonyítás mechanikus számolásra redukálódik: (n − 1)! + (n − 1)! (n − 1)! 1  1 C nm−1 + C nm−−11 = = ⋅ + = m !⋅ (n − m − 1)! (m − 1)!⋅ (n − m )! (m − 1)!⋅ (n − m − 1)!  m n − m  =

(n − 1)! n! n ⋅ = = C nm (m − 1)!⋅ (n − m − 1)! m ⋅ (n − m ) m !⋅ (n − m )!

b) Ezt már a 3.3.4. feladat megoldása után tett megjegyzésben igazoltuk (n helyett (n+1)-et és k helyett m-et kell helyettesítenünk). A képleteken alapuló bizonyítás a következő: C nm++11 Cm (n + 1)! n! 1 1 = ⋅ = ⋅ = n . n + 1 n + 1 (m + 1)!⋅ (n − m )! m + 1 m !⋅ (n − m )! m + 1 II.3.4. A Pascal-háromszög és a C nk számok mértani értelmezése 3.4.1. Feladat. Az következő ábra minden mezőjére írjuk rá, hogy hány különböző úton lehet odajutni, ha egy mezőről csak a jobb oldali vagy az alatta levő mezőre léphetünk! Néhány mezőre már ráírtuk a megfelelő számot. Írd rá a többire is!

A

1

1

1

1

1

1

2

1

3

6

10 15

21

1

4

10

20 35

1

5

15

35 70

1

6

21

1

7

1

8

1

1

B

Világos, hogy az első sor és az első oszlop minden mezején 1 áll. A lépésszabályok szerint minden mezőre a bal oldali és a fölötte álló mezőn elhelyezett számok összege kerül. Látható, hogy ezzel a módszerrel és kellő türelemmel kiszámolhatjuk bármely tetszőlegesen nagy tábla bármely mezejére írt számot. Ha azonban arra gondolunk, hogy a 120-dik sorban és 120-dik oszlopban elhelyezett számot szeretnénk kiszámolni, (vagy akár nagyságát becsülni) valószínű, hogy inkább egy más módszert próbálunk találni. Ha az m-edik sorban és n-edik oszlopban található mezőre szeretnénk érni, akkor n − 1 vízszintes és m − 1 függőleges lépést kell tennünk, tehát az összes lehetséges ilyen út n − 1 vízszintes és m − 1 függőleges lépést tartalmaz. Ha valakinek le szeretnénk írni egy ilyen utat, akkor elégséges lenne m + n − 2 számú betűt írnunk: v-t minden vízszintes lépésre és f-et minden függőleges lépésre. Az ábrán szürkével

Fejezet tartalma

Tartalomjegyzék 55


jelzett út a vffvvvff jelsorozattal írható le. Mivel az n − 1 darab v betűt és m − 1 darab f betűt tartalmazó jelsorozat egyértelműen meghatározza az utat és fordítva, elégséges az ilyen jelsorozatok számát meghatározni. Egy jelsorozat egyértelműen meghatározott, ha az m + n − 2 helyből kijelölünk m − 1 -et (ide kerülnek a v betűk és a többi helyre az f betűk). Ezt a 3.3.5. tétel szerint C mm+−1n − 2 különböző módon tehetjük meg, tehát az m-edik sorban és n-edik oszlopban C mm+−1n − 2 áll. Ennek alapján a táblázatba írjuk be a C nk számokat, és vizsgáljuk meg az indexeket! A

3 C10 C 22 C 3 C 44 C 55 C 66 C 77

4 C10 C 21 C32 C 43 C 5

C 20 C 31 C 42 C 53 C 30 C 41 C52 C 40 C 51

C 50 C 60 C 70

B

Látható, hogy az AB átlóra merőleges irány mentén az alsó indexek nem változnak. Ezt jobban látjuk, ha a táblázatot elfordítjuk úgy, hogy az AB átló függőleges legyen. Az így kapott háromszögalakú táblázatot Pascal-háromszögnek nevezzük. A 3.3.4. feladat a) pontja alapján a szélektől egyforma távolságra levő számok egymással egyenlők. A feladat első megoldását (vagy a 3.3.7. feladat b) pontját) figyelembe véve a C nk számok (és a Pascal-háromszög) egyszerű generálási szabályához jutunk. Minden sorban az első és utolsó elem az 1, és a többi elem a fölötte álló két szám összege (lásd az ábrát). 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 II.3.5. Newton binomiális tétele 3.5.1. Feladat. Számítsuk ki (a + b )n -t, ha n ∈ {1, 2, 3, 4, 5 } , majd hasonlítsuk össze az együtthatókat a Pascal-háromszög elemeivel!

Tartalomjegyzék

Fejezet tartalma

56


Megoldás. Ha n ∈ { 0, 1, 2, 3 } , a kifejtéseket már az elmúlt évek tananyagából ismerjük. Mi ezeket beírtuk az alábbi táblázatba, a te feladatod az, hogy kitöltsd a következő két sort még mielőtt tovább olvasnád a könyvet! Binom: Kifejtés: Együtthatók: 0 1 1 ( a + b) =

(a + b)1 =

a+b

(a + b ) = (a + b )3 = (a + b )4 = (a + b )5 = 2

2

1

a + 2ab + b

2

1

a 3 + 3a 2 b + 3ab 2 + b 3

1 2

1

1 3 3 1 ……………

a 4 + ... a 3b + ... a 2 b 2 + .... ab 3 + ... b 4

…………… a 5 + ... a 4 b + ... a 3b 2 + ... a 2 b 3 + .... ab 4 + ... b 5 A táblázat alapján a következő sejtésünk alakulhat ki: az a kitevői (akárcsak az I. fejezet 3.3.2. tételében) egyesével csökkennek, a b kitevői egyesével növekednek, és a tagok együtthatói pedig a Pascal-háromszög megfelelő sorának elemeivel egyenlőek. Mindezt az (a + b) n = C n0 ⋅ a n + C n1 ⋅ a n−1b + C n2 ⋅ a n− 2 b 2 + ... + C nn−1 ⋅ ab n−1 + C nn ⋅ b n n

egyenlőségbe foglalhatjuk össze. Ezt tömörebben az (a + b) n = ∑ C nk ⋅ a n −k b k k =0

alakban írhatjuk. Ha a kifejtés tagjait T1-gyel, T2-vel, T3-mal,..., Tn-nel és Tn +1 -gyel jelöljük, akkor sejtésünk szerint T1 = C n0 ⋅ a n , T2 = C n1 ⋅ a n−1b1 , és általában

Tk +1 = C nk ⋅ a n− k b k , ha k ∈ { 0, 1, 2, 3, 4,..., n} . A következő tétel a sejtésünk helyességére vonatkozik:

3.5.2. Tétel (Newton binomiális tétele) n

Ha a és b két valós szám és n ∈ N , akkor (a + b ) n = ∑ C nk ⋅ a n− k b k .

(7)

k =0

Bizonyítás. A matematikai indukció módszerét használjuk. A 3.5.1. feladatban láttuk, hogy n ∈ { 0, 1, 2, 3, 4, 5 } esetén a tétel állítása igaz. Tételezzük fel, hogy a

tétel állítása igaz n-re, és számítsuk ki az (a + b) n+1 -t. n  n  (a + b) n+1 = (a + b) ⋅ (a + b) n = ( a + b) ⋅  ∑ C nk ⋅ a n−k b k  = ∑ C nk ⋅ a n+1−k b k +  k =0  k =0 n

n

n

n

+ ∑ C nk ⋅ a n− k b k +1 = ∑ C nk ⋅ a n +1− k b k + ∑ C nk ⋅ a ( n+1) −( k +1) b k +1 = ∑ C nk ⋅ a n +1− k b k + k =0

k =0

k =0

n +1

k =0

n

n

+ ∑ C nk −1 ⋅ a n +1− k b k = a n+1 + ∑ C nk ⋅ a n +1− k b k + ∑ C nk −1 ⋅ a n +1− k b k + b n+1 = k =1

n

(

)

k =1

k =1

n +1

= a n+1 + ∑ C nk + C nk −1 ⋅ a n+1−k b k + b n+1 = ∑ C nk+1 ⋅ a n +1− k b k k =1

k =0

Az előbbi egyenlőségekben felhasználtuk a C n0+1 = C nn++11 = C n0 = C nn = 1 összefüggéseket.

(8)

C nk + C nk −1 = C nk+1 , valamint a

Fejezet tartalma

Tartalomjegyzék


57

A (8) egyenlőség és a matematikai indukció elve alapján a tétel állítása igaz ∀ n ∈ N esetén. 3.5.3. Megjegyzések n−k 1. A C nk +1 = ⋅ C nk összefüggés alapján a kifejtés együtthatói rekurzív módon is k +1 megkaphatók a következő szabály szerint: – az első együttható 1, és a következő megegyezik a binom kitevőjével; – a (k+2)-dik tag együtthatóját, a Cnk +1 megkaphatjuk, ha a (k+1)-edik tag

együtthatóját, a Cnk szorozzuk az a-nak a (k+1)-edik tagban szereplő kitevőjével, (n–k)-val és osztjuk az illető tag sorszámával, (k+1)-gyel. A szabály felhasznásával megkezdhetjük az (a + b)10 kifejtés együtthatóit írni. Folytasd a megkezdett kifejtést: 10 ⋅ 9 8 2 45 ⋅ 8 7 3 ⋅a b + ⋅ a b + ................................. (a + b)10 = a 10 + 10 ⋅ a 9 b + 2 3 2. A tétel bizonyítását direkt kombinatorikus meggondolásokra is építhetjük. Ehhez csak annyit kell tudjunk, hogy két vagy több polinomot úgy szorzunk össze, hogy mindenik tényezőből választunk egy-egy monomot, ezeket összeszorozzuk, majd az összes lehetséges ilyen szorzatot összeadjuk. Ennek alapján az (a + b) n = (a + b) ⋅ ( a + b) ⋅ (a + b) ⋅ ... ⋅ (a + b) szorzatból úgy kaphatunk a n − k b k

n − szer

alakú szorzatot, hogy k darab zárójelből b-t választunk és a többiből a-t. Ezt viszont C nk módon tehetjük meg, tehát C nk darab a n − k b k alakú tagot kapunk, ha elvégezzük a kijelölt szorzásokat. Ezeket összevonjuk, így az a n − k b k együtthatója éppen C nk lesz. 3.5.4. Alkalmazás Számítsuk ki az alábbi összegeket! a) S 0 = C n0 + C n1 + C n2 + ... + C nn ; b) S1 = C n0 + C n2 + C n4 + C n6 + ... ; n

c) S 2 = ∑ 2 k ⋅ C nk k =0

Megoldás a) A (7)-es összefüggésben alkalmazzuk az a = b = 1 helyettesítést: n

2 n = (1 + 1) n = ∑ C nk = S 0 , k =0

n

tehát a keresett összeg értéke 2 .

Fejezet tartalma

Tartalomjegyzék 58


b) Jelöljük S 3 -mal a C n1 + C n3 + C n5 + ... összeget. Ha a (7) összefüggésbe a = 1n

et és b = 1-et helyettesítünk, a 0 n = (1 − 1) n = ∑ (−1) k C nk egyenlőséghez jutunk, k =0

tehát 0 = S1 − S 4 . Az a) pont alapján S1 + S 3 = S 0 = 2 n , tehát S1 = S 3 = 2 n −1 . c) A (7)-es összefüggésbből az a = 1 és b = 2 helyettesítéssel kapjuk, hogy: n

3 n = (1 + 2) n = ∑ 2 k C nk = S 2 , k =0

n

tehát a keresett összeg értéke 3 . Megjegyzés. Mivel C nk az n elemű halmaz k elemű részhalmazainak a száma, az S 0 összeg egyenlő az n elemű halmaz összes részhalmazának számával. Ezt megszámolhatjuk a következőképpen is: jelöljünk A-val egy n elemű halmazt és ai -

vel az elemeit i = 1, n . Az A minden X részhalmazához rendeljük hozzá azt a kettes számrendszerbeli, legfennebb n-jegyű számot, amelynek az i-edik jegye 1 vagy 0, aszerint, hogy ai eleme X-nek vagy sem. Például A = {1, 2, 3, 4, 5, 6, 7 } és a k = k esetén ( k = 1, 7 ), az X = { 3, 5, 7 } részhalmazhoz a 0010101 számot rendeljük és az Y = {1, 2, 5, 6 } halmazhoz az 1100110 számot. Látható, hogy így megkapjuk az összes, legfennebb n-jegyű kettes számrendszerbeli számot, és különböző halmazokhoz különböző számok tartoznak2. Másrészt, a kettes számrendszerben pontosan 2n, legfennebb n-jegyű szám van (0-tól 2 n − 1 = 11 ...1 -ig), tehát az A N n − szer

n

részhalmazainak száma is 2 . Hasonló meggondolások alapján a másik két összeg is kiszámítható. Próbáljatok meg egy-egy olyan számlálási feladatot találni, amelynek segítségével ki tudjátok számolni a másik két összeget is! II.3.6. Megoldott feladatok 1. Az alábbi ábrán az A-val jelzett mezőről a B-vel jelzett mezőre kell eljutnunk. Hány különböző módon lehetséges ez, ha egy mezőről csak a jobb oldali, vagy a fölötte álló szomszédos mezőre lehet lépni? Hogyan változik a lehetséges utak száma, ha n sort és n oszlopot tartalmaz az ábra? B

A

2

Az így szerkesztett szám az X karakterisztikus függvényének a rendezett képhalmaza .

Fejezet tartalma

Tartalomjegyzék


59

Megoldás. Egy konkrét n-re a megoldás különösebb ötletek nélkül megkapható, hisz minden mezőre ráírjuk az oda vezető utak számát. Jóval nehezebb a dolgunk, ha az Aból B-be vezető utakat más módszerrel szeretnénk megszámolni. Vizsgáljuk meg, mi

az összefüggés (egyáltalán van-e összefüggés) a C nk számok geometriai értelmezése és a mi feladatunk közt. E célból egészítsük ki az adott táblát úgy, hogy egy négyzet alakú táblán dolgozzunk (lásd a következő ábrát). Így megváltozott az A-ból B-be vezető utak száma. A kiegészített táblán az A-ból B-be vezető utak közül azokat nevezzük „jó”-nak, amelyek csak az eredeti ábra mezőit érintik, a többit „rossz”-nak. Az új táblán az A-ból a B-be összesen C 2nn−−1 2 út vezet (lásd 3.4.1. feladat megoldását). A „jó” utak számát megkaphatjuk, ha az összes út számából kivonjuk a „rossz” utak számát. Minden rossz út metszi az ábrán látható a átlót, tehát a rossz úton haladva lesz egy legelső pillanat, amikor elérjük az a átlót. Szerkesszük meg az út e részének az a egyenes szerinti szimmetrikusát. Az alábbi ábrán a vékony vonal egy rossz utat ábrázol, a fekete csomópont az a egyenessel való metszéspontját jelöli, és a vastag vonal a metszéspont előtti rész a szerinti szimmetrikusát. Ez azt jelenti, hogy a táblát még egy oszloppal ki kell bővítenünk. a

Az előbbi szerkesztés eredményeként egy olyan utat kapunk, amely a P-vel jelzett mezőről indul. Az is belátható, hogy minden P-ből B-be vezető út pontosan egy rossz útnak felel meg, tehát a „rossz” utak száma C 2nn − 2 . Így a „jó” utak száma 1 C 2nn−−12 − C 2nn − 2 = ⋅ C 2nn−−12 . n n

2. Számítsuk ki az S (n) = ∑ k ⋅ C nk összeget! k =1

1. megoldás. Vizsgáljuk meg a k ⋅ C nk kifejezést, és próbáljuk az első tényezőt

beolvasztani a C nk kifejezésbe! (n − 1)! = n ⋅ C k −1 n! n! k ⋅ C nk = k ⋅ = = n⋅ n −1 (k − 1)!⋅ (n − k )! k !⋅ (n − k )! (k − 1)!⋅ (n − k )! A kiszámítandó összeget a következőképpen alakíthatjuk:

Tartalomjegyzék

Fejezet tartalma

60

Számlálási feladatok. A kombinatorika elemei n

n

n

k =1

k =1

k =1

(

)

k k −1 k −1 0 1 2 n −1 n ∑ k ⋅ C n = ∑ n ⋅ C n−1 = n ⋅ ∑ C n−1 = n ⋅ C n−1 + C n−1 + C n−1 + ... + C n−1 = n ⋅ 2 .

Az utolsó egyenlőséget 3.5.4. feladat alapján kaptuk. A keresett összeg tehát: S ( n) = n ⋅ 2 n . 2. megoldás. Találjunk egy olyan számlálási feladatot, amelynek S (n) az eredménye, és amelyet rövidebb úton is kiszámolhatunk. Mivel az összeg minden tagjában az alsó index ugyanaz, válasszunk egy n elemű halmazt, a szemléletesség kedvéért egy n tagú társaságot. A 3.3.4. feladatból tudjuk, hogy a k tagú, elnökkel rendelkező (működőképes) bizottságok száma k ⋅ C nk , így a feladatban szereplő összeg az összes lehetséges (1, 2, 3,…, n tagú) működőképes bizottság száma. Másrészt egy ilyen bizottság egyértelműen meghatározott, ha kijelöljük az elnököt és a többi n–1 tag közül néhányat. Az elnök kijelölésére n lehetőségünk van, míg a további tagság megválasztására 2 n −1 (az n–1 tagból alkotott halmaz bármely részhalmazát kiválaszthatjuk, és a 3.5.4. feladatban láttuk, hogy az ilyen részhalmazok száma 2 n −1 ), tehát összesen n ⋅ 2 n működőképes bizottság létezik. 3.6.1. Megjegyzés. A második megoldás előnye az, hogy azonnal általánosítható. Ha a bizottságban nem egy elnököt, hanem egy m tagú vezetőtanácsot kell

kiválasztanunk, akkor k tagú bizottság esetén C nk ⋅ C km lehetőségünk van. Ez azt jelenti, n

hogy az olyan bizottságok száma, amelyben m tagú vezetőtanács van: ∑ C nk ⋅ C km . k =m

Másrészt, ha előbb a vezetőtanácsot jelöljük ki

( C nm

lehetőség) és azután a többi tagot,

akkor 2 n − m ⋅ C nm ilyen bizottságot kaphatunk. Ez azt jelenti, hogy n

k m n−m ⋅ C nm , ha n ≥ m . ∑ Cn ⋅ Ck = 2

k =m

m

3. Számítsuk ki az S n (m) = ∑ (−1) k ⋅ C nk összeget, ha n ≥ 2 . k =0

Megoldás. Szerkesztünk egy polinomot, amelyben az egyik tag együtthatója éppen a

kívánt összeg. A

(−1)k ⋅ C nk

kifejezés az

(1 − x )n

kifejtésében az x k -nak az

m

együtthatója. Ahhoz, hogy az S n (m) = ∑ (−1) k ⋅ C nk összeget megkaphassuk, olyan k =0

polinomokat kell összeadnunk, amelyekben a hatványának együtthatója. Ezért az x

n−k

(−1)k ⋅ C nk

kifejezés x ugyanazon

⋅ (1 − x ) alakú polinomokat adjuk össze. Így n

n

az összegben az x együtthatója S n (m) . Másrészt m

∑x

k =0

n−k

m

(

)

⋅ (1 − x) n = (1 − x )n ⋅ ∑ x n − k = (1 − x )n ⋅ x n − m 1 + x + x 2 + ... + x m = (1 − x) n ⋅ k =0

Tartalomjegyzék

Fejezet tartalma

61


(

)

x m +1 − 1 = (1 − x )n −1 ⋅ x n − m ⋅ 1 − x m +1 = x n − m ⋅ (1 − x )n −1 − x n +1 ⋅ (1 − x )n −1 . x −1 Az x n+1 ⋅ (1 − x )n−1 polinomban nincs n-ed fokú tag (mert minden monom fokszáma ⋅ x n−m ⋅

legalább n+1), tehát az x n − m ⋅ (1 − x )n −1 polinom n-ed fokú tagjának együtthatóját kell

meghatároznunk. Ez éppen az (1 − x )

(− 1)m ⋅ C nm−1 , ha

n −1

kifejtésében az x m együtthatója, vagyis

m < n . Ha m = n , akkor az összeg nem tartalmaz n-ed fokú tagot,

tehát

(− 1)m ⋅ Cnm , k m ( ) ∑ − 1 ⋅ Cn =  m

ha m < n,

0,

k =0

ha m = n.

4. Jelöljük S k (n) -nel az 1k + 2 k + 3 k + ... + (n − 1) k + n k összeget. Bizonyítsuk be, hogy k +1

(n + 1)k +1 − 1 = ∑ Ckm+1 ⋅ S k +1− m ,

∀k ≥ 1.

m =1

k +1

Megoldás. Az (x + 1)k +1 = ∑ C km+1 ⋅ x k +1− m azonosságban x helyére rendre az 1, 2, m=0

3,…, n értéket helyettesítjük, majd a kapott egyenlőségek megfelelő oldalait összeadjuk (a 2.3. paragrafus első részében használt második módszerhez hasonlóan). A (k+1)-dik hatványok közül csak az 1k +1 és (n + 1) k +1 szerepel egy-egy helyen. A többi az egyenlőség mindkét oldalán megjelenik, tehát a végső összegben az S 0 ( n), S1 (n), S 2 (n), …, S k (n) összegek jelennek meg. A számolásokat a következő ábra szemlélteti: + + … + + 1 n k +1 (n + 1) k +1 = C k1 +1 ⋅ n k C kk+1 ⋅ n n k +1

= (n − 1) k +1

+ C 1 ⋅ (n − 1) k k +1

(n − 1)k +1

= (n − 2) k +1

+ C 1 ⋅ ( n − 2) k + … + C k ⋅ ( n − 2) + 1 k +1 k +1

+ … + C k ⋅ (n − 1) + 1 k +1

..................................................................................................................... = + + … + + 1 3 k +1 2 k +1 C1 ⋅ 2k Ck ⋅2 k +1

2 k +1

=

1k +1

+

C k1 +1 ⋅ 1k

(n + 1)k +1

=

1

+

C k1 +1 ⋅ S k (n)

k +1

+ … +

C kk+1 ⋅ 1

+ … + C k ⋅ S ( n) k +1 1

+ 1 + n

Fejezet tartalma

Tartalomjegyzék 62

Számlálási feladatok. A kombinatorika elemei k +1

Ha az utolsó egyenlőséget zárt alakban írjuk, akkor az (n + 1) k +1 − 1 = ∑ C km+1 ⋅ S k +1− m m =1

összefüggést kapjuk, amely éppen a kívánt egyenlőség. Az előbbi összefüggés alapján kiszámíthatjuk az S k (n) értékét minden k-ra. Például

k = 2 esetén az összefüggés alapján (n + 1)3 − 1 = 3 ⋅ S 2 (n) + 3 ⋅ S1 ( n) + S 0 . Mivel n ⋅ (n + 1) n ⋅ ( n + 1) ⋅ (2n + 1) S0(n) = n és S1 (n) = , következik: S 2 (n) = . A k =3 2 6 esetben a bizonyított összefüggésből (n + 1)4 – 1 = 4 S3(n) + 6S2(n) + 4S1(n) + S0(n) 2

 n ⋅ (n + 1)  adódik. Innen, ha kifejezzük az S 3 (n) -et, akkor az S 3 (n) =   egyen2   lőséghez jutunk. Az előbb kiszámolt összegek sok más feladatban megjelenhetnek, ezért érdemes őket megjegyezni. A te feladatod az S 4 (n) és az S 5 ( n) összegek kiszámítása. A könnyebb memorizálás érdekében összesítettük az eddig kiszámolt összegeket. n ⋅ (n + 1) S1 (n) = 2 n ⋅ (n + 1) ⋅ (2n + 1) S 2 ( n) = 6 2

 n ⋅ ( n + 1)  S 3 ( n) =   2   S 4 (n) = ....................

S 5 (n) = ....................

II.4. Gyakorlatok és feladatok 1. Egy tájfutóversenyen részt vevő csapatok a mellékelt térképvázlatot kapták. Feladatuk, hogy A-ból a B, C és D pont érintésével visszajussanak az A-ba. Melyik a legrövidebb útvonal?

2. Janiék osztályában 13 lány és 12 fiú tanul. Találomra kiválasztunk két lányt és egy fiút versmondásra, két lányt és egy fiút színházjegyvásárlásra és két lányt és egy


Tartalomjegyzék 63

fiút tűzoltósági felkészítőre. Hányféleképpen állíthatunk össze ilyen kilenctagú csapatot? 3. Két egyforma kockával egyszerre dobunk. Mennyi a valószínűsége annak, hogy a megjelenő két szám összege 7? 4. Változik-e az előbbi kérdésre adott válasz, ha nem egyforma kockákkal dobunk? 5. Hány különböző módon lehet 10 embert egy kerek asztal köré leültetni? 6. Hány háromszög látható az alábbi ábrán?

Hány háromszöget láthatsz, ha az alapot n, egyenlő részre osztjuk? 7. Hány téglalap látható a mellékelt ábrán?

8. Az 1, 2, 3, 4, 5, 6, 7, 8 és 9 számjegyekből hány darab olyan kilencjegyű szám alkotható, amelynek számjegyei egymástól különbözőek, és a) az 1-es közvetlenül a 2-es előtt áll; b) az 1-es előbb áll, mint a 2-es? 9. Egy pénzérmét n-szer dobunk fel, és lejegyezzük az eredményeket. (Minden dobás eredménye fej vagy írás.) Hány különböző, k darab fejet tartalmazó, fej-írás dobássorozat lehetséges? 10. A 0, 1, 2, 3,..., 2 n − 1 halmaz elemei közül találomra kiválasztunk egyet. Mennyi a valószínűsége annak, hogy a) a kiválasztott szám 2-nek hatványa; b) a szám bináris számjegyeinek3 összege k? 11. Határozd meg az A = { ( X , Y ) X , Y ⊂ {1, 2, 3,..., n }, X ∩ Y = ∅, X ∪ Y = {1, 2, 3,..., n } } és

{

}

B = { ( X , Y ) X , Y ⊂ {1, 2, 3,..., n }, X ∪ Y = {1, 2, 3,..., n } } halmazok elemeinek számát! 12. A sík n pontja legfeljebb hány különböző egyenest határoz meg? A sík négy pontja hány különböző egyenest határozhat meg? 13. Oldd meg az alábbi egyenleteket! a) n ! = 110 ; b) n !+( n + 1) ! = 134 ;

3

Valamely szám bináris számjegyei az illető szám kettes számrendszerbeli felírásában megjelenő számjegyek.

Tartalomjegyzék

Fejezet tartalma

64


n !+ (n − 1) ! = 12 ; (n + 1) ⋅ (n − 2) ! 1 1 1 − = ; e) n ! (n + 1) ! 30 1 1 1 g) k − k = k ; C 4 C5 C6

c)

d)

n! =6; (n − 1) !

f) Vn5 = 18 ⋅ Vn1−2 ; h) C nn++31 = n 2 − 4 ;

2

14.

15.

i) C 3nn +−6n+1 = 660 ; j) C n2 + C n2−3 + C n2− 2 = 19 . Oldd meg a következő egyenletrendszereket! n −1 k  k −1 V2nm−2 = 8 ⋅ V2nm−3  x ⋅ C n −2 + k − 1 ⋅ y = n − 1 a)  b)  . ; 3 ⋅ C 2nm− 2 = 8 ⋅ C 2nm−3  x ⋅ C k −2 − n − 1 ⋅ y = k − 1 n −1 k n −1  Oldd meg az alábbi egyenlőtlenségeket! n −1 n a) C10 > 2 ⋅ C10 ;

16.

17.

b) 5 ⋅ C n3 > C n4+ 2 .

 Cp C p+i   C p C p +i  m − p + 1 Bizonyítsd be, hogy  pm−1 − pm++i −i 1  :  pn−1 − pn++ii−1  = , C m + i   Cn Cn + i  n − p + 1  Cm ha 1 ≤ p ≤ m és 1 ≤ p ≤ n . Számítsd ki a következő összegeket: a) c)

n

∑ k ⋅ k !; k =1 n

b)

k

∑ (k + 1) ! ;

d)

k =1

n

∑ (k + 1) 2 ⋅ k ! ; k =1 n

k+2

∑ k !+(k + 1) !+(k + 2) ! ; k =1

C nk ; k =1k + 1

n

n

e) ∑ k 2 ⋅ C nk ;

f) ∑

k =1

n C nk C nk ; . h) ∑ (−1) k ( k + 1) ⋅ (k + 2) k =1( k + 1) ⋅ ( k + 2) ⋅ ( k + 3) k =1 Bizonyítsd be legalább két különböző módszer segítségével a n

g) ∑

18.

n

k n−k n ∑ C a ⋅ C b = C a +b (Vandermonde-féle) azonosságot!

k =0

19.

Számítsd ki az alábbi összegeket!

( ); ∑ k ⋅ (C ) n

a) ∑ C nk c) 20.

k =0 n k =0

k 2 n

( ); ∑ (−1) ⋅ (C ) n

2

b) ∑ k 2 ⋅ C nk

;

d)

k =0 n

k

k =0

2

k 2 n

.

Bizonyítsd be a következő azonosságokat: n

a) C nn + C nn+1 + C nn+ 2 + ... + C mn = C mn ++11 ; b) ∑ (−1) k −1 ⋅ k =1

1 k 1 1 ⋅ C n = 1 + + ... + ; 2 k n

Tartalomjegyzék

Fejezet tartalma

65

Számlálási feladatok. A kombinatorika elemei m−2

n

c) C 1p + ∑ C 2p++kk = C nn++ 2p +1 ;

d) 2 ⋅ ∑ C mk −1 ⋅ C mk +−11 =

k =0

m −1

e) 2 ⋅ ( −1) n+1 ⋅ ∑ (−1) k ⋅ C nk ⋅ C n2 m− k = k =0

21.

k =0

( )

2 C nm

m −1 ⋅ C 2mm ; 2m − 1

− C nm .

Határozd meg a) a (3x + y − 3)10 kifejtés együtthatóinak összegét; 9

 1   kifejtés hatodik tagját; b) a  3 x + 3 x  n

T  1 1   kifejtésében 7 = ; c) az n értékét, ha a  3 2 + 3 T 6 3  n −5 1 2 d) az  +  3 3

(

e) az 1 + 3 5

120

kifejtés legnagyobb tagját;

)

2001

kifejtés racionális tagjait;

f) az x együtthatóját az (1 + x) n + (1 + x) n−1 kifejtésben (a tagok összevonása után), ha a kifejtésben megjelenő binomiális együtthatók összege 1536; 6

g) az m értékét, ha a (2 + m) m kifejtés legnagyobb tagja a tizedik tag; h) azt, hogy az együtthatója! 22.

(2 x + x )

2 2001

(

Bizonyítsd be, hogy a 2 + 3

(

és hogy a 2 + 3

)

2001

kifejtés hányadik tagjának a legnagyobb az

)

2001

(

+ 2− 3

szám egészrésze páratlan!

)

2001

(

kifejezés értéke egész szám,

)

2001

23. Legkevesebb hány irracionális tagja van a n+4n kifejtésnek, ha n természetes szám, és n nem írható fel egyetlen természetes szám negyedik hatványaként sem? 24. Egy n oldalú konvex sokszögben meghúzzuk az átlókat. Legtöbb hány belső metszéspont keletkezhet? 25. A hadsereg fegyverraktára a mellékelt ábrán az R-rel jelölt mezőn található, míg a hadtest a H-val jelölt mezőn állomásozik. A raktárból fegyverszállítmányt kell eljuttatni a hadtesthez. A szállítmány minden mezőről a jobb oldali vagy az alatta elhelyezkedő szomszédos mezőre juthat át. Néhány gerilla aláaknázta a szürkével befestett mezőket. Ha a szállítmány egy ilyen mezőre kerül, akkor felrobban. Mennyi a valószínűsége annak, hogy a hadtest hozzájusson a szállítmányhoz?

R


Tartalomjegyzék 66

H Ha csak egy mezőt tudnának aláaknázni a gerillák, és ez nem lehet a vastag vonallal bekerített részen, melyik mezőt érdemes aláaknázni ahhoz, hogy a szállítmány felrobbanásának valószínűsége a lehető legnagyobb legyen? 26. Egy csomag franciakártyát megkevertünk, majd egyesével kihúzzuk a lapokat. Hányadik helyen a legvalószínűbb a második ász kihúzása? 27. Lehetséges-e két kockát úgy cinkelni, hogy a feldobásuk után a kapott számokat összeadva azonos valószínűséggel jelenjen meg minden lehetséges összeg? 28. Mennyi a valószínűsége annak, hogy ha két egyforma kockával dobunk 24 dobásból lesz egy dupla hatosunk? 29. Bizonyítsd be, hogy ha egy pénzérmét 200-szor feldobunk, akkor 95%-nál nagyobb annak a valószínűsége, hogy legalább hat egymás utáni fej vagy hat egymás utáni írás lesz! 30.

n

Számítsd ki az S n = ∑ ( −1) k ⋅ C nk ⋅ C 3nn−k összeget! k =0

(Megyei olimpia, 1997, Maros megye) 31. Bizonyítsd be, hogy a és C nn −1 számok legnagyobb közös osztója akkor és akkor a 2, ha az n a 2-nek hatványa!

C n1 ,

32.

C n2 ,...,

C nn − 2

Ha m, n ∈ N , n ≠ 0 és m ≤ n , jelöljük S m -mel a C n0 + C n1 + C n2 + ... + C nm

összeget. Bizonyítsd be, hogy C n0 ⋅ S 0 + C n1 ⋅ S1 + ... + C nn ⋅ S n = 2 2 n −1 + C 2nn−−11 . (Országos olimpia, 1993) 33. Határozd meg az (x n )n∈N sorozat általános tagjának képletét, ha 4 ⋅ (2n − 1) ⋅ xn −1 , ∀ n ≥ 1 . n +1 (Hegyi Lajos emlékverseny, 1998) 34. Az alábbi háromszög képzési szabálya ugyanaz, mint a Pascal-háromszögnek csak az n-edik sor első és utolsó eleme minden n ≥ 1 esetén éppen n. Határozd meg az n-edik sor k-edik elemének képletét! 1 2 2 3 4 3 4 7 7 4 5 11 14 11 5 6 16 25 25 16 6 x 0 = 1, x1 = 2 és xn +1 = 2 ⋅ xn +

Tovább

II. FEJEZET SZÁMLÁLÁSI FELADATOK. A KOMBINATORIKA ELEMEI II.1. Valószínűségszámítási feladatok

Recommend Documents