Denne artikel vil fokusere på en særlig sektion af matematik kaldet kombinatorik. Formler, regler, eksempler på problemløsning - alt dette kan du finde her ved at læse artiklen til det sidste.
Så, hvad er dette afsnit? Combinatorics beskæftiger sig med spørgsmålet om at tælle eventuelle objekter. Men i dette tilfælde er genstandene ikke blommer, pærer eller æbler, men noget andet. Combinatorics hjælper os med at finde sandsynligheden for en begivenhed. For eksempel, når man spiller kort, hvad er sandsynligheden for, at modstanderen har et trumfkort? Eller sådan et eksempel - hvad er sandsynligheden for, at du får præcis hvid af en pose med tyve kugler? Det er til denne slags opgaver, at vi i det mindste skal kende det grundlæggende i denne sektion af matematik.
Kombinatoriske konfigurationer
I betragtning af spørgsmålet om de grundlæggende begreber og formler for kombinatorik, kan vi ikke andet end at være opmærksomme på kombinatoriske konfigurationer. De bruges ikke kun til formulering, men også til at løse forskellige kombinatoriske problemer. Eksempler på sådanne modeller er:
- placement;
- permutation;
- kombination;
- nummersammensætning;
- opdelt nummer.
Vi vil tale om de første tre mere detaljeret senere, men vi vil være opmærksomme på komposition og opdeling i dette afsnit. Når de taler om sammensætningen af et bestemt tal (f.eks. a), mener de repræsentationen af tallet a som en ordnet sum af nogle positive tal. Og en opdeling er en uordnet sum.
Sektioner
Før vi går direkte til kombinatorikkens formler og overvejelser om problemer, er det værd at være opmærksom på, at kombinatorikken, ligesom andre dele af matematikken, har sine egne underafsnit. Disse omfatter:
- enumerative;
- strukturel;
- ekstrem;
- Ramsey-teori;
- sandsynlighed;
- topologisk;
- uendelig.
I det første tilfælde taler vi om enumerativ kombinatorik, problemerne overvejer opregning eller optælling af forskellige konfigurationer, der er dannet af elementer af sæt. Som regel er der pålagt nogle begrænsninger for disse sæt (skelnelighed, ikke-skelnelighed, mulighed for gentagelse og så videre). Og antallet af disse konfigurationer beregnes ved hjælp af reglen om addition eller multiplikation, som vi vil tale om lidt senere. Strukturel kombinatorik omfatter teorierne om grafer og matroider. Et eksempel på et ekstremal kombinatorisk problem er, hvad der er den største dimension af en graf, der opfylder følgende egenskaber… I det fjerde afsnit nævnte vi Ramsey-teorien, som studerer tilstedeværelsen af regulære strukturer i tilfældige konfigurationer. Probabilistiskkombinatorik er i stand til at besvare spørgsmålet - hvad er sandsynligheden for, at et givet sæt har en bestemt egenskab. Som du måske kan gætte, anvender topologisk kombinatorik metoder i topologi. Og endelig, det syvende punkt - infinitær kombinatorik studerer anvendelsen af kombinatoriske metoder til uendelige mængder.
Tilføjelsesregel
Blandt kombinatorikkens formler kan man finde ganske simple, som vi har været fortrolige med længe. Et eksempel er sumreglen. Antag, at vi får to handlinger (C og E), hvis de er gensidigt udelukkende, kan handling C udføres på flere måder (f.eks. a), og handling E kan udføres på b-veje, så enhver af dem (C eller E) kan gøres på a + b måder.
I teorien er dette ret svært at forstå, vi vil forsøge at formidle hele pointen med et simpelt eksempel. Lad os tage det gennemsnitlige antal elever i en klasse – lad os sige, at det er femogtyve. Blandt dem er femten piger og ti drenge. Der tildeles en ledsager til klassen dagligt. Hvor mange måder er der til at tildele en klasseassistent i dag? Løsningen på problemet er ret enkel, vi vil ty til tilføjelsesreglen. Opgaveteksten siger ikke, at kun drenge eller kun piger kan være på vagt. Derfor kan det være enhver af de femten piger eller en af de ti drenge. Ved at anvende sumreglen får vi et ret simpelt eksempel, som en folkeskoleelev sagtens kan klare: 15 + 10. Efter at have regnet ud, får vi svaret: femogtyve. Det vil sige, at der kun er femogtyve mådertildel en vagtklasse for i dag.
Multiplikationsregel
Reglen om multiplikation hører også til kombinatorikkens grundformler. Lad os starte med teori. Antag, at vi skal udføre flere handlinger (a): den første handling udføres på 1 måder, den anden - på 2 måder, den tredje - på 3 måder, og så videre, indtil den sidste a-handling udføres på sa måder. Så kan alle disse handlinger (som vi har i alt) udføres på N måder. Hvordan beregner man det ukendte N? Formlen hjælper os med dette: N \u003d c1c2c3…ca.
Igen, intet er klart i teorien, lad os gå videre til et simpelt eksempel på anvendelse af multiplikationsreglen. Lad os tage den samme klasse på femogtyve personer, hvor femten piger og ti drenge studerer. Kun denne gang skal vi vælge to ledsagere. De kan enten kun være drenge eller piger, eller en dreng med en pige. Vi vender os til den elementære løsning af problemet. Vi vælger den første ledsager, som vi besluttede i sidste afsnit, vi får femogtyve mulige muligheder. Den anden person på vagt kan være enhver af de resterende personer. Vi havde femogtyve elever, vi valgte én, hvilket betyder, at enhver af de resterende fireogtyve personer kan være den anden på vagt. Til sidst anvender vi multiplikationsreglen og finder ud af, at de to ledsagere kan vælges på seks hundrede måder. Vi fik dette tal ved at gange femogtyve og fireogtyve.
Swap
Nu vil vi overveje endnu en kombinatorisk formel. I dette afsnit af artiklen vil viLad os tale om permutationer. Overvej problemet med det samme med et eksempel. Lad os tage billardkugler, vi har n-te antal af dem. Vi skal beregne: hvor mange muligheder der er for at arrangere dem i en række, det vil sige at lave et bestilt sæt.
Lad os starte, hvis vi ikke har bolde, så har vi også nul placeringsmuligheder. Og hvis vi har en bold, så er arrangementet også det samme (matematisk kan dette skrives som følger: Р1=1). To bolde kan arrangeres på to forskellige måder: 1, 2 og 2, 1. Derfor er Р2=2. Tre bolde kan arrangeres på seks måder (Р3=6): 1, 2, 3; 1, 3, 2; 2, 1, 3; 2, 3, 1; 3, 2, 1; 3, 1, 2. Og hvis der ikke er tre sådanne bolde, men ti eller femten? At liste alle de mulige muligheder er meget lang, så kommer kombinatorik til vores hjælp. Permutationsformlen hjælper os med at finde svaret på vores spørgsmål. Pn=nP(n-1). Hvis vi forsøger at forenkle formlen, får vi: Pn=n (n - 1) … 21. Og dette er produktet af de første naturlige tal. Et sådant tal kaldes et fakultativt tal og betegnes som n!
Lad os overveje problemet. Lederen bygger hver morgen sin løsrivelse i en række (tyve personer). Der er tre bedste venner i løsrivelsen - Kostya, Sasha og Lesha. Hvad er sandsynligheden for, at de vil være ved siden af hinanden? For at finde svaret på spørgsmålet skal du dividere sandsynligheden for et "godt" resultat med det samlede antal udfald. Det samlede antal permutationer er 20!=2,5 kvintillioner. Hvordan tæller man antallet af "gode" resultater? Antag, at Kostya, Sasha og Lesha er en supermand. Så viVi har kun atten fag. Antallet af permutationer i dette tilfælde er 18=6,5 kvadrillioner. Med alt dette kan Kostya, Sasha og Lesha vilkårligt bevæge sig indbyrdes i deres udelelige triple, og dette er 3 mere!=6 muligheder. Så vi har 18 "gode" konstellationer i alt! 3! Vi skal bare finde den ønskede sandsynlighed: (18!3!) / 20! Hvilket er cirka 0,016. Hvis det omregnes til en procentdel, viser det sig kun at være 1,6%.
Overnatning
Nu vil vi overveje en anden meget vigtig og nødvendig kombinatorisk formel. Indkvartering er vores næste nummer, som vi foreslår, at du overvejer i dette afsnit af artiklen. Vi bliver mere komplicerede. Lad os antage, at vi vil overveje mulige permutationer, kun ikke fra hele mængden (n), men fra en mindre (m). Det vil sige, vi betragter permutationer af n elementer med m.
De grundlæggende formler for kombinatorik skal ikke bare huskes, men forstås. Selv på trods af at de bliver mere komplicerede, da vi ikke har én parameter, men to. Antag, at m \u003d 1, så A \u003d 1, m \u003d 2, så A \u003d n(n - 1). Hvis vi yderligere forenkler formlen og skifter til notation ved hjælp af faktorialer, får vi en ganske kortfattet formel: A \u003d n! / (n - m)!
kombination
Vi har overvejet næsten alle de grundlæggende formler for kombinatorik med eksempler. Lad os nu gå videre til den sidste fase med at overveje det grundlæggende kursus i kombinatorik - at lære kombinationen at kende. Nu vil vi vælge m varer fra det n vi har, mens vi vælger dem alle på alle mulige måder. Hvordan adskiller dette sig så fra indkvartering? Vi vil ikkeoverveje orden. Dette uordnede sæt vil være en kombination.
Introducer straks notationen: C. Vi tager placeringer af m kugler ud af n. Vi holder op med at være opmærksomme på orden og får gentagne kombinationer. For at få antallet af kombinationer skal vi dividere antallet af placeringer med m! (m faktoriel). Det vil sige C \u003d A / m! Der er således et par måder at vælge mellem n bolde, omtrent lig med hvor mange at vælge næsten alt. Det er der et logisk udtryk for: At vælge lidt er det samme som at smide næsten alt væk. Det er også vigtigt at nævne på dette tidspunkt, at det maksimale antal kombinationer kan opnås, når man prøver at vælge halvdelen af emnerne.
Hvordan vælger man en formel til at løse et problem?
Vi har undersøgt de grundlæggende formler for kombinatorik i detaljer: placering, permutation og kombination. Nu er vores opgave at lette valget af den nødvendige formel til løsning af problemet i kombinatorik. Du kan bruge følgende ret simple skema:
- Spørg dig selv: er rækkefølgen af elementerne taget i betragtning i problemteksten?
- Hvis svaret er nej, så brug kombinationsformlen (C=n! / (m!(n - m)!)).
- Hvis svaret er nej, skal du besvare et spørgsmål mere: er alle elementerne inkluderet i kombinationen?
- Hvis svaret er ja, så brug permutationsformlen (P=n!).
- Hvis svaret er nej, så brug tildelingsformlen (A=n! / (n - m)!).
Eksempel
Vi har overvejet elementerne i kombinatorik, formler og nogle andre problemer. Lad os nu gå videre tilovervejer et reelt problem. Forestil dig, at du har en kiwi, en appelsin og en banan foran dig.
Spørgsmål et: På hvor mange måder kan de omarrangeres? For at gøre dette bruger vi permutationsformlen: P=3!=6 måder.
Spørgsmål to: På hvor mange måder kan én frugt vælges? Dette er indlysende, vi har kun tre muligheder - vælg kiwi, appelsin eller banan, men vi anvender kombinationsformlen: C \u003d 3! / (2!1!)=3.
Spørgsmål tre: På hvor mange måder kan to frugter vælges? Hvilke muligheder har vi? Kiwi og appelsin; kiwi og banan; appelsin og banan. Det vil sige tre muligheder, men det er nemt at kontrollere ved hjælp af kombinationsformlen: C \u003d 3! / (1!2!)=3
Spørgsmål fire: På hvor mange måder kan tre frugter vælges? Som du kan se, er der kun én måde at vælge tre frugter på: Tag en kiwi, en appelsin og en banan. C=3! / (0!3!)=1.
Spørgsmål fem: hvor mange måder kan du vælge mindst én frugt på? Denne betingelse indebærer, at vi kan tage en, to eller alle tre frugter. Derfor tilføjer vi C1 + C2 + C3=3 + 3 + 1=7. Det vil sige, vi har syv måder at tage mindst ét stykke frugt fra bordet på.
