Kombinatorika
5 (100%) 1 vote

Kombinatorika

1.Naturalieji skaiciai. Matematines indukcijos principas

Nepriestaringumo desnis. Du vienas kitam priesingi teiginiai p ir ¯p vienu metu negali buti teisingi (p^¯p=0)

Treciojo negalimo desnis. Is dvieju priesingu teiginiu p ir ¯p vienas visada yra teisingas (p^¯p=1).

Apibrezimas. Naturaliaisiais skaiciais vadiname netuscios aibes N elementus, jeigu tarp kai kuriu is ju

egzistuoja sarysis ,,a‘ eina po a“, tenkinantis aksiomas:

1) egzistuoja skaicius (vadinamas vienetu), neinantis po jokio kito skaiciaus;

2) po kiekvieno skaiciaus eina tik vienas skaicius;

3) kiekvienas skaicius eina ne daugiau kaip po vieno skaiciaus;

4) aibes N poaibis M sutampa su pacia aibe N, jei jis turi tokias savybes:

a) 1 $ M,

b) jeigu skaicius a priklauso M, tai ir po a einantis skaicius a‘ taip pat priklauso aibei M

Matematines indukcijos principas

Tegu p(n) – kazkoks teiginys apie naturaluji skaiciu n. Tarkime, kad p(1) yra teisingas, ir is prielaidos, kad p(n) yra teisingas, sugebame isvesti, kad p(n‘) irgi yra teisingas. Darome isvada: teiginys p(n) yra teisingas visiems n $ N.

Archimedo aksioma. Bet kuriai naturaliuju skaiciu porai a, b galima rasti toki naturaluji skaiciu n, kad an>b.

Maziausiojo elemento principas. Kiekvienas netuscias naturaliuju skaiciu aibes poaibis turi maziausia elementa.

Dirichle (P.G.L. Dirichlet, 1805–1859) principas. Jei m rutuliu yra sudeti i n < m deziu, tai bent vienoje dezeje yra 2 ar daugiau rutuliu.

2.Dauginimo tasykle

Dekarto ( Rene Descartes, 1596–1650) sandauga. Tai sutvarkytuju poru aibe.

A × B = {(ai, bj) : ai e A, bj e B, 1 ≤i ≤ n, 1 ≤ j≤ m}

1 teorema. |A × B| = |A| |B|.

2 teorema. Jei abecele A turi n raidziu, tai galime sudaryti n^k zodziu, kuriu ilgis yra k.

3 teorema. Aibes A = {a1, . . . , an} poaibiu, iskaitant ir tusciaji, skaicius lygus 2^n.

|>Nagrinekime visu poaibiu aibes atvaizdi aibeje, sudarytoje is n zodziu su ,,raidemis“ 0, 1. Sis atvaizdis apibreztas taip: A ] P = {ai1 , . . . , aik} 7! (0 . . . , 0, 1, 0 . . . , 0, 1, 0, . . . 0) cia ,,raide“ 1 irasyta is-oje pozicijoje pabreziant, kad is-asis aibes A elementas patenka i poaibi P. Atvaizdis yra bijekcija. Pagal 2 teorema siu zodziu aibes galia lygi 2^n ir sutampa su k poaibiu aibes galia.<|

4 teorema. Jei X = {x1, . . . , xn} ir Y = {y1, . . . , ym}, tai funkciju f : X ->aibes galia lygi m^n.

|>Kiekviena funkcija f : X ->galime vienareiksmiskai isreiksti vektoriumi (f(x1),…,f(xn)). Kadangi dabar ,,raide“ f(xj ), 1≤ j≤ n, imama is abeceles Y, turincios m raidziu, teoremos teiginys isplaukia is 2 teorem. <|

Sioje teoremoje isvesta formule paaiskina daznai naudojama zymeni {f : X ->Y } =: Y^X .

3. Gretiniai, keliniai ir deriniai

1 teorema. Ak/n = n(n − 1)(n − 2) • • • (n − k + 1).

2 teorema. Deriniu is n po k skaicius lygus Ck/n = (Ak/n)/k!= n!/(k!(n − k)!)

Mokslineje literaturoje vartojami ir tokie deriniu is n po k zymemys: (n//k)= (n//(k, n − k))

Paimtas is n aibes k elementu rinkinys su galimais pasikartojimais vadinamas kartotiniu sios aibes k deriniu. Ju skaicius Hk/n = Ck/(n+k−1)=((n+k−1)//k)

4. Kartotiniai gretiniai

Teorema. Polinominiu koeficientu formule yra (n//(p1, . . . , pk))

|>Dauginkime panariui n nezinomuju sumu, imdami xi1 is pirmosios sumos, xi2 is antrosios sumos ir t.t., xin is n-osios sumos ir sudekime visas sandaugas

(2) xi1 • • • xin. Kadangi ij 2 {1, . . . , k}, 1 ≤ j ≤ n, tai turesime k^n sandaugu (visus n zodzius is k raidziu x1, . . . , xk). Sudedant (2) sandaugas, reikia sutraukti panasius narius. Jie bus to paties pavidalo, t.y.

Šiuo metu Jūs matote 52% šio straipsnio.
Matomi 545 žodžiai iš 1050 žodžių.
Peržiūrėkite iki 100 straipsnių per 24 val. Pasirinkite apmokėjimo būdą:
El. bankininkyste - 1,45 Eur.
Įveskite savo el. paštą (juo išsiųsime atrakinimo kodą) ir spauskite Tęsti.
SMS žinute - 2,90 Eur.
Siųskite sms numeriu 1337 su tekstu INFO MEDIA ir įveskite gautą atrakinimo kodą.
Turite atrakinimo kodą?
Po mokėjimo iškart gausite atrakinimo kodą, kurį įveskite į laukelį žemiau:
Kodas suteikia galimybę atrakinti iki 100 straispnių svetainėje ir galioja 24 val.