Kombinatorik är en gren av matematiken som studerar frågor om hur många olika kombinationer, under vissa förutsättningar, som kan göras av givna objekt. Grunderna i kombinatorik är mycket viktiga för att uppskatta sannolikheten för slumpmässiga händelser, eftersom de tillåter oss att beräkna det fundamentalt möjliga antalet olika alternativ händelseutvecklingen.
Grundformel för kombinatorik
Låt det finnas k grupper av element, och i:e gruppen består av n i element. Låt oss välja ett element från varje grupp. Sedan Totala numret De N sätt på vilka ett sådant val kan göras bestäms av relationen N=n 1 *n 2 *n 3 *...*n k .
Exempel 1. Låt oss förklara denna regel med ett enkelt exempel. Låt det finnas två grupper av element, och den första gruppen består av n 1 element, och den andra - av n 2 element. Hur många olika par av element kan göras från dessa två grupper, så att paret innehåller ett element från varje grupp? Låt oss säga att vi tog det första elementet från den första gruppen och, utan att ändra det, gick igenom alla möjliga par och ändrade bara elementen från den andra gruppen. Det kan finnas n 2 sådana par för detta element. Sedan tar vi det andra elementet från den första gruppen och gör även alla möjliga par för det. Det kommer också att finnas n 2 sådana par. Eftersom det bara finns n 1 element i den första gruppen kommer det totala antalet möjliga alternativ att vara n 1 *n 2 .
Exempel 2. Hur många tresiffriga jämna tal kan göras av siffrorna 0, 1, 2, 3, 4, 5, 6, om siffrorna kan upprepas?
Lösning: n 1 =6 (eftersom du kan ta valfritt tal från 1, 2, 3, 4, 5, 6 som den första siffran), n 2 =7 (eftersom du kan ta valfritt tal från 0 som den andra siffran , 1, 2 , 3, 4, 5, 6), n 3 =4 (eftersom alla tal från 0, 2, 4, 6 kan tas som den tredje siffran).
Så, N=n 1 *n 2 *n 3 =6*7*4=168.
I det fall då alla grupper består av samma nummer element, dvs. n 1 =n 2 =...n k =n vi kan anta att varje urval görs från samma grupp, och elementet efter urvalet returneras till gruppen. Då är antalet av alla urvalsmetoder n k . Denna metod för urval i kombinatorik kallas prover med retur.
Exempel 3. Hur många fyrsiffriga nummer kan göras av siffrorna 1, 5, 6, 7, 8?
Lösning. För varje siffra i ett fyrsiffrigt tal finns det fem möjligheter, vilket betyder N=5*5*5*5=5 4 =625.
Betrakta en mängd som består av n element. I kombinatorik kallas denna uppsättning allmänna befolkningen.
Antal placeringar av n element med m
Definition 1. Boende från n element av m i kombinatorik någon beställt set från m olika element valda från befolkningen i n element.
Exempel 4. Olika arrangemang av tre element (1, 2, 3) och två kommer att vara uppsättningarna (1, 2), (2, 1), (1, 3), (3, 1), (2, 3), (3) , 2). Placeringar kan skilja sig från varandra både i element och i deras ordning.
Antalet placeringar i kombinatorik betecknas med A n m och beräknas med formeln:
Kommentar: n!=1*2*3*...*n (läs: "en factorial"), dessutom antas det att 0!=1.
Exempel 5. Hur många tvåsiffriga tal finns det där tiosiffran och enhetssiffran är olika och udda?
Lösning: därför att Om det finns fem udda siffror, nämligen 1, 3, 5, 7, 9, så handlar denna uppgift om att välja och placera två av de fem olika siffrorna i två olika positioner, dvs. de angivna siffrorna kommer att vara:
Definition 2. Kombination från n element av m i kombinatorik någon oordnat set från m olika element valda från befolkningen i n element.
Exempel 6. För uppsättningen (1, 2, 3) är kombinationerna (1, 2), (1, 3), (2, 3).
Antal kombinationer av n element, m vardera
Antalet kombinationer betecknas med C n m och beräknas med formeln:
Exempel 7. På hur många sätt kan en läsare välja två böcker av sex tillgängliga?
Lösning: Antalet metoder är lika med antalet kombinationer av sex böcker av två, dvs. är lika med:
Permutationer av n element
Definition 3. Permutation från n element kallas alla beställt set dessa element.
Exempel 7a. Alla möjliga permutationer av en uppsättning som består av tre element (1, 2, 3) är: (1, 2, 3), (1, 3, 2), (2, 3, 1), (2, 1, 3) , (3, 2, 1), (3, 1, 2).
Antalet olika permutationer av n element betecknas med P n och beräknas med formeln P n =n!.
Exempel 8. På hur många sätt kan sju böcker av olika författare ordnas på en rad på en hylla?
Lösning: Det här problemet handlar om antalet permutationer av sju olika böcker. Det finns P 7 =7!=1*2*3*4*5*6*7=5040 sätt att ordna böckerna.
Diskussion. Vi ser att antalet möjliga kombinationer kan beräknas enligt olika regler (permutationer, kombinationer, placeringar) och resultatet blir annorlunda, eftersom Beräkningsprincipen och själva formlerna är olika. Om du tittar noga på definitionerna kommer du att märka att resultatet beror på flera faktorer samtidigt.
För det första, från hur många element vi kan kombinera uppsättningar av (hur stor helheten av element är).
För det andra beror resultatet på storleken på de uppsättningar element vi behöver.
Slutligen är det viktigt att veta om ordningen på elementen i uppsättningen är viktig för oss. Låt oss förklara den sista faktorn med hjälp av följande exempel.
Exempel 9. På föräldramöte 20 personer är närvarande. Hur många olika alternativ finns det för sammansättningen av föräldranämnden om den måste omfatta 5 personer?
Lösning: I det här exemplet är vi inte intresserade av ordningen på namnen på kommittélistan. Om, som ett resultat, samma personer visar sig vara en del av det, så är detta i betydelse för oss samma alternativ. Därför kan vi använda formeln för att beräkna antalet kombinationer med 20 element 5 vardera.
Saker och ting kommer att vara annorlunda om varje kommittémedlem initialt är ansvarig för ett specifikt arbetsområde. Då finns det med samma listsammansättning av nämnden möjligen 5 inom den! alternativ permutationer den saken. Antalet olika (både i sammansättning och ansvarsområde) alternativ bestäms i detta fall av antalet placeringar med 20 element 5 vardera.
Självtestuppgifter
1. Hur många tresiffriga jämna tal kan göras av siffrorna 0, 1, 2, 3, 4, 5, 6, om siffrorna kan upprepas?
2. Hur många femsiffriga tal finns det som läses lika från vänster till höger och från höger till vänster?
3. Det är tio ämnen i klassen och fem lektioner om dagen. På hur många sätt kan du skapa ett schema för en dag?
4. På hur många sätt kan 4 delegater väljas ut till en konferens om det finns 20 personer i gruppen?
5. På hur många sätt kan åtta olika bokstäver läggas i åtta olika kuvert, om bara en bokstav placeras i varje kuvert?
6. En kommission bestående av två matematiker och sex ekonomer bör bestå av tre matematiker och tio ekonomer. På hur många sätt kan detta göras?
Att använda förhandsvisning presentationer skapa dig ett konto ( konto) Google och logga in: https://accounts.google.com
Bildtexter:
Element av kombinatorik Nikandrova I.A. MBOU "Lyceum 10" Velikiye Luki
Exempel på kombinatoriska problem. Problem där man måste göra olika kombinationer av ett ändligt antal element och räkna antalet kombinationer kallas för kombinatorisk gren där sådana problem betraktas. Ordet "kombinatorik" kommer från den latinska combinare - "att ansluta, kombinera"
Exempel 1 Från en grupp tennisspelare, som omfattar fyra personer - Antonov, Grigoriev, Sergeev och Fedorov, väljer tränaren ett par att delta i tävlingar. Hur många alternativ finns det för att välja ett sådant par? AG, AS, AF GS, GF SF Detta betyder att det finns sex alternativ totalt. Den resonemangsmetod vi använde kallas brute force möjliga alternativ
Exempel 2 Hur många tresiffriga nummer kan göras av siffrorna 1, 3, 5, 7, utan att använda vart och ett av dem mer än en gång för att skriva numret? För att svara på frågan om problemet skriver vi ner alla sådana siffror. Vi kommer att skriva de erhållna resultaten i fyra rader, som var och en innehåller sex siffror: 135 137 153 157 173 175 315 317 351 357 371 375 513 517 531 537 571 573 5 7 3 7 5 7 3 7
Metod två Uppräkningen av alternativ illustreras i diagrammet. Ett sådant diagram kallas ett träd med möjliga alternativ
Metod tre Den första siffran kan väljas på fyra sätt. Eftersom det kommer att finnas tre kvar efter att den första siffran valts, kan den andra siffran väljas på tre sätt. Slutligen kan den tredje siffran väljas på två sätt. Följaktligen är det totala antalet nödvändiga tal lika med produkten 4*3*2, det vill säga 24 Den kombinatoriska multiplikationsregeln användes: Låt det finnas n element och du måste välja k element från dem efter varandra. Om det första elementet kan väljas på n1 sätt, varefter det andra elementet kan väljas på n2 sätt från de återstående, så kan det tredje elementet väljas på n3 sätt från de återstående, etc., då antalet sätt där alla k element kan väljas är lika med produkten n1 · p2 · p2 · … · pk .
Exempel 3 Det finns två vägar från stad A till stad B, tre vägar från stad B till stad C och två vägar från stad C till piren. Turister vill resa från stad A genom B och C till piren. På hur många sätt kan de välja en väg? Lösning: 2*3*2=12
Problem 1. Caféet erbjuder två förrätter: borsjtj, rassolnik och fyra andrarätter: gulasch, kotletter, korv, dumplings. Lista alla tvårätters måltider som en middag kan beställa. Konstruera ett träd med möjliga alternativ 2. Stadion har fyra ingångar: A, B, C, D. Ange alla möjliga sätt, där en besökare kan komma in genom en ingång och gå ut genom en annan. Hur många sådana sätt finns det? Svar: 12 sätt 3. Använd siffrorna 0,2,4,6 för att skapa alla möjliga tresiffriga nummer där siffrorna inte upprepas.
Uppgift 4. 9 personer deltar i en schackturnering. Var och en av dem spelade ett spel med varandra. Hur många matcher spelades totalt? Svar: 36 matcher 5. Under ett möte skakade 8 personer hand. Hur många handslag gjordes? Svar: 28 handslag 6. Elever i 9:e klass bestämde sig för att byta fotografier. Hur många bilder kommer det att krävas om det är 24 elever i klassen? Svar: 552 bilder
Problem 7. Caféet har tre förrätter, fem andrarätter och två tredjerätter. På hur många sätt kan en cafébesökare välja en lunch bestående av första, andra och tredje rätter? Svar: 30 sätt 8. Peter bestämde sig för att gå på nyårskarnevalen utklädd till en musketör. I uthyrningsbutiken erbjöds han ett urval av föremål i olika stilar och färger: fem typer av byxor, sex camisoles, tre hattar, två par stövlar. Hur många olika karnevalsdräkter kan göras av dessa föremål? Svar: 180 kostymer
Permutationer De enklaste kombinationerna som kan göras av element i en ändlig mängd är permutationer. Antalet permutationer av n element betecknas med symbolen P n (läs "P av n") För produkten av det första n. naturliga tal använd en speciell notation: n! (läs n faktoriell) 2!=2; 5 = 120; 1!=1
Exempel på problem Antalet möjliga permutationer av n element beräknas alltså med formeln: P n = n! Exempel 1. På hur många sätt kan de 8 deltagarna i finalloppet placeras på åtta löpband? P 8 =8!=40320 Exempel 2. Hur många olika fyrsiffriga nummer där siffrorna inte upprepas kan göras av siffrorna 0, 2, 4, 6? Från siffrorna 0,2,4,6 kan du få P 4 permutationer. Från detta tal måste vi utesluta de permutationer som börjar med 0. Vi får: P 4 -P 3 =4!-3!=18
Exempel 3. Det finns 9 olika böcker, fyra av dem varav - läroböcker. På hur många sätt kan dessa böcker placeras på en hylla så att alla läroböcker ligger bredvid varandra? Först kommer vi att betrakta läroböcker som en bok. Då måste du placera inte 9 utan 6 böcker på hyllan. Detta kan göras på 6 sätt. I var och en av de resulterande kombinationerna är det möjligt att utföra P4-permutationer av läroböcker. Detta innebär att det erforderliga antalet sätt att ordna böcker på en hylla är lika med produkten P 6 * P 4 . Vi får: P 6 *P 4 =6!*4!=720*24=17280
Problem 1. På hur många sätt får 4 personer plats på en fyrsitsig bänk? Svar:24 2. Kuriren måste leverera paket till 7 olika institutioner. Hur många vägar kan han välja? Svar: 5040 3. Hur många sexsiffriga nummer (utan att upprepa siffror) kan göras av siffrorna: a) 1,2,5,6,7,8; b)0,2,5,6,7,8? Svar: a) 720; b) 600 4. Schemat för måndagen har sex lektioner: algebra, geometri, biologi, historia, fysisk utbildning, kemi På hur många sätt kan lektionsschemat för denna dag göras så att två matematiklektioner är bredvid varandra? Svar: 240
Problem 5. Är talet 14 delbart? På: A)168; b)136;c)147;d)132? 6. 7. Svar på 6) :15; 1/90; 1722; 40
Provarbete Alternativ 1 Alternativ 2 1. Kombinatoriska problem 2. Metoder för att lösa kombinatoriska problem 3. Beräkna 1. Permutationer, formel 2. Kombinatorik 3. Beräkna
Placeringar Låt det vara 4 bollar och 3 tomma celler. Tre bollar från denna uppsättning bollar kan placeras i de tomma cellerna på olika sätt. Att välja olika sätt den första, andra och tredje bollen kommer vi att få olika trillingar av bollar. Varje ordnad trippel som kan bestå av fyra element kallas ett arrangemang av fyra element med tre Ett arrangemang av n element med k (k
Exempel 1. Elever i andra klass läser 8 ämnen. På hur många sätt kan du skapa ett schema för en dag så att det innehåller 4 olika ämnen? I detta exempel vi pratar om om placeringar av 8 element av 4. Vi har: 2. Hur många tresiffriga tal (utan att upprepa siffrorna i siffernotationen) kan göras av talen 0,1,2,3,4,5,6? Bland dessa nummer finns talet 0, som inte kan börja ett tresiffrigt tal. Det är därför:
Problem 1. På hur många sätt får en familj på tre personer plats i en fyrsitsig kupé om det inte finns några andra passagerare i kupén? Svar: 24 2. Av de 30 deltagarna i mötet ska en ordförande och en sekreterare utses. På hur många sätt kan detta göras? Svar: 870 3. På hur många sätt kan arrangörerna av tävlingen bestämma vem av de 15 deltagarna som kommer att prestera etta, tvåa och trea? Svar: 2730 4. Det finns 6 lediga platser för bilder på albumsidan. På hur många sätt kan du lägga i de tomma utrymmena: a) 2 fotografier; b) 4 fotografier; c) 6 bilder? Svar: 30;360;720
Kombinationer En kombination av n element med k är vilken mängd som helst som består av givna n element. Till skillnad från placeringar i kombinationer spelar det ingen roll i vilken ordning elementen specificeras. Två kombinationer av element med k skiljer sig från varandra med minst ett element . Beteckna Läs "C" från n till k" Formel för antalet kombinationer av n element till k, där k.
Exempel 1. Av 15 medlemmar i en turistgrupp ska tre personer i tjänst väljas ut. På hur många sätt kan detta val göras? Varje val skiljer sig från det andra med minst en skötare. Det betyder att vi här talar om kombinationer av 15 element av 3. Vi har: 2. Från en fruktskål som innehåller 9 äpplen och 6 päron måste du välja 3 äpplen och 2 päron. På hur många sätt kan ett sådant val göras? Vi har:
Uppgifter 1. Det är 7 personer i klassen som framgångsrikt gör matematik. På hur många sätt kan du välja två av dem att delta i Matematisk Olympiad? Svar:21 2. Eleverna fick en lista med 10 böcker som rekommenderas att läsa under semestern. På hur många sätt kan en elev välja 6 böcker från dem? Svar: 210 3. Det är 16 pojkar och 12 flickor i klassen. Fyra pojkar och tre flickor krävs för att städa området. På hur många sätt kan detta göras? Svar: 400400 4. I biblioteket erbjöds läsaren att välja mellan 10 böcker och 4 tidningar från nyanlända. På hur många sätt kan han välja 3 böcker och 2 tidningar från dem? Svar: 720
Självständigt arbete Alternativ 1 1. På hur många sätt kan 9 tävlingsdeltagare prestera i prioritetsordning i finalen? 2. Är talet 40 delbart? n a: a) 410; b) 500; 3. Med hjälp av siffrorna 0,3,7,8, gör upp alla möjliga dubbla siffror, där siffrorna inte upprepas 4. Det finns 10 suppleanter i Stadsduman under 30 år. På hur många sätt kan tre av dem väljas ut att sitta i kommittén? ungdomspolitik? Alternativ 2 1. Budet måste leverera pizza till sex adresser. Hur många vägar kan han välja? 2. Är talet 50 delbart? n a: a) 400; b) 98; 3. Använd jämna nummer 0,2,4,6,8 och gör upp alla möjliga tresiffriga tal där talen inte upprepas 4. Det är 9 elever i gruppen som talar bra främmande språk. På hur många sätt kan fyra av dem väljas ut att arbeta i praktiken med utlänningar?
Svar Alternativ 1 1. 9!=362880 2. a) nej b) ja c) ja 3. 30 70 80 37 73 83 38 78 87 4. 120 Alternativ 2 1. 6!=720 2. a) ja b) c) ja 3. 48 nummer 4. 126
Det bör noteras att kombinatorik är en självständig gren av högre matematik (och inte en del av terver) och tunga läroböcker har skrivits om denna disciplin, vars innehåll ibland inte är lättare än abstrakt algebra. En liten del teoretisk kunskap kommer dock att räcka för oss, och i den här artikeln kommer jag att försöka analysera i en tillgänglig form grunderna i ämnet med typiska kombinatoriska problem. Och många av er kommer att hjälpa mig ;-)
Vad ska vi göra? I en snäv mening är kombinatorik beräkningen av olika kombinationer som kan göras från en viss uppsättning diskret föremål. Objekt förstås som alla isolerade föremål eller levande varelser - människor, djur, svampar, växter, insekter, etc. Samtidigt bryr sig kombinatorik inte alls om att setet består av en tallrik gryngröt, en lödkolv och en träskgroda. Det är fundamentalt viktigt att dessa objekt kan räknas upp - det finns tre av dem (diskret) och det viktiga är att ingen av dem är identisk.
Vi har sysslat med mycket, nu om kombinationer. De vanligaste typerna av kombinationer är permutationer av objekt, deras urval från en uppsättning (kombination) och distribution (placering). Låt oss se hur detta händer just nu:
Permutationer, kombinationer och placeringar utan upprepning
Var inte rädd för oklara termer, särskilt eftersom vissa av dem verkligen inte är särskilt bra. Låt oss börja med titelns svans - vad gör " inga upprepningar"? Detta innebär att vi i detta avsnitt kommer att överväga uppsättningar som består av olika föremål. Till exempel ... nej, jag kommer inte bjuda på gröt med lödkolv och groda, det är bättre att ha något godare =) Tänk dig att ett äpple, ett päron och en banan har materialiserats på bordet framför dig ( om du har dem kan situationen simuleras i verkligheten). Vi lägger ut frukterna från vänster till höger i följande ordning:
äpple/päron/banan
Fråga ett: På hur många sätt kan de ordnas om?
En kombination har redan skrivits ovan och det finns inga problem med resten:
äpple / banan / päron
päron / äpple / banan
päron / banan / äpple
banan / äpple / päron
banan / päron / äpple
Total: 6 kombinationer eller 6 permutationer.
Okej, det var inte svårt att lista alla möjliga fall, men vad händer om det finns fler föremål? Med bara fyra olika frukter kommer antalet kombinationer att öka avsevärt!
Öppna referensmaterialet (det är bekvämt att skriva ut manualen) och i punkt nr 2, hitta formeln för antalet permutationer.
Inget krångel - 3 objekt kan ordnas om på olika sätt.
Fråga två: På hur många sätt kan du välja a) en frukt, b) två frukter, c) tre frukter, d) minst en frukt?
Varför välja? Så vi fick upp aptiten i föregående punkt - för att kunna äta! =)
a) En frukt kan naturligtvis väljas på tre sätt - ta antingen ett äpple, ett päron eller en banan. Den formella beräkningen utförs enl formel för antalet kombinationer
:
Registrera dig för I detta fall bör förstås på följande sätt: "på hur många sätt kan du välja 1 frukt av tre?"
b) Låt oss lista alla möjliga kombinationer av två frukter:
äpple och päron;
äpple och banan;
päron och banan.
Antalet kombinationer kan enkelt kontrolleras med samma formel:
Posten förstås på ett liknande sätt: "på hur många sätt kan du välja 2 frukter av tre?"
c) Och slutligen finns det bara ett sätt att välja tre frukter:
Förresten, formeln för antalet kombinationer förblir meningsfull för ett tomt prov:
På detta sätt kan du inte välja en enda frukt - faktiskt, ta ingenting och det är det.
d) På hur många sätt kan du ta åtminstone ett frukt? Villkoret "minst en" innebär att vi är nöjda med 1 frukt (vilken som helst) eller vilken som helst 2 frukt eller alla 3 frukterna:
med dessa metoder kan du välja minst en frukt.
Läsare som noggrant har studerat den inledande lektionen på sannolikhetsteori , vi har redan gissat något. Men mer om innebörden av plustecknet senare.
Att svara nästa fråga Jag behöver två volontärer... ...Tja, eftersom ingen vill, då kallar jag dig till styrelsen =)
Fråga tre: På hur många sätt kan du dela ut en frukt vardera till Dasha och Natasha?
För att distribuera två frukter måste du först välja dem. Enligt paragraf "vara" föregående fråga, det finns sätt att göra detta, jag kommer att skriva om dem:
äpple och päron;
äpple och banan;
päron och banan.
Men nu blir det dubbelt så många kombinationer. Tänk till exempel på det första fruktparet:
Du kan behandla Dasha med ett äpple och Natasha med ett päron;
eller vice versa - Dasha kommer att få päronet, och Natasha kommer att få äpplet.
Och en sådan permutation är möjlig för varje par frukter.
Tänk på samma studentgrupp som gick på dansen. På hur många sätt kan en pojke och en flicka paras ihop?
På sätt kan du välja 1 ung man;
sätt du kan välja 1 tjej.
Alltså en ung man Och Du kan välja en tjej: 
sätt.
När 1 objekt väljs från varje uppsättning är följande princip för att räkna kombinationer giltig: " varje ett objekt från en uppsättning kan bilda ett par med varje föremål för en annan uppsättning."
Det vill säga, Oleg kan bjuda in någon av de 13 tjejerna att dansa, Evgeny kan också bjuda in någon av de tretton, och resten av ungdomarna har ett liknande val. Totalt: möjliga par.
Det bör noteras att i i detta exempel"Historien" för parets bildande spelar ingen roll; Men om vi tar hänsyn till initiativet måste antalet kombinationer fördubblas, eftersom var och en av de 13 tjejerna också kan bjuda in vilken kille som helst till dans. Allt beror på förutsättningarna för en viss uppgift!
En liknande princip gäller för mer komplexa kombinationer, till exempel: på hur många sätt kan man välja två unga män? Och två tjejer att delta i en KVN-skit?
Union OCH antyder tydligt att kombinationerna måste multipliceras:
Möjliga grupper av konstnärer.
Med andra ord, varje ett par pojkar (45 unika par) kan uppträda med några ett par tjejer (78 unika par). Och om vi tänker på rollfördelningen mellan deltagarna blir det ännu fler kombinationer. ...Jag vill verkligen, men jag kommer ändå att avstå från att fortsätta för att inte ingjuta en motvilja mot dig studentliv =).
Regeln för att multiplicera kombinationer gäller även för stor kvantitet multiplikatorer:
Problem 8
Hur många tresiffriga tal finns det som är delbara med 5?
Lösning: för tydlighetens skull, låt oss beteckna givet nummer tre stjärnor: ***
I hundra plats Du kan skriva vilket som helst av siffrorna (1, 2, 3, 4, 5, 6, 7, 8 eller 9). Noll är inte lämpligt, eftersom numret i detta fall upphör att vara tresiffrigt.
Men i tians plats("i mitten") kan du välja vilken som helst av 10 siffror: .
Enligt villkoret ska talet vara delbart med 5. Ett tal är delbart med 5 om det slutar på 5 eller 0. Därmed nöjer vi oss med 2 siffror i den minst signifikanta siffran.
Totalt finns det: tresiffriga tal som är delbara med 5.
I det här fallet dechiffreras verket enligt följande: "9 sätt du kan välja ett nummer på hundra plats Och 10 sätt att välja ett nummer i tians plats Och 2 vägar in Enheter siffra»
Eller ännu enklare: " varje från 9 siffror till hundra plats kombinerar Med varje med 10 siffror tians plats och med varje från två siffror till Enheter siffra».
Svar: 180
Och nu…
Ja, jag glömde nästan bort den utlovade kommentaren till problem nr 5, där Bor, Dima och Volodya kan tilldelas ett kort var på olika sätt. Multiplikation här har samma betydelse: sätt att ta bort 3 kort från leken OCH i varje prov ordna om dem på ett sätt.
Och nu uppgiften för oberoende beslut... nu ska jag komma på något mer intressant, ... låt det handla om samma ryska version av blackjack:
Problem 9
Hur många vinnande kombinationer av 2 kort finns det när man spelar "point"?
För de som inte vet: den vinnande kombinationen är 10 + ACE (11 poäng) = 21 poäng och låt oss överväga den vinnande kombinationen av två ess.
(ordningen på korten i valfritt par spelar ingen roll)
En kort lösning och svar i slutet av lektionen.
Förresten, betrakta inte exemplet som primitivt. Blackjack är nästan det enda spelet för vilket det finns en matematiskt baserad algoritm som låter dig slå kasinot. Den som är intresserad kan enkelt hitta en mängd information om optimal strategi och taktik. Det är sant att sådana mästare hamnar ganska snabbt på den svarta listan över alla anläggningar =)
Det är dags att konsolidera materialet täckt med ett par solida uppgifter:
Problem 10
Vasya har 4 katter hemma.
a) på hur många sätt kan katter sitta i hörnen av rummet?
b) på hur många sätt kan du låta katter gå på promenad?
c) på hur många sätt kan Vasya plocka upp två katter (en till vänster och den andra till höger)?
Låt oss bestämma: För det första bör du återigen vara uppmärksam på det faktum att problemet handlar om annorlunda föremål (även om katter är det enäggstvillingar). Detta är väldigt viktigt tillstånd!
a) Tystnad av katter. Med förbehåll för detta utförande alla katter på en gång
+ deras plats är viktig, så det finns permutationer här:
med dessa metoder kan du placera katter i hörnen av rummet.
Jag upprepar att vid permutering är det bara antalet olika objekt och deras relativa positioner som har betydelse. Beroende på Vasyas humör kan hon placera djuren i en halvcirkel i soffan, i en rad på fönsterbrädan, etc. – i alla fall kommer det att finnas 24 permutationer För enkelhetens skull kan intresserade föreställa sig att katter är flerfärgade (till exempel vita, svarta, röda och tabby) och lista alla möjliga kombinationer.
b) På hur många sätt kan du låta katter gå på promenad?
Det antas att katter går på promenader endast genom dörren, och frågan innebär likgiltighet angående antalet djur - 1, 2, 3 eller alla 4 katterna kan gå på promenad.
Vi räknar alla möjliga kombinationer:
På dessa sätt kan du låta en katt (vilken som helst av de fyra) gå på promenad; 
sätt du kan låta två katter gå på promenad (lista alternativen själv);
på ett sätt kan du låta tre katter gå på promenad (en av de fyra sitter hemma);
På så sätt kan du släppa alla katter.
Du gissade förmodligen att de resulterande värdena borde summeras:
sätt att låta katter gå på promenader.
För entusiaster erbjuder jag en komplicerad version av problemet - när vilken katt som helst i vilket prov som helst kan gå ut slumpmässigt, både genom dörren och genom fönstret på 10:e våningen. Det kommer att bli en märkbar ökning av kombinationer!
c) På hur många sätt kan Vasya plocka upp två katter?
Situationen involverar inte bara att välja två djur, utan också att placera dem i varje hand:
På dessa sätt kan du plocka upp 2 katter.
Andra lösningen: du kan välja två katter med metoder Och sätt att plantera varje ett par till hands: 
Svar: a) 24, b) 15, c) 12
Tja, för att rensa ditt samvete, något mer specifikt om att multiplicera kombinationer... Låt Vasya få 5 extra katter =) På hur många sätt kan du låta 2 katter gå en promenad? Och 1 katt?
Det vill säga med varje ett par katter kan släppas varje katt.
Ett annat knappdragspel för oberoende lösning:
Problem 11
3 passagerare gick ombord på hissen i en 12-våningsbyggnad. Alla, oavsett de andra, kan gå ut på vilken (med början från 2:a) våningen med lika stor sannolikhet. På hur många sätt:
1) passagerare kan gå av på samma våning (utgångsordning spelar ingen roll);
2) två personer kan gå av på en våning och en tredje på den andra;
3) människor kan gå ut på olika våningar;
4) kan passagerare gå ur hissen?
Och här frågar de ofta igen, jag förtydligar: om 2 eller 3 personer går ut på samma våning, så spelar ordningen för utgången ingen roll. TÄNK, använd formler och regler för att lägga till/multiplicera kombinationer. I händelse av svårigheter är det användbart för passagerare att ge namn och spekulera i vilka kombinationer de kan lämna hissen. Det finns ingen anledning att bli upprörd om något inte fungerar, till exempel är punkt nr 2 ganska lömsk.
Fullständig lösning med detaljerade kommentarer i slutet av lektionen.
Det sista stycket ägnas åt kombinationer som också förekommer ganska ofta - enligt min subjektiva bedömning, i ungefär 20-30 % av kombinatoriska problem:
Permutationer, kombinationer och placeringar med upprepningar
Listade arter kombinationer beskrivs i punkt nr 5 referensmaterial Grundläggande formler för kombinatorik , men vissa av dem kanske inte är särskilt tydliga vid första behandlingen. I det här fallet är det först tillrådligt att bekanta dig med praktiska exempel och först då förstå den allmänna formuleringen. Gå:
Permutationer med upprepningar
I permutationer med upprepningar, som i "vanliga" permutationer, alla de många föremålen på en gång, men det finns en sak: i denna uppsättning upprepas ett eller flera element (objekt). Uppfyll nästa standard:
Problem 12
Hur många olika bokstavskombinationer kan fås genom att ordna om kort med följande bokstäver: K, O, L, O, K, O, L, b, Ch, I, K?
Lösning: i händelse av att alla bokstäver var olika, måste en trivial formel användas, men det är helt klart att för den föreslagna uppsättningen kort kommer vissa manipulationer att fungera "tomt", till exempel om du byter två kort med bokstäverna "K" " i vilket ord som helst får du samma ord. Dessutom kan korten fysiskt vara väldigt olika: ett kan vara runt med bokstaven "K" tryckt på den, den andra kan vara fyrkantig med bokstaven "K" ritad på den. Men enligt meningen med uppgiften, även sådana kort anses lika, eftersom villkoret frågar om bokstavskombinationer.
Allt är extremt enkelt - bara 11 kort, inklusive bokstaven:
K - upprepas 3 gånger;
O – upprepas 3 gånger;
L - upprepas 2 gånger;
b – upprepas 1 gång;
H – upprepas 1 gång;
Och - upprepas 1 gång.
Kontrollera: 3 + 3 + 2 + 1 + 1 + 1 = 11, vilket är vad som behövde kontrolleras.
Enligt formeln antal permutationer med upprepningar
:
olika bokstavskombinationer kan erhållas. Mer än en halv miljon!
För att snabbt beräkna ett stort faktorvärde är det bekvämt att använda standardfunktionen Excel: skriv in i valfri cell =FAKTA(11) och tryck Stiga på.
I praktiken är det helt acceptabelt att inte skriva den allmänna formeln och dessutom utelämna enhetsfaktorerna: 
Men det krävs preliminära kommentarer om upprepade brev!
Svar: 554400
Ett annat typiskt exempel på permutationer med upprepning förekommer i schackpjäsplaceringsproblemet, som finns i lagret färdiga lösningar i motsvarande pdf. Och för en oberoende lösning kom jag på en mindre formelrik uppgift:
Problem 13
Alexey går in för sport, 4 dagar i veckan - friidrott, 2 dagar - styrkeövningar och vilar 1 dag. På hur många sätt kan han skapa ett veckoschema för sig själv?
Formeln fungerar inte här eftersom den tar hänsyn till tillfälliga byten (exempelvis att byta onsdagens styrkeövningar mot torsdagens styrkeövningar). Och igen - faktiskt samma 2 kraftträning kan vara mycket olika varandra, men i sammanhanget för uppgiften (ur schemasynpunkt) anses de vara samma element.
Tvåradslösning och svar i slutet av lektionen.
Kombinationer med repetitioner
Funktion Denna typ av kombination består i att provet tas från flera grupper, som var och en består av identiska objekt.
Alla har jobbat hårt idag, så det är dags att fräscha upp dig:
Problem 14
Studentmatsalen säljer korv i deg, cheesecakes och munkar. På hur många sätt kan du köpa fem pajer?
Lösning: uppmärksamma omedelbart det typiska kriteriet för kombinationer med upprepningar - enligt villkoret är det inte en uppsättning objekt som sådan som erbjuds för val, men olika sorter föremål; det antas att det finns minst fem varmkorvar, 5 cheesecakes och 5 munkar till försäljning. Pajerna i varje grupp är förstås olika - eftersom helt identiska munkar bara kan simuleras på en dator =) Dock fysiska egenskaper pajer är inte signifikanta i problemets mening, och korv/cheesecakes/munkar anses vara likadana i sina grupper.
Vad kan finnas i provet? Först och främst bör det noteras att det definitivt kommer att finnas identiska pajer i provet (eftersom vi väljer 5 stycken och det finns 3 typer att välja mellan). Här finns alternativ för alla smaker: 5 varmkorv, 5 ostkakor, 5 munkar, 3 korv + 2 ostkakor, 1 varmkorv + 2 ostkakor + 2 munkar, etc.
Som med "vanliga" kombinationer spelar ordningen för urval och placering av pajer i urvalet ingen roll - du valde bara 5 stycken och det är allt.
Vi använder formeln 
antal kombinationer med repetitioner: 
Du kan köpa 5 pajer med denna metod.
Smaklig måltid!
Svar: 21
Vilken slutsats kan dras av många kombinatoriska problem?
Ibland är det svåraste att förstå tillståndet.
Ett liknande exempel för en oberoende lösning:
Problem 15
Det finns tillräckligt i plånboken Ett stort antal 1-, 2-, 5- och 10-rubelmynt. På hur många sätt kan tre mynt tas bort från en plånbok?
För självkontrollsyften, svara ett par enkla frågor:
1) Kan alla mynt i provet vara olika?
2) Nämn den "billigaste" och "dyraste" kombinationen av mynt.
Lösning och svar i slutet av lektionen.
Från min personlig erfarenhet, Jag kan säga att kombinationer med upprepningar är den sällsynta gästen i praktiken, vilket inte kan sägas om följande formulär kombinationer:
Placeringar med upprepningar
Från en uppsättning bestående av element väljs element, och ordningen på elementen i varje urval är viktig. Och allt skulle vara bra, men ett ganska oväntat skämt är att vi kan välja vilket objekt som helst i originaluppsättningen så många gånger vi vill. Bildligt talat, "mängden kommer inte att minska."
När händer detta? Typiskt exempelär ett kombinationslås med flera skivor, men på grund av teknikutvecklingen är det mer relevant att överväga dess digitala ättling:
Problem 16
Hur många fyrsiffriga PIN-koder finns det?
Lösning: i själva verket, för att lösa problemet, räcker kunskap om reglerna för kombinatorik: på ett sätt kan du välja den första siffran i PIN-koden Och sätt - den andra siffran i PIN-koden Och på lika många sätt - tredje Och samma nummer - den fjärde. Sålunda, enligt regeln om att multiplicera kombinationer, kan en fyrsiffrig pinkod vara sammansatt på: sätt.
Och använder nu formeln. Enligt villkoret erbjuds vi en uppsättning nummer, från vilka numren väljs och ordnas i en viss ordning, medan siffrorna i provet kan upprepas (dvs vilken siffra som helst i originaluppsättningen kan användas ett godtyckligt antal gånger). Enligt formeln för antalet placeringar med repetitioner: 
Svar: 10000
Vad tänker jag på... ...om bankomaten "äter upp" kortet efter det tredje misslyckat försök ange en PIN-kod, då är chansen att plocka upp den på måfå mycket liten.
Och vem sa att kombinatorik inte har någon praktisk betydelse? En kognitiv uppgift för alla läsare av sajten:
Problem 17
Enligt statlig standard, en bilskylt består av 3 siffror och 3 bokstäver. I det här fallet är ett nummer med tre nollor oacceptabelt, och bokstäver väljs från uppsättningen A, B, E, K, M, N, O, P, S, T, U, X (endast de kyrilliska bokstäverna används vars stavning sammanfaller med latinska bokstäver).
Hur många olika registreringsskyltar kan skapas för en region?
Inte så många av dem förresten. I stora regioner finns det inte tillräckligt med sådan kvantitet, och därför finns det flera koder för inskriptionen RUS för dem.
Lösningen och svaret finns i slutet av lektionen. Glöm inte att använda kombinatorikens regler ;-) ...Jag ville visa upp det som var exklusivt, men det visade sig inte vara exklusivt =) Jag tittade på Wikipedia - det finns beräkningar där, fast utan kommentarer. Även om i utbildningssyften antagligen var det få som bestämde.
Vår spännande lektion har kommit till sitt slut, och till sist vill jag säga att du inte slösade bort din tid - av den anledningen att kombinatoriska formler hittar en annan viktig praktisk användning: de möts i olika uppgifter Förbi sannolikhetsteori
,
och i problem som involverar den klassiska sannolikhetsbestämningen
– speciellt ofta =)
Tack alla för ert aktiva deltagande och vi ses snart!
Lösningar och svar:
Uppgift 2: Lösning: hitta antalet möjliga permutationer av 4 kort:
När ett kort med nolla placeras på 1:a plats blir numret tresiffrigt, så dessa kombinationer bör uteslutas. Låt noll vara på 1:a plats, då kan de återstående 3 siffrorna i de nedre siffrorna ordnas om på olika sätt.
Notera
: därför att Eftersom det bara finns ett fåtal kort är det enkelt att lista alla alternativ här:
0579
0597
0759
0795
0957
0975
Så från den föreslagna uppsättningen kan vi göra:
24 – 6 = 18 fyrsiffriga nummer
Svar
: 18
Uppgift 4: Lösning: på ett sätt kan du välja 3 kort av 36.
Svar
: 7140
Uppgift 6: Lösning: 
sätt.
En annan lösning
: sätt att välja två personer från gruppen och och
2) Det "billigaste" setet innehåller 3 rubelmynt och det "dyraste" - 3 tiorubelmynt.
Problem 17: Lösning: 
sätt du kan skapa en digital kombination registrerings skylts nummer, och en av dem (000) bör uteslutas: .
med dessa metoder kan du skapa en bokstavskombination av ett registreringsnummer.
Enligt regeln att multiplicera kombinationer kan summan göras:
registreringsskyltar
(varje digital kombination kombineras Med varje bokstavskombination).
Svar
: 1726272
