Konspektai

Kombinatorikos ir grafų teorijos medžiaga

9.8   (3 atsiliepimai)
Kombinatorikos ir grafų teorijos medžiaga 1 puslapis
Kombinatorikos ir grafų teorijos medžiaga 2 puslapis
Kombinatorikos ir grafų teorijos medžiaga 3 puslapis
Kombinatorikos ir grafų teorijos medžiaga 4 puslapis
www.nemoku.lt
www.nemoku.lt
Aukščiau pateiktos peržiūros nuotraukos yra sumažintos kokybės. Norėdami matyti visą darbą, spustelkite peržiūrėti darbą.
Ištrauka

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 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.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. 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. (3) xp1/1 · · · xpk/k, nusakomo vektoriumi ¯p. Kiek tokiu panasiu nariu kaip (3)? Raide x1 (2) sandaugoje galejo uzimti p1 poziciju is n galimu, t.y. buvo (n//p1) budu, x2 – ((n−p1)//p2 ) budu ir t.t. Tesdami si procesa, gautume (n//p1)· ((n−p1)//p2)···((n−p1−p2−·· ·− pk−1)//pk )= n!/(p1! . . . pk!) Cia pasinaudojome binominio koeficiento formule.Pagal 3 teorema Snm =(n∑k=m)(−1)^k(n//m)*((n − m)//(k − m))=(n//m)(n∑k=m)(−1)*k((n − m)//(k − m)) Pakeiskime sumavimo indeksa k − m = j ir gausime Snm = (n//m)(n−m∑j=0)(−1)^(j+m)((n−m)//j) = (−1)^m(n//m)(1 − 1)^(n−m) = 0,jei m≠n.Jei teisinga pirmoji lygybe, tai istatydami patikriname antraja. Skaiciuojame keisdami sumavimo tvarka (n∑k=0)(−1)^k(n//k)bk =(n∑k=0)(−1)^k(n//k)*(k∑m=0)(−1)^m(k//m)am = (n∑m=0)(−1)^m*am (n∑k=m)(−1)^k (n//k)*(k//m) = anδnn = an. Paskutiniame zingsnyje pritaikeme ortogonalumo sarysi (6 teorema). Desiniojoje lygybes puseje esanciam binominiam koeficientui pritaikykime Paskalio lygybe. Gauname hn := (n∑k=1)(−1)^(k+1)(n//k)1/k = (n∑k=1)(−1)^(k+1)(((n − 1)//k)+((n − 1)//(k − 1))1/k = hn−1 + (−1)^(n+1) ((n − 1)//n)1/n + (n∑k=1)(−1)^(k+1)((n − 1//(k − 1))1/k (1) Antrasis demuo lygus nuliui, skaiciuojame treciaji. Jis lygus (n∑k=1)(−1)^(k+1) ((n − 1)!)/(k!(n − k)!) = −1/n (n∑k=1)(−1)^k(n//k) = −1/n[(1 − 1)^n − 1] = 1/n. Istate i (1) lygybe gauname rekurentuji sarysi hn = hn−1 + 1/n. Kadangi f1 = 1, pagal matematines indukcijos principa is jo isplaukia hn = 1 + 1/2+1/3+ · · · +1/n. Pazymekime U = A1U· · ·UAn. Fukcija IA : U -> {0, 1} vadinsime poaibio A C U indikatoriumi, jeigu IA(x) = 1 tada ir tik tada, kai x e A. Vadinasi, |A| = (∑x2U)IA(x). Todel a(i) = (∑x2U)IAi (x), a(i, j) =(∑x2U) IAi∩Aj (x), . . . , a(i1, . . . , ik) =(∑x2U)IAi1 ∩···∩Aik(x), 1≤i

Daugiau informacijos...

Šį darbą sudaro 6933 žodžiai, tikrai rasi tai, ko ieškai!

★ Klientai rekomenduoja


Šį rašto darbą rekomenduoja mūsų klientai. Ką tai reiškia?

Mūsų svetainėje pateikiama dešimtys tūkstančių skirtingų rašto darbų, kuriuos įkėlė daugybė moksleivių ir studentų su skirtingais gabumais. Būtent šis rašto darbas yra patikrintas specialistų ir rekomenduojamas kitų klientų, kurie po atsisiuntimo įvertino šį mokslo darbą teigiamai. Todėl galite būti tikri, kad šis pasirinkimas geriausias!

Detali informacija
Darbo tipas
Lygis
Universitetinis
Failo tipas
Word failas (.doc)
Apimtis
4 psl., (6933 ž.)
Darbo duomenys
  • Kombinatorikos konspektas
  • 4 psl., (6933 ž.)
  • Word failas 146 KB
  • Lygis: Universitetinis
www.nemoku.lt Atsisiųsti šį konspektą
Privalumai
Pakeitimo garantija Darbo pakeitimo garantija

Atsisiuntei rašto darbą ir neradai jame reikalingos informacijos? Pakeisime jį kitu nemokamai.

Sutaupyk 25% pirkdamas daugiau Gauk 25% nuolaidą

Pirkdamas daugiau nei vieną darbą, nuo sekančių darbų gausi 25% nuolaidą.

Greitas aptarnavimas Greitas aptarnavimas

Išsirink norimus rašto darbus ir gauk juos akimirksniu po sėkmingo apmokėjimo!

Atsiliepimai
www.nemoku.lt
Dainius Studentas
Naudojuosi nuo pirmo kurso ir visad randu tai, ko reikia. O ypač smagu, kad įdėjęs darbą gaunu bet kurį nemokamai. Geras puslapis.
www.nemoku.lt
Aurimas Studentas
Puiki svetainė, refleksija pilnai pateisino visus lūkesčius.
www.nemoku.lt
Greta Moksleivė
Pirkau rašto darbą, viskas gerai.
www.nemoku.lt
Skaistė Studentė
Užmačiau šią svetainę kursiokės kompiuteryje. :D Ką galiu pasakyti, iš kitur ir nebesisiunčiu, kai čia yra viskas ko reikia.
Palaukite! Šį darbą galite atsisiųsti visiškai NEMOKAMAI! Įkelkite bet kokį savo turimą mokslo darbą ir už kiekvieną įkeltą darbą būsite apdovanoti - gausite dovanų kodus, skirtus nemokamai parsisiųsti jums reikalingus rašto darbus.
Vilkti dokumentus čia:

.doc, .docx, .pdf, .ppt, .pptx, .odt