Denne artikkelen vil fokusere på en spesiell del av matematikken k alt kombinatorikk. Formler, regler, eksempler på problemløsning – alt dette finner du her ved å lese artikkelen helt til slutt.
Så, hva er denne delen? Kombinatorikk tar for seg spørsmålet om å telle objekter. Men i dette tilfellet er ikke gjenstandene plommer, pærer eller epler, men noe annet. Kombinatorikk hjelper oss å finne sannsynligheten for en hendelse. For eksempel, når du spiller kort, hva er sannsynligheten for at motstanderen har et trumfkort? Eller et slikt eksempel - hva er sannsynligheten for at du får akkurat hvit fra en pose med tjue baller? Det er for denne typen oppgaver vi i det minste trenger å kunne det grunnleggende i denne delen av matematikk.
Kombinatoriske konfigurasjoner
Med tanke på spørsmålet om de grunnleggende konseptene og formlene for kombinatorikk, kan vi ikke annet enn å ta hensyn til kombinatoriske konfigurasjoner. De brukes ikke bare til formulering, men også for å løse ulike kombinatoriske problemer. Eksempler på slike modeller er:
- plassering;
- permutation;
- kombinasjon;
- nummersammensetning;
- delt nummer.
Vi vil snakke om de tre første mer detaljert senere, men vi vil ta hensyn til komposisjon og splitting i denne delen. Når de snakker om sammensetningen av et bestemt tall (si, a), mener de representasjonen av tallet a som en ordnet sum av noen positive tall. Og en splitt er en uordnet sum.
Sections
Før vi går direkte til kombinatorikkens formler og vurderingen av problemer, er det verdt å være oppmerksom på at kombinatorikken, i likhet med andre deler av matematikken, har sine egne underavsnitt. Disse inkluderer:
- enumerative;
- strukturell;
- ekstrem;
- Ramsey-teori;
- probabilistic;
- topologisk;
- uendelig.
I det første tilfellet snakker vi om enumerativ kombinatorikk, problemene vurderer oppregning eller telling av forskjellige konfigurasjoner som er dannet av elementer av sett. Som regel er det pålagt noen begrensninger for disse settene (utmerkbarhet, umulig å skille, gjentakelsesmuligheten og så videre). Og antallet av disse konfigurasjonene beregnes ved å bruke regelen for addisjon eller multiplikasjon, som vi vil snakke om litt senere. Strukturell kombinatorikk inkluderer teoriene om grafer og matroider. Et eksempel på et ekstremt kombinatorisk problem er hva som er den største dimensjonen til en graf som tilfredsstiller følgende egenskaper… I fjerde avsnitt nevnte vi Ramsey-teorien, som studerer tilstedeværelsen av regulære strukturer i tilfeldige konfigurasjoner. Probabilistiskkombinatorikk er i stand til å svare på spørsmålet - hva er sannsynligheten for at et gitt sett har en viss egenskap. Som du kanskje gjetter, bruker topologisk kombinatorikk metoder i topologi. Og til slutt, det syvende punktet - infinitær kombinatorikk studerer anvendelsen av kombinatoriske metoder på uendelige sett.
Tilleggsregel
Blant kombinatorikkens formler kan man finne ganske enkle, som vi har vært kjent med lenge. Et eksempel er sumregelen. Anta at vi får to handlinger (C og E), hvis de utelukker hverandre, kan handling C utføres på flere måter (for eksempel a), og handling E kan utføres på b-veier, så kan hvilken som helst av dem (C). eller E) kan gjøres på a + b måter.
I teorien er dette ganske vanskelig å forstå, vi skal prøve å formidle hele poenget med et enkelt eksempel. La oss ta gjennomsnittlig antall elever i en klasse – la oss si at det er tjuefem. Blant dem er femten jenter og ti gutter. En ledsager tildeles klassen daglig. Hvor mange måter er det å tildele en klasseassistent i dag? Løsningen på problemet er ganske enkel, vi vil ty til tilleggsregelen. Teksten i oppgaven sier ikke at bare gutter eller bare jenter kan være på vakt. Derfor kan det være hvilken som helst av de femten jentene eller hvilken som helst av de ti guttene. Ved å bruke sumregelen får vi et ganske enkelt eksempel som en barneskoleelev lett kan takle: 15 + 10. Etter å ha regnet ut får vi svaret: tjuefem. Det vil si at det bare er tjuefem måtertildel en tjenestetime for i dag.
Multiplikasjonsregel
Regelen for multiplikasjon hører også til kombinatorikkens grunnleggende formler. La oss starte med teori. Anta at vi må utføre flere handlinger (a): den første handlingen utføres på 1 måter, den andre - på 2 måter, den tredje - på 3 måter, og så videre til den siste a-handlingen utføres på sa måter. Da kan alle disse handlingene (som vi har tot alt) utføres på N måter. Hvordan beregne den ukjente N? Formelen vil hjelpe oss med dette: N \u003d c1c2c3…ca.
Igjen, ingenting er klart i teorien, la oss gå videre til et enkelt eksempel på bruk av multiplikasjonsregelen. La oss ta den samme klassen på tjuefem personer, der femten jenter og ti gutter studerer. Bare denne gangen må vi velge to ledsagere. De kan enten være bare gutter eller jenter, eller en gutt med en jente. Vi vender oss til den elementære løsningen av problemet. Vi velger den første ledsageren, som vi bestemte i siste avsnitt, får vi tjuefem mulige alternativer. Den andre personen på vakt kan være hvilken som helst av de gjenværende personene. Vi hadde tjuefem studenter, vi valgte én, noe som betyr at hvilken som helst av de resterende tjuefire personene kan være den andre på vakt. Til slutt bruker vi multiplikasjonsregelen og finner ut at de to ledsagerne kan velges på seks hundre måter. Vi fikk dette tallet ved å multiplisere tjuefem og tjuefire.
Swap
Nå skal vi vurdere enda en kombinatorisk formel. I denne delen av artikkelen, viLa oss snakke om permutasjoner. Vurder problemet umiddelbart med et eksempel. La oss ta biljardballer, vi har n-te antall av dem. Vi må beregne: hvor mange alternativer det er for å ordne dem på rad, det vil si å lage et bestilt sett.
La oss begynne, hvis vi ikke har baller, så har vi også null plasseringsmuligheter. Og hvis vi har en ball, er arrangementet også det samme (matematisk kan dette skrives som følger: Р1=1). To baller kan ordnes på to forskjellige måter: 1, 2 og 2, 1. Derfor er Р2=2. Tre baller kan ordnes på seks måter (Р3=6): 1, 2, 3; 1, 3, 2; 2, 1, 3; 2, 3, 1; 3, 2, 1; 3, 1, 2. Og om det ikke er tre slike baller, men ti eller femten? Å liste opp alle mulige alternativer er veldig lang, så kommer kombinatorikk til hjelp. Permutasjonsformelen vil hjelpe oss å finne svaret på spørsmålet vårt. Pn=nP(n-1). Hvis vi prøver å forenkle formelen, får vi: Pn=n (n - 1) … 21. Og dette er produktet av de første naturlige tallene. Et slikt tall kalles en faktoriell, og er betegnet som n!
La oss vurdere problemet. Lederen bygger hver morgen sin avdeling i en linje (tjue personer). Det er tre bestevenner i avdelingen - Kostya, Sasha og Lesha. Hva er sannsynligheten for at de vil være ved siden av hverandre? For å finne svaret på spørsmålet må du dele sannsynligheten for et "godt" utfall med det totale antallet utfall. Tot alt antall permutasjoner er 20!=2,5 kvintillioner. Hvordan telle antall "gode" utfall? Anta at Kostya, Sasha og Lesha er en supermann. Da viVi har bare atten fag. Antall permutasjoner i dette tilfellet er 18=6,5 kvadrillioner. Med alt dette kan Kostya, Sasha og Lesha vilkårlig flytte seg imellom i deres udelelige trippel, og dette er 3 til!=6 alternativer. Så vi har 18 "gode" konstellasjoner tot alt!3! Vi må bare finne ønsket sannsynlighet: (18!3!) / 20! Som er omtrent 0,016. Hvis det konverteres til en prosentandel, viser det seg å være bare 1,6%.
Overnatting
Nå skal vi vurdere en annen svært viktig og nødvendig kombinatorisk formel. Overnatting er vår neste utgave, som vi foreslår at du vurderer i denne delen av artikkelen. Vi kommer til å bli mer kompliserte. La oss anta at vi ønsker å vurdere mulige permutasjoner, bare ikke fra hele settet (n), men fra en mindre (m). Det vil si at vi vurderer permutasjoner av n elementer med m.
De grunnleggende formlene for kombinatorikk bør ikke bare huskes, men forstås. Selv til tross for at de blir mer kompliserte, siden vi ikke har én parameter, men to. Anta at m \u003d 1, deretter A \u003d 1, m \u003d 2, deretter A \u003d n(n - 1). Hvis vi forenkler formelen ytterligere og bytter til notasjon ved hjelp av faktorialer, får vi en ganske kortfattet formel: A \u003d n! / (n - m)!
kombinasjon
Vi har vurdert nesten alle de grunnleggende formlene for kombinatorikk med eksempler. La oss nå gå videre til den siste fasen av å vurdere grunnkurset i kombinatorikk - bli kjent med kombinasjonen. Nå skal vi velge m varer fra den n vi har, mens vi skal velge alle på alle mulige måter. Hvordan er dette forskjellig fra overnatting? Vi vil ikkevurdere rekkefølge. Dette uordnede settet vil være en kombinasjon.
Introduser umiddelbart notasjonen: C. Vi tar plasseringer av m kuler fra n. Vi slutter å ta hensyn til orden og får gjentatte kombinasjoner. For å få antall kombinasjoner må vi dele antall plasseringer på m! (m faktoriell). Det vil si C \u003d A / m! Dermed er det noen få måter å velge mellom n baller, omtrent lik hvor mange å velge nesten alt. Det er et logisk uttrykk for dette: å velge litt er det samme som å kaste nesten alt. Det er også viktig å nevne på dette tidspunktet at det maksimale antallet kombinasjoner kan oppnås når du prøver å velge halvparten av elementene.
Hvordan velge en formel for å løse et problem?
Vi har undersøkt i detalj de grunnleggende formlene for kombinatorikk: plassering, permutasjon og kombinasjon. Nå er vår oppgave å lette valget av den nødvendige formelen for å løse problemet i kombinatorikk. Du kan bruke følgende ganske enkle opplegg:
- Spør deg selv: er det tatt hensyn til rekkefølgen på elementene i oppgaveteksten?
- Hvis svaret er nei, bruk kombinasjonsformelen (C=n! / (m!(n - m)!)).
- Hvis svaret er nei, må du svare på ett spørsmål til: er alle elementene inkludert i kombinasjonen?
- Hvis svaret er ja, bruk permutasjonsformelen (P=n!).
- Hvis svaret er nei, bruk allokeringsformelen (A=n! / (n - m)!).
Eksempel
Vi har vurdert elementene i kombinatorikk, formler og noen andre problemer. La oss nå gå videre tilvurderer et reelt problem. Tenk deg at du har en kiwi, en appelsin og en banan foran deg.
Spørsmål én: på hvor mange måter kan de omorganiseres? For å gjøre dette bruker vi permutasjonsformelen: P=3!=6 måter.
Spørsmål to: på hvor mange måter kan én frukt velges? Dette er åpenbart, vi har bare tre alternativer - velg kiwi, appelsin eller banan, men vi bruker kombinasjonsformelen: C \u003d 3! / (2!1!)=3.
Spørsmål tre: på hvor mange måter kan to frukter velges? Hvilke alternativer har vi? Kiwi og appelsin; kiwi og banan; appelsin og banan. Det vil si tre alternativer, men dette er enkelt å sjekke ved å bruke kombinasjonsformelen: C \u003d 3! / (1!2!)=3
Spørsmål fire: På hvor mange måter kan tre frukter velges? Som du kan se, er det bare én måte å velge tre frukter på: ta en kiwi, en appelsin og en banan. C=3! / (0!3!)=1.
Spørsmål fem: hvor mange måter kan du velge minst én frukt på? Denne tilstanden innebærer at vi kan ta en, to eller alle tre fruktene. Derfor legger vi til C1 + C2 + C3=3 + 3 + 1=7. Det vil si at vi har syv måter å ta minst ett stykke frukt fra bordet på.
