Dit artikel gaat over een speciaal onderdeel van de wiskunde dat combinatoriek wordt genoemd. Formules, regels, voorbeelden van probleemoplossing - dit alles kunt u hier vinden door het artikel tot het einde te lezen.
Dus, wat is deze sectie? Combinatoriek houdt zich bezig met het tellen van objecten. Maar in dit geval zijn de objecten geen pruimen, peren of appels, maar iets anders. Combinatoriek helpt ons de waarschijnlijkheid van een gebeurtenis te vinden. Wat is bijvoorbeeld de kans dat de tegenstander een troefkaart heeft bij het kaarten? Of zo'n voorbeeld - wat is de kans dat je precies wit krijgt uit een zak met twintig ballen? Voor dit soort taken moeten we op zijn minst de basis van dit deel van de wiskunde kennen.
Combinatorische configuraties
Gezien de kwestie van de basisconcepten en formules van combinatoriek, kunnen we niet anders dan aandacht besteden aan combinatorische configuraties. Ze worden niet alleen gebruikt voor formulering, maar ook voor het oplossen van verschillende combinatorische problemen. Voorbeelden van dergelijke modellen zijn:
- plaatsing;
- permutatie;
- combinatie;
- nummer samenstelling;
- gesplitst nummer.
We zullen later meer in detail over de eerste drie praten, maar we zullen in deze sectie aandacht besteden aan compositie en splitsing. Als ze het hebben over de samenstelling van een bepaald getal (zeg, a), bedoelen ze de weergave van het getal a als een geordende som van enkele positieve getallen. En een splitsing is een ongeordende som.
Secties
Voordat we direct naar de formules van combinatoriek en het beschouwen van problemen gaan, is het de moeite waard aandacht te schenken aan het feit dat combinatoriek, net als andere delen van de wiskunde, zijn eigen subsecties heeft. Deze omvatten:
- enumerative;
- structureel;
- extreem;
- Ramsey-theorie;
- probabilistisch;
- topologisch;
- oneindig.
In het eerste geval hebben we het over enumeratieve combinatoriek, de problemen betreffen het opsommen of tellen van verschillende configuraties die worden gevormd door elementen van verzamelingen. Aan deze verzamelingen worden in de regel enkele beperkingen opgelegd (onderscheidbaarheid, ononderscheidbaarheid, mogelijkheid tot herhaling, enzovoort). En het aantal van deze configuraties wordt berekend met behulp van de regel van optellen of vermenigvuldigen, waar we het later over zullen hebben. Structurele combinatoriek omvat de theorieën van grafieken en matroïden. Een voorbeeld van een extremaal combinatorisch probleem is wat de grootste afmeting is van een graaf die aan de volgende eigenschappen voldoet… In de vierde paragraaf noemden we de Ramsey-theorie, die de aanwezigheid van regelmatige structuren in willekeurige configuraties bestudeert. waarschijnlijkheidcombinatoriek is in staat om de vraag te beantwoorden - wat is de kans dat een bepaalde verzameling een bepaalde eigenschap heeft. Zoals je zou kunnen raden, past topologische combinatoriek methoden toe in de topologie. En tot slot, het zevende punt - oneindige combinatoriek bestudeert de toepassing van combinatorische methoden op oneindige verzamelingen.
Toevoegingsregel
Onder de formules van combinatoriek kan men vrij eenvoudige vinden, waarmee we al heel lang bekend zijn. Een voorbeeld is de somregel. Stel dat we twee acties (C en E) krijgen, als ze elkaar uitsluiten, kan actie C op verschillende manieren worden gedaan (bijvoorbeeld a), en actie E kan in b-manieren worden gedaan, dan kan elk van hen (C of E) kan op a + b manieren worden gedaan.
In theorie is dit vrij moeilijk te begrijpen, we zullen proberen het hele punt over te brengen met een eenvoudig voorbeeld. Laten we het gemiddelde aantal studenten in één klas nemen - laten we zeggen dat het vijfentwintig is. Onder hen zijn vijftien meisjes en tien jongens. Er wordt dagelijks één begeleider toegewezen aan de klas. Hoeveel manieren zijn er om vandaag een klassenbegeleider toe te wijzen? De oplossing voor het probleem is vrij eenvoudig, we zullen onze toevlucht nemen tot de optelregel. De tekst van de taak zegt niet dat alleen jongens of alleen meisjes dienst mogen hebben. Daarom kan het een van de vijftien meisjes zijn of een van de tien jongens. Als we de somregel toepassen, krijgen we een vrij eenvoudig voorbeeld waar een basisschoolleerling gemakkelijk mee uit de voeten kan: 15 + 10. Na berekening krijgen we het antwoord: vijfentwintig. Dat wil zeggen, er zijn slechts vijfentwintig manierenwijs een dienstklasse toe voor vandaag.
Regel van vermenigvuldiging
De vermenigvuldigingsregel behoort ook tot de basisformules van combinatoriek. Laten we beginnen met de theorie. Stel dat we meerdere acties (a) moeten uitvoeren: de eerste actie wordt op 1 manieren uitgevoerd, de tweede - op 2 manieren, de derde - op 3 manieren, enzovoort totdat de laatste a-actie op sa manieren wordt uitgevoerd. Dan kunnen al deze acties (waarvan we een totaal hebben) op N manieren worden uitgevoerd. Hoe de onbekende N te berekenen? De formule helpt ons hierbij: N \u003d c1c2c3…ca.
Nogmaals, in theorie is niets duidelijk, laten we verder gaan met een eenvoudig voorbeeld van het toepassen van de vermenigvuldigingsregel. Laten we dezelfde klas van vijfentwintig mensen nemen, waarin vijftien meisjes en tien jongens studeren. Alleen moeten we deze keer twee begeleiders kiezen. Het kunnen alleen jongens of meisjes zijn, of een jongen met een meisje. We wenden ons tot de elementaire oplossing van het probleem. We kiezen de eerste begeleider, zoals we in de laatste paragraaf hebben besloten, we krijgen vijfentwintig mogelijke opties. De tweede dienstdoende persoon kan een van de overige personen zijn. We hadden vijfentwintig studenten, we kozen er één uit, wat betekent dat elk van de overige vierentwintig mensen de tweede van dienst kan zijn. Ten slotte passen we de vermenigvuldigingsregel toe en vinden dat de twee bedienden op zeshonderd manieren kunnen worden gekozen. We hebben dit getal verkregen door vijfentwintig en vierentwintig te vermenigvuldigen.
Wissel
Nu zullen we nog een combinatorische formule overwegen. In dit gedeelte van het artikel gaan weLaten we het hebben over permutaties. Beschouw het probleem onmiddellijk met een voorbeeld. Laten we biljartballen nemen, we hebben er het n-de aantal. We moeten berekenen: hoeveel opties er zijn om ze op een rij te zetten, dat wil zeggen, om een geordende set te maken.
Laten we beginnen, als we geen ballen hebben, hebben we ook nul plaatsingsopties. En als we één bal hebben, dan is de rangschikking ook hetzelfde (wiskundig kan dit als volgt worden geschreven: Р1=1). Twee ballen kunnen op twee verschillende manieren worden gerangschikt: 1, 2 en 2, 1. Daarom is Р2=2. Drie ballen kunnen op zes manieren worden gerangschikt (Р3=6): 1, 2, 3; 1, 3, 2; 2, 1, 3; 2, 3, 1; 3, 2, 1; 3, 1, 2. En als er niet drie van zulke ballen zijn, maar tien of vijftien? Alle mogelijke opties opsommen is erg lang, dan komt combinatoriek ons te hulp. De permutatieformule zal ons helpen het antwoord op onze vraag te vinden. Pn=nP(n-1). Als we de formule proberen te vereenvoudigen, krijgen we: Pn=n (n - 1) … 21. En dit is het product van de eerste natuurlijke getallen. Zo'n getal wordt een faculteit genoemd en wordt aangeduid als n!
Laten we eens kijken naar het probleem. De leider bouwt elke ochtend zijn detachement in een rij (twintig man). Er zijn drie beste vrienden in het detachement - Kostya, Sasha en Lesha. Hoe groot is de kans dat ze naast elkaar staan? Om het antwoord op de vraag te vinden, moet je de kans op een "goede" uitkomst delen door het totale aantal uitkomsten. Het totale aantal permutaties is 20!=2,5 triljoen. Hoe tel je het aantal "goede" uitkomsten? Stel dat Kostya, Sasha en Lesha één superman zijn. Dan gaan weWe hebben maar achttien onderwerpen. Het aantal permutaties is in dit geval 18=6,5 quadriljoen. Met dit alles kunnen Kostya, Sasha en Lesha willekeurig onderling bewegen in hun ondeelbare triple, en dit zijn er nog 3!=6 opties. In totaal hebben we dus 18 "goede" sterrenbeelden!3! We hoeven alleen maar de gewenste kans te vinden: (18!3!) / 20! Dat is ongeveer 0,016. Als het wordt omgerekend naar een percentage, blijkt het slechts 1,6% te zijn.
Accommodatie
Nu zullen we een andere zeer belangrijke en noodzakelijke combinatorische formule overwegen. Accommodatie is ons volgende nummer, dat we u aanraden in dit gedeelte van het artikel te bespreken. We gaan het nog ingewikkelder maken. Laten we aannemen dat we mogelijke permutaties willen beschouwen, alleen niet van de hele verzameling (n), maar van een kleinere (m). Dat wil zeggen, we beschouwen permutaties van n items met m.
De basisformules van combinatoriek moeten niet alleen worden onthouden, maar begrepen. Zelfs ondanks het feit dat ze ingewikkelder worden, omdat we niet één parameter hebben, maar twee. Stel dat m \u003d 1, dan A \u003d 1, m \u003d 2, dan A \u003d n(n - 1). Als we de formule verder vereenvoudigen en overschakelen naar notatie met behulp van faculteiten, krijgen we een vrij beknopte formule: A \u003d n! / (n - m)!
Combinatie
We hebben bijna alle basisformules van combinatoriek overwogen met voorbeelden. Laten we nu verder gaan met de laatste fase van het overwegen van de basiscursus combinatoriek - de combinatie leren kennen. Nu zullen we m items kiezen uit de n die we hebben, terwijl we ze allemaal op alle mogelijke manieren zullen kiezen. Hoe is dit dan anders dan accommodatie? We zullen nietorde overwegen. Deze ongeordende set zal een combinatie zijn.
Voer onmiddellijk de notatie in: C. We nemen plaatsingen van m-ballen uit n. We letten niet meer op de bestelling en krijgen steeds terugkerende combinaties. Om het aantal combinaties te krijgen, moeten we het aantal plaatsingen delen door m! (m faculteit). Dat wil zeggen, C \u003d A / m! Er zijn dus een paar manieren om uit n ballen te kiezen, ongeveer gelijk aan het aantal om bijna alles te kiezen. Daar is een logische uitdrukking voor: een beetje kiezen is hetzelfde als bijna alles weggooien. Het is ook belangrijk om op dit punt te vermelden dat het maximale aantal combinaties kan worden bereikt wanneer u probeert de helft van de items te selecteren.
Hoe kies je een formule om een probleem op te lossen?
We hebben de basisformules van combinatoriek in detail onderzocht: plaatsing, permutatie en combinatie. Nu is het onze taak om de keuze van de noodzakelijke formule voor het oplossen van het probleem in combinatoriek te vergemakkelijken. U kunt het volgende vrij eenvoudige schema gebruiken:
- Vraag jezelf af: wordt er rekening gehouden met de volgorde van de elementen in de tekst van de opgave?
- Als het antwoord nee is, gebruik dan de combinatieformule (C=n! / (m!(n - m)!)).
- Als het antwoord nee is, moet je nog een vraag beantwoorden: zitten alle elementen in de combinatie?
- Als het antwoord ja is, gebruik dan de permutatieformule (P=n!).
- Als het antwoord nee is, gebruik dan de verdeelsleutel (A=n! / (n - m)!).
Voorbeeld
We hebben de elementen van combinatoriek, formules en enkele andere zaken overwogen. Laten we nu verder gaan metgezien een reëel probleem. Stel je voor dat je een kiwi, een sinaasappel en een banaan voor je hebt.
Vraag één: op hoeveel manieren kunnen ze worden herschikt? Hiervoor gebruiken we de permutatieformule: P=3!=6 manieren.
Vraag twee: op hoeveel manieren kan één vrucht worden gekozen? Dit is duidelijk, we hebben maar drie opties - kies kiwi, sinaasappel of banaan, maar we passen de combinatieformule toe: C \u003d 3! / (2!1!)=3.
Vraag drie: op hoeveel manieren kunnen twee vruchten worden gekozen? Welke opties hebben we? Kiwi en sinaasappel; kiwi en banaan; sinaasappel en banaan. Dat wil zeggen, drie opties, maar dit is eenvoudig te controleren met behulp van de combinatieformule: C \u003d 3! / (1!2!)=3
Vraag vier: op hoeveel manieren kunnen drie vruchten worden gekozen? Zoals je kunt zien, is er maar één manier om drie soorten fruit te kiezen: neem een kiwi, een sinaasappel en een banaan. C=3! / (0!3!)=1.
Vraag vijf: op hoeveel manieren kun je ten minste één vrucht kiezen? Deze voorwaarde houdt in dat we één, twee of alle drie de vruchten kunnen nemen. Daarom voegen we C1 + C2 + C3=3 + 3 + 1=7 toe. Dat wil zeggen, we hebben zeven manieren om ten minste één stuk fruit van de tafel te nemen.
