Presentasjon om temaet kombinatorikk. Presentasjon om emnet: Elements of Combinatorics!!! Anvendelse av grafteori

1 lysbilde

Vi trenger ikke å bruke et blad, vi søker ikke høylytt ære. Han vinner som er kjent med kunsten å tenke, subtil. Den engelske poeten Wordsworth

2 lysbilde

Innledning Formålet med arbeidet Mål med arbeidet Hva er «kombinatorikk»? Opprinnelseshistorie Regler for løsning av kombinatoriske problemer Sumregel Produktregel Kombinasjoner Med repetisjoner Uten repetisjoner Tesaurus Liste over brukt litteratur og nettressurser Konklusjon Forfatterens side

3 lysbilde

Lag en referanseveiledning for elever på 10.-11. trinn, som studerer på grunnleggende nivå, i utdanningsinstitusjoner. Forbered den første delen av et stort prosjekt "Teorien om sannsynlighet som det vanligste fenomenet i våre liv."

4 lysbilde

1.1 Velg litteratur og nettressurser om emnet "Kombinatorikk". 1.2 Utforske alle mulige metoder for å løse kombinatoriske problemer basert på det virkelige liv. 1.3 Spor historien til identifiseringen av et uavhengig felt av matematikk - kombinatorikk. 2.1 Begrunn studiet av et kombinatorikkkurs i videregående skole som en reell nødvendighet når du implementerer kurset på prinsippet om kontinuitet i utdanningen "Skole - Universitet". 2.2 Skissere mulige alternativer for å introdusere et kombinatorikkkurs i skolens undervisningsrom. 2.3 Velg materiale for å lage en oppslagsbok.

5 lysbilde

En person må ofte håndtere problemer der han trenger å telle antall alle mulige måter å plassere noen gjenstander på eller antall alle mulige måter å utføre en handling på. De forskjellige banene eller alternativene som en person må velge, utgjør en lang rekke kombinasjoner. Slike problemer må tas i betraktning når man bestemmer den mest fordelaktige kommunikasjonen i en by, når man organiserer et automatisk kontrollsystem, og derfor i sannsynlighetsteori og i matematisk statistikk med alle deres mange anvendelser. Og en hel gren av matematikken, kalt kombinatorikk, er opptatt med å søke etter svar på spørsmålene: hvor mange kombinasjoner er det i et gitt tilfelle?

6 lysbilde

Kombinatorikk er en gren av matematikk der problemene med å velge elementer fra et innledende sett og ordne dem i en bestemt kombinasjon i henhold til gitte regler studeres og løses.

7 lysbilde

Kombinatorikk som vitenskap begynte å utvikle seg på 1200-tallet. parallelt med fremveksten av sannsynlighetsteori. Den første vitenskapelige forskningen på dette emnet tilhørte de italienske forskerne G. Cardano, N. Chartalier (1499-1557), G. Galileo (1564-1642) og de franske forskerne B. Piscamo (1623-1662) og P. Fermat. Den tyske vitenskapsmannen G. Leibniz var den første som betraktet kombinatorikk som en uavhengig gren av matematikk i sitt arbeid "On the Art of Combinatorics", utgitt i 1666. Han laget også begrepet "Combinatorics" for første gang.

8 lysbilde

Lysbilde 9

Oppgave: Det er 3 svarte og 5 røde blyanter på bordet. På hvor mange måter kan du velge en blyant i hvilken som helst farge? Løsning: Du kan velge en blyant i hvilken som helst farge på 5+3=8 måter. Sumregel i kombinatorikk: Hvis element a kan velges på m måter, og element b på n måter, og ethvert valg av element a er forskjellig fra alle valg av elementer i b, så kan valget "a eller b" gjøres i m + n måter. Prøveproblemer

10 lysbilde

Oppgave: I en klasse driver 10 elever idrett, de resterende 6 elevene går på en danseklubb. 1) Hvor mange par elever kan velges slik at en av paret er en idrettsutøver, den andre en danser? 2) Hvor mange valg har en elev? Løsning: 1) Muligheten for å velge 10 utøvere, og for hver av de 10 utøverne er det 6 valg av danser Dette betyr at muligheten for å velge par danser og utøver er 10·6=60. 2) Mulighet for å velge én elev 10+6=16.

11 lysbilde

Problem: Det er 3 veier som fører fra by A til by B. Og fra by B til by C er det 4 veier. Hvor mange veier gjennom B går fra A til C? Løsning: Du kan resonnere på denne måten: for hver av de tre stiene fra A til B er det fire måter å velge veien fra B til C på. Det totale antallet forskjellige stier fra A til C er lik produktet 3·4 , dvs. 12. Produktregel: La deg velge k elementer. Hvis det første elementet kan velges på n1 måter, det andre på n2 måter osv., så er antall måter k elementer lik produktet n1 · n2 ·... nк. Prøveproblemer

12 lysbilde

Problem: Det er 2 første, 5 andre og 4 tredje kurs i skolens kantine. På hvor mange måter kan en student velge en lunsj bestående av første, andre og tredje kurs? Løsning: Den første retten kan velges på 2 måter. For hvert valg av første kurs er det 5 andre kurs. De to første rettene kan velges på 2·5=10 måter. Og til slutt, for hver 10 av disse valgene, er det fire muligheter for å velge den tredje retter, dvs. det er 2·5·4 måter å komponere et tre-retters måltid. Så, lunsj kan komponeres på 40 måter.

Lysbilde 13

Lysbilde 14

15 lysbilde

Et arrangement av n elementer med k (k≤n) er ethvert sett som består av hvilke som helst k elementer tatt i en bestemt rekkefølge fra de gitte n elementene. Antallet av alle plasseringer av n elementer med m er betegnet med: Eksempler på oppgaver n! – faktor av tall n

16 lysbilde

Problem: På hvor mange måter kan 4 gutter invitere fire av seks jenter til dans? Løsning: To gutter kan ikke invitere samme jente samtidig. Og alternativene der de samme jentene danser med forskjellige gutter anses som forskjellige, derfor: 360 alternativer er mulige.

Lysbilde 17

En permutasjon av n elementer er hvert arrangement av disse elementene i en bestemt rekkefølge. Antallet av alle permutasjoner av n elementer er angitt med Pn Pn=n! Prøveproblemer

18 lysbilde

Kvartett Naughty Monkey Donkey, Goat, Ja, klumpfot bjørn De begynte å spille en kvartett... Stopp, brødre, stopp! - Apen roper, - vent! Hvordan skal musikken gå? Tross alt, du sitter ikke sånn... Og du byttet plass på denne måten – igjen går ikke musikken bra. Nå har de flere diskusjoner og stridigheter enn noen gang om hvem som skal sitte og hvordan... Avgjørelse

20 lysbilde

En kombinasjon uten repetisjon er et arrangement der rekkefølgen på elementene ikke spiller noen rolle. Dermed vil antallet alternativer når de kombineres, være mindre enn antall plasseringer. Antall kombinasjoner av n elementer med m er betegnet med: Eksempler på problemer

21 lysbilder

Problem: Hvor mange tre-knappskombinasjoner er det på en kombinasjonslås (alle tre knappene trykkes samtidig) hvis det bare er 10 sifre på den. Løsning: Siden knappene trykkes samtidig, er det en kombinasjon å velge disse tre knappene. Herfra er det mulig:

22 lysbilde

Ofte i kombinatoriske problemer er det sett der noen komponenter gjentas. For eksempel: i talloppgaver - tall. For slike problemer brukes følgende formler: hvor n er antallet av alle elementer, n1,n2,...,nr er antallet identiske elementer. Eksempler på oppgaver Eksempler på oppgaver Eksempler på oppgaver

Lysbilde 23

Problem: Hvor mange tresifrede tall kan lages av tallene 1, 2, 3, 4, 5? Løsning: Siden rekkefølgen av tallene i et tall er signifikant, kan tallene gjentas, da vil disse være plasseringer med repetisjoner av fem elementer i treere, og antallet er lik:

24 lysbilde

Oppgave: Et konditori solgte 4 typer kaker: eclairs, sandkaker, napoleoner og butterkaker. På hvor mange måter kan du kjøpe 7 kaker? Løsning: Kjøpet avhenger ikke av rekkefølgen de kjøpte kakene legges i esken. Innkjøp vil være forskjellige hvis de er forskjellige i antall kjøpte kaker av minst én type. Derfor er antallet forskjellige kjøp lik antall kombinasjoner av fire typer kaker, syv hver -

Lysbilde 27

Vi mener at arbeidet nådde sine mål. Vi har laget en oppslagsbok som tar sikte på å levendegjøre skolematematikk ved å introdusere interessante problemer som vil reise teoretiske spørsmål for elevene. Arbeidet er ment for studenter i klasse 10-11, som studerer på et grunnleggende nivå, utdanningsinstitusjoner for å utdype kunnskaper i matematikk. De særegne trekkene til denne håndboken er: en teoretisk del som er gjennomførbar for studenter på tredje trinn; utvelgelse og sammenstilling av oppgaver basert på livsmateriale og eventyrplott. Vi håper at arbeidet vårt vil interessere studentene, bidra til å utvikle deres horisont og tenkning, og bidra til bedre forberedelser til å bestå den enhetlige statlige eksamen.

28 lysbilde

Student: Dmitry Zakharov Klasse: 10 Leder: Toropova Nina Anatolyevna kommunale utdanningsinstitusjon "Videregående skole med fordypning i enkeltfag nr. 5", Krasnoyarsk

Kombinatorikk er en gren av matematikken som studerer spørsmål om hvor mange forskjellige kombinasjoner, under visse betingelser, kan lages av gitte objekter.
Ordet "combinatorics" kommer fra det latinske ordet "combinare", som oversatt til russisk betyr "å kombinere", "å koble til".
Begrepet "kombinatorikk" ble introdusert av den berømte Gottfried Wilhelm Leibniz, en verdensberømt tysk vitenskapsmann.

Kombinatorikk er en viktig gren av matematikk,
kunnskap som er nødvendig for representanter for en rekke spesialiteter. Fysikere, kjemikere, biologer, lingvister, kodespesialister osv. må forholde seg til kombinatoriske problemer.
Kombinatoriske metoder ligger til grunn for løsningen av mange teoretiske problemer
sannsynligheter og
sine applikasjoner.

I antikkens Hellas

telte antall forskjellige kombinasjoner av lange og korte stavelser i poetiske meter, studerte teorien om figurerte tall, studerte figurer som kan lages av deler, etc.

Over tid har det dukket opp forskjellige spill
(backgammon, kort, brikker, sjakk osv.)

I hvert av disse spillene måtte forskjellige kombinasjoner av figurer vurderes, og vinneren var den som studerte dem bedre, kjente vinnerkombinasjonene og visste hvordan man kunne unngå å tape.

Gottfried Wilhelm Leibniz (01.07.1646 - 14.11.1716)

Den tyske vitenskapsmannen G. Leibniz var den første som betraktet kombinatorikk som en uavhengig gren av matematikk i sitt arbeid "On the Art of Combinatorics", utgitt i 1666. Han laget også begrepet "Combinatorics" for første gang.

Leonhard Euler (1707–1783)

vurderte problemer rundt partisjonering av tall, matching, sykliske arrangementer, konstruksjon av magi og latinske firkanter, la grunnlaget for et helt nytt forskningsfelt, som senere vokste til en stor og viktig vitenskap innen topologi, som studerer de generelle egenskapene til rom og figurer.

Hvis noe objekt A kan velges på m måter, og et annet objekt B kan velges på n måter, kan valget "enten A eller B" gjøres på (m+n) måter.

Hvis noe objekt A kan velges på m måter, og et annet objekt B kan velges på n måter, kan valget "enten A eller B" gjøres på (m+n) måter.
Når du bruker sumregelen, må du sørge for at ingen av metodene for å velge objekt A faller sammen med noen metode for å velge objekt B.
Hvis det er slike treff, er sumregelen ikke lenger gyldig, og vi får kun (m + n - k) utvalgsmetoder, hvor k er antall treff.

Det er 10 baller i boksen: 3 hvite, 2 svarte, 1 blå og 4 røde. På hvor mange måter kan du ta en farget ball fra boksen?

Det er 10 baller i boksen: 3 hvite, 2 svarte, 1 blå og 4 røde. På hvor mange måter kan du ta en farget ball fra boksen?
Løsning:
En farget ball er enten blå eller rød, så vi bruker sumregelen:

Hvis objekt A kan velges på m måter og hvis objekt B etter hvert slikt valg kan velges på n måter, kan utvalget av paret (A, B) i den angitte rekkefølgen gjøres på mn måter.

Hvis objekt A kan velges på m måter og hvis objekt B etter hvert slikt valg kan velges på n måter, kan utvalget av paret (A, B) i den angitte rekkefølgen gjøres på mn måter.
I dette tilfellet avhenger ikke antall måter å velge det andre elementet på av nøyaktig hvordan det første elementet er valgt.

Hvor mange forskjellige kombinasjoner av mynter kan det være?

Hvor mange forskjellige kombinasjoner av mynter kan det være?
sider når du kaster to terninger?
Løsning:
Den første terningen kan ha: 1,2,3,4,5 og 6 poeng, dvs. 6 alternativer.
Den andre har 6 alternativer.
Totalt: 6*6=36 alternativer.

Summen og produktreglene er sanne for et hvilket som helst antall objekter.

nr. 1. Det er 6 veier som fører fra by A til by B, og 3 veier fra by B til by C. På hvor mange måter kan du reise fra by A til by C?

nr. 1. Det er 6 veier som fører fra by A til by B, og 3 veier fra by B til by C. På hvor mange måter kan du reise fra by A til by C?
nr. 2. I bokhylla er det 3 bøker om algebra, 7 om geometri og 2 om litteratur. På hvor mange måter kan du ta én mattebok fra hyllen?
nr. 3. Menyen har 4 førsteretter, 3 hovedretter og 2 desserter. Hvor mange forskjellige lunsjer kan du lage av dem?

"En factorial" -n!.

Definisjon.
Produkt av påfølgende første n
naturlige tall er angitt med n! og ring
«en factorial»: n!=1 2 3 … (n-1) n.

1 2 3=

1 2 3 4=

1 2 3 4 5=

1 2 3 4 5 6=

1 2 3 4 5 6 7=

n!=(n-1)! n

Praktisk formel!!!

Kombinasjoner av n-elementer som bare skiller seg fra hverandre i den rekkefølgen elementene vises i, kalles permutasjoner.

Kombinasjoner av n-elementer som bare skiller seg fra hverandre i den rekkefølgen elementene vises i, kalles permutasjoner.
Utpekt av Pn

Omorganiseringer

Lag et tresifret tall fra tallene 1, 5, 9
et tall uten repeterende sifre.

2 kombinasjoner

2 kombinasjoner

2 kombinasjoner

Totalt 2 3=6 kombinasjoner.

Kombinasjoner av n-elementer i k, som er forskjellige fra hverandre i sammensetning og rekkefølge, kalles plasseringer.

Kombinasjoner av n-elementer i k, som er forskjellige fra hverandre i sammensetning og rekkefølge, kalles plasseringer.

Plasseringer

Kombinasjoner av n-elementer ved Til Til.

Kombinasjoner av n-elementer ved Til, som bare skiller seg i sammensetningen av elementene, kalles kombinasjoner av n-elementer iht Til.

Kombinasjoner

Av 20 elever må du velge to vaktledere.

Av 20 elever må du velge to vaktledere.
På hvor mange måter kan dette gjøres?

Løsning:

Du må velge to personer av 20.
Det er klart at ingenting avhenger av rekkefølgen av valg, det vil si,
Ivanov - Petrov eller Petrov - Ivanov er en
og det samme paret ledsagere. Derfor vil disse være kombinasjoner av 20 ganger 2.

1. Hvor mange ord kan dannes av bokstavene i ordfragmentet hvis ordene må bestå av: 8 bokstaver; på 7 bokstaver; på 3 bokstaver?

1. Hvor mange ord kan dannes av bokstavene i ordfragmentet hvis ordene må bestå av: 8 bokstaver; på 7 bokstaver; på 3 bokstaver?
2. Studenten skal bestå 4 eksamener innen ti dager. På hvor mange måter kan du planlegge eksamenene hans?
3. På hvor mange måter kan en kommisjon bestående av fem medlemmer velges blant åtte personer?
4. Hvor mange forskjellige skilt er det som består av 5 siffer hvis det første ikke er null? Hva om tallet består av én bokstav etterfulgt av fire sifre som ikke er null?
5. Entreprenøren trenger 4 snekkere, og 10 har henvendt seg til ham med tilbud om sine tjenester På hvor mange måter kan han velge fire av dem?
6. På hvor mange måter kan syv bøker ordnes på en hylle?
7. Hvor mange 5-bokstavsord kan dannes ved å bruke 10 forskjellige bokstaver.
8. På hvor mange måter kan du velge flere frukter fra syv epler, fire sitroner og ni appelsiner? (Frukter av samme type regnes som umulige å skille.)

Petrov Vladimir, student av den 12. gruppen av den statlige budsjettmessige utdanningsinstitusjonen SO NPO "Vocational School No. 22", Saratov

Presentasjonen diskuterer eksempler på å løse problemer med å finne permutasjoner, plasseringer og kombinasjoner.

Nedlasting:

Forhåndsvisning:

For å bruke forhåndsvisninger av presentasjoner, opprett en Google-konto og logg på den: https://accounts.google.com

Lysbildetekster:

Elementer av kombinatorikk: permutasjoner, kombinasjoner og plasseringer Presentasjonen ble utarbeidet av Vladimir Petrov, en student i gruppe 12 ved Statens budsjettmessige utdanningsinstitusjon SO NPO.

Kombinatorikk er en gren av matematikk som er opptatt med å søke etter svar på spørsmål: hvor mange kombinasjoner er det i et gitt tilfelle, hvordan velge den beste fra alle disse kombinasjonene. Ordet "combinatorics" kommer fra det latinske ordet "combinare", som oversatt til russisk betyr "å kombinere", "å koble til". Begrepet "kombinatorikk" ble introdusert av den berømte Gottfried Wilhelm Leibniz, en verdensberømt tysk vitenskapsmann.

Kombinatoriske problemer er delt inn i flere grupper: Permutasjonsproblemer Plasseringsproblemer Kombinasjonsproblemer

Omorganiseringsproblemer På hvor mange måter kan 3 forskjellige bøker ordnes i en bokhylle? Dette er et permutasjonsproblem

Skriv n! lyder slik: "en factorial" Faktoriell er produktet av alle naturlige tall fra 1 til n For eksempel 4! = 1*2*3*4 = 24 n! = 1 · 2 · 3 · ... · n.

n 1 2 3 4 5 6 7 8 9 10 n! 1 4 6 24 120 720 5040 40320 362880 3628800 Faktorer vokser overraskende raskt:

Oppgave. På hvor mange måter kan de 8 deltakerne i finaleløpet arrangeres på åtte tredemøller? P8 = 8!= 1 ∙2∙ 3 ∙4∙ 5 ∙6∙ 7 ∙8 = 40320

En permutasjon av n elementer er hvert arrangement av disse elementene i en bestemt rekkefølge. P n = 1 · 2 · 3 · ... · n. Pn=n!

Oppgave. Kvartett Naughty Monkey Donkey, Goat, Ja, klumpfot bjørn De begynte å spille en kvartett... Stopp, brødre, stopp! - Apen roper, - vent! Hvordan skal musikken gå? Tross alt, du sitter ikke sånn... Og du byttet plass på denne måten – igjen går ikke musikken bra. Nå har de flere diskusjoner og stridigheter enn noen gang om hvem som skal sitte og hvordan... På hvor mange måter kan fire musikere sitte? P = 4! = 1 * 2 * 3 * 4 = 24

Plasseringsoppgaver

Problem: Vi har 5 bøker, at vi kun har én hylle, og at den kun har plass til 3 bøker. På hvor mange måter kan 3 bøker ordnes på en hylle? Vi velger en av 5 bøker og legger den på første plass i hyllen. Vi kan gjøre dette på 5 måter. Nå er det to plasser igjen i hyllen og vi har 4 bøker igjen. Vi kan velge den andre boken på 4 måter og plassere den ved siden av en av de 5 mulige første. Det kan være 5·4 slike par. Det er 3 bøker og en plass igjen. En bok av 3 kan velges på 3 måter og plasseres ved siden av et av de mulige 5·4 parene. Du får 5·4·3 forskjellige trillinger. Dette betyr at det totale antallet måter å plassere 3 bøker av 5 på er 5·4·3 = 60. Dette er et plasseringsproblem.

Et arrangement av n elementer med k (k≤n) er ethvert sett som består av k elementer tatt i en viss rekkefølge fra de gitte n elementene.

Oppgave. Elever i andre klasse studerer 9 fag. På hvor mange måter kan du lage en timeplan for én dag slik at den inneholder 4 forskjellige fag? A 4 9 = = 6∙ 7∙ 8∙ 9 = 3024

Bestem selv: Det er 27 elever i klassen. Du må sende en elev for å få kritt, den andre for å være på vakt i kafeteriaen, og den tredje for å ringe til tavlen. På hvor mange måter kan dette gjøres?

Kombinasjonsproblemer: Problem. På hvor mange måter kan 3 bind ordnes i en bokhylle hvis du velger dem fra de 5 eksternt umulige bøkene som er tilgjengelige? Bøkene er utad umulig å skille. Men de er forskjellige, og betydelig! Disse bøkene er forskjellige i innhold. En situasjon oppstår når sammensetningen av prøveelementene er viktig, men rekkefølgen på deres arrangement er uviktig. 123 124 125 134 135 145 234 235 245 345 svar: 10 Dette er et kombinasjonsproblem

En kombinasjon av n elementer med k er ethvert sett sammensatt av k elementer valgt fra de gitte n elementene.

Oppgave. Det er 7 personer i klassen som lykkes med matematikk. På hvor mange måter kan du velge to av dem til å delta i matematikk-olympiaden? C72 = = 21

Bestem selv: I klasse 7 gjør elevene det bra i matematikk. På hvor mange måter kan to av dem velges ut til å bli sendt for å delta i matematisk olympiad?

Et spesielt trekk ved kombinatoriske problemer er et spørsmål som kan formuleres slik at det begynner med ordene "På hvor mange måter ..." eller "Hvor mange alternativer ..."

Permutasjoner Plasseringer Kombinasjoner av n elementer n celler n elementer k celler n elementer k celler Rekkefølge er viktig Rekkefølge spiller ingen rolle La oss lage en tabell:

Løs oppgavene selv: 1. Det er 10 hvite og 6 sorte kuler i boksen. På hvor mange måter kan en kule av hvilken som helst farge tas ut av en boks? 2. Olga husker at vennens telefonnummer slutter med tre tall 5, 7, 8, men hun glemte i hvilken rekkefølge disse numrene er plassert. Angi det største antallet alternativer hun må gå gjennom for å komme gjennom til vennen sin. 3. Filatelibutikken selger 8 forskjellige sett med frimerker dedikert til sportstemaer. På hvor mange måter kan du velge 3 sett fra dem?

Elementer av kombinatorikk 9-11 klassetrinn, MBOU Kochnevskaya ungdomsskolelærer Gryaznova A.K. Hovedspørsmål:

Hva er kombinatorikk?

Hvilke problemer anses som kombinatoriske?

Omorganiseringer
Plasseringer
Kombinasjoner

La oss ikke krangle - la oss beregne. G. Leibnitz

Kombinatorikk– en gren av matematikk som omhandler problemer med å telle antall kombinasjoner laget i henhold til visse regler.

II. Hvilke problemer anses som kombinatoriske? Kombinatoriske problemer Problemer med å telle antall kombinasjoner fra et begrenset antall elementer

Kombinatorikk– fra det latinske ordet kombinere, som betyr "å koble sammen, kombinere."
Kombinatoriske metoder er mye brukt innen fysikk, kjemi, biologi, økonomi og andre kunnskapsfelt.
Kombinatorikk kan betraktes som en del av settteori - ethvert kombinatorisk problem kan reduseres til et problem om endelige mengder og deres tilordninger.

I. Nivåer for å løse kombinatoriske problemer 1. Første nivå. Oppgaven med å finne minst en løsning, minst ett arrangement av objekter med gitte egenskaper er å finne en slik ordning på ti punkter på fem segmenter, der det er fire punkter på hvert segment; - et slikt arrangement med åtte dronninger på et sjakkbrett der de ikke slår hverandre. Noen ganger er det mulig å bevise at dette problemet ikke har noen løsning (for eksempel er det umulig å arrangere 10 kuler i 9 urner slik at hver urne ikke inneholder mer enn én ball - minst én urne vil inneholde minst to kuler). 2. Andre nivå. 2. Andre nivå. Hvis et kombinatorisk problem har flere løsninger, oppstår spørsmålet om å telle antall slike løsninger og beskrive alle løsninger på dette problemet.

3. Tredje nivå.

optimal

For eksempel:

En reisende ønsker å forlate by A, besøke byer B, C og D, og deretter gå tilbake til by A.

I fig. viser et diagram over rutene som forbinder disse byene. Ulike reisealternativer skiller seg fra hverandre i rekkefølgen de besøker byene B, C og D. Det er seks reisealternativer. Tabellen viser alternativene og lengdene for hver bane:

Kombinatoriske optimaliseringsproblemer må løses av en arbeidsleder som streber etter raskest fullføring av en oppgave, en agronom som streber etter høyest utbytte i gitte felt, etc.

Vi vil kun vurdere problemer med å telle antall løsninger på et kombinatorisk problem.

Vi vil kun vurdere problemer med å telle antall løsninger på et kombinatorisk problem.

oppregningsteori

Sum og produktregler

1. Hvor mange forskjellige cocktailer kan lages av fire drinker, blande dem i like mengder av to?
AB, AC, AD, BC, BD, CD – 6 cocktailer totalt

2. Hvor mange forskjellige tosifrede tall kan lages av sifrene 0, 1, 2, 3?

2. Hvor mange forskjellige tosifrede tall kan lages av sifrene 0, 1, 2, 3?
Første siffer andre siffer

Produktregel:

Hvis element A kan velges fra et sett med elementer på n måter og for hvert slikt valg kan element B velges på t måter, så kan to elementer (par) A og B velges på n måter.

"Eksempler på å løse kombinatoriske problemer: oppregning av alternativer, sumregel, multiplikasjonsregel."

På hvor mange måter kan de 4 deltakerne i finaleløpet plasseres på fire tredemøller?

R n = 4 3 2 1= 24 måter (permutasjoner av 4 elementer)

2 3 4 1 3 4 1 2 4 1 2 3

1 spor

II. Permutasjoner (1) K v a r t e t Den slemme apen, eselet, geiten og den klumpfotede bjørnen De begynte å spille en kvartett. …………………………………………………………. De treffer buene, de kjemper, men det er ingen vits. «Stopp, brødre, stopp! - Apen roper. - Vente! Hvordan skal musikken gå? Tross alt, du sitter ikke slik.»

4·3·2·1 = 4! måter

II. Permutasjoner (2)

Permutasjon fra P- elementer er kombinasjoner som bare skiller seg fra hverandre i rekkefølgen av elementene
Pn - antall permutasjoner (P er den første bokstaven i det franske ordet permutation - permutation)

Рп= n

Overnattingssteder (1)

Fire medreisende bestemte seg for å bytte visittkort. Hvor mange kort ble brukt totalt?

Kombinasjoner laget av k elementer hentet fra n elementer, og som skiller seg fra hverandre enten i sammensetning eller i rekkefølgen av arrangement av elementer, kalles plasseringer fra n elementer av k(0< k ≤n ).

Overnatting fra n elementer av k elementer. Og den første bokstaven

fransk ord ordning: "plassering",

"sette ting i orden"

Overnattingssteder (2)

Det er 4 tomme baller og 3 tomme celler. La oss betegne ballene med bokstaver a, b, c, d. Tre baller fra dette settet kan plasseres i de tomme cellene på forskjellige måter.
Ved å velge den første, andre og tredje ballen forskjellig, vil vi få forskjellige bestilt tre baller
Hver bestilt en trippel som kan bestå av fire elementer kalles plassering av fire elementer, tre hver

Overnattingssteder (3)

Hvor mange plasseringer kan gjøres fra 4 elementer ( abcd) tre?
abc abd acb acd adb adc
bac dårlig bca bcd bda bdc
cab cad cba cbd cda cdb
dab dac dba dbc dca dcb

Det ble besluttet å gjennomgå alternativene

Overnattingssteder (4)

Du kan løse dette uten å skrive ut selve plasseringene:
først et element kan velges på fire måter, så det kan være et hvilket som helst element av fire;
for hver første sekund kan velges på tre måter;
for hver av de to første er det to måter å velge på tredje element fra de resterende to.

Vi får

Løst ved hjelp av multiplikasjonsregelen

Kombinasjoner

En kombinasjon av P elementer av k er ethvert sett sammensatt av k elementer valgt fra P elementer

I motsetning til plasseringer i kombinasjoner rekkefølgen på elementene spiller ingen rolle. To kombinasjoner skiller seg fra hverandre i minst ett element

Løser problemer: 1. Det er 5 punkter merket på flyet. Hvor mange segmenter blir det hvis du kobler sammen punktene i par?

2. Merket på sirkelen P poeng. Hvor mange trekanter er det med hjørner på disse punktene?

Informasjonskilder

V.F. Butuzov, Yu.M. Kolyagin, G.L. Lukankin, E.G. Poznyak og andre. "Matematikk" lærebok for utdanningsinstitusjoner i 11. klasse / anbefalt av utdanningsdepartementet i Den russiske føderasjonen / M., Prosveshchenie, 1996.
E.A. Bunimovich, V.A. Bulychev: "Sannsynlighet og statistikk", en håndbok for generelle utdanningsinstitusjoner klasse 5 – 9 / godkjent av utdanningsdepartementet i den russiske føderasjonen // Bustard Moskva 2002
Yu.N. Makarychev, N.G. Mindyuk "Algebra: elementer av statistikk og sannsynlighetsteori, karakterer 7 - 9" Redigert av S.A. Telyakovsky M: Prosveshchenie, 2006
Trekanter http://works.doklad.ru/images/_E3ZV-_wFwU/md87b96f.gif

Resten av tegningene ble laget av A.K. Gryaznova.

Elementer
kombinatorikk.
Elektronisk pedagogisk manual
for elever i 9.-11.
Forfatter-kompilator:
Katorova O.G.,
matematikklærer
MBOU "Gymnasium nr. 2"
Sarov

Kombinatorikk

Kombinatorikk er en seksjon
matematikk, som studerer
spørsmål om valg eller plassering
elementer av settet i samsvar
med gitte regler.
"Kombinatorikk" kommer fra latin
ordene "combina", som er oversatt til russisk
betyr "å kombinere", "å koble".

HISTORISK REFERANSE
Begrepet "kombinatorikk" var
introdusert i matematisk bruk
verdensomspennende
berømt
tysk
vitenskapsmann G.V. Leibniz, som i
1666 publiserte Diskurser
om kombinatorisk kunst."
G.W. Leibniz
På 1700-tallet vendte man seg mot å løse kombinatoriske problemer
og andre fremragende matematikere. Ja, Leonhard Euler
vurderte problemer med partisjonering av tall, matching,
sykliske ordninger, om konstruksjon av magiske og
latinske firkanter.

Combinatorics-avtaler
ulike typer forbindelser
(omorganiseringer, plasseringer,
kombinasjoner) som kan være
form fra elementer
noe begrenset sett.

Kombinatoriske forbindelser

Omorganiseringer
1.
2.
Permutasjoner uten repetisjon
Permutasjoner med repetisjoner
Plasseringer
1.
2.
Plasseringer uten repetisjoner
Plasseringer med repetisjoner
Kombinasjoner
1.
2.
Kombinasjoner uten repetisjoner
Kombinasjoner med repetisjoner

Permutasjoner - forbindelser,
som kan være sammensatt av n
elementer, endrer alle
mulige måter å bestille dem på.
Formel:

Historisk referanse

I 1713 ble den utgitt
essay av J. Bernoulli "Art
antakelser" der
ble presentert tilstrekkelig detaljert
kjent på den tiden
kombinatoriske fakta.
"Kunst
forutsetninger" ble ikke fullført
av forfatteren og dukket opp etter hans død.
Essayet besto av 4 deler,
kombinatorikk ble viet
den andre delen, som inneholder
formel for antall permutasjoner av n
elementer.

Eksempel

På hvor mange måter kan 8 personer stå i
kø i billettkontoret?
Løsningen på problemet:
Det er 8 seter som må besettes av 8 personer.
Hvilken som helst av 8 personer kan ta førsteplassen, dvs. måter
ta førsteplassen - 8.
Etter at én person er på førsteplass er det 7 igjen
seter og 7 personer som kan få plass på dem, d.v.s.
måter å ta andreplassen - 7. Tilsvarende for tredje,
fjerde osv. steder.
Ved å bruke multiplikasjonsprinsippet får vi produktet. Dette
produktet er betegnet som 8! (les 8 factorial) og
kalles P8-permutasjonen.
Svar: P8 = 8!

Sjekk deg selv

1) På hvor mange måter kan du plassere
det er fire forskjellige på hyllen ved siden av hverandre
bøker?
LØSNING

Sjekk deg selv

2) På hvor mange måter kan du sette
10 forskjellige kort i 10 tilgjengelig
konvolutter (ett postkort per konvolutt)?
LØSNING

Sjekk deg selv

3) På hvor mange måter kan du plante
åtte barn på åtte stoler i spisestuen
barnehage?
LØSNING

Sjekk deg selv

4) Hvor mange forskjellige ord kan du finne på?
omorganisere bokstaver i et ord
"trekant" (inkludert selve ordet)?
LØSNING

Sjekk deg selv

5) Hvor mange måter kan du installere
plikt på én person per dag blant syv
gruppestudenter i 7 dager (hver
må være på vakt en gang)?
LØSNING

Sjekk deg selv

Permutasjoner med
repetisjoner
Enhver plassering med repetisjoner, i
hvor element a1 gjentas k1 ganger, element
a2 gjentas k2 ganger osv. et element
gjentatte kn ganger, hvor k1, k2, ..., kn er data
nummer kalles en permutasjon med
repetisjoner av ordren
m = k1 + k2 + … + kn, hvor dataene
elementene a1, a2, …, an gjentas
henholdsvis k1, k2, .., kn ganger.

Sjekk deg selv

Permutasjoner med
repetisjoner
Teorem. Antall forskjellige permutasjoner med
repetisjoner av elementer (a1, ..., an), i
hvis elementer a1, …, an gjentas
henholdsvis k1, ..., kn ganger, lik
(k1+k2+…+kn)!
m!
P
k1! k2! ... kn!
k1! k2! ... kn!

Sjekk deg selv

Eksempel
Ord og uttrykk med bokstaver omorganisert
kalles anagrammer. Hvor mange anagrammer kan du
laget av ordet "makak"?
Løsning.
Det er totalt 6 bokstaver i ordet "MACACA" (m=6).
La oss bestemme hvor mange ganger hver bokstav brukes i et ord:
"M" - 1 gang (k1=1)
"A" - 3 ganger (k2=3)
"K" - 2 ganger (k3=2)
m!
P=
k1! k2! …kn!
6!
4*5*6
Р1,3,2 =
= 2 = 60.
1! 3! 2!

Sjekk deg selv

1) Hvor mange forskjellige ord kan du få,
omorganisere bokstavene i ordet "matematikk"?
LØSNING

Sjekk deg selv

2) På hvor mange måter kan du ordne
første horisontale sjakkbrettsett
hvite brikker (konge, dronning, to tårn, to
elefant og to riddere)?
LØSNING

Sjekk deg selv
3) Mamma har 2 epler, 3 pærer og 4 appelsiner.
Hver dag i ni dager på rad hun
gir sønnen en av de gjenværende fruktene.
På hvor mange måter kan dette gjøres?
LØSNING

Historisk referanse
Kombinatoriske motiver kan være
legg merke til også i symbolikken til den kinesiske «boken
endringer" (V århundre f.Kr.).
På 1100-tallet. Indisk matematiker Bhaskara
hans hovedverk "Lilavati" i detalj
studert problemer med permutasjoner og
kombinasjoner, inkludert permutasjoner med
repetisjoner.

Eksempel

Plasseringer
Ved å plassere n elementer i k rekkefølge
(k n) er ethvert sett
bestående av alle k elementer tatt inn
en viss rekkefølge av n elementer.
To arrangementer av n elementer vurderes
annerledes hvis de er forskjellige selv
elementer eller rekkefølgen de er ordnet i.
A n(n 1)(n 2) ... (n (k 1))
k
n

Sjekk deg selv

Eksempel
På hvor mange måter av 40 elever i en klasse
Eiendelen kan identifiseres som følger:
leder, fysiker og veggavisredaktør?
Løsning:
Det er nødvendig å velge bestilte treelementer
delsett av et sett som inneholder 40
elementer, dvs. finn antall plasseringer uten
repetisjoner av 40 elementer av 3.
40!
A=
=38*39*40=59280
37!
3
40

Sjekk deg selv

1. Velg mellom syv forskjellige bøker
fire. Hvor mange måter er dette mulig?
gjøre?
LØSNING

Sjekk deg selv

2. De deltar i fotballmesterskapet
ti lag. Hvor mange finnes
ulike muligheter å ta
lag tre førsteplasser?
LØSNING

Sjekk deg selv

3. Det studeres 7 emner i klassen. onsdag 4
leksjoner, og hver enkelt er forskjellig. Hvor mange
måter du kan lage en tidsplan for
Onsdag?
LØSNING

Sjekk deg selv

Plasseringer med
repetisjoner
Plasseringer med repetisjoner –
forbindelser som inneholder n elementer,
valgt fra m forskjellige elementer
art (n m) og forskjellig fra
en annen enten ved sammensetning eller rekkefølge
elementer.
Antallet deres er antatt
ubegrenset antall elementer
hver type er lik

Sjekk deg selv

Eksempel på bruk
Til biblioteket, som har mange
ti like lærebøker
fag, 5 skoleelever kom,
hver av dem ønsker å ta en lærebok.
Bibliotekaren skriver i en journal
rekkefølge av navn (uten nummer) tatt
lærebøker uten navn på elevene som ga dem
har tatt. Hvor mange forskjellige lister er det i bladet?
kan det dukke opp?

Historisk referanse

Løsningen på problemet
Siden lærebøker for hver
emnet er det samme, og bibliotekaren
registrerer bare navnet (uten
tall), så er listen plassering med
repetisjon, antall elementer
originalsettet er 10, og
antall stillinger – 5.
Da er antall ulike lister lik
= 100000.
Svar: 100 000

Plasseringer

Sjekk deg selv!
1. Telefonnummeret består av 7 sifre.
Hva er det største antallet samtaler
taper-Petya kan forplikte seg
før du gjetter riktig tall.
LØSNING
LØSNING

Eksempel

Sjekk deg selv!
2. På hvor mange måter kan du
skrive et ord som består av
fire bokstaver i det engelske alfabetet?
LØSNING

Sjekk deg selv

Sjekk deg selv!
3. I en butikk hvor det er 4 typer baller,
Vi bestemte oss for å sette 8 baller på rad. Hvor mange
måter du kan gjøre dette på hvis de
Betyr plasseringen noe?
LØSNING

Sjekk deg selv

Sjekk deg selv!
4. På hvor mange måter kan du sy på
seks knapp foret klovnedrakt
en av fire farger å få
mønster?
LØSNING

Sjekk deg selv

Kombinasjoner
Kombinasjoner - forbindelser som inneholder hver
m elementer ut av n, forskjellige fra hverandre
venn med minst ett element.
Kombinasjoner er endelige sett, i
rekkefølgen spiller ingen rolle.

Sjekk deg selv

Kombinasjoner
Formel for å finne mengde
kombinasjoner uten repetisjon:

Sjekk deg selv

Historisk referanse
I 1666 publiserte Leibniz Diskurser
om kombinatorisk kunst." I sitt essay
Leibniz, introduserer spesielle symboler, vilkår for
delmengder og operasjoner på dem, finner alle k kombinasjoner av n elementer, viser egenskaper
kombinasjoner:
,
,

Sjekk deg selv

Eksempel på bruk:
På hvor mange måter kan du velge to
vaktledere fra en klasse med 25 elever?
Løsning:
m = 2 (nødvendig antall vaktpersonell)
n = 25 (totalt elever i klassen)

Plasseringer med repetisjoner

Sjekk deg selv!
1) På hvor mange måter kan du
delegere tre studenter til
interuniversitetskonferanse med 9 medlemmer
vitenskapelig samfunn?
LØSNING

Eksempel på bruk

Sjekk deg selv!
2) Ti konferansedeltakere
håndhilste håndhilste
til hver. Hvor mange håndtrykk var det?
laget?
LØSNING

Løsningen på problemet

Sjekk deg selv!
3) Det er 6 jenter og 4 gutter i skolekorpset.
Hvor mange måter kan du velge mellom
skolekorpssammensetning: 2 jenter og 1 gutt
å delta i fremføringen av distriktskoret?
LØSNING

Sjekk deg selv!

4) På hvor mange måter kan du velge 3
idrettsutøvere fra en gruppe på 20 personer for
deltakelse i konkurranser?
LØSNING

Sjekk deg selv!

5) Det er 10 akademiske emner og 5 forskjellige i klassen
leksjoner per dag. På hvor mange måter kan
være timene fordelt på samme dag?
LØSNING

Sjekk deg selv!

Kombinasjoner med repetisjoner
Definisjon
Kombinasjoner med repetisjoner fra m til
n er forbindelser som består av n
elementer valgt fra m elementer
forskjellige typer, og forskjellig fra
en annen med minst ett element.
Antall kombinasjoner fra m til n
betegne

Sjekk deg selv!

Kombinasjoner med repetisjoner
Hvis man velger fra et sett som inneholder n elementer
vekselvis m elementer, med det valgte elementet
kommer tilbake hver gang, deretter antall måter
lage en uordnet prøve - antall kombinasjoner med
repetisjoner – gjør opp

Sjekk deg selv!

Historisk referanse
Ledende indisk matematiker
Bhaskara Akaria (1114–1185) også
studerte ulike typer kombinatoriske
forbindelser. Han eier avhandlingen
"Sidhanta-Shiromani" ("undervisningens krone"),
omskrevet på 1200-tallet. på striper
palmeblader. I den ga forfatteren
verbale regler for å finne
Og
, som indikerer deres applikasjoner og plassering
mange eksempler

Sjekk deg selv!

Eksempel på bruk
Oppgave nr. 1
Hvor mange sett med 7 kaker
kan kompileres hvis tilgjengelig
Finnes det 4 typer kaker?
Løsning:

Sjekk deg selv!

Eksempel på bruk
Oppgave nr. 2
Hvor mange bein er det i en normal
dominospill?
Løsning: Domino kan betraktes som
kombinasjoner med repetisjoner av to av syv sifre
sett (0,1,2,3,4,5,6).
Antallet på alle slike
kombinasjoner er like

Sjekk deg selv!

Sjekk deg selv
Oppgave 1.
Gymnasiums kafeteria selger 5 varianter
paier: med epler, med kål,
poteter, kjøtt og sopp. Hvor mange
flere måter du kan kjøpe fra
10 paier?
LØSNING

Kombinasjoner

Sjekk deg selv
Oppgave 2.
Boksen inneholder kuler i tre farger -
rødt, blått og grønt. Hvor mange
måter du kan lage et sett med to på
baller?
LØSNING

Kombinasjoner

Sjekk deg selv
Oppgave 3.
På hvor mange måter kan du velge 4
mynter fra fire fem-kopek mynter og fra
fire to-kopek mynter?
LØSNING

Sjekk deg selv
Oppgave 4.
Hvor mange dominobrikker blir det?
hvis i deres
utdanning bruker alle tall?
LØSNING

Sjekk deg selv
Oppgave 5.
Den unge impresjonistens palett består av 8
ulike farger. Kunstneren tar en pensel
tilfeldig noen av fargene og setter fargen
flekk på whatman-papir. Så tar den neste
pensel, dypper den i noen av malingene og lager
andre plass ved siden av. Hvor mange
forskjellige kombinasjoner finnes for
seks plasser?
LØSNING

Brukte bøker
Algebra og begynnelsen av matematikk
analyse. 11. klasse / Yu.M. Kolyagin, M.V. Tkacheva,
N.E. Fedorova, M.I. Shabunin. –
M.: Utdanning, 2011.
Vilenkin N.Ya. Kombinatorikk. – M., 1969
Vilenkin N.Ya. Kombinatorikk. – MCMNO,
2010
ru.wikipedia.org›wiki/History of combinatorics