Mulige kombinasjoner. Kombinasjoner

Tenk på problemet med å telle antall prøver fra et gitt sett i generelle termer. La det være et sett N, bestående av n elementer. Enhver undergruppe av m elementer kan vurderes uten å ta hensyn til rekkefølgen deres, og med det, dvs. når du endrer rekkefølgen, gå til en annen m- prøvetaking.

Vi formulerer følgende definisjoner:

Plasseringer uten repetisjon

Ved å plassere uten å gjenta utn elementer avm Ninneholdermulike elementer.

Det følger av definisjonen at to arrangementer skiller seg fra hverandre, både i elementer og i rekkefølge, selv om elementene er like.

Teorem 3. Antall plasseringer uten repetisjon er lik produktet m faktorer, hvorav den største er antallet n . Skrive ned:

Permutasjoner uten repetisjon

Permutasjoner fran elementer kalles forskjellige rekkefølger av settetN.

Det følger av denne definisjonen at to permutasjoner bare er forskjellige i rekkefølgen av elementene og kan betraktes som et spesielt tilfelle av arrangementer.

Teorem 4. Antall forskjellige permutasjoner uten repetisjon beregnes av formelen

Kombinasjoner uten repetisjon

En kombinasjon uten repetisjon avn elementer avm enhver uordnet delmengde av et sett kallesNinneholderm ulike elementer.

Det følger av definisjonen at to kombinasjoner bare skiller seg i elementer, rekkefølgen er ikke viktig.

Teorem 5. Antall kombinasjoner uten repetisjoner beregnes ved å bruke en av følgende formler:

Eksempel 1. Det er 5 stoler i rommet. På hvor mange måter kan du plassere

a) 7 personer; b) 5 personer; c) 3 personer?

Beslutning: a) Først av alt må du velge 5 personer av 7 til å sitte på stolene. Det kan gjøres
vei. Med hvert valg av en bestemt fem, kan man produsere
permutasjoner på steder. I følge multiplikasjonsteoremet er ønsket antall landingsmetoder likt.

Kommentar: Problemet kan løses ved å bruke bare produktteoremet, og argumenter som følger: det er 7 alternativer for å lande på 1. stol, 6 alternativer på 2. stol, 5 på 3., 4 på 4. og 5. -3. Da er antall måter å sitte på 7 personer på 5 stoler lik . Løsningene er konsistente på begge måter, siden

b) Løsningen er åpenbar -

i) - antall valg av okkuperte stoler.

- antall plasseringer av tre personer på tre utvalgte stoler.

Det totale antallet valg er .

Det er ikke vanskelig å sjekke formlene
;

;

Antallet av alle delmengder av settet som består av n elementer.

Plasseringer med repetisjon

Plassering med repetisjon fran elementer avm er en hvilken som helst ordnet delmengde av et settN, bestående avm elementer slik at et hvilket som helst element kan inkluderes i denne delmengden fra 1 tilmganger, eller ikke i det hele tatt.

Antall plasseringer med repetisjon er angitt og beregnet i henhold til formelen, som er en konsekvens av multiplikasjonssetningen:

Eksempel 2. La et sett med tre bokstaver N = (a, b, c) gis. La oss kalle et ord et hvilket som helst sett med bokstaver som er inkludert i dette settet. La oss finne antall ord med lengde 2 som kan dannes fra disse bokstavene:
.

Kommentar: Opplegg med repetisjon kan selvsagt også vurderes
.

Eksempel 3. Det kreves fra bokstavene (a, b) å komponere alle mulige ord med lengde 3. På hvor mange måter kan dette gjøres?

Svar:

Kombinatorikk er en gren av matematikken som studerer spørsmål om hvor mange forskjellige kombinasjoner, under visse betingelser, kan lages av gitte objekter. Det grunnleggende om kombinatorikk er svært viktig for å estimere sannsynlighetene for tilfeldige hendelser, fordi det er de som gjør det mulig å beregne det fundamentalt mulige antallet ulike scenarier for utvikling av hendelser.

Grunnleggende kombinatorisk formel

La det være k grupper av elementer, og den i-te gruppen består av n i elementer. La oss velge ett element fra hver gruppe. Da er det totale antallet N måter et slikt valg kan gjøres på, bestemt av forholdet N=n 1 *n 2 *n 3 *...*n k .

Eksempel 1 La oss forklare denne regelen med et enkelt eksempel. La det være to grupper av elementer, den første gruppen består av n 1 elementer, og den andre - av n 2 elementer. Hvor mange forskjellige elementpar kan lages fra disse to gruppene slik at paret inneholder ett element fra hver gruppe? Anta at vi tok det første elementet fra den første gruppen og, uten å endre det, gikk gjennom alle mulige par, og endret bare elementene fra den andre gruppen. Det er n 2 slike par for dette elementet. Så tar vi det andre elementet fra den første gruppen og lager også alle mulige par for det. Det vil også være n 2 slike par. Siden det bare er n 1 elementer i den første gruppen, vil det være n 1 *n 2 mulige alternativer.

Eksempel 2 Hvor mange tresifrede partall kan lages fra sifrene 0, 1, 2, 3, 4, 5, 6 hvis sifrene kan gjentas?
Beslutning: n 1 \u003d 6 (siden du kan ta et hvilket som helst siffer fra 1, 2, 3, 4, 5, 6 som det første sifferet), n 2 \u003d 7 (siden du kan ta et hvilket som helst siffer fra 0 som det andre sifferet , 1 , 2, 3, 4, 5, 6), n 3 \u003d 4 (siden du kan ta et hvilket som helst siffer fra 0, 2, 4, 6 som det tredje sifferet).
Så, N=n 1 *n 2 *n 3 =6*7*4=168.

I tilfellet når alle grupper består av like mange elementer, dvs. n 1 =n 2 =...n k =n vi kan anta at hvert valg er gjort fra samme gruppe, og elementet går tilbake til gruppen etter valget. Da er antallet av alle måter å velge på lik n k . Denne måten å velge på i kombinatorikk kalles returnere prøver.

Eksempel 3 Hvor mange firesifrede tall kan lages av tallene 1, 5, 6, 7, 8?
Beslutning. Det er fem muligheter for hvert siffer i et firesifret tall, så N=5*5*5*5=5 4 =625.

Tenk på et sett som består av n elementer. Dette settet i kombinatorikk kalles generell befolkning.

Antall plasseringer fra n elementer med m

Definisjon 1. Overnatting fra n elementer av m i kombinatorikk kalles enhver bestilt sett fra m ulike elementer valgt fra den generelle befolkningen i n elementer.

Eksempel 4 Ulike arrangementer av tre elementer (1, 2, 3) to og to vil være sett (1, 2), (2, 1), (1, 3), (3, 1), (2, 3), (3) , 2). Plasseringer kan avvike fra hverandre både i elementer og i rekkefølge.

Antall plasseringer i kombinatorikk er angitt med A n m og beregnes med formelen:

Kommentar: n!=1*2*3*...*n (les: "en factorial"), i tillegg antas det at 0!=1.

Eksempel 5. Hvor mange tosifrede tall er det der titallet og enhetssifferet er forskjellige og odde?
Beslutning: fordi det er fem oddetall, nemlig 1, 3, 5, 7, 9, så er dette problemet redusert til å velge og plassere to av de fem forskjellige sifrene i to forskjellige posisjoner, dvs. de gitte tallene vil være:

Definisjon 2. Kombinasjon fra n elementer av m i kombinatorikk kalles enhver uordnet sett fra m ulike elementer valgt fra den generelle befolkningen i n elementer.

Eksempel 6. For settet (1, 2, 3) er kombinasjonene (1, 2), (1, 3), (2, 3).

Antall kombinasjoner av n elementer med m

Antall kombinasjoner er angitt med C n m og beregnes med formelen:

Eksempel 7 På hvor mange måter kan leseren velge to bøker av seks tilgjengelige?

Beslutning: Antall måter er lik antall kombinasjoner av seks bøker med to, dvs. er lik:

Permutasjoner av n elementer

Definisjon 3. Permutasjon fra n elementer kalles enhver bestilt sett disse elementene.

Eksempel 7a. Alle mulige permutasjoner av et sett som består av tre elementer (1, 2, 3) er: (1, 2, 3), (1, 3, 2), (2, 3, 1), (2, 1, 3) , (3, 2, 1), (3, 1, 2).

Antall forskjellige permutasjoner av n elementer er betegnet med P n og beregnes med formelen P n =n!.

Eksempel 8 På hvor mange måter kan syv bøker av forskjellige forfattere ordnes etter hverandre på en hylle?

Beslutning: dette problemet handler om antall permutasjoner av syv forskjellige bøker. Det er P 7 =7!=1*2*3*4*5*6*7=5040 måter å ordne bøkene på.

Diskusjon. Vi ser at antall mulige kombinasjoner kan beregnes i henhold til ulike regler (permutasjoner, kombinasjoner, plasseringer), og resultatet vil bli annerledes, fordi prinsippet om telling og selve formlene er forskjellige. Ser man nøye på definisjonene kan man se at resultatet avhenger av flere faktorer samtidig.

For det første, fra hvor mange elementer vi kan kombinere settene deres (hvor stor er den generelle populasjonen av elementer).

For det andre avhenger resultatet av hvilken størrelse sett med elementer vi trenger.

Til slutt er det viktig å vite om rekkefølgen av elementene i settet har betydning for oss. La oss forklare den siste faktoren med følgende eksempel.

Eksempel 9 Det er 20 personer på foreldremøtet. Hvor mange ulike alternativer for sammensetningen av foreldreutvalget er det dersom det skal omfatte 5 personer?
Beslutning: I dette eksempelet er vi ikke interessert i rekkefølgen på navnene på komitélisten. Hvis som et resultat de samme menneskene vises i sammensetningen, er dette det samme alternativet når det gjelder mening for oss. Derfor kan vi bruke formelen til å beregne tallet kombinasjoner av 20 elementer, 5.

Ting vil være annerledes hvis hvert medlem av komiteen i utgangspunktet er ansvarlig for et bestemt arbeidsområde. Da, med samme lønnsliste til komiteen, er 5 mulige inne i den! alternativer kombinasjonsmuligheter den saken. Antall forskjellige (både når det gjelder sammensetning og ansvarsområde) alternativer bestemmes i dette tilfellet av antallet plasseringer av 20 elementer, 5.

Oppgaver for selvtest
1. Hvor mange tresifrede partall kan lages av tallene 0, 1, 2, 3, 4, 5, 6 hvis tallene kan gjentas?

2. Hvor mange femsifrede tall er det som leses på samme måte fra venstre til høyre og fra høyre til venstre?

3. Det er ti fag i klassen og fem leksjoner om dagen. På hvor mange måter kan du lage en tidsplan for én dag?

4. På hvor mange måter kan 4 delegater velges til konferansen hvis det er 20 personer i gruppen?

5. På hvor mange måter kan åtte forskjellige bokstaver legges i åtte forskjellige konvolutter hvis bare én bokstav legges i hver konvolutt?

6. Fra tre matematikere og ti økonomer er det nødvendig å lage en kommisjon bestående av to matematikere og seks økonomer. På hvor mange måter kan dette gjøres?

Det skal bemerkes at kombinatorikk er en uavhengig del av høyere matematikk (og ikke en del av terver), og det er skrevet tunge lærebøker i denne disiplinen, hvis innhold til tider ikke er enklere enn abstrakt algebra. En liten del av teoretisk kunnskap vil imidlertid være nok for oss, og i denne artikkelen vil jeg prøve å analysere det grunnleggende i emnet med typiske kombinatoriske problemer i en tilgjengelig form. Og mange av dere vil hjelpe meg ;-)

Hva skal vi gjøre? I en snever forstand er kombinatorikk beregningen av forskjellige kombinasjoner som kan lages fra et bestemt sett diskret gjenstander. Objekter forstås som alle isolerte gjenstander eller levende vesener - mennesker, dyr, sopp, planter, insekter, etc. Samtidig bryr kombinatorikk seg ikke i det hele tatt om at settet består av en tallerken med semulegryn, et loddebolt og en myrfrosk. Det er grunnleggende viktig at disse gjenstandene er tallrike - det er tre av dem. (diskrethet) og det er viktig at ingen av dem er like.

Med mye ordnet, nå om kombinasjonene. De vanligste typene kombinasjoner er permutasjoner av objekter, deres valg fra et sett (kombinasjon) og distribusjon (plassering). La oss se hvordan dette skjer akkurat nå:

Permutasjoner, kombinasjoner og plasseringer uten repetisjon

Ikke vær redd for obskure termer, spesielt siden noen av dem egentlig ikke er særlig vellykkede. La oss starte med halen av tittelen - hva gjør " uten repetisjon"? Dette betyr at vi i denne delen vil vurdere sett som består av diverse gjenstander. For eksempel ... nei, jeg byr ikke på grøt med loddebolt og frosk, noe bedre er bedre =) Tenk deg at et eple, en pære og en banan materialiserte seg på bordet foran deg (hvis det er enhver, situasjonen kan simuleres i virkeligheten). Vi legger ut fruktene fra venstre til høyre i følgende rekkefølge:

eple / pære / banan

Spørsmål en: På hvor mange måter kan de omorganiseres?

En kombinasjon er allerede skrevet ovenfor, og det er ingen problemer med resten:

eple / banan / pære
pære / eple / banan
pære / banan / eple
banan / eple / pære
banan / pære / eple

Total: 6 kombinasjoner eller 6 kombinasjonsmuligheter.

Vel, det var ikke vanskelig å liste opp alle mulige tilfeller her, men hva om det er flere elementer? Allerede med fire forskjellige frukter vil antallet kombinasjoner øke betraktelig!

Vennligst åpne referansemateriale (Manualen er enkel å skrive ut) og i avsnitt nummer 2 finner du formelen for antall permutasjoner.

Ingen pine - 3 gjenstander kan omorganiseres på måter.

Spørsmål to: På hvor mange måter kan du velge a) én frukt, b) to frukter, c) tre frukter, d) minst én frukt?

Hvorfor velge? Så de fikk opp en appetitt i forrige avsnitt - for å spise! =)

a) Én frukt kan selvsagt velges på tre måter - ta enten et eple eller en pære, eller en banan. Den formelle opptellingen er basert på formel for antall kombinasjoner:

Oppføringen i dette tilfellet skal forstås som følger: "på hvor mange måter kan du velge 1 frukt av tre?"

b) Vi lister opp alle mulige kombinasjoner av to frukter:

eple og pære;
eple og banan;
pære og banan.

Antall kombinasjoner er lett å kontrollere ved å bruke samme formel:

Oppføringen forstås på samme måte: "på hvor mange måter kan du velge 2 frukter av tre?".

c) Og til slutt kan tre frukter velges på en unik måte:

Forresten, formelen for antall kombinasjoner gir også mening for en tom prøve:
På denne måten kan du velge ikke en eneste frukt - faktisk ta ingenting og det er det.

d) På hvor mange måter kan du ta minst en frukt? Betingelsen "minst én" innebærer at vi er fornøyd med 1 frukt (hvilken som helst) eller 2 frukter eller alle 3 fruktene:
måter du kan velge minst én frukt på.

Lesere som nøye har studert den innledende leksjonen på sannsynlighetsteori har allerede funnet ut av noe. Men om betydningen av plusstegnet senere.

For å svare på det neste spørsmålet trenger jeg to frivillige ... ... Vel, siden ingen vil, så ringer jeg til styret =)

Spørsmål tre: På hvor mange måter kan én frukt distribueres til Dasha og Natasha?

For å distribuere to frukter, må du først velge dem. I henhold til avsnittet "be" i forrige spørsmål, kan dette gjøres på måter, jeg vil skrive dem om igjen:

eple og pære;
eple og banan;
pære og banan.

Men nå blir det dobbelt så mange kombinasjoner. Tenk for eksempel på det første paret frukt:
du kan behandle Dasha med et eple, og Natasha med en pære;
eller omvendt - Dasha vil få pæren, og Natasha vil få eplet.

Og en slik permutasjon er mulig for hvert par frukt.

Tenk på den samme studentgruppen som gikk på dansen. På hvor mange måter kan en gutt og en jente kobles sammen?

Måter du kan velge 1 ung mann på;
måter du kan velge 1 jente på.

Altså en ung mann ogén jente kan velges: måter.

Når 1 objekt er valgt fra hvert sett, er følgende prinsipp for tellekombinasjoner gyldig: " Hver et objekt fra ett sett kan danne et par med hver gjenstand for et annet sett.

Det vil si at Oleg kan invitere hvilken som helst av de 13 jentene til dans, Evgeny - også hvilken som helst av de tretten, og andre unge mennesker har et lignende valg. Totalt: mulige par.

Det skal bemerkes at i dette eksemplet spiller "historien" til pardannelse ingen rolle; men hvis initiativ tas i betraktning, må antall kombinasjoner dobles, siden hver av de 13 jentene også kan invitere hvilken som helst gutt til dans. Alt avhenger av betingelsene for en bestemt oppgave!

Et lignende prinsipp er gyldig for mer komplekse kombinasjoner, for eksempel: på hvor mange måter kan to unge menn velges og to jenter til å delta i et KVN-spill?

Union Og antyder entydig at kombinasjonene må multipliseres:

Mulige kunstnergrupper.

Med andre ord, Hver guttepar (45 unike par) kan konkurrere med noen et par jenter (78 unike par). Og vurderer vi rollefordelingen mellom deltakerne, så blir det enda flere kombinasjoner. ... Jeg har veldig lyst, men likevel vil jeg la være å fortsette, for ikke å innpode deg en aversjon mot studentlivet =).

Multiplikasjonsregelen gjelder for flere multiplikatorer:

Oppgave 8

Hvor mange tresifrede tall er det som er delbare med 5?

Beslutning: for klarhetens skyld betegner vi dette tallet med tre stjerner: ***

PÅ hundrevis plass du kan skrive hvilket som helst av tallene (1, 2, 3, 4, 5, 6, 7, 8 eller 9). Null er ikke bra, for i dette tilfellet slutter tallet å være tresifret.

Men i titalls plass("i midten") kan du velge hvilket som helst av de 10 sifrene: .

Etter betingelse må tallet være delelig med 5. Tallet er delelig med 5 hvis det ender på 5 eller 0. I det minst signifikante sifferet er vi altså fornøyd med 2 siffer.

Totalt, det er: tresifrede tall som er delbare med 5.

Samtidig er verket dechiffrert slik: «9 måter du kan velge et tall på hundrevis plass og 10 måter å velge et nummer på titalls plass og 2 veier inn enhetssiffer»

Eller enda enklere: Hver fra 9 sifre til hundrevis plass kombinert med hver på 10 sifre titalls plass og med hver av to sifre enheter siffer».

Svar: 180

Og nå…

Ja, jeg glemte nesten den lovede kommentaren til problem nr. 5, der Borya, Dima og Volodya kan få ett kort hver på forskjellige måter. Multiplikasjon her har samme betydning: på en måte kan du trekke ut 3 kort fra bunken Og i hver prøve for å omorganisere dem.

Og nå oppgaven for en uavhengig løsning ... nå skal jeg komme opp med noe mer interessant, ... la det handle om den samme russiske versjonen av blackjack:

Oppgave 9

Hvor mange vinnende kombinasjoner av 2 kort er det i et "poeng"-spill?

For de som ikke vet: vinner kombinasjon 10 + ESS (11 poeng) = 21 poeng, og la oss vurdere vinnerkombinasjonen av to ess.

(rekkefølgen på kortene i et par spiller ingen rolle)

Kort løsning og svar på slutten av timen.

Forresten, det er ikke nødvendig å vurdere et eksempel primitivt. Blackjack er nesten det eneste spillet det finnes en matematisk begrunnet algoritme for som lar deg slå kasinoet. De som ønsker det kan enkelt finne mye informasjon om den optimale strategien og taktikken. Riktignok faller slike mestere raskt inn på svartelisten over alle virksomheter =)

Det er på tide å konsolidere materialet dekket med et par solide oppgaver:

Oppgave 10

Vasya har 4 katter hjemme.

a) På hvor mange måter kan kattene sitte i hjørnene av rommet?
b) På hvor mange måter kan katter få lov til å streife rundt?
c) på hvor mange måter kan Vasya plukke opp to katter (en til venstre, den andre til høyre)?

Vi bestemmer: For det første bør det igjen bemerkes at problemet handler om annerledes gjenstander (selv om kattene er eneggede tvillinger). Dette er en veldig viktig betingelse!

a) Stillhet av katter. Denne utførelsen er underlagt alle katter på en gang
+ deres plassering er viktig, så det er permutasjoner her:
måter du kan plassere katter i hjørnene av rommet.

Jeg gjentar at ved permutering er det bare antall forskjellige objekter og deres relative plassering som betyr noe. Avhengig av humøret hans, kan Vasya sette dyrene i en halvsirkel på sofaen, på rad i vinduskarmen, etc. - det vil være 24 permutasjoner i alle tilfeller.For enkelhets skyld kan de som ønsker det tenke seg at kattene er flerfargede (for eksempel hvite, svarte, røde og stripete) og liste opp alle mulige kombinasjoner.

b) På hvor mange måter kan katter få lov til å streife rundt?

Det antas at katter går tur bare gjennom døren, mens spørsmålet innebærer likegyldighet om antall dyr - 1, 2, 3 eller alle 4 kattene kan gå på tur.

Vi vurderer alle mulige kombinasjoner:

Måter du kan gi slipp på en tur med én katt (hvilken som helst av de fire);
måter du kan la to katter gå på tur (liste opp alternativene selv);
måter du kan la tre katter gå på tur (en av de fire sitter hjemme);
måten du kan slippe alle kattene.

Du har sannsynligvis gjettet at de oppnådde verdiene burde oppsummeres:
måter å la katter gå på tur.

For entusiaster tilbyr jeg en komplisert versjon av problemet - når en hvilken som helst katt i en prøve kan gå tilfeldig ut, både gjennom døren og gjennom vinduet i 10. etasje. Det blir flere kombinasjoner!

c) På hvor mange måter kan Vasya plukke opp to katter?

Situasjonen involverer ikke bare valget av 2 dyr, men også deres plassering på hendene:
måter du kan plukke opp 2 katter på.

Den andre løsningen: på måter kan du velge to katter og måter å plante på hver et par i hånden:

Svar: a) 24, b) 15, c) 12

Vel, for å rense samvittigheten min, noe mer spesifikt om multiplikasjon av kombinasjoner .... La Vasya få 5 ekstra katter =) Hvor mange måter kan du la 2 katter gå på tur og 1 katt?

Det vil si med Hver et par katter kan slippes løs hver katt.

Et annet knappetrekkspill for en uavhengig avgjørelse:

Oppgave 11

3 passasjerer gikk inn i heisen til en 12-etasjers bygning. Alle, uavhengig av de andre, kan gå ut i hvilken som helst (fra 2.) etasje med samme sannsynlighet. På hvor mange måter:

1) Passasjerer kan gå av i samme etasje (utgangsrekkefølge spiller ingen rolle);
2) to personer kan gå av i en etasje og en tredje i en annen;
3) folk kan gå av i forskjellige etasjer;
4) Kan passasjerer gå ut av heisen?

Og her spør de ofte igjen, jeg presiserer: hvis 2 eller 3 personer går ut i samme etasje, så spiller ikke rekkefølgen på utgang noen rolle. TENK, bruk formler og regler for addisjons-/multiplikasjonskombinasjoner. Ved vanskeligheter er det nyttig for passasjerene å oppgi navn og begrunnelse i hvilke kombinasjoner de kan komme seg ut av heisen. Det er ingen grunn til å bli lei seg hvis noe ikke fungerer, for eksempel er punkt nummer 2 ganske lumsk.

Komplett løsning med detaljerte kommentarer på slutten av opplæringen.

Det siste avsnittet er viet kombinasjoner som også forekommer ganske ofte - etter min subjektive vurdering, i omtrent 20-30 % av kombinatoriske problemer:

Permutasjoner, kombinasjoner og plasseringer med repetisjoner

De listede kombinasjonstypene er skissert i avsnitt nr. 5 i referansematerialet Grunnleggende formler for kombinatorikk, men noen av dem er kanskje ikke veldig klare ved første lesing. I dette tilfellet er det tilrådelig å først gjøre deg kjent med praktiske eksempler, og først deretter forstå den generelle formuleringen. Gå:

Permutasjoner med repetisjoner

I permutasjoner med repetisjoner, som i "vanlige" permutasjoner, hele settet med objekter på en gang, men det er én ting: i dette settet gjentas ett eller flere elementer (objekter). Møt neste standard:

Oppgave 12

Hvor mange forskjellige bokstavkombinasjoner kan fås ved å omorganisere kort med følgende bokstaver: K, O, L, O, K, O, L, L, H, I, K?

Beslutning: i tilfelle alle bokstaver var forskjellige, bør en triviell formel brukes, men det er ganske klart at for det foreslåtte settet med kort vil noen manipulasjoner fungere "tomgang", så for eksempel hvis du bytter to kort med bokstavene "K i et hvilket som helst ord, det vil være det samme ordet. Dessuten kan kortene fysisk være veldig forskjellige: det ene kan være rundt med en trykt bokstav "K", det andre er firkantet med en tegnet bokstav "K". Men i henhold til meningen med problemet, selv slike kort betraktet som det samme, siden betingelsen spør om bokstavkombinasjoner.

Alt er ekstremt enkelt - totalt: 11 kort, inkludert bokstaven:

K - gjentas 3 ganger;
O - gjentas 3 ganger;
L - gjentas 2 ganger;
b - gjentas 1 gang;
H - gjentas 1 gang;
Og - gjentas 1 gang.

Sjekk: 3 + 3 + 2 + 1 + 1 + 1 = 11, som er det vi ønsket å sjekke.

I henhold til formelen antall permutasjoner med repetisjoner:
ulike bokstavkombinasjoner kan fås. Mer enn en halv million!

For en rask beregning av en stor faktorverdi er det praktisk å bruke standard Excel-funksjonen: vi scorer i hvilken som helst celle =FAKTA(11) og klikk Tast inn.

I praksis er det ganske akseptabelt å ikke skrive ned den generelle formelen og i tillegg utelate enhetsfaktorene:

Men det kreves foreløpige kommentarer om gjentatte brev!

Svar: 554400

Et annet typisk eksempel på permutasjoner med repetisjoner finnes i problemet med å arrangere sjakkbrikker, som finnes på lageret ferdige løsninger i tilsvarende pdf. Og for en uavhengig løsning kom jeg på en mindre maloppgave:

Oppgave 13

Alexey går inn for sport, og 4 dager i uken - friidrett, 2 dager - styrkeøvelser og 1 hviledag. På hvor mange måter kan han planlegge sine ukentlige klasser?

Formelen fungerer ikke her fordi den tar hensyn til overlappende permutasjoner (for eksempel når styrkeøvelser på onsdag byttes ut med styrkeøvelser på torsdag). Og igjen - faktisk kan de samme 2 styrketreningsøktene være svært forskjellige fra hverandre, men i sammenheng med oppgaven (i form av tidsplanen), regnes de som de samme elementene.

To-linjers løsning og svar på slutten av timen.

Kombinasjoner med repetisjoner

Et karakteristisk trekk ved denne typen kombinasjon er at prøven er trukket fra flere grupper, som hver består av de samme objektene.

Alle har jobbet hardt i dag, så det er på tide å friske opp deg selv:

Oppgave 14

Studentkafeteriaen selger pølser i deig, ostekaker og smultringer. På hvor mange måter kan fem kaker kjøpes?

Beslutning: Vær umiddelbart oppmerksom på det typiske kriteriet for kombinasjoner med repetisjoner - i henhold til tilstanden, ikke et sett med objekter som sådan, men forskjellige typer gjenstander; det antas at det er minst fem pølser, 5 ostekaker og 5 smultringer på salg. Paiene i hver gruppe er selvfølgelig forskjellige - fordi helt identiske smultringer bare kan simuleres på en datamaskin =) De fysiske egenskapene til paiene er imidlertid ikke essensielle i forhold til problemet, og pølser / ostekaker / smultringer i deres grupper anses de samme.

Hva kan være i prøven? Først av alt bør det bemerkes at det definitivt vil være identiske paier i prøven (fordi vi velger 5 stykker, og 3 typer tilbys å velge mellom). Alternativer her for enhver smak: 5 pølser, 5 ostekaker, 5 smultringer, 3 pølser + 2 ostekaker, 1 pølser + 2 + ostekaker + 2 smultringer, etc.

Som med "vanlige" kombinasjoner, spiller rekkefølgen på utvalg og plassering av paier i prøven ingen rolle - de valgte bare 5 stykker og det er det.

Vi bruker formelen antall kombinasjoner med repetisjoner:
måte du kan kjøpe 5 paier.

God appetitt!

Svar: 21

Hvilken konklusjon kan trekkes fra mange kombinatoriske problemer?

Noen ganger er det vanskeligste å forstå tilstanden.

Et lignende eksempel for en gjør-det-selv-løsning:

Oppgave 15

Lommeboken inneholder et ganske stort antall 1-, 2-, 5- og 10-rubelmynter. På hvor mange måter kan tre mynter tas ut av lommeboken?

For selvkontrollformål, svar på et par enkle spørsmål:

1) Kan alle mynter i prøven være forskjellige?
2) Nevn den "billigste" og den "dyreste" kombinasjonen av mynter.

Løsning og svar på slutten av timen.

Fra min personlige erfaring kan jeg si at kombinasjoner med repetisjoner er den sjeldneste gjesten i praksis, noe som ikke kan sies om følgende type kombinasjoner:

Plasseringer med repetisjoner

Fra et sett bestående av elementer velges elementer, og rekkefølgen på elementene i hver prøve er viktig. Og alt ville vært bra, men en ganske uventet vits er at vi kan velge hvilket som helst objekt i originalsettet så mange ganger vi vil. Billedlig talt, fra "mengden vil ikke avta."

Når skjer det? Et typisk eksempel er en kombinasjonslås med flere disker, men på grunn av teknologiutviklingen er det mer relevant å vurdere dens digitale etterkommer:

Oppgave 16

Hvor mange 4-sifrede pinkoder er det?

Beslutning: faktisk, for å løse problemet, er det nok å kjenne reglene for kombinatorikk: du kan velge det første sifferet i pinkoden på måter og måter - det andre sifferet i pinkoden og på like mange måter - en tredjedel og like mange - den fjerde. I henhold til regelen om multiplikasjon av kombinasjoner, kan en firesifret pinkode være sammensatt: på måter.

Og nå med formelen. Av vilkår tilbys vi et sett med tall, hvorfra tall velges og plasseres i en bestemt rekkefølge, mens tallene i prøven kan gjentas (dvs. ethvert siffer i originalsettet kan brukes et vilkårlig antall ganger). I henhold til formelen for antall plasseringer med repetisjoner:

Svar: 10000

Hva kommer til tankene her ... ... hvis minibanken "spiser" kortet etter det tredje mislykkede forsøket på å taste inn pinkoden, så er sjansene for å plukke det opp tilfeldig veldig illusoriske.

Og hvem sa at det ikke er noen praktisk mening i kombinatorikk? En kognitiv oppgave for alle lesere av nettstedet:

Oppgave 17

I henhold til statens standard består et bilskilt av 3 tall og 3 bokstaver. I dette tilfellet er et tall med tre nuller ikke tillatt, og bokstavene er valgt fra settet A, B, E, K, M, H, O, R, C, T, U, X (bare de kyrilliske bokstavene brukes, hvor stavemåten samsvarer med de latinske bokstavene).

Hvor mange forskjellige bilskilt kan det lages for en region?

Ikke så, forresten, og mye. I store regioner er ikke dette tallet nok, og derfor er det flere koder for inskripsjonen RUS for dem.

Løsning og svar på slutten av leksjonen. Ikke glem å bruke kombinatorikkens regler ;-) …Jeg ville skryte av å være eksklusiv, men det viste seg å ikke være eksklusivt =) Jeg så på Wikipedia - det er beregninger, men uten kommentarer. Selv om det sannsynligvis var for pedagogiske formål, var det få som løste det.

Vår spennende leksjon har nådd slutten, og til slutt vil jeg si at du ikke kastet bort tiden din - av den grunn at kombinatorikkformlene finner en annen viktig praktisk anvendelse: de finnes i forskjellige oppgaver på sannsynlighetsteori,
og i oppgaver om den klassiske definisjonen av sannsynlighet- spesielt ofte

Takk alle sammen for deres aktive deltakelse og ses snart!

Løsninger og svar:

Oppgave 2: Beslutning: finn antall mulige permutasjoner av 4 kort:

Når et kort med null er på 1. plass, blir tallet tresifret, så disse kombinasjonene bør utelukkes. La null være på 1. plass, så kan de resterende 3 sifrene i de minst signifikante sifrene omorganiseres på måter.

Merk : fordi det er få kort, det er enkelt å liste opp alle slike alternativer her:
0579
0597
0759
0795
0957
0975

Derfor, fra det foreslåtte settet, kan du lage:
24 - 6 = 18 firesifrede tall
Svar : 18

Oppgave 4: Beslutning: 3 kort kan velges fra 36 måter.
Svar : 7140

Oppgave 6: Beslutning: måter.
En annen løsning : måter du kan velge to personer fra gruppen og og
2) Det "billigste" settet inneholder 3 rubelmynter, og det "dyreste" settet inneholder 3 ti-rubelmynter.

Oppgave 17: Beslutning: måter du kan lage en digital kombinasjon av et nummerskilt på, mens en av dem (000) bør utelukkes:.
måter du kan lage en bokstavkombinasjon av et bilnummer på.
I henhold til regelen om multiplikasjon av kombinasjoner kan alt være sammensatt:
bilnummer
(Hver digital kombinasjon kombinert med hver bokstavkombinasjon).
Svar : 1726272

For å gjøre det lettere å navigere i materialet, vil jeg legge til innholdet i dette emnet:

Introduksjon. Sett og utvalg.

I dette emnet vil vi vurdere de grunnleggende konseptene for kombinatorikk: permutasjoner, kombinasjoner og plasseringer. La oss finne ut deres essens og formler som du kan finne nummeret deres.

For å komme i gang trenger vi litt bakgrunnsinformasjon. La oss starte med et så grunnleggende matematisk konsept som et sett. Konseptet med et sett ble beskrevet i detalj i emnet "Konseptet til et sett. Metoder for å spesifisere sett" .

En veldig kort historie om mengden: Vis skjul

Kort sagt, et sett er en samling av gjenstander. Sett er skrevet i krøllete parenteser. Rekkefølgen elementene er skrevet i spiller ingen rolle; repetisjon av elementer er ikke tillatt. For eksempel vil settet med sifre for nummeret 11115555999 være: $$1,5,9 $$. Settet med konsonantbokstaver i ordet "tigerunge" er som følger: $$t, r, r, n, k$$. Notasjonen $5\i A$ betyr at element 5 tilhører settet $A=$1,5,9 $$. Antall elementer i en begrenset mengde kalles makt av dette settet og er merket med $|A|$. For eksempel, for et sett $A=$1,5,9 $$ som inneholder 3 elementer, har vi: $|A|=3$.

La oss se på et ikke-tomt begrenset sett $U$, hvis kardinalitet er lik $n$, $|U|=n$ (det vil si at settet $U$ har $n$-elementer). La oss introdusere et slikt konsept som prøve(noen forfattere kaller det en tuppel). Med et utvalg av størrelsen $k$ av $n$-elementer (forkortet $(n,k)$-selection) mener vi et sett med elementer $(a_1, a_2,\ldots, a_k)$, der $a_i\in U$. Et utvalg sies å være ordnet hvis rekkefølgen på elementene er spesifisert i det. To ordnede prøver som bare er forskjellige i rekkefølgen på elementene er forskjellige. Hvis rekkefølgen på elementene i prøven ikke er signifikant, kalles prøven uordnet.

Legg merke til at utvalgsdefinisjonen ikke sier noe om gjentagelser av gjenstander. I motsetning til settelementer kan utvalgselementer gjentas.

Tenk for eksempel på settet $U=$a,b,c,d,e$$. Settet $U$ inneholder 5 elementer, dvs. $|U|=5$. En prøve uten repetisjoner kan være: $(a,b,c)$. Denne prøven inneholder 3 elementer, dvs. størrelsen på denne prøven er 3. Dette er med andre ord en $(5,3)$-prøve.

En prøve med repetisjoner kan være: $(a,a,a,a,a,c,c,d)$. Den inneholder 8 elementer, dvs. volumet er 8. Dette er med andre ord en $(5,8)$-prøve.

Tenk på ytterligere to $(5,3)$-prøver: $(a,b,b)$ og $(b,a,b)$. Hvis vi antar at prøvene våre er uordnet, så er prøven $(a,b,b)$ lik prøven $(b,a,b)$, dvs. $(a,b,b)=(b,a,b)$. Hvis vi antar at prøvene våre er bestilt, vil $(a,b,b)\neq(b,a,b)$.

La oss se på et annet eksempel, litt mindre abstrakt :) Tenk deg at det er seks godteri i en kurv, og alle er forskjellige. Hvis det første godteriet er tildelt nummer 1, det andre godteriet er nummer 2, og så videre, kan følgende sett assosieres med godteriet i kurven: $U=$1,2,3,4,5 ,6$$. Tenk deg at vi tilfeldig legger hånden ned i kurven for å trekke ut tre søtsaker. De uttrukket søtsaker - dette er prøven. Siden vi trekker ut 3 godterier fra 6, får vi en (6,3)-prøve. Rekkefølgen som godteriene er plassert i håndflaten er helt irrelevant, så denne prøven er uordnet. Vel, og siden alle godterier er forskjellige, er prøven uten repetisjon. Så i denne situasjonen snakker vi om et uordnet (6,3)-utvalg uten repetisjoner.

La oss nå gå fra den andre siden. La oss tenke oss at vi er i en godterifabrikk, og denne fabrikken produserer fire typer godteri. Settet $U$ i denne situasjonen er som følger: $U=$1,2,3,4 $$ (hvert siffer er ansvarlig for sin egen type godteri). Tenk deg nå at alle søtsakene helles i en enkelt renne, i nærheten av som vi står. Og i stedet for håndflatene velger vi 20 søtsaker fra denne strømmen. Godteri i en håndfull - dette er prøven. Spiller rekkefølgen på godteriene i håndfullen en rolle? Naturligvis nei, så prøven er uordnet. Det er bare 4 varianter av søtsaker, og vi velger tjue stykker fra den generelle flyten - repetisjoner av varianter er uunngåelige. Samtidig kan prøvene være svært forskjellige: Vi kan til og med ha alle godterier av samme sort. Følgelig har vi i denne situasjonen å gjøre med et uordnet (4.20)-utvalg med repetisjoner.

La oss se på et par flere eksempler. La forskjellige 7 bokstaver skrives på kubene: k, o, n, f, e, t, a. Disse bokstavene danner settet $U=$k,o,n,f,e,t,a$$. Anta at vi vil lage "ord" av 5 bokstaver fra disse kubene. Bokstavene i disse ordene (for eksempel "confé", "tenko" og så videre) danner (7,5)-valg: $(k,o,n,f,e)$, $(t,e,n ,k ,o)$ osv. Det er klart at rekkefølgen på bokstavene i en slik prøve er viktig. For eksempel er ordene "nokft" og "kfton" forskjellige (selv om de består av de samme bokstavene), fordi de ikke har samme rekkefølge av bokstaver. Det er ingen repetisjoner av bokstaver i slike "ord", fordi det bare er syv kuber. Så sett med bokstaver for hvert ord er en ordnet (7,5)-prøve uten repetisjoner.

Et annet eksempel: vi lager alle slags åttesifrede tall fra fire sifre 1, 5, 7, 8. For eksempel 11111111, 15518877, 88881111 og så videre. Settet $U$ er som følger: $U=$1,5,7,8$$. Sifrene til hvert kompilerte nummer danner en (4,8)-prøve. Rekkefølgen på sifrene i et tall er viktig, dvs. prøven er bestilt. Repetisjoner er tillatt, så her har vi å gjøre med et ordnet (4,8)-utvalg med repetisjoner.

Tildelinger uten repetisjoner av $n$ elementer med $k$

Tildeling uten repetisjoner av $n$ elementer etter $k$ - bestilt $(n,k)$-utvalg uten repetisjoner.

Siden elementene i prøven som vurderes ikke kan gjentas, kan vi ikke velge flere elementer i prøven enn det er i originalsettet. Derfor, for slike prøver, er følgende ulikhet sann: $n≥ k$. Antall plasseringer uten repetisjoner av $n$-elementer med $k$ bestemmes av følgende formel:

\begin(ligning)A_(n)^(k)=\frac(n{(n-k)!} \end{equation} !}

Hva betyr tegnet "!": Vis skjul

Opptak av "n!" (les "en factorial") betegner produktet av alle tall fra 1 til n, dvs.

$$ n!=1\cdot2\cdot 3\cdot \ldots\cdot n $$

Per definisjon antas det at $0!=1!=1$. La oss for eksempel finne 5!:

$$ 5!=1\cdot 2\cdot 3\cdot 4\cdot 5=120. $$

Eksempel #1

Alfabetet består av et sett med tegn $E=$+,*,0,1,f$$. La oss bestemme antallet slike tretegnsord i dette alfabetet som ikke inneholder gjentatte bokstaver.

Med ord på tre tegn mener vi uttrykk som "+*0" eller "0f1". Settet $E$ har fem elementer, så bokstavene i tretegnsordene danner (5,3)-utvalg. Det første spørsmålet er: er disse prøvene bestilt eller ikke? Ord som bare avviker i rekkefølgen på bokstavene, antas å være forskjellige, så rekkefølgen på elementene i prøven er viktig. Så prøven er bestilt. Det andre spørsmålet: er repetisjoner tillatt eller ikke? Svaret på dette spørsmålet er gitt av betingelsen: ord skal ikke inneholde gjentatte bokstaver. Oppsummering: Bokstavene i hvert ord som tilfredsstiller problemets tilstand danner en ordnet (5,3)-prøve uten repetisjoner. Med andre ord danner bokstavene i hvert ord et arrangement uten repetisjoner av 5 elementer av 3. Her er eksempler på slike arrangementer:

$$ (+,*,f), \; (*,+,f), \; (1,+,0) $$

Vi er også interessert i det totale antallet av disse plasseringene. I henhold til formel (1) vil antall plasseringer uten repetisjoner av 5 elementer med 3 være som følger:

$$ A_(5)^(3)=\frac(5{(5-3)!}=\frac{5!}{2!}=60. $$ !}

De. du kan lage 60 ord med tre tegn, hvor bokstavene ikke vil bli gjentatt.

Svar: 60.

Allokeringer med repetisjoner av $n$ elementer med $k$

Plassering med repetisjoner av $n$ elementer over $k$ er et ordnet $(n,k)$-utvalg med repetisjoner.

Antall plasseringer med repetisjoner av $n$-elementer med $k$ bestemmes av følgende formel:

\begin(ligning)\bar(A)_(n)^(k)=n^k \end(ligning)

Eksempel #2

Hvor mange femsifrede tall kan dannes fra settet med sifre $$5,7,2$$?

Fra dette settet med tall kan du lage femsifrede tall 55555, 75222 og så videre. Sifrene til hvert slikt tall danner en (3,5)-prøve: $(5,5,5,5,5)$, $(7,5,2,2,2)$. La oss spørre oss selv: hva er disse prøvene? For det første kan sifre i tall gjentas, så vi har å gjøre med prøver med repetisjoner. For det andre er rekkefølgen av tallene i tallet viktig. For eksempel er 27755 og 77255 forskjellige tall. Derfor har vi å gjøre med ordnede (3,5)-utvalg med repetisjoner. Det totale antallet slike prøver (dvs. det totale antallet nødvendige femsifrede tall) kan bli funnet ved å bruke formel (2):

$$ \bar(A)_(3)^(5)=3^5=243. $$

Derfor, fra de gitte sifrene, kan 243 femsifrede tall lages.

Svar: 243.

Permutasjoner uten repetisjoner av $n$-elementer

En permutasjon uten repetisjoner av $n$-elementer er et ordnet $(n,n)$-utvalg uten repetisjoner.

Faktisk er permutasjon uten repetisjon et spesielt tilfelle av plassering uten repetisjon, når prøvestørrelsen er lik kraften til det originale settet. Antall permutasjoner uten repetisjoner av $n$ elementer bestemmes av følgende formel:

\begin(ligning)P_(n)=n! \end(ligning)

Denne formelen er forresten enkel å få til hvis vi tar i betraktning at $P_n=A_(n)^(n)$. Da får vi:

$$ P_n=A_(n)^(n)=\frac(n{(n-n)!}=\frac{n!}{0!}=\frac{n!}{1}=n! $$ !}

Eksempel #3

Fryseren inneholder fem porsjoner iskrem fra ulike selskaper. På hvor mange måter kan du velge rekkefølgen de skal spises i?

La tallet 1 tilsvare den første isen, tallet 2 til den andre, og så videre. Vi vil få et sett $U=$1,2,3,4,5$$ som vil representere innholdet i fryseren. Matrekkefølgen kan være $(2,1,3,5,4)$ eller $(5,4,3,1,2)$. Hver slik samling er en (5,5)-prøve. Det vil være ryddig og uten gjentakelser. Med andre ord er hver slik prøve en permutasjon av 5 elementer av det originale settet. I henhold til formel (3) er det totale antallet av disse permutasjonene:

$$ P_5=5!=120. $$

Derfor er det 120 bestillinger av spiserekkefølge.

Svar: 120.

Permutasjoner med repetisjoner

En permutasjon med repetisjoner er et ordnet $(n,k)$-utvalg med repetisjoner der elementet $a_1$ gjentas $k_1$ ganger, $a_2$ gjentas $k_2$ ganger, og så videre, til det siste elementet $a_r$, som gjentas $ k_r$ ganger. Dessuten, $k_1+k_2+\ldots+k_r=k$.

Det totale antallet permutasjoner med repetisjoner er gitt av:

\begin(ligning)P_(k)(k_1,k_2,\ldots,k_r)=\frac(k{k_1!\cdot k_2!\cdot \ldots \cdot k_r!} \end{equation} !}

Eksempel #4

Ord er dannet på grunnlag av alfabetet $U=$a,b,d$$. Hvor mange forskjellige ord på syv tegn kan settes sammen hvis bokstaven "a" må gjentas 2 ganger i disse ordene; bokstaven "b" - 1 gang, og bokstaven "d" - 4 ganger?

Her er eksempler på søkeord: "aabdddd", "daddabd" og så videre. Bokstavene i hvert ord danner et (3,7)-eksempel med repetisjoner: $(a,a,b,d,d,d,d)$, $(d,a,d,d,a,b,d )$ og etc. Hvert slikt utvalg består av to "a"-elementer, ett "b"-element og fire "d"-elementer. Med andre ord, $k_1=2$, $k_2=1$, $k_3=4$. Det totale antallet repetisjoner av alle tegn er selvfølgelig lik prøvestørrelsen, dvs. $k=k_1+k_2+k_3=7$. Ved å erstatte disse dataene i formel (4), vil vi ha:

$$ P_7(2,1,4)=\frac(7{2!\cdot 1!\cdot 4!}=105. $$ !}

Derfor er det totale antallet søkte ord 105.

Svar: 105.

Kombinasjoner uten repetisjoner av $n$ elementer med $k$

En kombinasjon uten repetisjoner av $n$ elementer med $k$ er et uordnet $(n,k)$-utvalg uten repetisjoner.

Det totale antallet kombinasjoner uten repetisjoner av $n$ elementer med $k$ bestemmes av formelen:

\begin(ligning)C_(n)^(k)=\frac(n{(n-k)!\cdot k!} \end{equation} !}

Eksempel #5

Kurven inneholder kort som det er skrevet heltall fra 1 til 10. 4 kort tas ut av kurven og tallene som er skrevet på dem summeres. Hvor mange forskjellige sett med kort kan trekkes fra kurven?

Så i denne oppgaven er startsettet som følger: $U=$1,2,3,4,5,6,7,8,9,10$$. Fra dette settet velger vi fire elementer (dvs. fire kort fra kurven). Tallene på de uttrukkete elementene danner en (10,4)-prøve. Gjentakelser i denne prøven er ikke tillatt, siden tallene på alle kortene er forskjellige. Spørsmålet er: betyr rekkefølgen kortene velges i eller ikke? Det vil si at for eksempel er prøvene $(1,2,7,10)$ og $(10,2,1,7)$ like eller ikke like? Her må du vende deg til tilstanden til problemet. Kort tas ut for å finne summen av elementene. Og dette betyr at rekkefølgen på kortene ikke er viktig, siden beløpet ikke endres fra å endre plassering av vilkårene. Eksempelet $(1,2,7,10)$ og prøven $(10,2,1,7)$ vil for eksempel samsvare med det samme tallet $1+2+7+10=10+2+1+7 = 20$. Konklusjon: det følger av problemets tilstand at vi har å gjøre med uordnede prøver. De. vi må finne det totale antallet uordnede (10,4)-prøver uten repetisjoner. Med andre ord må vi finne antall kombinasjoner av 10 elementer med 4. Vi bruker formel (5) for dette:

$$ C_(10)^(4)=\frac(10{(10-4)!\cdot 4!}=\frac{10!}{6!\cdot 4!}=210. $$ !}

Derfor er det totale antallet nødvendige sett 210.

Svar: 210.

Kombinasjoner med repetisjoner av $n$ elementer med $k$

En kombinasjon med repetisjoner av $n$ elementer over $k$ er et uordnet $(n,k)$-utvalg med repetisjoner.

Det totale antallet kombinasjoner med repetisjoner av $n$ elementer over $k$ bestemmes av formelen:

\begin(ligning)\bar(C)_(n)^(k)=\frac((n+k-1){(n-1)!\cdot k!} \end{equation} !}

Eksempel #6

Tenk deg at vi er på en godterifabrikk - rett ved siden av transportbåndet som fire typer godteri beveger seg langs. Vi legger hendene i denne bekken og trekker ut tjue av dem. Hvor mange forskjellige "godterikombinasjoner" kan det være i en håndfull?

Hvis vi antar at tallet 1 tilsvarer den første sorteringen, tallet 2 tilsvarer den andre sorteringen, og så videre, så er startsettet i oppgaven vår som følger: $U=\(1,2,3,4\ )$. Fra dette settet velger vi 20 elementer (dvs. de samme 20 godteriene fra transportøren). En håndfull søtsaker danner en (4,20)-prøve. Naturligvis vil det være repetisjoner av varianter. Spørsmålet er, spiller rekkefølgen på elementene i utvalget en rolle eller ikke? Det følger av betingelsene for problemet at rekkefølgen av elementene ikke spiller noen rolle. Det spiller ingen rolle for oss om håndfull inneholder 15 slikker først, og deretter 4 sjokolader, eller først 4 sjokolader, og først deretter 15 slikker. Så vi har å gjøre med en uordnet (4,20) prøve med repetisjoner. For å finne det totale antallet av disse prøvene bruker vi formel (6):

$$ \bar(C)_(4)^(20)=\frac((4+20-1){(4-1)!\cdot 20!}=\frac{23!}{3!\cdot 20!}=1771. $$ !}

Derfor er det totale antallet ønskede kombinasjoner 1771.

KOMBINATORIKK

Kombinatorikk er en gren av matematikk som studerer problemene med å velge og arrangere elementer fra noen grunnleggende sett i samsvar med gitte regler. Formler og prinsipper for kombinatorikk brukes i sannsynlighetsteori for å beregne sannsynligheten for tilfeldige hendelser og følgelig for å oppnå lovene for distribusjon av tilfeldige variabler. Dette gjør det igjen mulig å studere lovene til tilfeldige massefenomener, noe som er svært viktig for en korrekt forståelse av de statistiske lovene som manifesterer seg i naturen og teknologien.

Regler for addisjon og multiplikasjon i kombinatorikk

Sumregel. Hvis to handlinger A og B utelukker hverandre, og handling A kan utføres på m måter, og B på n måter, så kan en av disse handlingene (enten A eller B) utføres på n + m måter.

Eksempel 1

Det er 16 gutter og 10 jenter i klassen. På hvor mange måter kan en ledsager utnevnes?

Beslutning

Du kan tilsette enten en gutt eller en jente på vakt, dvs. hvilken som helst av de 16 guttene eller noen av de 10 jentene kan være på vakt.

I følge sumregelen får vi at én vaktleder kan tildeles 16+10=26 veier.

Produktregel. La det være nødvendig å utføre sekvensielle k handlinger. Hvis den første handlingen kan utføres på n 1 måter, den andre handlingen på n 2 måter, den tredje på n 3 måter, og så videre opp til den kth handlingen som kan utføres på n k måter, så kan alle k handlinger sammen være utført:

måter.

Eksempel 2

Det er 16 gutter og 10 jenter i klassen. På hvor mange måter kan to ledsagere utnevnes?

Beslutning

Den første personen på vakt kan enten være en gutt eller en jente. Fordi det er 16 gutter og 10 jenter i klassen, da kan du utnevne førstevakt på 16 + 10 = 26 måter.

Etter at vi har valgt første vaktleder, kan vi velge den andre blant de resterende 25 personene, d.v.s. 25 måter.

Ved multiplikasjonsteoremet kan to ledsagere velges på 26*25=650 måter.

Kombinasjoner uten repetisjon. Kombinasjoner med repetisjoner

Det klassiske problemet med kombinatorikk er problemet med antall kombinasjoner uten repetisjoner, hvis innhold kan uttrykkes ved spørsmålet: hvor mange måter kan velge m fra n forskjellige elementer?

Eksempel 3

Du må velge 4 av de 10 forskjellige bøkene som er tilgjengelige som gave. På hvor mange måter kan dette gjøres?

Beslutning

Vi må velge 4 av 10 bøker, og rekkefølgen av valg spiller ingen rolle. Dermed må du finne antall kombinasjoner av 10 elementer med 4:

Tenk på problemet med antall kombinasjoner med repetisjoner: det er r identiske objekter av hver av n forskjellige typer; hvor mange måter kan velge m() av disse (n*r) elementer?

Eksempel 4

Konditoriet solgte 4 typer kaker: napoleoner, eclairs, sandkaker og puff. På hvor mange måter kan 7 kaker kjøpes?

Beslutning

Fordi blant 7 kaker kan det være kaker av samme variasjon, deretter bestemmes antall måter 7 kaker kan kjøpes på av antall kombinasjoner med repetisjoner fra 7 til 4.

Plasseringer uten repetisjon. Plasseringer med repetisjoner

Det klassiske problemet med kombinatorikk er problemet med antall plasseringer uten repetisjoner, hvis innhold kan uttrykkes ved spørsmålet: hvor mange måter kan velge og plass på m annerledes steder m fra n annerledes varer?

Eksempel 5

Noen aviser har 12 sider. Det er nødvendig å plassere fire fotografier på sidene til denne avisen. På hvor mange måter kan dette gjøres hvis ingen side i avisen skal inneholde mer enn ett fotografi?

Beslutning.

I denne oppgaven velger vi ikke bare bilder, men plasserer dem på bestemte sider i avisen, og hver side i avisen skal ikke inneholde mer enn ett bilde. Dermed er problemet redusert til det klassiske problemet med å bestemme antall plasseringer uten repetisjoner fra 12 elementer med 4 elementer:

Dermed kan 4 bilder på 12 sider ordnes på 11880 måter.

Også den klassiske oppgaven til kombinatorikk er problemet med antall plasseringer med repetisjoner, hvis innhold kan uttrykkes ved spørsmålet: hvor mange måter kan dubhæren og plass på m annerledes steder m fra n elementermedredi hvilken spise det samme?

Eksempel 6

Gutten hadde frimerker med tallene 1, 3 og 7 fra settet til brettspillet. Han bestemte seg for å bruke disse stemplene til å sette femsifrede tall på alle bøkene – for å lage en katalog. Hvor mange forskjellige femsifrede tall kan gutten lage?

Permutasjoner uten repetisjon. Permutasjoner med repetisjoner

Det klassiske problemet med kombinatorikk er problemet med antall permutasjoner uten repetisjon, hvis innhold kan uttrykkes ved spørsmålet: hvor mange måter kan plass n diverse gjenstander på n annerledes steder?

Eksempel 7

Hvor mange "ord" på fire bokstaver kan lages av bokstavene i ordet "ekteskap"?

Beslutning

Det generelle settet er 4 bokstaver av ordet "ekteskap" (b, p, a, k). Antall "ord" bestemmes av permutasjonene til disse 4 bokstavene, dvs.

For tilfellet når det blant de valgte n elementene er de samme (utvalg med retur), kan problemet med antall permutasjoner med repetisjoner uttrykkes ved spørsmålet: På hvor mange måter kan n objekter omorganiseres på n forskjellige steder hvis det blant n objekter er k forskjellige typer (k< n), т. е. есть одинаковые предметы.

Eksempel 8

Hvor mange forskjellige bokstavkombinasjoner kan lages av bokstavene i ordet "Mississippi"?

Beslutning

Det er 1 bokstav "m", 4 bokstaver "i", 3 bokstaver "c" og 1 bokstav "p", 9 bokstaver totalt. Derfor er antallet permutasjoner med repetisjoner

BAKGRUNNSOPPSUMMERING OM AVSNITTET "KOMBINATORIKK"