Šiame straipsnyje pagrindinis dėmesys bus skiriamas specialiam matematikos skyriui, vadinamam kombinatorika. Formulės, taisyklės, problemų sprendimo pavyzdžiai – visa tai rasite čia, perskaitę straipsnį iki pat pabaigos.
Taigi, kas tai per skyrius? Kombinatorika nagrinėja bet kokių objektų skaičiavimo klausimą. Tačiau šiuo atveju objektai yra ne slyvos, kriaušės ar obuoliai, o kažkas kita. Kombinatorika padeda mums nustatyti įvykio tikimybę. Pavyzdžiui, kokia tikimybė, kad žaidžiant kortomis priešininkas turi kozirį? Arba toks pavyzdys – kokia tikimybė, kad iš dvidešimties kamuoliukų maišelio gausite būtent b altą? Norėdami atlikti tokias užduotis, turime žinoti bent šio matematikos skyriaus pagrindus.
Kombinatorinės konfigūracijos
Atsižvelgdami į pagrindinių kombinatorikos sąvokų ir formulių klausimą, negalime neatkreipti dėmesio į kombinatorines konfigūracijas. Jie naudojami ne tik formuluojant, bet ir sprendžiant įvairius kombinacinius uždavinius. Tokių modelių pavyzdžiai:
- vieta;
- permutacija;
- kombinacija;
- numerio kompozicija;
- skaičius padalintas.
Apie pirmuosius tris plačiau pakalbėsime vėliau, tačiau šioje dalyje atkreipsime dėmesį į kompoziciją ir skaidymą. Kalbėdami apie tam tikro skaičiaus (tarkim, a) sudėtį, jie reiškia skaičiaus a vaizdavimą kaip tam tikrų teigiamų skaičių sutvarkytą sumą. O padalijimas yra netvarkinga suma.
Skyriai
Prieš pereinant tiesiai prie kombinatorikos formulių ir uždavinių svarstymo, verta atkreipti dėmesį į tai, kad kombinatorika, kaip ir kitos matematikos dalys, turi savo poskyrius. Tai apima:
- enumerative;
- struktūrinis;
- ekstremalus;
- Ramsey teorija;
- tikimybinė;
- topologinė;
- begalinis.
Pirmuoju atveju kalbame apie išvardinamąją kombinatoriką, problemos nagrinėja skirtingų konfigūracijų, kurias sudaro aibių elementai, surašymą arba skaičiavimą. Paprastai šiems rinkiniams yra taikomi tam tikri apribojimai (išsiskiriamumas, neatskiriamumas, pasikartojimo galimybė ir pan.). Ir šių konfigūracijų skaičius apskaičiuojamas naudojant sudėjimo arba daugybos taisyklę, apie kurią kalbėsime šiek tiek vėliau. Struktūrinė kombinatorika apima grafikų ir matroidų teorijas. Ekstremalios kombinatorikos problemos pavyzdys – koks yra didžiausias grafo matmuo, atitinkantis šias savybes… Ketvirtoje pastraipoje paminėjome Ramsey teoriją, kuri tiria taisyklingų struktūrų buvimą atsitiktinėse konfigūracijose. Tikimybiniskombinatorika geba atsakyti į klausimą – kokia tikimybė, kad duotoji aibė turi tam tikrą savybę. Kaip jau galima spėti, topologinė kombinatorika taiko metodus topologijoje. Ir galiausiai septintas punktas – begalinė kombinatorika tiria kombinatorikos metodų taikymą begalinėms aibėms.
Papildymo taisyklė
Tarp kombinatorikos formulių galima rasti gana paprastų, su kuriomis esame pažįstami seniai. Pavyzdys yra sumos taisyklė. Tarkime, kad mums duoti du veiksmai (C ir E), jei jie vienas kitą paneigia, veiksmas C gali būti atliktas keliais būdais (pavyzdžiui, a), o veiksmas E gali būti atliktas b būdais, tada bet kuris iš jų (C arba E) galima atlikti a + b būdais.
Teoriškai tai gana sunku suprasti, pabandysime perteikti visą esmę paprastu pavyzdžiu. Paimkime vidutinį mokinių skaičių vienoje klasėje – tarkime, dvidešimt penki. Tarp jų – penkiolika mergaičių ir dešimt berniukų. Kasdien į klasę paskiriamas vienas palydovas. Kiek būdų šiandien galima priskirti klasės palydovą? Problemos sprendimas yra gana paprastas, mes pasinaudosime papildymo taisyklėmis. Užduoties tekste nėra parašyta, kad budėti gali tik berniukai ar tik merginos. Todėl tai gali būti bet kuri iš penkiolikos mergaičių arba bet kuris iš dešimties berniukų. Taikydami sumos taisyklę, gauname gana paprastą pavyzdį, su kuriuo pradinukas nesunkiai susidoroja: 15 + 10. Paskaičiavę gauname atsakymą: dvidešimt penki. Tai yra, yra tik dvidešimt penki būdaipriskirti šios dienos pareigų klasę.
Daugybos taisyklė
Daugybos taisyklė taip pat priklauso pagrindinėms kombinatorikos formulėms. Pradėkime nuo teorijos. Tarkime, reikia atlikti kelis veiksmus (a): pirmasis veiksmas atliekamas 1 būdais, antrasis - 2, trečiasis - 3 būdais ir taip toliau, kol bus atliktas paskutinis veiksmas sa būdais. Tada visus šiuos veiksmus (kurių turime iš viso) galima atlikti N būdų. Kaip apskaičiuoti nežinomą N? Formulė mums padės: N \u003d c1c2c3…ca.
Vėlgi, teoriškai niekas neaišku, pereikime prie paprasto daugybos taisyklės taikymo pavyzdžio. Paimkime tą pačią dvidešimt penkių žmonių klasę, kurioje mokosi penkiolika mergaičių ir dešimt berniukų. Tik šį kartą reikia pasirinkti du palydovus. Jie gali būti tik berniukai arba mergaitės, arba berniukas su mergina. Mes kreipiamės į elementarų problemos sprendimą. Mes pasirenkame pirmąjį palydovą, kaip nusprendėme paskutinėje pastraipoje, gauname dvidešimt penkis galimus variantus. Antruoju budinčiu asmeniu gali būti bet kuris iš likusių žmonių. Turėjome dvidešimt penkis mokinius, pasirinkome vieną, vadinasi, bet kuris iš likusių dvidešimt keturių žmonių gali būti antrasis budintis. Galiausiai taikome daugybos taisyklę ir nustatome, kad du palydovus galima pasirinkti šešiais šimtais būdų. Šį skaičių gavome padauginę iš dvidešimt penkių ir dvidešimt keturių.
Pakeisti
Dabar apsvarstysime dar vieną kombinatorikos formulę. Šioje straipsnio dalyje mesPakalbėkime apie permutacijas. Nedelsdami apsvarstykite problemą pateikdami pavyzdį. Paimkime biliardo kamuoliukus, jų turime n-tą skaičių. Turime paskaičiuoti: kiek yra galimybių juos išdėstyti iš eilės, tai yra sudaryti užsakytą rinkinį.
Pradėkime, jei neturime kamuoliukų, tada taip pat turime nulinių išdėstymo variantų. Ir jei mes turime vieną rutulį, tada išdėstymas taip pat yra toks pat (matematiškai tai galima parašyti taip: Р1=1). Du rutuliai gali būti išdėstyti dviem skirtingais būdais: 1, 2 ir 2, 1. Todėl Р2=2. Trys kamuoliukai gali būti išdėstyti šešiais būdais (Р3=6): 1, 2, 3; 1, 3, 2; 2, 1, 3; 2, 3, 1; 3, 2, 1; 3, 1, 2. O jei tokių kamuoliukų yra ne trys, o dešimt ar penkiolika? Išvardinti visus galimus variantus labai ilgas, tada mums į pagalbą ateina kombinatorika. Permutacijos formulė padės rasti atsakymą į mūsų klausimą. Pn=nP(n-1). Jei bandytume supaprastinti formulę, gautume: Pn=n (n - 1) … 21. Ir tai yra pirmųjų natūraliųjų skaičių sandauga. Toks skaičius vadinamas faktorialu ir žymimas n!
Panagrinėkime problemą. Vadovas kiekvieną rytą stato savo būrį į eilę (dvidešimt žmonių). Būryje yra trys geriausi draugai - Kostja, Sasha ir Lesha. Kokia tikimybė, kad jie bus vienas šalia kito? Norėdami rasti atsakymą į klausimą, turite padalyti „gero“rezultato tikimybę iš bendro rezultatų skaičiaus. Bendras permutacijų skaičius yra 20!=2,5 kvintilijono. Kaip suskaičiuoti „gerų“rezultatų skaičių? Tarkime, kad Kostja, Sasha ir Lesha yra vienas supermenas. Tada mesTurime tik aštuoniolika dalykų. Permutacijų skaičius šiuo atveju yra 18=6,5 kvadrilijono. Turėdami visa tai, Kostya, Sasha ir Lesha gali savavališkai judėti tarpusavyje savo nedalomu trigubu, ir tai yra dar 3!=6 variantai. Taigi iš viso turime 18 „gerų“žvaigždynų!3! Tereikia rasti norimą tikimybę: (18!3!) / 20! Tai yra apytiksliai 0,016. Pavertus procentais, pasirodo, tik 1,6%.
Apgyvendinimas
Dabar panagrinėsime dar vieną labai svarbią ir reikalingą kombinatorikos formulę. Apgyvendinimas yra kitas mūsų numeris, kurį siūlome apsvarstyti šioje straipsnio dalyje. Mes tapsime sudėtingesni. Tarkime, kad norime nagrinėti galimas permutacijas, tik ne iš visos aibės (n), o iš mažesnės (m). Tai yra, mes svarstome n elementų permutacijas pagal m.
Pagrindines kombinatorikos formules reikia ne tik įsiminti, bet ir suprasti. Net nepaisant to, kad jie tampa sudėtingesni, nes turime ne vieną parametrą, o du. Tarkime, m \u003d 1, tada A \u003d 1, m \u003d 2, tada A=n(n - 1). Jei dar labiau supaprastinsime formulę ir pereisime prie žymėjimo naudodami faktorines, gausime gana glaustą formulę: A \u003d n! / (n - m)!
Derinys
Išnagrinėjome beveik visas pagrindines kombinatorikos formules su pavyzdžiais. Dabar pereikime prie paskutinio pagrindinio kombinatorikos kurso svarstymo etapo – derinio pažinimo. Dabar pasirinksime m elementų iš turimų n, tuo tarpu visus pasirinksime visais įmanomais būdais. Kuo tai skiriasi nuo apgyvendinimo? Mes neapsvarstyti tvarką. Šis nesutvarkytas rinkinys bus derinys.
Nedelsdami įveskite žymėjimą: C. Paimame m kamuoliukų išdėstymą iš n. Nustojame kreipti dėmesį į tvarką ir gauname pasikartojančius derinius. Norėdami gauti derinių skaičių, turime padalinti vietų skaičių iš m! (m faktorialas). Tai yra, C \u003d A / m! Taigi, yra keletas būdų, kaip pasirinkti iš n rutuliukų, maždaug lygių tam, kiek pasirinkti beveik viską. Tam yra logiška išraiška: pasirinkti šiek tiek yra tas pats, kas išmesti beveik viską. Taip pat šioje vietoje svarbu paminėti, kad bandant pasirinkti pusę elementų galima pasiekti maksimalų derinių skaičių.
Kaip pasirinkti formulę problemai išspręsti?
Išsamiai išnagrinėjome pagrindines kombinatorikos formules: išdėstymą, permutaciją ir derinimą. Dabar mūsų užduotis yra palengvinti reikalingos kombinatorikos problemos sprendimo formulės pasirinkimą. Galite naudoti šią gana paprastą schemą:
- Paklauskite savęs: ar užduoties tekste atsižvelgiama į elementų tvarką?
- Jei atsakymas yra neigiamas, naudokite kombinuotą formulę (C=n! / (m!(n - m)!)).
- Jei atsakymas yra neigiamas, turite atsakyti į dar vieną klausimą: ar visi elementai įtraukti į derinį?
- Jei atsakymas yra taip, naudokite permutacijos formulę (P=n!).
- Jei atsakymas yra neigiamas, naudokite paskirstymo formulę (A=n! / (n - m)!).
Pavyzdys
Apsvarstėme kombinatorikos elementus, formules ir kai kuriuos kitus klausimus. Dabar pereikime prieatsižvelgiant į tikrą problemą. Įsivaizduokite, kad prieš jus yra kivis, apelsinas ir bananas.
Pirmas klausimas: kiek būdų juos galima pertvarkyti? Norėdami tai padaryti, naudojame permutacijos formulę: P=3!=6 būdai.
Antras klausimas: kiek būdų galima pasirinkti vieną vaisių? Tai akivaizdu, turime tik tris variantus - pasirinkti kivi, apelsiną arba bananą, tačiau taikome kombinacijos formulę: C \u003d 3! / (2!1!)=3.
Trečias klausimas: kiek būdų galima pasirinkti du vaisius? Kokias galimybes turime? Kiviai ir apelsinai; kivi ir bananas; apelsinas ir bananas. Tai yra, trys parinktys, tačiau tai lengva patikrinti naudojant kombinuotą formulę: C \u003d 3! / (1!2!)=3
Ketvirtas klausimas: kaip galima pasirinkti tris vaisius? Kaip matote, yra tik vienas būdas pasirinkti tris vaisius: paimkite kivi, apelsiną ir bananą. C=3! / (0!3!)=1.
Penktas klausimas: kiek būdų galite pasirinkti bent vieną vaisių? Ši sąlyga reiškia, kad galime paimti vieną, du arba visus tris vaisius. Todėl pridedame C1 + C2 + C3=3 + 3 + 1=7. Tai yra, turime septynis būdus, kaip nuo stalo paimti bent vieną vaisiaus gabalėlį.
