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

Kombinatorika: deriniai su pasikartojimais ir išimtys

6. DERINIAI BE PASIKARTOJIMŲ- KĖLINIŲ SU PASIKARTOJIMAIS ATSKIRAS ATVEJIS

Tokią išvadą padarysime, jei kiekvienam deriniui iš n po m elementų, t.y. nesutvarkytam m elementų rinkiniui abipus vienareikšmiškai priskirsime sutvarkytąjį n elementų rinkinį ( kėlinį su pasikartojimais), kuriame bus m vienetukų, ir
n- m nuliukų.
Pavyzdys: Panagrinėsime atvejį n=5, m=3.
Pradinė aibė: [a, b, c, d, e].
Sudarome galimus derinius be pasikartojimų. Toliau kairėje pusėje pateikti deriniai ( iš 5 po 2), dešinėje- juos atitinkantys kėliniai su pasikartojimais.
{a, b, c}            (1,1,1,0,0)
{a, b, d}            (1,1,0,1,0)
{a, b, e}            (1,1,0,0,1)
{a, c, d}            (1,0,1,1,0)
{a, c, e}            (1,0,1,0,1)
{a, d, e}            (1,0,0,1,1)
{b, c, d}            (0,1,1,1,0)
{b, c, e}            (0,1,1,0,1)
{b, d, e}            (0,1,0,1,1)
{{c, d, e}            (0,0,1,1,1)
Aišku, matome visus derinius ( be pasikartojimų) iš 5 po 3 elementus, ir tiek pat skirtingų kėlinių su pasikartojimais, kurie sudaryti iš trijų vienetų ir dviejų nulių.
Todėl
C(5, 3) = K(3, 2) = 5! / 2! 3! =10.
Taigi, gerai žinome derinių be pasikartojimų iš n po m elementų skaičiaus formulė gali būti gauta, taikant kėlinių su pasikartojimais (apie juos kalbėjome ankstesnėje pamokėlėje http://www.ematematikas.lt/forumas/t10550-matematikos-pamokele-kombinatorika-2.html ) formulę:
C(n, m) = K( m, n- m) = n! / (m! (n -m)! ).

7.    DERINIAI SU PASIKARTOJIMAIS

Panagrinėkime pavyzdį:
Pavyzdys:  Parduotuvėje yra penkių rūšių tušinukų. Keliais būdais pirkėjas gali pasirinkti tris tušinukus?
Pradinis rinkinys:
[a, b, c, d, e]
Deriniai su pasikartojimais ( iš penkių po tris):
{a,a, a}
{a, a, b}
{a,b,b}
...........
{a,b,c}
..........
{d,e,e}
{e,e,e}
Kaip apskaičiuoti tokių derinių, t.y. nesutvarkytųjų rinkinių, kurių elementai gali kartotis, skaičių?
Mums ir vėl padės kėliniai be pasikartojimų. Jei tik mes sugebėsime kiekvienam deriniui abipus vienareikšmiškai priskirti kėlinį su pasikartojimais. O kėlinių su pasikartojimais skaičių skaičiuoti mokame.
Darome taip. Pradinėje aibėje yra n=5 elementai, tarp jų yra
n- 1 =4 tarpeliai. Tarpelius žymėsime nuliukais, elementus ( kurių vietas nurodo jų padėtis pradiniame rinkinyje), patekusius į derinį- vienetukais, į derinį nepatekusius elementus- vėl nuliukais. Tokiu būdu formuosime kėlinius, kurių kiekviename bus  k=3 vienetukų, ir n- 1=4 nuliukų. Kiekviename tokiame kėlinyje bus n +k -1 =7 elementai.
Pavyzdžiui, derinį {a, a, a} atitinka kėlinys (1,1,1,0,0,0,0)
Derinį {a,a,b} atitinka kėlinys  ( 1,1,0,1,0,0,0)
Derinį {a, b, c} atitinka kėlinys ( 1,0,1,0,1,0,0)
Derinį (d, e,e} atitinka kėlinys  (0,0,0,1,0,1,1)
Ir t.t.
Taigi, derinių su pasikartojimais iš n=5 po k=3 galima sudaryti tiek, kiek galima sudaryti skirtingų kėlinių su pasikartojimais, kiekviename kurių yra k=3 vienetukų ir n-1=4 nuliukų:
K(k, n- 1) = K(3, 4) = 7! / (3! 4!) = C( 7, 3) =35.
Derinių su pasikartojimais iš n po k elementų skaičių žymėsime D(n,k).
Kaip jau matėme,
D(n, k) = K(k, n- !) = C(n+k- 1, k)
t.y.  D(n, k) = (n+k -1)! / (k! (n -1)! )
Pavyzdys:  Yra 6 rūšių gėlių. Keliais būdais galima sukomponuoti puokštę iš 10 gėlių?
Sprendimas pagal formulę:
n=6, k=10, n+k- 1 = 15.
D(6, 10) = C( 15, 10) = 15! /(10! 5! ) = 3003.
Modelio pavyzdžiai:
[a, b, c, d, e, f]
Puokštės (deriniai)  ir atitinkami kėliniai:
{a, a, a, b, d, d, d,e,f,f}    (1,1,1,0,1,0,0,1,1,1,0,1,0,1,1)
{a,b,c, d, d, e, e, f, f, f}    (1,0,1,0,1,0,1,1,0,1,1,0,1,1,1)
Ir t.t.

0

Norėdami rašyti žinutes privalote prisijungti!