Hierdie artikel sal fokus op 'n spesiale afdeling van wiskunde genaamd kombinatorika. Formules, reëls, voorbeelde van probleemoplossing - dit alles kan jy hier vind deur die artikel tot aan die einde te lees.
So, wat is hierdie afdeling? Kombinatorika handel oor die kwessie van die tel van enige voorwerpe. Maar in hierdie geval is die voorwerpe nie pruime, pere of appels nie, maar iets anders. Kombinatorika help ons om die waarskynlikheid van 'n gebeurtenis te vind. Byvoorbeeld, wanneer kaarte gespeel word, wat is die waarskynlikheid dat die opponent 'n troefkaart het? Of so 'n voorbeeld - wat is die waarskynlikheid dat jy presies wit sal kry uit 'n sak met twintig balle? Dit is vir hierdie soort take wat ons ten minste die basiese beginsels van hierdie afdeling van wiskunde moet ken.
Kombinatoriese konfigurasies
In die lig van die kwessie van die basiese konsepte en formules van kombinatorika, kan ons nie anders as om aandag te gee aan kombinatoriese konfigurasies nie. Hulle word nie net vir formulering gebruik nie, maar ook vir die oplossing van verskeie kombinatoriese probleme. Voorbeelde van sulke modelle is:
- plasing;
- permutasie;
- kombinasie;
- nommersamestelling;
- gedeelde nommer.
Ons sal later in meer besonderhede oor die eerste drie praat, maar ons sal in hierdie afdeling aandag gee aan samestelling en verdeling. Wanneer hulle praat oor die samestelling van 'n sekere getal (sê, a), bedoel hulle die voorstelling van die getal a as 'n geordende som van sommige positiewe getalle. En 'n verdeling is 'n ongeordende som.
Seksies
Voordat ons direk na die formules van kombinatorika en die oorweging van probleme gaan, is dit die moeite werd om aandag te skenk aan die feit dat kombinatorika, soos ander afdelings van wiskunde, sy eie onderafdelings het. Dit sluit in:
- enumeratief;
- struktureel;
- ekstreem;
- Ramsey-teorie;
- probabilistic;
- topologies;
- oneindig.
In die eerste geval praat ons van enumeratiewe kombinatorika, die probleme oorweeg opsomming of tel van verskillende konfigurasies wat deur elemente van versamelings gevorm word. As 'n reël word sekere beperkings op hierdie stelle opgelê (onderskeibaarheid, ononderskeibaarheid, die moontlikheid van herhaling, ensovoorts). En die aantal van hierdie konfigurasies word bereken deur die reël van optelling of vermenigvuldiging, waaroor ons 'n bietjie later sal praat. Strukturele kombinatorika sluit die teorieë van grafieke en matroïede in. 'n Voorbeeld van 'n ekstremale kombinatoriese probleem is wat die grootste dimensie van 'n grafiek is wat aan die volgende eienskappe voldoen… In die vierde paragraaf het ons die Ramsey-teorie genoem, wat die teenwoordigheid van gereelde strukture in ewekansige konfigurasies bestudeer. Waarskynlikkombinatorika is in staat om die vraag te beantwoord - wat is die waarskynlikheid dat 'n gegewe versameling 'n sekere eienskap het. Soos jy dalk kan raai, pas topologiese kombinatorika metodes in topologie toe. En laastens, die sewende punt - infinitêre kombinatorika bestudeer die toepassing van kombinatoriese metodes op oneindige versamelings.
byvoegreël
Onder die formules van kombinatorika kan 'n mens redelik eenvoudige formules vind, waarmee ons al lank vertroud is. 'n Voorbeeld is die somreël. Gestel ons kry twee aksies (C en E), as hulle mekaar uitsluit, kan aksie C op verskeie maniere gedoen word (byvoorbeeld, a), en aksie E kan in b-maniere gedoen word, dan kan enige van hulle (C of E) kan op a + b maniere gedoen word.
In teorie is dit nogal moeilik om te verstaan, ons sal probeer om die hele punt met 'n eenvoudige voorbeeld oor te dra. Kom ons neem die gemiddelde aantal studente in een klas – kom ons sê dit is vyf-en-twintig. Onder hulle is vyftien meisies en tien seuns. Een bediende word daagliks aan die klas toegewys. Hoeveel maniere is daar om vandag 'n klasbediende toe te wys? Die oplossing vir die probleem is redelik eenvoudig, ons sal na die optelreël toevlug. Die teks van die taak sê nie dat slegs seuns of slegs meisies aan diens kan wees nie. Daarom kan dit enige van die vyftien meisies of enige van die tien seuns wees. Deur die somreël toe te pas, kry ons 'n redelik eenvoudige voorbeeld waarmee 'n laerskoolleerling maklik kan klaarkom: 15 + 10. Nadat ons dit bereken het, kry ons die antwoord: vyf-en-twintig. Dit wil sê, daar is net vyf-en-twintig manierewys 'n diensklas vir vandag toe.
Vermenigvuldigingsreël
Die reël van vermenigvuldiging behoort ook tot die basiese formules van kombinatorika. Kom ons begin met teorie. Gestel ons moet verskeie aksies (a) uitvoer: die eerste aksie word op 1 maniere uitgevoer, die tweede - op 2 maniere, die derde - op 3 maniere, en so aan totdat die laaste a-aksie op sa maniere uitgevoer word. Dan kan al hierdie aksies (waarvan ons 'n totaal het) op N maniere uitgevoer word. Hoe om die onbekende N te bereken? Die formule sal ons hiermee help: N \u003d c1c2c3…ca.
Weereens, niks is duidelik in teorie nie, kom ons gaan aan na 'n eenvoudige voorbeeld van die toepassing van die vermenigvuldigingsreël. Kom ons neem dieselfde klas van vyf-en-twintig mense, waarin vyftien meisies en tien seuns studeer. Net hierdie keer moet ons twee bediendes kies. Hulle kan óf net seuns óf meisies wees, óf 'n seun met 'n meisie. Ons gaan na die elementêre oplossing van die probleem. Ons kies die eerste bywoner, soos ons in die laaste paragraaf besluit het, kry ons vyf-en-twintig moontlike opsies. Die tweede persoon aan diens kan enige van die oorblywende mense wees. Ons het vyf-en-twintig studente gehad, ons het een gekies, wat beteken dat enige van die oorblywende vier-en-twintig mense die tweede aan diens kan wees. Ten slotte pas ons die vermenigvuldigingsreël toe en vind dat die twee bywoners op seshonderd maniere gekies kan word. Ons het hierdie getal gekry deur vyf-en-twintig en vier-en-twintig te vermenigvuldig.
Ruil
Nou sal ons nog een kombinatoriese formule oorweeg. In hierdie afdeling van die artikel, onsKom ons praat oor permutasies. Oorweeg die probleem dadelik met 'n voorbeeld. Kom ons neem biljartballe, ons het n-de getal daarvan. Ons moet bereken: hoeveel opsies daar is om hulle in 'n ry te rangskik, dit wil sê om 'n geordende stel te maak.
Kom ons begin, as ons nie balle het nie, dan het ons ook geen plasingsopsies nie. En as ons een bal het, dan is die rangskikking ook dieselfde (wiskundig kan dit soos volg geskryf word: Р1=1). Twee balle kan op twee verskillende maniere gerangskik word: 1, 2 en 2, 1. Daarom is Р2=2. Drie balle kan op ses maniere gerangskik word (Р3=6): 1, 2, 3; 1, 3, 2; 2, 1, 3; 2, 3, 1; 3, 2, 1; 3, 1, 2. En as daar nie drie sulke balle is nie, maar tien of vyftien? Om al die moontlike opsies te lys is baie lank, dan kom kombinatorika ons te hulp. Die permutasieformule sal ons help om die antwoord op ons vraag te vind. Pn=nP(n-1). As ons probeer om die formule te vereenvoudig, kry ons: Pn=n (n - 1) … 21. En dit is die produk van die eerste natuurlike getalle. So 'n getal word 'n faktoriaal genoem, en word aangedui as n!
Kom ons kyk na die probleem. Die leier bou elke oggend sy losbandigheid in 'n ry (twintig mense). Daar is drie beste vriende in die afdeling - Kostya, Sasha en Lesha. Wat is die waarskynlikheid dat hulle langs mekaar sal wees? Om die antwoord op die vraag te vind, moet jy die waarskynlikheid van 'n "goeie" uitkoms deur die totale aantal uitkomste deel. Die totale aantal permutasies is 20!=2,5 kwintiljoen. Hoe om die aantal "goeie" uitkomste te tel? Veronderstel dat Kostya, Sasha en Lesha een superman is. Toe onsOns het net agtien vakke. Die aantal permutasies in hierdie geval is 18=6,5 kwadriljoen. Met dit alles kan Kostya, Sasha en Lesha arbitrêr onder mekaar beweeg in hul ondeelbare trippel, en dit is nog 3!=6 opsies. Ons het dus altesaam 18 "goeie" konstellasies!3! Ons moet net die gewenste waarskynlikheid vind: (18!3!) / 20! Wat ongeveer 0,016 is. As dit na 'n persentasie omgeskakel word, blyk dit net 1,6% te wees.
Akkommodasie
Nou sal ons nog 'n baie belangrike en noodsaaklike kombinatoriese formule oorweeg. Akkommodasie is ons volgende uitgawe, wat ons voorstel dat jy in hierdie afdeling van die artikel oorweeg. Ons gaan meer ingewikkeld raak. Kom ons neem aan dat ons moontlike permutasies wil oorweeg, net nie uit die hele versameling (n), maar van 'n kleiner een (m). Dit wil sê, ons beskou permutasies van n items deur m.
Die basiese formules van kombinatorika moet nie net gememoriseer word nie, maar verstaan word. Selfs ten spyte van die feit dat hulle meer ingewikkeld raak, aangesien ons nie een parameter het nie, maar twee. Gestel dat m \u003d 1, dan A \u003d 1, m \u003d 2, dan A \u003d n(n - 1). As ons die formule verder vereenvoudig en oorskakel na notasie met behulp van faktoriale, kry ons 'n redelik bondige formule: A \u003d n! / (n - m)!
kombinasie
Ons het byna al die basiese formules van kombinatorika met voorbeelde oorweeg. Kom ons gaan nou oor na die finale stadium van die oorweging van die basiese kursus van kombinatorika - om die kombinasie te leer ken. Nou sal ons m items kies uit die n wat ons het, terwyl ons almal op alle moontlike maniere sal kies. Hoe verskil dit dan van verblyf? Ons sal nieorde oorweeg. Hierdie ongeordende stel sal 'n kombinasie wees.
Stel die notasie dadelik in: C. Ons neem plasings van m balle uit n. Ons hou op om aandag te gee aan orde en kry herhalende kombinasies. Om die aantal kombinasies te kry, moet ons die aantal plasings deur m deel! (m faktoriaal). Dit wil sê, C \u003d A / m! Daar is dus 'n paar maniere om uit n balle te kies, ongeveer gelyk aan hoeveel om byna alles te kies. Daar is 'n logiese uitdrukking hiervoor: om 'n bietjie te kies is dieselfde as om byna alles weg te gooi. Dit is ook belangrik om op hierdie punt te noem dat die maksimum aantal kombinasies bereik kan word wanneer jy probeer om die helfte van die items te kies.
Hoe om 'n formule te kies om 'n probleem op te los?
Ons het die basiese formules van kombinatorika in detail ondersoek: plasing, permutasie en kombinasie. Nou is ons taak om die keuse van die nodige formule vir die oplossing van die probleem in kombinatorika te fasiliteer. Jy kan die volgende redelik eenvoudige skema gebruik:
- Vra jouself: word die volgorde van die elemente in ag geneem in die teks van die probleem?
- As die antwoord nee is, gebruik dan die kombinasieformule (C=n! / (m!(n - m)!)).
- As die antwoord nee is, moet jy nog een vraag beantwoord: is al die elemente by die kombinasie ingesluit?
- As die antwoord ja is, gebruik dan die permutasieformule (P=n!).
- As die antwoord nee is, gebruik dan die toekenningsformule (A=n! / (n - m)!).
Voorbeeld
Ons het die elemente van kombinatorika, formules en 'n paar ander kwessies oorweeg. Kom ons gaan nou verder na'n werklike probleem oorweeg. Stel jou voor dat jy 'n kiwi, 'n lemoen en 'n piesang voor jou het.
Vraag een: op hoeveel maniere kan hulle herrangskik word? Om dit te doen, gebruik ons die permutasieformule: P=3!=6 maniere.
Vraag twee: op hoeveel maniere kan een vrug gekies word? Dit is voor die hand liggend, ons het net drie opsies - kies kiwi, lemoen of piesang, maar ons pas die kombinasieformule toe: C \u003d 3! / (2!1!)=3.
Vraag drie: op hoeveel maniere kan twee vrugte gekies word? Watter opsies het ons? Kiwi en lemoen; kiwi en piesang; lemoen en piesang. Dit is drie opsies, maar dit is maklik om te kontroleer met behulp van die kombinasieformule: C \u003d 3! / (1!2!)=3
Vraag vier: op hoeveel maniere kan drie vrugte gekies word? Soos jy kan sien, is daar net een manier om drie vrugte te kies: neem 'n kiwi, 'n lemoen en 'n piesang. C=3! / (0!3!)=1.
Vraag vyf: hoeveel maniere kan jy ten minste een vrug kies? Hierdie toestand impliseer dat ons een, twee of al drie vrugte kan neem. Daarom voeg ons C1 + C2 + C3=3 + 3 + 1=7 by. Dit wil sê, ons het sewe maniere om ten minste een stukkie vrugte van die tafel af te neem.
