Tento článok sa zameria na špeciálnu časť matematiky nazývanú kombinatorika. Vzorce, pravidlá, príklady riešenia problémov - to všetko nájdete tu, keď si prečítate článok až do konca.
A čo je teda táto sekcia? Kombinatorika sa zaoberá problematikou počítania akýchkoľvek predmetov. Ale v tomto prípade nejde o slivky, hrušky alebo jablká, ale o niečo iné. Kombinatorika nám pomáha nájsť pravdepodobnosť udalosti. Napríklad pri hraní kariet, aká je pravdepodobnosť, že súper má tromf? Alebo taký príklad – aká je pravdepodobnosť, že z vrecúška s dvadsiatimi loptičkami dostanete práve biele? Práve na tento druh úloh potrebujeme poznať aspoň základy tejto časti matematiky.
Kombinatorické konfigurácie
Vzhľadom na problematiku základných pojmov a vzorcov kombinatoriky nemôžeme nevenovať pozornosť kombinatorickým konfiguráciám. Používajú sa nielen na formuláciu, ale aj na riešenie rôznych kombinatorických problémov. Príklady takýchto modelov sú:
- placement;
- permutation;
- combination;
- zloženie čísla;
- rozdeliť číslo.
O prvých troch si povieme podrobnejšie neskôr, no v tejto časti sa budeme venovať kompozícii a deleniu. Keď hovoria o zložení určitého čísla (povedzme a), majú na mysli zobrazenie čísla a ako usporiadaného súčtu nejakých kladných čísel. A rozdelenie je neusporiadaná suma.
Sekcie
Skôr než prejdeme priamo k vzorcom kombinatoriky a zvažovaniu problémov, stojí za to venovať pozornosť tomu, že kombinatorika, podobne ako ostatné časti matematiky, má svoje podsekcie. Patria sem:
- enumerative;
- structural;
- extreme;
- Ramseyho teória;
- pravdepodobnostné;
- topological;
- nekonečno.
V prvom prípade hovoríme o enumeratívnej kombinatorike, problémom je enumerácia alebo počítanie rôznych konfigurácií, ktoré sú tvorené prvkami množín. Na tieto zostavy sú spravidla uvalené určité obmedzenia (rozlíšiteľnosť, nerozlíšiteľnosť, možnosť opakovania a pod.). A počet týchto konfigurácií sa vypočíta pomocou pravidla sčítania alebo násobenia, o ktorom budeme hovoriť o niečo neskôr. Štrukturálna kombinatorika zahŕňa teórie grafov a matroidov. Príkladom problému extrémnej kombinatoriky je, aký je najväčší rozmer grafu, ktorý spĺňa nasledujúce vlastnosti… Vo štvrtom odseku sme spomenuli Ramseyho teóriu, ktorá študuje prítomnosť pravidelných štruktúr v náhodných konfiguráciách. Pravdepodobnýkombinatorika je schopná odpovedať na otázku – aká je pravdepodobnosť, že daná množina má určitú vlastnosť. Ako môžete hádať, topologická kombinatorika aplikuje metódy v topológii. A nakoniec, siedmy bod - nekonečná kombinatorika študuje aplikáciu kombinatoriky na nekonečné množiny.
Pravidlo pridávania
Medzi vzorcami kombinatoriky možno nájsť celkom jednoduché, ktoré poznáme už dlho. Príkladom je pravidlo súčtu. Predpokladajme, že máme dve akcie (C a E), ak sa navzájom vylučujú, akciu C možno vykonať niekoľkými spôsobmi (napríklad a) a akciu E možno vykonať spôsobmi b, potom ktorýkoľvek z nich (C alebo E) možno vykonať spôsobmi a + b.
Teoreticky je to dosť ťažké pochopiť, pokúsime sa celú pointu priblížiť jednoduchým príkladom. Vezmime si priemerný počet žiakov v jednej triede – povedzme dvadsaťpäť. Je medzi nimi pätnásť dievčat a desať chlapcov. Do triedy je denne priradený jeden sprievodca. Koľkými spôsobmi je dnes možné prideliť účastníka triedy? Riešenie problému je celkom jednoduché, uchýlime sa k pravidlu sčítania. V texte úlohy sa nehovorí, že službu môžu mať len chlapci alebo len dievčatá. Preto to môže byť ktorékoľvek z pätnástich dievčat alebo ktorýkoľvek z desiatich chlapcov. Aplikovaním súčtového pravidla dostaneme pomerne jednoduchý príklad, s ktorým si ľahko poradí aj žiak základnej školy: 15 + 10. Po výpočte dostaneme odpoveď: dvadsaťpäť. To znamená, že existuje len dvadsaťpäť spôsobovprideľte dnes služobnú triedu.
Pravidlo násobenia
K základným vzorcom kombinatoriky patrí aj pravidlo násobenia. Začnime teóriou. Predpokladajme, že musíme vykonať niekoľko akcií (a): prvá akcia sa vykoná 1 spôsobmi, druhá - 2 spôsobmi, tretia - 3 spôsobmi a tak ďalej, kým sa posledná a-akcia nevykoná spôsobmi sa. Potom je možné všetky tieto akcie (ktorých máme celkom) vykonať N spôsobmi. Ako vypočítať neznáme N? Vzorec nám s tým pomôže: N \u003d c1c2c3…ca.
Opäť, teoreticky nie je nič jasné, prejdime k jednoduchému príkladu použitia pravidla násobenia. Vezmime si rovnakú triedu dvadsiatich piatich ľudí, v ktorej študuje pätnásť dievčat a desať chlapcov. Tentoraz si musíme vybrať dvoch sprievodcov. Môžu to byť buď len chlapci alebo dievčatá, alebo chlapec s dievčaťom. Obraciame sa na základné riešenie problému. Vyberáme prvého obsluhujúceho, ako sme sa rozhodli v poslednom odseku, dostaneme dvadsaťpäť možných možností. Druhá osoba v službe môže byť ktorákoľvek zo zostávajúcich osôb. Mali sme dvadsaťpäť študentov, vybrali sme si jedného, čo znamená, že druhý v službe môže byť ktorýkoľvek zo zvyšných dvadsiatich štyroch ľudí. Nakoniec použijeme pravidlo násobenia a zistíme, že dvoch sprievodcov možno vybrať šesťsto spôsobmi. Toto číslo sme dostali vynásobením dvadsiatich piatich a dvadsiatich štyroch.
Výmena
Teraz zvážime ešte jeden kombinatorický vzorec. V tejto časti článku smeHovorme o permutáciách. Okamžite zvážte problém pomocou príkladu. Zoberme si biliardové gule, máme ich n-tý počet. Musíme vypočítať: koľko možností je na to, aby sme ich usporiadali do radu, teda aby sme vytvorili usporiadanú súpravu.
Začnime, ak nemáme loptičky, tak máme aj nulové možnosti umiestnenia. A ak máme jednu guľu, potom je usporiadanie tiež rovnaké (matematicky to možno zapísať takto: Р1=1). Dve loptičky môžu byť usporiadané dvoma rôznymi spôsobmi: 1, 2 a 2, 1. Preto Р2=2. Tri loptičky môžu byť usporiadané šiestimi spôsobmi (Р3=6): 1, 2, 3; 1, 3, 2; 2, 1, 3; 2, 3, 1; 3, 2, 1; 3, 1, 2. A ak nie sú tri takéto loptičky, ale desať alebo pätnásť? Vymenovať všetky možné možnosti je veľmi dlhé, vtedy nám prichádza na pomoc kombinatorika. Permutačný vzorec nám pomôže nájsť odpoveď na našu otázku. Pn=nP(n-1). Ak sa pokúsime vzorec zjednodušiť, dostaneme: Pn=n (n - 1) … 21. A toto je súčin prvých prirodzených čísel. Takéto číslo sa nazýva faktoriál a označuje sa ako n!
Pozrime sa na problém. Vodca každé ráno buduje svoje oddelenie v rade (dvadsať ľudí). V oddelení sú traja najlepší priatelia - Kostya, Sasha a Lesha. Aká je pravdepodobnosť, že budú vedľa seba? Ak chcete nájsť odpoveď na otázku, musíte vydeliť pravdepodobnosť „dobrého“výsledku celkovým počtom výsledkov. Celkový počet permutácií je 20!=2,5 quintilióna. Ako spočítať počet „dobrých“výsledkov? Predpokladajme, že Kostya, Sasha a Lesha sú jeden superman. Potom myMáme len osemnásť predmetov. Počet permutácií je v tomto prípade 18=6,5 kvadriliónov. S tým všetkým sa Kostya, Sasha a Lesha môžu ľubovoľne pohybovať medzi sebou vo svojej nedeliteľnej trojke a toto sú ešte 3!=6 možností. Celkovo teda máme 18 „dobrých“konštelácií! 3! Musíme len nájsť požadovanú pravdepodobnosť: (18!3!) / 20! Čo je približne 0,016. Ak sa prevedie na percento, ukáže sa, že je to len 1,6 %.
Ubytovanie
Teraz zvážime ďalší veľmi dôležitý a potrebný kombinatorikový vzorec. Ubytovanie je našou ďalšou otázkou, ktorú odporúčame zvážiť v tejto časti článku. Ideme to skomplikovať. Predpokladajme, že chceme uvažovať o možných permutáciách, len nie z celej množiny (n), ale z menšej (m). To znamená, že uvažujeme permutácie n položiek podľa m.
Základné vzorce kombinatoriky by ste si nemali len zapamätať, ale aj pochopiť. Aj napriek tomu, že sa stávajú komplikovanejšími, keďže nemáme jeden parameter, ale dva. Predpokladajme, že m \u003d 1, potom A \u003d 1, m \u003d 2, potom A \u003d n(n - 1). Ak vzorec ďalej zjednodušíme a prejdeme na zápis pomocou faktoriálov, dostaneme celkom výstižný vzorec: A \u003d n! / (n - m)!
Kombinácia
Zvážili sme takmer všetky základné vzorce kombinatoriky s príkladmi. Teraz prejdime k záverečnej fáze zvažovania základného kurzu kombinatoriky – k poznaniu kombinácie. Teraz vyberieme m položiek z n, ktoré máme, pričom vyberieme všetky všetkými možnými spôsobmi. Ako sa to teda líši od ubytovania? Nebudemezvážiť poriadok. Táto neusporiadaná sada bude kombináciou.
Okamžite zaveďte zápis: C. Z n vyberieme umiestnenia m loptičiek. Prestávame venovať pozornosť objednávke a dostávame opakujúce sa kombinácie. Aby sme získali počet kombinácií, musíme počet umiestnení vydeliť m! (m faktoriál). To znamená, C \u003d A / m! Existuje teda niekoľko spôsobov, ako si vybrať z n loptičiek, približne rovnakých, koľko si vybrať takmer všetko. Existuje na to logické vyjadrenie: vybrať si trochu je to isté, ako vyhodiť takmer všetko. Na tomto mieste je tiež dôležité spomenúť, že maximálny počet kombinácií možno dosiahnuť pri pokuse vybrať polovicu položiek.
Ako si vybrať vzorec na vyriešenie problému?
Podrobne sme preskúmali základné vzorce kombinatoriky: umiestnenie, permutáciu a kombináciu. Teraz je našou úlohou uľahčiť výber potrebného vzorca na riešenie problému v kombinatorike. Môžete použiť nasledujúcu pomerne jednoduchú schému:
- Opýtajte sa sami seba: Zohľadňuje sa poradie prvkov v texte problému?
- Ak je odpoveď nie, potom použite kombinovaný vzorec (C=n! / (m!(n - m)!)).
- Ak je odpoveď nie, musíte odpovedať ešte na jednu otázku: sú všetky prvky zahrnuté v kombinácii?
- Ak je odpoveď áno, použite permutačný vzorec (P=n!).
- Ak je odpoveď nie, potom použite alokačný vzorec (A=n! / (n - m)!).
Príklad
Zvážili sme prvky kombinatoriky, vzorce a niektoré ďalšie otázky. Teraz prejdime kvzhľadom na skutočný problém. Predstavte si, že máte pred sebou kiwi, pomaranč a banán.
Otázka prvá: Koľkými spôsobmi je možné ich preusporiadať? Na to použijeme permutačný vzorec: P=3!=6 spôsobov.
Otázka druhá: Koľkými spôsobmi možno vybrať jedno ovocie? To je zrejmé, máme len tri možnosti - vyberte si kiwi, pomaranč alebo banán, ale použijeme kombinovaný vzorec: C \u003d 3! / (2!1!)=3.
Otázka tretia: Koľkými spôsobmi možno vybrať dva druhy ovocia? Aké máme možnosti? Kiwi a pomaranč; kiwi a banán; pomaranč a banán. To znamená tri možnosti, ale je ľahké to skontrolovať pomocou kombinovaného vzorca: C \u003d 3! / (1!2!)=3
Otázka štvrtá: Koľkými spôsobmi možno vybrať tri druhy ovocia? Ako vidíte, existuje len jeden spôsob, ako si vybrať tri druhy ovocia: vezmite si kiwi, pomaranč a banán. C=3! / (0!3!)=1.
Piata otázka: na koľko spôsobov si môžete vybrať aspoň jedno ovocie? Táto podmienka znamená, že môžeme vziať jedno, dve alebo všetky tri plody. Preto sčítame C1 + C2 + C3=3 + 3 + 1=7. To znamená, že máme sedem spôsobov, ako zobrať zo stola aspoň jeden kúsok ovocia.
