Bendrieji kombinatorikos dėsniai

Bendrieji kombinatorikos dėsniai

Sprendžiant įvairius kombinatorikos uždavinius, dažniausiai naudojami sumavimo, sandaugos, priskirties ir išskirties dėsniai.

Sumavimo dėsnis

Jei kokiam nors objektui A pasirinkti yra m būdų, o kitam objektui B pasirinkti yra n būdų, tai pasirinkti “arba A, arba B” yra m + n būdų.

Pastaba. Taikant taip suformuluot¹ sumavimo dėsnį, reikia žiūrėti, kad nei vienas objekto A pasirinkimo būdas nesutaptų su kuriuo nors objekto B pasirinkimo būdu. Jei tokių sutapimų yra k, tai susidaro m + n – k pasirinkimo būdų.

Pavyzdys. Pintinėje yra 12 obuolių ir 10 apelsinų. Jonukas pasirenka arba obuolį, arba apelsin¹, o paskui Onutė ima ir obuolį, ir apelsin¹. Keliais būdais Jonukas gali paimti vaisių ir kada Onutei didesnė pasirinkimo laisvė: ar kai Jonukas paima obuolį, ar kai apelsin¹?

Aišku, kad Jonukas obuolį gali pasirinkti 12 skirtingų būdų, o apelsin¹ – 10 skirtingų būdų. Vadinasi, pasirinkti arba obuolį, arba apelsin¹ galima 12 + 10 = 22 būdais.

Į antr¹ klausimo dalį atsakysime po sandaugos dėsnio.

Sandaugos dėsnis

Jei objektui A pasirinkti yra m būdų, o po kiekvieno tokio pasirinkimo objekt¹ B galima pasirinkti n būdais, tai por¹ (A, B) pasirinkti nurodyt¹ja tvarka galima m n būdais.

Pavyzdys. Panagrinėkime aukščiau pateikt¹ pavyzdį. Tarkime, Jonukas pasirinko obuolį. Tada Onutei galimų pasirinkimo būdų yra 11 10. Jei Jonukas būtų pasirinkźs apelsin¹, tai Onutei paimti ir obuolį, ir apelsin¹ būtų galima 12   9 būdais. Kadangi 11 10 > 12 9, tai Onutei didesnė pasirinkimo laisvė bus tada, jei Jonukas pasirinks obuolį.

Priskirties ir išskirties dėsnis

Sakykime, kad kai kuriems iš N turimų daiktų būdingos savybės . Simboliu pažymėkime skaičių daiktų, turinčių savybes (į kitas tų daiktų savybes nekreipiame dėmesio). Jei reikės pabrėžti, kad imami tik tie daiktai, kurie neturi kurios nors savybės, tai t¹ savybź rašysime su brūkšneliu. Pavyzdžiui, žymi skaičių daiktų, turinčių savybes ir , bet neturinčių savybės (į kitas jų savybes nekreipiame dėmesio).

Tada priskirties ir išskirties dėsnis bus užrašomas taip:

(3.2.1)

Įrodymas. Šį dėsnį įrodysime pilnosios matematinės indukcijos metodu.

Dėsnis teisingas, kai kiekvienas daiktas turi savybź a. Tada .

Tarkime, kad dėsnis teisingas, kai savybių skaičius lygus :

(3.2.2)

Įrodysime, kad dėsnis teisingas, kai savybių skaičius yra n.

(3.2.2) formulź taikykime daiktų aibei. Gausime:

(3.2.3)

Iš (3.2.2) lygybės atėmź (3.2.3), gausime

(3.2.4)

(3.2.4) formulės kairiosios pusės skirtumas

yra lygus , nes iš skaičiaus daiktų, kurie neturi savybių atimame skaičių daiktų, neturinčių tų pačių savybių ir turinčių savybź . Vadinasi, atėmus liks skaičus daiktų, neturinčių savybių

Pavyzdys. Pasinaudodami priskirties ir išskirties formule, apskaičuokime, kiek tarp natūraliųjų skaičių nuo vieneto iki 100 yra skaičių, kurie nesidalo nei iš 2-jų, nei iš 3-jų, nei iš penkių.

Tarkime, – tai skaičiaus savybė dalintis iš 2-jų, – tai skaičiaus savybė dalintis iš 3-jų, o – tai skaičiaus savybė dalintis iš 5-ių. Tada

Norint sužinoti, kiek skaičių nuo 1 iki N dalijasi iš n, reikia N padalinti iš n ir imti gautojo dalmens sveik¹j¹ dalį į mažesni¹j¹ pusź. Todėl , , , , , , .

Vadinasi, .