eMatematikas.lt
Pradžia Forumai + Nauja tema Nariai
Įrankiai
Formulės Testai Egzaminai
Prisijungti Registruotis
       

Kombinatorika: kėliniai, gretiniai ir deriniai be pasikartojimų

1.  KĖLINIŲ BE PASIKARTOJIMŲ SKAIČIUS.

Pradinė aibė: {a, b, c, d, e). 
Sudarome KĖLINIUS BE PASIKARTOJIMŲ.
(a, b, c, d, e),
(a, c, b, d, e),
(a, e, d, b, c)
...................
Kėlinių ( iš penkių elementų) skaičius 5*4*3*2*1 =5! = 120.
Pavyzdys: Yra 5 vaikinai ir penkios merginos. Keliais būdais gali susidaryt penkios porelės?  Atsakymas: 5! = 120.
Kėlinių iš n elementų skaičius lygus n!.

2.  GRETINIAI BE PASIKARTOJIMŲ.

Imkime tą pačią pradinę aibę: {a, b, c, d, e}.
Dabar iš jos imkime ( po vieną) tik tris elementus, ir dėliokime juos eilės tvarka. Galimi sutvarkytieji rinkiniai,-tai ir yra gretiniai:
(a, b, c),
(b, c, a),
(a, b, d)
..........
(c, d, e)
..........
(e, d, c).
Gretinių skaičių taipogi lengva gauti, taikant "kombinatorinę daugybą). Šiuo atveju ( gretinių iš 5 po 3) skaičius yra
5 * 4 * 3 = 60.
Beje, šią sandaugą galima "užfaktorialinti" .
5*4*3 = (5*4*3*2*1)/ (2*1) = 5! / 2!
Kitaip tariant, gretinių ( iš 5 po 3) skaičius gali būti išreikštas faktorialais:
5! / (5 - 3)!.
Būtent taip ir "gimsta" gretinių be pasikartojimo iš n po m skaičiaus formulė
A(n, m) = n! / (n -m)!.
Tačiau, skaičiuojant gretinių skaičių, galima naudotis paprasčiausiąja "kombinatorine daugyba".
Pavyzdys:  Eilėje yra dvylika kėdžių. Keliais būdais penki žmonės gali pasirinkti vietas?
Tai- gretinių skaičius.  A(12, 5) = 12*11*10*9*8 = 95040.
Pavyzdys: Yra septyni sportininkai. Keliais būdais jie gali pasirinkti tris SKIRTINGAS prizines vietas?
Vėl gretinių skaičius, nes svarbu ne tik tai, kokie sportininkai bus nugalėtojai, bet ir kokią prizinę vietą ( pirmąją, antrąją, ar trečiąja) gaus kiekvienas iš jų.
Taigi, vėl turime modeli:
Pradinė aibė: { a, b, c, d, e, f, g}.
Apdovanojimų variantai (gretiniai iš 7 po 3) yra sutvarkytieji rinkiniai:
( a, b, c)
(a, c, b)
...........
(c, b, a)
...........
(a, c, d)
...........
(g, f, e).
Ieškome gretinių ( iš 7 po 3) skaičiaus:
A( 7 , 3) = 7! / 4! ,
arba tiesiog 7*6*5 = 210.
3.  DERINIAI BE PASIKARTOJIMŲ

Pradinė aibė: {a, b, c, d, e, f, g}.
Tai, pavyzdžiui, gali būti neseniai nagrinėto pavyzdžio septyni sportininkai, tik dabar situacija tokia. Bus išrinkti vėl trys nugalėtojai, tačiau bus pritaikytas "lygiavos principas"- JIE VISI GAUS VIENODUS PRIZUS. Pavyzdžiui, jie gaus kelionę į Kiprą.
Taigi, dabar jau galima kalbėti tiesiog apie "nugalėtojų TREJETUKĄ". Jo viduje TVARKA NĖRA SVARBI. Todėl dabar turėsime NESUTVARKYTUOSIUS RINKINIUS- DERINIUS.
Deriniai ( t.y. nesutvarkytieji rinkiniai) iš 7 po 3Ж
{a, b, c},
{a, b, d},
{a, d, e}
...........
{e, f, g}.
Beje, atkreipkite dėmesį,- sutvarkytieji rinkiniai ( kėliniai, deriniai) rašomi apvaliuose skliaustuose, kurie savaime pabrėžia tvarkos svarbą ( prisiminkime, pavyzdžiui, koordinates x, y, z, -jos irgi rašomos apvaliuose skliaustuose, nes svarbi jų tvarka). O nesutvarkytieji rinkiniai,-deriniai,-rašomi riestiniuose skliaustuose. Kaip aibės ar poaibiai.
Grįžkime prie 7 sportininkų, iš kurių renkamas tiesiog nugalėtojų trejetukas.
Kadangi derinių bus mažiau, nei gretinių 3! kartų ( nes, kai buvo skirtingi prizai, tai "trejetukas" galėjo savęs viduje juos dalintis 3! būdais), tai derinių ( iš 7 po 3) skaičius lygus A(7, 3) / 3! = 7! / ( 3! 4!).
Derinių iš n po m skaičių žymėsime C(n, m). Mūsų pavyzdyje:
C(7, 3) = 7! / (3! 4!).
Taip ir gimsta įžymioji derinių ( iš n po m) skaičiaus formulė":
C(n, m) = n! / m! (n-m)!
Šios formulės kilmę galima ir taip paaiškinti:
Vėl grįžkime prie 7 sportininkų, iš kurių renkamas "vienodų nugalėtojų trejetukas".
Kadangi trys nugalėtojai bus vertinami vienodai, tai juos galime žymėt "vienetukais", likusius keturis sportininkus- "nuliukais".
Gauname pradinį rinkinį:
{ 1, 1, 1, 0 , 0, 0, 0}.
Telieka išsiaiškinti, keliais būdais galima šio rinkinio elementus išdėlioti.
Jei visi 7 elementai būtų skirtingi, tai "dėlionių" skaičius, aišku, būtų kėlinių skaičius, t.y. 7!. Tačiau trys vienetai yra vienodi, juos galima perstatinėt vietomis 3! būdais, bet to "niekas nepastebės". Nieko nekeis ir keturių nulių perstatinėjimas vietomis, nors tai irgi mažins "dėlionių" skaičių, beje, 4! kartų.
Taip ir gauname 7! /(3! 4!).
Pavyzdys: Yra 12 specialistų. Keliais būdais galima sudaryti brigadą, kurioje būtų vadovas, trys pavaduotojai, ir penki nariai?
Sprendimas:
1 būdas: Vadovą galima išrinkt 12 būdais.
Tris pavaduotojus - C(11, 3) = 11! / 3! 8! = 165 būdais.
Penkis narius galima išrinkti C(8, 5) = 56 būdais.
Kadangi renkame vadovą IR pavaduotojus IR narius, tai gautus skaičius reikia sudauginti ( "kombinatorinė daugyba):
12*165*56 = 110880.
2 būdas:
Iš pradžių renkam 9 brigados dalyvius. Tai galima atlikti
C(12, 9) = 220 būdais.
Na, o jie jau ten "aiškinasi tarpusavyje".
Jie renka vadovą: 9 būdai.
Po to renkami ( iš likusių aštuonių) trys pavaduotojai.
C( 8, 3) =56 būdai.
Likusieji penki automatiškai tampa "nariais".
Sudauginę, gauname: 220*9*56 =110880.
Pavyzdys: Grupėje yra šeši vaikinai ir penkios merginos. Keliais būdais galima sudaryti 4 žmonių pogrupį taip, kad jame būtų bent viena mergina?
Sprendimas:
Keturių žmonių pogrupį galima suburt C( 11, 4) =330 būdais.
"Neleistiną pogrupį" ( t.y. be merginų) galima sudaryti
C( 6, 4) = 15 būdais.
Todėl pogrupį, kuriame būtų bent viena ( t.y. viena arba daugiau) mergina, galima sudaryti 330 - 15 = 315 būdais.

0

Norėdami rašyti žinutes privalote prisijungti!