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, .