Read Kombinatorika.pdf text version

VI. KOMBINATORIKA

Kombinatorika është degë e matematikës që merret me njehsimin e numrit të mënyrave sipas të cilave mund të kryhet një proces. Në nivel elementar, kombinatorika, zakonisht konsiderohet si degë e matematikës diskrete. Ajo ka zbatim të madh edhe në degët e ndryshme të matematikës, shkencës kompjuterike si dhe në shkencat tjera natyrore dhe teknike. Gjatë këtij kapitulli kryesisht do të mësojmë teknikat themelore kombinatoriale që zbatohen gjatë zgjidhjes së problemeve të ndryshme.

1. RREGULLA E SHUMËS DHE RREGULLA E PRODHIMIT

a) RREGULLA E SHUMËS

Nëse një ngjarje mund të zhvillohet në m mënyra dhe ngjarja tjetër në n mënyra, dhe nëse këto dy ngjarje nuk ndodhin njëkohësisht, atëherë njëra nga këto dy ngjarje mund të ndodh në m + n mënyra. Në përgjithësi, nëse Ei (i = 1,2,..., k ) janë k ngjarje ashtu që asnjë dyshe e tyre nuk ndodh njëkohësisht dhe nëse Ei mund të ndodh në ni mënyra, atëherë njëra nga k ngjarjet mund të ndodh në n1 + n2 + ... + nk mënyra. Le të ilustrojmë këtë me anë të shembujve vijues: Shembulli 1. Nëse klasa ka 11 djem dhe 9 vajza, atëherë kemi 11 + 9 = 20 mënyra që të zgjedhim 1 student (djalë ose vajzë) si përfaqësues i klasës. Shembulli 2. Le të jetë A ngjarja që të zgjedhet numri i thjesht më i vogël se 10 dhe B ngjarja që të zgjedhet numri çift më i vogël se 10. Atëherë ngjarja A mund të ndodh në këto raste:

2,3,5,7.

Pra gjithsejtë në 4 raste. Ngjarja B mund të ndodh në rastet:

2,4,6,8.

Pra në 4 raste.

SISTEMET DISKRETE

61

Meqë 2 është numri i thjesht çift, atëherë ngjarja A dhe B mund të ndodh në 4 + 4 - 1 = 7 raste. Detyra për ushtrime të pavarura 1. Le të jetë A ngjarja që të zgjidhet numri i thjesht më i vogël se 20 dhe B ngjarja që të zgjidhet numri tek më i vogël se 20. Në sa raste mund të ndodh ngjarja A ose B? 2. Le të jetë A ngjarja që të zgjidhet numri i thjesht më i vogël se 20 dhe B ngjarja që të zgjidhet numri tek më i vogël se 15. Në sa raste mund të ndodh ngjarja A ose B?

b) RREGULLA E PRODHIMIT

Nëse një ngjarje mund të paraqitet në m mënyra dhe ngjarja tjetër në n mënyra dhe nëse numri i mënyrave të paraqitjes së ngjarjes së dytë nuk varet nga fakti se si ndodh ngjarja e parë, atëherë të dy ngjarjet njëkohësisht mund të paraqiten në m n mënyra. Në përgjithësi Ei (i = 1,2,..., k ) janë k ngjarje dhe nëse E1 mund të ndodh në n1 mënyra, E2 në n2 mënyra (pa marrë parasysh si zhvillohet ngjarja E1 ), E3 mund të ndodh në n3 mënyra (pa marrë parasysh si zhvillohen ngjarjet E1 , E2 ,..., Ek ) zhvillohen në nk mënyra (pa marrë parasysh si zhvillohen ngjarjet E1 , E2 ,..., Ek -1 ) atëherë k ngjarjet njëkohësisht mund të ndodhin në n1 n2 ... nk mënyra. Le të shohim këtë me anë të shembujve vijues: Shembulli 3. Në shitoren e automobilave në shitje janë 5 lloje automobilash: MERCEDES, BMW, AUDI, GOLF, OPEL. Secili nga automobilat ka tri nënlloje ngjyrash: E KUQE, E KALTËR, E BARDHË. Sa lloje të automobilave gjenden në shitore? Zgjidhja. Meqë janë 5 lloje automobilash dhe secili lloj ka nga tri nënlloje në shitore gjithsej janë 5 3 = 15 automobila. Kombinimet janë paraqitur në figurë e mëposhtme.

Përgatitur nga Armend Shabani

www.armendshabani.org

62

UNIVERSITETI PER BIZNES DHE TEKNOLOGJI

KUQE MERCEDES KALTËR BARDHË KUQE BMW KALTËR BARDHË KUQE AUDI KALTËR BARDHË KUQE GOLF KALTËR BARDHË KUQE OPEL KALTËR BARDHË

Problemi mund të shprehet edhe me anë të kuptimit të bashkësive. Le të jetë A bashkësia e automobilave dhe C bashkësia e ngjarjeve. Automobili OPEL me ngjyrë të KALTËR konsiderohet si dyshe e renditur (OPEL, KALTËR). Kështu bashkësia e të gjitha dysheve të renditura është prodhimi kartezian A × C , kështu që problemi sillet në caktimin e numrit kardinal (numrit të elementeve) të bashkësisë A × C . Dhe përgjigja arrihet duke shumëzuar numrin kardinal të bashkësisë A me numrin kardinal të bashkësisë C. Pra, për dy bashkësi të fundme X , Y vlen:

n( X × Y ) = n( X ) n(Y )

dhe në përgjithësi:

n( X 1 × X 2 × ... × X n ) = n( X 1 ) n( X 2 ) ... n( X n ).

Shembulli 4. Në vitrinë gjenden 6 libra të ndryshme të Matematikës, 8 të Programimit dhe 10 të Fizikës.

Përgatitur nga Armend Shabani www.armendshabani.org

SISTEMET DISKRETE

63

Sipas rregullës së prodhimit ka

6 8 10 = 480

mënyra që të zgjedhen 3 libra, 1 nga secila lëmi. Sipas rregullës së shumës ka

6 + 8 + 10 = 24

mënyra që të zgjedhet një libër, pa marrë parasysh lëminë. Nëse dëshirojmë të zgjedhim një libër të Matematikës dhe një libër të Programimit këtë mund ta bëjmë në

6 8 = 48 mënyra.

Zgjedhjen e një libri të Matematikës dhe një libri të Fizikës mund ta bëjmë në

6 10 = 60 mënyra.

Zgjedhjen e një libri të Programimit dhe të Fizikës mund të bëjmë në

8 10 = 80 mënyra.

Në sa mënyra mund të zgjedhim dy libra nga dy lëmi? (përgjigja 48 + 60 + 80 = 188). Shembulli 5. Shifra e përdoruesit përbëhet nga 3 shkronja që përcillen pastaj me tre numra dhe në fund me një shkronjë, p.sh. ABC 702 F . Supozojmë se kemi 26 shkronja dhe se nuk ka dallim në mes të shkronjave të mëdha dhe të vogla të alfabetit. a) Sa shifra të ndryshme gjithsejtë mund të konstruktohen? b) Në sa prej atyre shifrave, numri 0 paraqitet së paku një herë? Zgjidhja. a) Shkronja e parë mund të jetë një nga 26 shkronjat e alfabetit. Ngjashëm vlen për shkronjën e dytë dhe të tretë. Karakteri i katërt, i pestë dhe i gjashtë mund të zgjidhen nga 10 numrat. Karakteri i shtatë zgjidhet nga 26 shkronjat. Në bazë të rregullës së prodhimit kemi:

26 26 26 10 10 10 26 = 456976000 shifra të ndryshme.

b) Në vend se të kërkojmë drejtpërdrejtë numrin e shifrave që përmbajnë të paktën një zero, është më lehtë të kërkohet numri i shifrave që nuk përmbajnë zero dhe përgjigjen t'ia zbresim rezultatit nën a). Nëse shifra nuk ka zero atëherë në dispozicion kemi vetëm 9 numra, kështu që numri i shifrave pa zero është:

Përgatitur nga Armend Shabani www.armendshabani.org

64

UNIVERSITETI PER BIZNES DHE TEKNOLOGJI

26 26 26 9 9 9 26 = 333135504.

Përfundojmë se numri i shifrave që përmbajnë së paku një zero është

26 26 26 10 10 10 26 - 26 26 26 9 9 9 26 = 123840 496.

2. PERMUTACIONET, VARIACIONET DHE KOMBINACIONET

Le të shqyrtojmë shembullin vijues. Shembulli 1. Le të jetë S = { A, B, C}. a) Sa vargje tre elementëshe, me elemente të ndryshme mes vete, mund të formohen nga elementet e bashkësisë S? b) Sa vargje dy elementëshe, me elemente të ndryshme mes vete, mund të formohen nga elementet e bashkësisë S? c) Nëse A, B, C janë tri pika të një rrafshi që nuk i takojnë një drejtëze, sa segmente përcaktohen prej tyre? Zgjidhja. a) Le të shohim vargjet tre elementëshe:

ABC , ACB, BAC , BCA, CAB, CBA.

Pra, gjithsejtë kemi gjashtë vargje të tilla. b) Le të shohim vargjet dy elementëshe:

AB, AC , BA, BC , CA, CB.

Pra, gjithsejtë kemi gjashtë vargje të tilla. c) E dijmë se çdo dy pika të ndryshme përcaktojnë një drejtëz. Pra, të gjitha vargjet dy elementëshe nga rasti b) përcaktojnë segmente. Por segmenti AB është i njëjtë me segmentin BA . Për këtë kemi këto segmente: AB, BC , CA. C

B A Në rastin a) kemi të bëjmë me permutacionet, në rastin e dytë kemi të bëjmë me variacionet dhe në rastin e tretë me kombinacionet.

Përgatitur nga Armend Shabani www.armendshabani.org

SISTEMET DISKRETE

65

a) PERMUTACIONET

Permutacionet që merren nga elementet A, B, C , janë paraqitur grafikisht.

h.1 A h.2 B ABC C ACB A BAC B h.2 C BCA A CAB C h.2 B CBA

Fillojmë me hapin e parë i cili parashtron pyetjen: Cili element të vendoset i pari? Merren tri drejtëza që i korrespondojnë tri përgjigjeve të mundshme. Procesi vazhdon me pyetjen: Kush të vendoset i dyti? Për secilin rast merren dy drejtëza që tregojnë përgjigjet e mundshme. Më sipër pamë se nëse bashkësia ka tri elemente atëherë prej tyre formohen 6 permutacione. Shtrohet pyetja: Sa permutacione formohen nga bashkësia n elementëshe? Elementi i parë i permutacionit mund të jetë secili prej n elementeve. Pasi ky element të jetë zgjedhur, atëherë elementi i dytë mund të jetë cilido prej n - 1 elementeve. Duke vazhduar në këtë mënyrë elementi i tretë mund të jetë secili prej n - 2 elementeve. E kështu me radhë. Është e qartë se për elementin e fundit ka vetëm një mundësi. Në bazë të rregullës së prodhimit, numri i tërësishëm i permutacioneve është:

n( n - 1)(n - 2) ... 3 2 1 = n!

Pra, numri i permutacioneve të bashkësisë me n ­ elemente është n! . Shembulli 2. Të shkruhen të gjitha permutacionet e elementeve: a) 1, 2,3, 4; Zgjidhja. a) 1234 1243 1324 1342 1423 1432

Përgatitur nga Armend Shabani

b) x, y, z , t. 2134 2143 2314 2341 2413 2431 3124 3142 3214 3241 3412 3421 4123 4132 4213 4231 4312 4321

www.armendshabani.org

66

UNIVERSITETI PER BIZNES DHE TEKNOLOGJI

b) në mënyrë analoge. Shembulli 3. Të paraqiten të gjitha permutacionet e elementeve 1,2,3,4 me vetitë: a) 3 gjendet i pari dhe 1 i fundit b) 24 gjenden të parët c) 13 gjenden të fundit. Zgjidhja. a) 3241; 3421, a) 12345; Zgjidhja. a) Është e qartë se të gjitha permutacionet e elementeve 1, 2, 3, 4, 5 paraqesin numra 5 shifrorë, prandaj kemi b) 2413; 2431, b) 01234? c) 2413; 4213. Shembulli 4. Sa numra pesëshifror mund të formohen nga shifrat

p (5) = 5! = 120 - gjithsej 120 numra.

b) Nga numrat 0, 1, 2, 3, 4 siç pamë nga rasti a) mund të formohen 5! numra 5 shifrorë, por në këtë rast duhet të jemi të kujdesshëm sepse numrat që fillojnë me 0 nuk paraqesin numra. Zero në pozitën e parë qëndron 4!=24 herë, prandaj gjithsejtë kemi 5!- 4! = 96. Shembulli 5. Në sa permutacione të elementeve 1, 2, 3, 4, 5, 6 elementet 2, 4, 6 gjenden pranë njëri tjetrit: a) në renditjen e dhënë, b) në renditjen e çfarëdoshme? Zgjidhja. a) Le të shënojmë renditjen 246 = a . Atëherë kemi numrat 1,3,5, a . Gjithsejtë kemi 4!=24 permutacione. b) Renditjet e çfarëdoshme të numrave 2, 4, 6 janë: 246 246 pra gjithsejtë 3!=6. D.m.th. numrat 2, 4, 6 paraqitjen në renditjen e çfarëdoshme

4! 3! = 24 6 = 144 herë.

426 462

624 642

Përgatitur nga Armend Shabani

www.armendshabani.org

SISTEMET DISKRETE

67

Shembulli 6. Sa numra natyrorë më të mëdhenj se 5000 mund të paraqiten me anë të shifrave 2, 3, 7, 8 nëse shifrat nuk përsëriten? Zgjidhja. Nga shifrat 2, 3, 7, 8 gjithsejtë kemi P(4) = 4! = 24 permutacione. Në gjashtë prej tyre shifra 2 gjenden në pozitën e parë dhe në gjashtë të tjera shifra 3 gjendet në pozitën e parë. Që numrat të jenë më të mëdhenj se 5000 duhet që shifra e parë doemos të jetë 7 ose 8. Pra, gjithsej kemi 12 numra. Shembulli 7. Të caktohet permutacioni i 604 i elementeve 1, 2, 3, 4, 5, 6. Zgjidhja. Dihet se nga 6 elemente kemi 6! = 720 permutacione. Permutacionet prej 1 ­ 120 numrin 1 e kanë si shifër të parë, ngjashëm veprohet me permutacionet tjera. Me fjalë të tjera, permutacioni i 601 është: 612345 Atëherë kemi: 612354 612435 612453 permutacioni i permutacioni i 602 603 kërkuar. permutacioni i 601

është permutacioni i

Detyra për ushtrime të pavarura 3. Të njehsohet vlera e shprehjes: a) 8!+ 9!; 4. Të thjeshtohen shprehjet: a)

1 1 - ; n! ( n + 1)!

b)

2005! ; 2003!

1 1 - . ( s - 1)! s !

c)

6!- 5! . 120

b)

5. Të vërtetohen identitetet: a) b)

(m + 3)! = ( m + 1)( m + 2)(m + 3); m!

n! = n( n - 1) ... (n - r + 1), n > r. (n - r )!

Përgatitur nga Armend Shabani

www.armendshabani.org

68

UNIVERSITETI PER BIZNES DHE TEKNOLOGJI

6. Të thjeshtohen thyesat: a)

(n - 2)! ; (n - 4)!

b)

(n + 1)! : ( n - 1)!

c)

(n - 4)! ; (n - 1)! (n + 1)! = 30; ( n - 1)!

d)

(n + 4)! . ( n - 2)!

7. Të zgjidhen ekuacionet: a) c)

(n + 2)! = 72; n!

(2 x )! 20 x ! = ; (2 x - 3)! ( x - 2)! ( n - 1)! < 72; (n - 3)! ( y + 2)! < 100; ( y + 1)( y + 2)

b) d)

y 12 y = . ( y - 4)! ( y - 2)! (2 x - 1)! > 420; (2 x - 3)! (m - 2)(m - 3) > 0,00002. ( m - 1)!

8. Të zgjidhen mosbarazimet: a) c) b) d)

9. Të vërtetohet se

1! 1 + 2! 2 + 3! 3 + ... + n! n = ( n + 1)!- 1, n N .

b) VARIACIONET

Variacionet paraqesin rast të përgjithshëm të permutacioneve. Supozojmë se dëshirojmë të zgjedhim r ­ elemente nga bashkësia me n elemente (n > r ), dhe ato elemente t'i radhisim sipas një renditje të caktuar. Në sa mënyra mund të bëhet kjo? Përgjigja merret duke vepruar në mënyrë analoge me rastin e parë. Elementi i parë i variacionit mund të jetë secili nga n ­ elementet e bashkësisë më të madhe. Elementi i dytë mund të zgjedhet nga n - 1 elementet e mbetura, elementi i tretë zgjedhet nga n - 2 elementet e mbetura e kështu me radhë. Elementi i fundit (elementi i r ­ të) mund të zgjedhet nga n - r + 1 elementet që kanë mbetur. Në bazë të rregullës së prodhimit, numri i tërësishëm i mënyrave që kjo të bëhet është:

n( n - 1)( n - 2) ... ( n - r + 1).

Shprehjen e fundit do ta shënojmë me Vrn . Në detyrën 5, rasti b) pamë se

Përgatitur nga Armend Shabani

www.armendshabani.org

SISTEMET DISKRETE

69

n! = n(n - 1)( n - 2) ... (n - r + 1). (n - r )!

Prandaj, mund të shkruajmë Vrn =

n! . ( n - r )!

Shembulli 8. Të paraqiten variacionet: a) e klasës së dytë b) e klasës së tretë për elementet a, b, c, d . Zgjidhja. a) Variacionet e klasës së dytë janë:

ab ac ad ba bc bd ca cb cd dc da db

pra gjithsejtë janë 12 variacione.

4 4! 4 3 2! = = 4 3 = 12 . V2 = (4 - 2)! 2!

b) Variacionet e klasës së tretë janë:

abc abd bac bad cab dab cad acb acd bca bcd cba cbd dbc adb adc bda bdc cda cdb dca dcb

dac bda

pra, gjithsejtë janë V34 =

4! = 24. (4 - 3)!

Shembulli 9. Të caktohet numri i numrave treshifrorë me shifra të ndryshme. Zgjidhja. Numrat e kërkuar treshifrorë formohen nga shifrat 0,1, 2,3, 4,5, 6, 7,8,9. Pra, kemi të bëjmë me variacione të klasës së dytë prej 3 elementeve.

V310 = 10! = 10 9 8 = 720. (10 - 3)!

Por në mesin e numrave të mësipërm ka të tillë që shifrën e parë e kanë 0. P.sh. 014. Të tillë ka gjithsejtë V29 = 9 8 = 72. (Pse?)

Përgatitur nga Armend Shabani www.armendshabani.org

70

UNIVERSITETI PER BIZNES DHE TEKNOLOGJI

D.m.th. kemi V310 - V29 = 720 - 72 = 648 ndryshme. Detyra për ushtrime të pavarura

numra treshifrorë me shifra të

10. Të caktohet numri i numrave katërshifrorë me shifra të ndryshme. 11. Shifra e përdoruesëve është numër pesëshifrorë (që nuk fillon as me zero e as me 1). Sa është numri i tërësishëm i shifrave? 12. Si pjesë e hulumtimeve në gazetari, të intervistuarëve u jepen 18 revista të ndryshme duke kërkuar prej tyre që të caktojmë 5 revista më të mira. Sa mundësi të përgjigjeve të ndryshme kemi? Shembulli 10. Është dhënë bashkësia N = {1,2,3,..., n}. Të paraqiten grafikisht variacionet e klasës së dytë. Zgjidhja.

2 3 1 4 2 1 3 4 n 1 2 3

n

n

n-1

Shembulli 11. Të caktohet numri natyror n për të cilin Zgjidhja. Zbatojmë formulën Vrn =

n! . Merret ( n - r )!

V32 n+ 4 2 = . V4n + 4 3

(2n + 4)(2n + 3)(2n + 2) 2 = . (n + 4)( n + 3)( n + 2)(n + 1) 3

Meqë n N merret

2( n + 2)(2 n + 3)2(n + 1) 2 = (n + 4)( n + 3)(n + 2)( n + 1) 3 4(2n + 3) 2 = prej nga merret n = 6. (n + 4)( n + 3) 3

Përgatitur nga Armend Shabani www.armendshabani.org

SISTEMET DISKRETE

71

Detyra për ushtrime të pavarura 13. Numri i variacioneve të n ­ elementeve të klasës së tretë është

5 e numrit 12 të variacioneve të klasës së tretë prej n + 2 elementeve. Të caktohet numri i elementeve.

14. Sa numra pesëshifrorë mund të paraqiten nga shifrat 0,1,3,5,7,9 nëse 0 nuk gjendet as në pozitën e parë e as në pozitën e fundit dhe nëse shifrat nuk përsëriten. 15. Të zgjidhen barazimet: a) V2x = 380; c) V4x : V5x -1 = 1: 3; 16. Të vërtetohet se Vnn-1 = Vnn = n! b) V2x = 72; d) 7 V3x = 6 V3x+1 .

c) KOMBINACIONET

Në pjesët paraprake shqyrtuam problemin e zgjedhjes së një numri të caktuar elementesh nga bashkësia, me ç'rast merrej në konsiderim renditja se si janë zgjedhur elementet. Një problem më praktik është caktimi i numrit të mënyrave për kryerjen e përzgjedhjes, pa marrë parasysh renditjen. P.sh. le të themi se jemi duke luajtur LOTO të tipit 7 nga 40. D.m.th. nga numrat natyrorë 1 deri në 40 duhet zgjedhur 7 numra. Në sa mënyra të ndryshme mund të kryhet përzgjedhja. Me fjalë të tjera, sa lojë duhet të luajmë që të jemi të sigurt në fitore? Së pari njehsojmë numrin e mundësive nëse merret parasysh renditja, pra V740 . Është e qartë se ky numër nuk është përgjigja e detyrës sepse përzgjedhjet e njëjta i kemi numëruar disa herë. Në fakt meqë janë 7! mënyra për të paraqitur 7 numrat e zgjedhur. Numrin V710 duhet pjesëtuar me 7!. Pra, numri i mënyrave të ndryshme është

V740 40 39 38 37 36 35 34 = 7! 7 6 5 4 3 2 1

Ky shembull na jep idenë për të zgjidhur problemin e kombinimeve në rastin e përgjithshëm. Supozojmë se kemi për të zgjedhur r elemente nga bashkësia prej n ­ elementesh, pa e marrë parasysh renditjen e zgjedhjes së bërë. Në sa mënyra mund të bëjmë këtë?

Përgatitur nga Armend Shabani www.armendshabani.org

72

UNIVERSITETI PER BIZNES DHE TEKNOLOGJI

Është e qartë se numri i mundësive kur merret parasysh renditja është Vrn . Tani nëse nuk duhet të merret parasysh renditja ky numër duhet të pjesëtohet me r!, Vn që paraqet numrin e permutacioneve të r elementeve të zgjedhura, pra kemi r r! mundësi. Duke ditur se Vrn = mundësi.

n Shprehjen e fundit e shënojmë me ose Crn . r

n! n! atëherë përfundojmë se gjithsejtë kemi (n - r )! r !( n - r )!

Shembulli 12. Zgjidhja.

Le të jetë N = {1,2,3,4,5,6}. kombinacionet e klasës së 3.

Të caktohen të gjitha

6 6! 6 5 4 3! Meqë C36 = = = = 20. 3 3!(6 - 3)! 3! 3!

Përfundojmë se gjithsejtë janë 20 kombinacione të klasës së tretë prej 6 elementesh. Ato janë:

123 124 125 126 134 135 136 145 146 156 234 235 236 245 246 256 345 346 356 456

Shembulli 13. Në një turne shahu marrin pjesë 15 shahist. Secili do të luaj me secilin. Sa ndeshje do të luhen gjatë turneut? Zgjidhja.

15 Kemi C2 =

15! = 105. 2!(15 - 2)!

Shembulli 14. Klasa ka 16 vajza dhe 20 djem. Kryesia e klasës duhet të zgjedhet më së paku katër nxënës ashtu që së paku njëri të jetë vajzë. Në sa mënyra mund të kryhet zgjedhja. Zgjidhja.

16 20 16 20 16 20 16 + + + = 54060. Arsyetoni. 1 3 2 2 3 1 4

Përgatitur nga Armend Shabani

www.armendshabani.org

SISTEMET DISKRETE

73

Detyra për ushtrime të pavarura 17. Të zgjidhen barazimet: a) 5C3x = C4x+ 2 ;

+1 c) Cnn-2 + 2C3n -1 = 7( n - 1); n b) 3Cn2-1 = 5Cn2 n-1 ;

d) V3n + Cnn-2 = 14n.

n n n + 1 b) + = ; k k - 1 k

18. Të vërtetohet se vlen:

n n a) = ; k n - k

n n n n + 2 c) + + 2 = ; k + 1 k - 1 k k +1 n - 2 n - 2 n - 2 n d) + + 2 = ; k k - 2 k -1 k n + 2 n + 2 n + 2 n + 4 e) + 2 + = . m - 1 m + 2 m + 3 m + 3

3. PERMUTACIONET ME PËRSËRITJE

Në njësinë paraprake pamë se nëse kemi bashkësinë S = {a1 , a2 , a3 } ekzistojnë 3! = 6 permutacione të elementeve a1 , a2 , a3 . Permutacionet janë:

a1a2 a3 , a1 a3 a2 , a2 a1 a3 , a2 a3 a1 , a3 a1 a2 , a3 a2 a1

(1)

Supozojmë se a1 = a2 . Atëherë permutacionet (1) marrin formën:

a1a1 a3 , a1a3 a1 , a1a1a3 , a1a3 a1 , a3 a1a1 , a3 a1a1

pra ekzistojnë tri permutacione të ndryshme. Ato janë: a1a1 a3 , a1 a3 a1 , a3 a1 a1 . Në këtë rast elementi a1 paraqitet dy herë, prandaj nga 2! permutacione shndërrohen në një dhe si rezultat merren

3! 6 = = 3 - permutacione. 2! 2

Përgatitur nga Armend Shabani

www.armendshabani.org

74

UNIVERSITETI PER BIZNES DHE TEKNOLOGJI

Në përgjithësi, nëse Pk (n) shënojmë numrin e të gjitha permutacioneve prej n ­ elementeve prej të cilave k janë të njëjta, atëherë numri i permutacioneve është:

Pk ( n) = n! . k!

Këtë rezultat, lehtë mund ta përgjithësojmë. Le të jetë Pk ,k ,...,k ( n) numri i permutacioneve prej n elementeve në mesin e të

1 2 m

cilave janë k1 të njëjta, pastaj k2 të njëjta, ..., km të njëjta atëherë:

Pk ,k ,...,k ( n) =

1 2 m

n! . k1 ! k2 ! ... km !

(2) i permutacioneve të elementeve

Shembulli

1.

caktohet

numri

0,0,1,1,0,0,1,0,1.

Zgjidhja. Vërejmë se kemi 9 elemente. Elementi 0 përsëritet 5 herë, kurse elementi 1 përsëritet 4 herë, prandaj në bazë të formulës (2) kemi:

P5,4 (9) =

9! 9 8 7 6 5! = = 126. 5! 4! 5! 4 3 2 1

Shembulli 2. Sa numra të ndryshëm pesëshifror mund të formohen nga numrat 11222? Zgjidhja. Në bazë të formulës (2) kemi P2,3 (5) =

5! = 10. 2! 3!

4. VARIACIONET ME PËRSËRITJE.

Le të jetë S = {a1 , a2 ,..., an }. Variacion me përsëritje të klasës k prej n elementeve të bashkësisë S është çdo k ­ she e renditur e elementeve të bashkësisë S. P.sh. variacionet e klasës së dytë të elementeve të bashkësisë S janë:

a1 a1 a2 a1 : an a1 a1a2 ... a1an a2 a2 ... a2 an : ... : an a2 ... an an

Vërejmë se gjithsejtë kemi n n = n2 variacione me përsëritje të klasës së dytë prej n ­ elementeve.

Përgatitur nga Armend Shabani www.armendshabani.org

SISTEMET DISKRETE

75

Nëse Vnk e shënojmë numrin e variacioneve me përsëritje të klasës k prej n ­ elementeve, atëherë me anë të induksionit matematik vërtetohet se Vnk = n k . Shembulli 1. Le të jetë S = {a1 , a2 }. Të caktohen variacionet me përsëritje të klasës së katërtë. Zgjidhja. Vërejmë se n = 2, k = 4, prandaj gjithsejtë kemi V24 = 24 = 16 variacione me përsëritje të klasës së katërt. Ato janë:

a1a1a1a1 a1 a2 a1a1 a2 a1a1a1 a2 a2 a1 a1 a1 a1a1a2 a1a2 a1 a1 a2 a1a1 a1 a2 a2 a1 a2 a1 a1a2 a1 a1a2 a2 a1 a2 a1 a2 a1 a2 a2 a2 a1 a1 a1a2 a2 a1a2 a2 a2 a2 a1a2 a2 a2 a2 a2 a2

Shembulli 2. Le të jetë S = {0,1,2,3,4}. Të caktohet numri i të gjithë numrave treshifrorë që formohen nga elementet e bashkësisë S. Zgjidhja. Numrat treshifror janë të gjitha variacionet me përsëritje të klasës së tretë të cilët nuk fillojnë me zero. Pra gjithsejtë kemi V53 - V52 = 53 - 52 = 100.

5. KOMBINACIONET ME PËRSËRITJE

Le të jetë S = {a1 , a2 ,..., an }. Kombinacione me përsëritje të klasës k prej n elementesh nga bashkësia S janë ato variacione me përsëritje të klasës k të atyre elementeve që konsiderohen të njëjtë vetëm nëse përbëhen prej elementeve të njëjta. Për shembull, të gjitha variacionet me përsëritje të klasës së dytë të elementeve të bashkësisë S = {a1 , a2 , a3 } janë: a1a1 a1a2 a1a3 a3 a3 a2 a1 a2 a2 a2 a3 a3 a1 a3 a2

Çiftet vijuese a1a2 dhe a2 a1 ; a1a3 dhe a3 a1 ; a2 a2 dhe a3 a2 i konsiderojmë të njëjta, kështu që të gjitha kombinacionet me përsëritje të klasës së dytë janë:

a1a1

a1 a2

a1 a3

a2 a2

a2 a3

a3 a3 .

www.armendshabani.org

Përgatitur nga Armend Shabani

76

UNIVERSITETI PER BIZNES DHE TEKNOLOGJI

Kombinacionet e klasës k prej n elementeve i shënojmë Cnk . Vlen

n + k - 1 Cnk = k (Cnk = Cnk+ k -1 ).

6. FORMULA E BINOMIT

Është lehtë të provohen identitetet vijuese:

( x + y)0 = 1 ( x + y )1 = x + y ( x + y ) 2 = x 2 + 2 xy + y 2 ( x + y )3 = x 3 + 3x 2 y + 3 xy 2 + y 3

Në përgjithësi vlen formula; që quhet Formula e Binomit (ose teorema e Binomit).

n n n n n n-1 n n ( x + y ) n = x n- k y k = x n + x n -1 y + ... + xy + y k =0 k 0 1 n - 1 n

(1)

Një vërtetim të formulës së mësipërme e kemi paraqitur tek induksionit matematik. Tek kjo formulë arrihet edhe sa vijon. Nisemi nga shprehja

( x + y ) n = ( x + y )( x + y ) ... ( x + y ) 14444 24444 3

n - faktorë

E zbërthejmë anën e djathtë dhe i grupojmë termat e formës x a y b . Meqë kemi n faktorë të trajtës ( x + y ) kemi a + b = n, kështu që termat duhet të jenë të formës x n- k y k . Koeficientet e shprehjes x n - k y k do të jenë baras me numrin e mënyrave në të cilat mund të zgjedhet y nga çfarëdo k faktorë (dhe x nga n - k n faktorët e mbetur) e që e dimë se është Ckn = . k

n Shprehja paraqet koeficientët binomial. k

Teorema e Binomit mund të zbatohet për të treguar identitetet që kanë të bëjnë me koeficientet binomial. P.sh. nëse në shprehjen (1) zëvendësojmë x = y = 1, merret

Përgatitur nga Armend Shabani www.armendshabani.org

SISTEMET DISKRETE

77

n n n n n (1 + 1) n = 2n = + + + ... + + . 0 1 2 n - 1 n

Shembulli 1. Tregoni se

(-1)

k =0

n

k

n n n n n n = - + - + ... + ( -1) n = 0. k 0 1 2 3 n

Udhëzim. Në formulën (1) zëvendësojmë x = 1, y = -1. Shembulli 2. Duke zbatuar formulën e Binomit të zbërthehet (1 + x )6 . Zgjidhja.

6 6 6 6 6 6 6 (1 + x )6 = + x + x 2 + x 3 + x 4 + x 5 + x 6 0 1 2 3 4 5 6

= 1 + 6 x + 15 x 2 + 20 x 3 + 15 x 4 + 6 x 5 + x 6 .

2 1 Shembulli 3. Të caktohet anëtari i pestë i zhvillimit binomial a 2 + b 3 . 12

Zgjidhja. Le të jetë Tk +1 anëtari i (k + 1) - të i zhvillimit binomial. Tregohet lehtë se

n Tk +1 = a n- k b k . k

Pra, në rastin tonë kërkohet T5 , ku x = a 2 ; y = b 3 , n = 12. D.m.th. T5 = T4+1 {

k

1

2

12 1 = a2 4

12 - 4

8 2 12! 4 8 3 a b 3 = 495 a 4 b 3 . b = 4! 8!

4

7. TREKËNDËSHI I PASKALIT. IDENTITET NË TREKËNDËSHIN E PASKALIT

Gjatë studimit të vetive të koeficienteve binomial, rëndësi paraqet skema vijuese, që njihet si trekëndëshi i Paskalit (emërtuar sipas matematikanit dhe filozofit françes Blaise Pascal, 1623 ­ 1662).

Përgatitur nga Armend Shabani

www.armendshabani.org

78

UNIVERSITETI PER BIZNES DHE TEKNOLOGJI

0 0 1 0 2 0 3 0 4 0 5 0 5 1 4 1 5 2 3 1 4 2 5 3 2 1 3 2 4 3 5 4 1 1 2 2 3 3 4 4 5 5

... Në vijim koeficientet binomial i zëvendësojmë me vlerat e tyre numerike.

1

1 1 1 1 1 1 1 1 8 7 28 6 21 56 5 15 35 70

...

1 2 1 3 6 4 10 20 35 56 15 21 28 5 6 7 8 1 1 1 1 1 1

3 4 10

Trekëndëshin e Paskalit në tekste të ndryshme mund ta hasim edhe në formën:

Përgatitur nga Armend Shabani

www.armendshabani.org

SISTEMET DISKRETE

79

1

1 1 1 1 1 1

1 2 3 4 5 6 1 3 6 10 15 1 4 10 20

...

1 5 15 1 6 1

Nëse e analizojmë trekëndëshin e Paskalit vërejmë një veti shumë të rëndësishme: çdo numër (me përjashtim të numrit 1) është shumë e dy numrave të mësipërm. Ky është në fakt një relacion që e kemi pasur tek kombinacionet.

n - 1 n - 1 n + = . k - 1 k k

Le të vërejmë me anë të disa shembujve zbatimin e koeficienteve binomial. Shembulli 4. Duke u nisur nga barazimi:

n n n n (1 + x ) n = + x + x 2 + ... + x n 0 1 2 n

njehsoni:

n n n n a) + 2 + 3 + ... + n 1 2 3 n n n n n b) + 2 + 3 + ... + (n + 1) 0 1 2 n n n n n c) + 2 + 3 + ... + ( n - 1) . 2 3 4 n

Zgjidhja.

n n n n a) A + 2 + 3 + ... + n 1 2 3 n

Përgatitur nga Armend Shabani www.armendshabani.org

80

UNIVERSITETI PER BIZNES DHE TEKNOLOGJI

n( n - 1) n(n - 1)( n - 2) + 3 + ... + n 2 1 2 3 ( n - 1)( n - 2) = n 1 + (n - 1) + + ... + 1 1 2 = n + 2 n - 1 n - 1 n - 1 n - 1 = n + + + ... + . n - 1 0 1 2

Më sipër treguam se:

n n n n n + + + ... + = 2 n 0 1 2

D.m.th.;

n - 1 n - 1 n - 1 n - 1 n -1 + + + ... + =2 . 0 1 2 n - 1

Prandaj, A n 2n -1. b)

n n n n B + 2 + 3 + ... + ( n + 1) 0 1 2 n

n n n n n n n n = + + + ... + + + 2 + 3 + ... + n n 1 2 3 n 0 1 2 = 2n + n 2n -1 = 2n-1 ( n + 2).

c)

n n n n + 2 + 3 + ... + (n - 1) 2 3 4 n

n n n n = + (3 - 1) + (4 - 1) + ... + ( n - 1) 2 3 4 n n n n n n n n n n n = - + 2 - + 3 - + 4 - + ... + n - 1 1 2 2 3 3 4 4 n n

n n n n n n n n = + 2 + 3 + ... + n - + + ... + + 0 1 n3 n 0 1 2 4 3 144444 2444444

A

= n 2 n-1 - 2n + 1 = 2n -1 (n - 2) + 1.

Përgatitur nga Armend Shabani www.armendshabani.org

SISTEMET DISKRETE

81

Detyra për ushtrime të pavarura Njehsoni:

n n n 0 1 3 19. + + + ... + 1 2 3 n n . n +1 n n . n +1

n n n 0 1 2 20. - + - ... + (-1) n 1 2 3

Le të vërejmë me anë të disa shembujve të tjerë zbatimin e koeficientëve binomial. Në vijim, le të shohim një zgjidhje tjetër të shembullit (1) të pikës paraprake. Duhet të tregojmë se vlen:

n n n n n n - + - + ... + ( -1) = 0. 0 1 2 3 n

(1)

n - 1 . 0

n n n - 1 Meqë = 1; = 1, atëherë mund të zëvendësojmë me 0 0 0

Në bazë të relacionit zëvendësime:

n n - 1 n - 1 = + k k - 1 k

mund të kryejmë këto

n n - 1 n - 1 + 1 0 1 n n - 1 n - 1 + 2 1 2

... Kështu që ana e majtë e relacionit (1) do të jetë:

n - 1 n - 1 n - 1 n - 1 n - 1 n - 1 n - 1 + + + + - + + ... 0 0 1 1 2 2 3

gjë që shihet qartë se është e barabartë me zero.

Përgatitur nga Armend Shabani

www.armendshabani.org

82

UNIVERSITETI PER BIZNES DHE TEKNOLOGJI

Detyrë për ushtrime të pavarura 21. Duke zbatuar të njëjtën ide të vërtetohet se vlen:

n n - 1 n n n n k k - + - + ... + ( -1) = (-1) 0 1 2 3 k k

Shembulli 2. Të vërtetohet se vlen

n n n n n 2n + + + ... + + = . 0 1 2 n - 1 n n

2 2 2 2 2

Le të vërejmë së pari disa raste. Kështu për shembull nëse n = 1 kemi:

1 1 2 1 2 2 + = . Vërtetë 1 + 1 = 2. 0 1 1

2 2

Për n = 2 kemi:

2 2 2 2 2 4 2 2 2 + + = 1 + 2 + 1 = 6; = = 6. 0 1 2 2 2

2 2 2

Po ashtu tregohet dhe për rastet n = 3, 4. Por siç e dimë disa raste të vetme nuk mjaftojnë për vërtetimin. Një qasje për vërtetimin e detyrës është induksioni matematik. Provoni! Në vijim do të shohim një vërtetim tjetër.

n n Gjatë vërtetimit do të zbatojmë rezultatin = ; 0 k n të cilin e kemi k n - k dhënë në detyrën 18.

Meqë (1 + x ) n (1 + x) n = (1 + x ) 2 n merret:

n n n 2 n n n n n 2 n n + x + x + ... + x + x + x + ... + x 2 n 0 1 2 n 0 1

2n 2n 2n 2n = + x + x 2 + ... + x n . 0 1 2 n

n n n n n n n + + ... + x + ... = n n 0 n 1 n - 1

Përgatitur nga Armend Shabani www.armendshabani.org

SISTEMET DISKRETE

83

2n 2n 2n 2 2n n + x + x + ... + x . 0 1 2 n

Duke barazuar koeficientin para x n merret:

n n n n n n 2n + + ... + = . 0 n 1 n - 1 n n n

Duke zbatuar rezultatin e mësipërmë merret:

n n n 2n + + ... + = , gjë që duhej treguar. 0 1 n n

2 2 2

Shembulli 3. Të vërtetohet se për çdo numër natyror n vlen:

(-1)

k =1

n

k +1

n 1 1 1 1 = 1 + + + ... + . k k 2 3 n

Zgjidhja. Për n = 1 kemi

1 1 (-1)1+1 = 1 gjë që është e saktë. 1 1

Supozojmë se pohimi është i saktë për n - 1.

(-1)

k =1

n -1

k +1

n - 1 1 1 1 . = 1 + + ... + n -1 2 k k n 1 n-1 = ( -1) k +1 k k k =1 =1+

=1+ =1+

(hi)

Vërtetë,

(-1)

k =1

n

k +1

n 1 n 1 + (-1) n+1 k k n n

n -1 n - 1 1 ( -1) n+1 1 1 + ... + + ( -1) k +1 + n - 1 k =1 n 2 k - 1 k

n -1 1 1 (n - 1)! 1 ( -1) n +1 + ... + + (-1)k +1 + 2 ( k - 1)! (n - k )! k n - 1 k =1 n n -1 1 1 1 (-1) n+1 n! + ... + + ( -1) k +1 + n - 1 k =1 k ! (n - k )! n n 2

Përgatitur nga Armend Shabani

www.armendshabani.org

84

UNIVERSITETI PER BIZNES DHE TEKNOLOGJI

=1+ =1+ =1+

n -1 n 1 n 1 1 1 + ... + + ( -1) k +1 + ( -1) n +1 2 n - 1 k =1 n k n n n n 1 1 1 + ... + + ( -1) k +1 2 n - 1 k =1 k n

n 1 1 1 n + ... + + (-1) k +1 n - 1 n k =1 2 k

n n 1 1 1 k +1 = 1 + + ... + + 1 - ( -1) 2 n - 1 n k =0 k 3 14 244 4 0 =1+ 1 1 1 + ... + + , gjë që duhej treguar. 2 n -1 n

Shënim. Zbatuam faktin që

n - 1 n - 1 1 ( -1) n +1 n n - 1 n - 1 n -1 = + = (-1) k +1 + + n k k k - 1 k =1 k k - 1 k

n -1 n - 1 1 (-1) n+1 n - 1 1 n -1 k +1 = ( -1) k +1 + (-1) + k k k =1 n k =1 k - 1 k 144 2444 4 3 ( hi )

Le të kthehemi sërish tek vetitë e trekëndëshit të Paskalit. Një veti e trekëndëshit të Paskalit është simetria, në lidhje me "vertikalen qendrore". Po ashtu nëse i analizojmë të dhënat vërejmë se në secilin rresht, numrat rriten dhe pastaj zvogëlohen. Nëse n është numër çift, ekziston elementi i vetëm i mesëm në rreshtin e n - të dhe ai është numri më i madh. Nëse n është numër tek, në mes gjenden dy elemente (numra) të njëjtë dhe ata janë numra më të mëdhenj. Le të tregojnë në vijim se të dhënat (numrat) rriten deri në mes prej nga pastaj zvogëlohen (duke u bazuar në simetrinë).

n n Do të shohim se në cilat raste < . k k + 1

Përgatitur nga Armend Shabani www.armendshabani.org

SISTEMET DISKRETE

85

Në bazë të formulave tek kombinacionet merret:

n! n! < k !(n - k )! ( k + 1)!(n - k - 1)! n(n - 1) ... ( n - k - 1) n(n - 1) ... ( n - k ) < k ( k - 1) ... 3 2 1 ( k + 1) k ... 3 2 1

1<

n-k k +1 n -1 . 2

prej nga

k<

Pra: nëse k < nëse k =

n n n -1 atëherë < 2 k k + 1

n n n -1 atëherë = (rasti kur dy elementet e mesme janë 2 k k + 1 të barabarta)

nëse k >

n n n -1 atëherë > . 2 k k + 1

Në figurën vijuese është paraqitur grafiku i rastit të n ­ të trekëndëshit të Paskalit për n = 10 dhe n = 100.

Përgatitur nga Armend Shabani

www.armendshabani.org

86

UNIVERSITETI PER BIZNES DHE TEKNOLOGJI

Detyra për ushtrime pavarura

1 22. Të caktohet x në zbërthimin 2 x + 4 . 3 x

6

7

23. Të vërtetohet se (1 + 2) n + (1 - 2) n , n N janë numra i plotë. 24. Të caktohen numrat k, n ashtu që të vlejë:

n n + 1 n + 1 a) : : = 3: 4 :8, k k k + 1 n n b) = 2002; = 3003. k - 1 k

Të vërtetohen identitetet:

n n n 25. 1 + 14 + 36 + 24 = ( n + 1) 4 - n 4 . 1 2 3 n n n n 26. - 2 + 3 - ... + (-1) n ( n + 1) = 0. 0 1 2 n n 1 n 1n 1 n 2n +1 - 1 27. + + + ... + . = n + 1 n n +1 0 2 1 3 2

Përgatitur nga Armend Shabani

www.armendshabani.org

Information

27 pages

Report File (DMCA)

Our content is added by our users. We aim to remove reported files within 1 working day. Please use this link to notify us:

Report this file as copyright or inappropriate

420903