Het aantal verschillende plaatsingen van a3 5 is gelijk. Samenvatting van formules voor alle soorten combinatorische verbindingen - permutaties en plaatsingen met en zonder herhalingen met voorbeelden

In dit artikel zullen we het hebben over een speciale tak van de wiskunde, genaamd combinatoriek. Formules, regels, voorbeelden van probleemoplossing - u kunt dit hier allemaal vinden door het artikel tot het einde te lezen.

Dus wat is deze sectie? Combinatoriek houdt zich bezig met de kwestie van het tellen van objecten. Maar in dit geval zijn de objecten geen pruimen, peren of appels, maar iets anders. Combinatoriek helpt ons de waarschijnlijkheid van een gebeurtenis te bepalen. Als u bijvoorbeeld kaarten speelt: wat is dan de kans dat de tegenstander een troefkaart heeft? Of dit voorbeeld: hoe groot is de kans dat je uit een zak met twintig knikkers een witte haalt? Voor dit soort problemen moeten we op zijn minst de basisprincipes van deze tak van de wiskunde kennen.

Combinatorische configuraties

Gezien de kwestie van basisconcepten en formules van combinatoriek, kunnen we niet anders dan aandacht besteden aan combinatorische configuraties. Ze worden niet alleen gebruikt om te formuleren, maar ook om op te lossen diverse voorbeelden Dergelijke modellen zijn:

• accommodatie;
• herschikking;
• combinatie;
• nummersamenstelling;
• een getal splitsen.

We zullen later meer in detail over de eerste drie praten, maar we zullen in deze sectie aandacht besteden aan compositie en verdeling. Als ze het hebben over de samenstelling van een bepaald getal (bijvoorbeeld a), bedoelen ze dat het getal a wordt weergegeven als een geordende som van bepaalde positieve getallen. En een partitie is een ongeordende som.

Secties

Voordat we direct naar de formules van de combinatoriek en de beschouwing van problemen gaan, is het de moeite waard aandacht te schenken aan het feit dat de combinatoriek, net als andere takken van de wiskunde, zijn eigen onderafdelingen heeft. Deze omvatten:

• opsomming;
• structureel;
• extreem;
• Ramsey-theorie;
• probabilistisch;
• topologisch;
• oneindig.

In het eerste geval waar we het over hebben over berekenende combinatoriek houden problemen rekening met het opsommen of tellen van verschillende configuraties die worden gevormd door de elementen van verzamelingen. In de regel worden aan deze sets enkele beperkingen opgelegd (onderscheidend vermogen, niet-onderscheidbaarheid, mogelijkheid tot herhaling, enzovoort). En het aantal van deze configuraties wordt berekend met behulp van de regels van optellen of vermenigvuldigen, waar we het later over zullen hebben. Structurele combinatoriek omvat de theorieën van grafieken en matroïden. Een voorbeeld van een extreem combinatorisch probleem: wat is de grootste dimensie van een grafiek die voldoet de volgende eigenschappen... In de vierde paragraaf noemden we de Ramsey-theorie, die de aanwezigheid van reguliere structuren in willekeurige configuraties bestudeert. Probabilistische combinatoriek kan de vraag beantwoorden: wat is de kans dat een bepaalde set een bepaalde eigenschap heeft. Zoals je misschien wel vermoedt, past topologische combinatoriek methoden toe in de topologie. En ten slotte, het zevende punt: oneindige combinatoriek bestudeert de toepassing van combinatorische methoden op oneindige verzamelingen.

Toevoegingsregel

Onder de combinatorische formules kun je vrij eenvoudige formules vinden, waarmee we al heel lang bekend zijn. Een voorbeeld is de somregel. Stel dat we twee acties (C en E) krijgen, als ze elkaar uitsluiten, kan actie C op verschillende manieren worden uitgevoerd (bijvoorbeeld a), en kan actie E op b-manieren worden uitgevoerd, dan kan elk van deze ( C of E) kan op a+b-manieren worden uitgevoerd.

In theorie is dit vrij moeilijk te begrijpen; we zullen proberen het hele punt over te brengen aan de hand van een eenvoudig voorbeeld. Laten we nemen gemiddeld aantal studenten van één klas - laten we zeggen dat het vijfentwintig zijn. Onder hen zijn vijftien meisjes en tien jongens. Elke dag is er in elke klas één persoon van dienst. Hoeveel manieren zijn er tegenwoordig om een ​​klassenmonitor aan te stellen? De oplossing voor het probleem is vrij eenvoudig; we zullen onze toevlucht nemen tot de optellingsregel. In de tekst van het probleem staat niet dat alleen jongens of alleen meisjes dienst kunnen hebben. Daarom kan het een van de vijftien meisjes zijn, of een van de tien jongens. Als we de somregel toepassen, krijgen we een vrij eenvoudig voorbeeld dat een schoolkind gemakkelijk aankan primaire klassen: 15 + 10. Na geteld te hebben, krijgen we het antwoord: vijfentwintig. Dat wil zeggen, er zijn slechts vijfentwintig manieren om een ​​klas van dienst voor vandaag toe te wijzen.

Vermenigvuldigingsregel

De basisformules van combinatoriek omvatten ook de vermenigvuldigingsregel. Laten we beginnen met de theorie. Laten we zeggen dat we verschillende acties (a) moeten uitvoeren: de eerste actie wordt op 1 manier uitgevoerd, de tweede - op 2 manieren, de derde - op 3 manieren, enzovoort tot de laatste a-actie, op 3 manieren uitgevoerd. Dan kunnen al deze acties (waarvan we een totaal hebben) op N manieren worden uitgevoerd. Hoe onbekende N berekenen? De formule helpt ons hierbij: N = c1 * c2 * c3 *…* ca.

Nogmaals, in theorie is niets duidelijk, laten we verder gaan met de overweging eenvoudig voorbeeld om de vermenigvuldigingsregel toe te passen. Laten we dezelfde klas van vijfentwintig mensen nemen, waarin vijftien meisjes en tien jongens zitten. Alleen deze keer moeten we twee dienstdoende mensen kiezen. Het kunnen alleen jongens of meisjes zijn, of een jongen en een meisje. Laten we verder gaan met de elementaire oplossing van het probleem. We kiezen de eerste dienstdoende persoon, zoals we in de laatste paragraaf hebben besloten, we krijgen er vijfentwintig mogelijke opties. De tweede dienstdoende persoon kan een van de overige personen zijn. We hadden vijfentwintig studenten, we kozen er één, wat betekent dat de tweede dienstdoende persoon een van de overige vierentwintig mensen kon zijn. Ten slotte passen we de vermenigvuldigingsregel toe en ontdekken dat twee dienstdoende officieren op zeshonderd manieren kunnen worden gekozen. We hebben dit getal verkregen door vijfentwintig en vierentwintig te vermenigvuldigen.

Herschikking

Nu zullen we naar een andere combinatorische formule kijken. In dit gedeelte van het artikel zullen we het hebben over permutaties. We stellen voor om het probleem onmiddellijk te bekijken aan de hand van een voorbeeld. Laten we biljartballen nemen, we hebben er een zoveelste. We moeten berekenen hoeveel opties er zijn om ze op een rij te rangschikken, dat wil zeggen om een ​​geordende set te maken.

Laten we beginnen: als we geen ballen hebben, hebben we ook geen plaatsingsmogelijkheden. En als we één bal hebben, dan is de opstelling ook hetzelfde (wiskundig kan dit als volgt worden geschreven: P1 = 1). Er kunnen twee ballen in twee worden geplaatst op verschillende manieren: 1.2 en 2.1. Daarom is P2 = 2. Drie ballen kunnen op zes manieren worden gerangschikt (P3 = 6): 1,2,3; 1,3,2; 2,1,3; 2,3,1; 3,2,1; 3,1,2. Wat als er niet drie van zulke ballen zijn, maar tien of vijftien? Het zou erg lang duren om alle mogelijke opties op te sommen, en dan komt combinatoriek ons ​​te hulp. De permutatieformule zal ons helpen het antwoord te vinden op de vraag die ons interesseert. Pn = n*P (n-1). Als we de formule proberen te vereenvoudigen, krijgen we: Pn = n* (n - 1) *…* 2 * 1. En dit is het product van de eerste natuurlijke getallen. Dit getal wordt faculteit genoemd en wordt aangegeven als n!

Laten we het probleem eens bekijken. Elke ochtend stelt de raadsman zijn team (twintig personen) op. Er zitten er drie in de ploeg beste vriend- Kostya, Sasha en Lesha. Hoe groot is de kans dat ze naast elkaar staan? Om het antwoord op de vraag te vinden, moet je de kans op een ‘goede’ uitkomst delen door het totale aantal uitkomsten. Totaal aantal Er zijn 20 permutaties! = 2,5 quintiljoen. Hoe tel je het aantal ‘goede’ resultaten? Laten we aannemen dat Kostya, Sasha en Lesha één superman zijn. Dan hebben we nog maar achttien vakken. Het aantal permutaties is in dit geval 18 = 6,5 biljard. Met dit alles kunnen Kostya, Sasha en Lesha willekeurig onder elkaar bewegen in hun ondeelbare drie, en dat zijn er nog drie! = 6 opties. Dit betekent dat we in totaal 18 ‘goede’ arrangementen hebben! * 3! Het enige wat we moeten doen is de gewenste waarschijnlijkheid vinden: (18! * 3!) / 20! Dat is ongeveer gelijk aan 0,016. Omgerekend naar percentages blijkt dit slechts 1,6% te zijn.

Accommodatie

Nu zullen we kijken naar een andere zeer belangrijke en noodzakelijke combinatorische formule. Plaatsing is onze volgende kwestie, die we u uitnodigen om in dit gedeelte van het artikel te bespreken. We gaan voor complicaties. Stel dat we mogelijke permutaties willen overwegen, niet uit de hele set (n), maar uit een kleinere set (m). Dat wil zeggen, we overwegen permutaties van n items door m.

De basisformules van de combinatoriek moeten niet alleen uit het hoofd worden geleerd, maar ook worden begrepen. Ook al worden ze ingewikkelder, omdat we niet één parameter hebben, maar twee. Stel dat m = 1, dan A = 1, m = 2, dan A = n * (n - 1). Als we de formule verder vereenvoudigen en overstappen op notatie met behulp van faculteiten, krijgen we een volledig laconieke formule: A = n! / (n - m)!

Combinatie

We hebben bijna alle basiscombinatieformules met voorbeelden beoordeeld. Laten we nu verder gaan laatste fase behandeling van de basiscursus combinatoriek - inleiding tot combinatie. Nu zullen we m items kiezen uit de n die we hebben, en we zullen iedereen kiezen mogelijke manieren. Hoe verschilt dit dan van plaatsing? Wij houden geen rekening met de bestelling. Deze ongeordende set wordt een combinatie.

Laten we onmiddellijk de notatie introduceren: C. We nemen de plaatsing van m ballen uit n. We letten niet meer op de volgorde en eindigen met herhalende combinaties. Om het aantal combinaties te krijgen, moeten we het aantal plaatsingen delen door m! (m faculteit). Dat wil zeggen, C = A / m! Er zijn dus maar een paar manieren om uit n ballen te selecteren, wat ongeveer gelijk is aan het aantal manieren om ze bijna allemaal te selecteren. Dit heeft logische uitdrukking: een beetje kiezen is hetzelfde als bijna alles weggooien. Het is ook belangrijk om op dit punt te vermelden dat het maximale aantal combinaties kan worden bereikt als u de helft van de items probeert te selecteren.

Hoe kies je een formule om een ​​probleem op te lossen?

We hebben de basisformules van de combinatoriek in detail onderzocht: plaatsing, permutatie en combinatie. Nu is het onze taak om de selectie van de noodzakelijke formule voor het oplossen van een combinatorisch probleem te vergemakkelijken. U kunt het volgende vrij eenvoudige schema gebruiken:

1. Vraag jezelf af: wordt er in de tekst van het probleem rekening gehouden met de volgorde waarin de elementen zijn geplaatst?
2. Als het antwoord nee is, gebruik dan de combinatieformule (C = n! / (m! * (n - m)!)).
3. Als het antwoord nee is, moet er nog een vraag worden beantwoord: zijn alle elementen opgenomen in de combinatie?
4. Als het antwoord ja is, gebruik dan de permutatieformule (P = n!).
5. Als het antwoord nee is, gebruik dan de plaatsingsformule (A = n! / (n - m)!).

Voorbeeld

We hebben gekeken naar elementen van combinatoriek, formules en enkele andere kwesties. Laten we nu verder gaan met het echte probleem. Stel je voor dat je een kiwi, een sinaasappel en een banaan voor je hebt.

Vraag één: op hoeveel manieren kunnen ze worden herschikt? Om dit te doen, gebruiken we de permutatieformule: P = 3! = 6 manieren.

Vraag twee: op hoeveel manieren kun je één vrucht kiezen? Dit is duidelijk, we hebben maar drie opties: kies kiwi, sinaasappel of banaan, maar laten we de combinatieformule toepassen: C = 3! / (2! * 1!) = 3.

Vraag drie: op hoeveel manieren kun je twee soorten fruit kiezen? Welke opties hebben we eigenlijk? Kiwi en sinaasappel; kiwi en banaan; sinaasappel en banaan. Dat wil zeggen, er zijn drie opties, maar dit is eenvoudig te controleren met behulp van de combinatieformule: C = 3! / (1! * 2!) = 3

Vraag vier: op hoeveel manieren kun je drie vruchten kiezen? Zoals je kunt zien, is er maar één manier om drie soorten fruit te kiezen: neem kiwi, sinaasappel en banaan. C=3! / (0! * 3!) = 1.

Vraag vijf: op hoeveel manieren kun je minstens één vrucht kiezen? Deze voorwaarde betekent dat we één, twee of alle drie de vruchten kunnen nemen. Daarom voegen we C1 + C2 + C3 = 3 + 3 + 1 = 7 toe. Dat wil zeggen, we hebben zeven manieren om minstens één vrucht van de tafel te nemen.

Combinatoriek is de tak van de wiskunde die zich bezighoudt met de vraag hoeveel combinaties er zijn bepaald type kan uit deze objecten (elementen) worden samengesteld.

Vermenigvuldigingsregel (basisformule van combinatoriek)

Het totale aantal manieren waarop men één element uit elke groep kan selecteren en deze in een bepaalde volgorde kan rangschikken (dat wil zeggen: een geordende set verkrijgen) is gelijk aan:

Voorbeeld 1

Er werd 3 keer met de munt gegooid. Hoeveel verschillende tosresultaten kun je verwachten?

Oplossing

De eerste munt heeft alternatieven: kop of munt. Voor de tweede munt zijn er ook alternatieven enz., nl. .

Vereist aantal manieren:

Toevoegingsregel

Als er twee groepen zijn en niet hebben gemeenschappelijke elementen, dan kan de selectie van één element uit , of uit , ...of uit op verschillende manieren gedaan worden.

Voorbeeld 2

Er staan ​​30 boeken op de plank, waarvan 20 wiskundig, 6 technisch en 4 economisch. Hoeveel manieren zijn er om één wiskundig of één economieboek te kiezen?

Oplossing

Een wiskundeboek kan op verschillende manieren worden geselecteerd, een economieboek op verschillende manieren.

Volgens de somregel is er een manier om een ​​wiskunde- of economieboek te kiezen.

Plaatsingen en herschikkingen

Plaatsingen- Dit zijn geordende verzamelingen elementen die qua samenstelling of volgorde van elementen van elkaar verschillen.

Plaatsingen zonder herhalingen, wanneer het geselecteerde element niet wordt teruggestuurd naar de populatie voordat het volgende wordt geselecteerd. Een dergelijke selectie wordt een sequentiële selectie zonder herhaling genoemd, en het resultaat is een plaatsing zonder herhaling van elementen door .

Het aantal verschillende manieren waarop een opeenvolgende selectie kan worden gemaakt zonder elementen uit de populatie van het volume terug te geven, is gelijk aan:

Voorbeeld 3

Het dagschema bestaat uit 5 verschillende lessen. Bepaal het aantal planningsmogelijkheden bij de keuze uit 11 disciplines.

Oplossing

Elke planningsoptie vertegenwoordigt een set van 5 disciplines uit 11, die zowel qua samenstelling als qua volgorde verschillen van andere opties. Dat is waarom:

Herschikkingen zijn geordende verzamelingen die alleen van elkaar verschillen in de volgorde van hun elementen. Het aantal van alle permutaties van een reeks elementen is gelijk aan

Voorbeeld 4

Op hoeveel manieren kunnen 4 personen aan één tafel zitten?

Oplossing

Elke zitoptie verschilt alleen in de volgorde van de deelnemers, dat wil zeggen, het is een permutatie van 4 elementen:

Plaatsingen met herhalingen, wanneer het geselecteerde element wordt teruggestuurd naar de populatie voordat het volgende wordt geselecteerd. Deze selectie wordt sequentiële selectie met return genoemd, en het resultaat ervan wordt plaatsing met herhalingen van elementen door genoemd.

Het totale aantal verschillende manieren waarop een selectie kan worden gemaakt om elementen uit de volumepopulatie terug te geven, is gelijk aan

Voorbeeld 5

De lift stopt op 7 verdiepingen. Op hoeveel manieren kunnen 6 passagiers in een liftcabine deze verdiepingen verlaten?

Om ervoor te zorgen dat de oplossing voor een probleem in de kansrekening zo nauwkeurig en correct mogelijk is, bestellen velen goedkoop testwerk op deze site. Meer details (hoe een aanvraag indienen, prijzen, deadlines, betaalmethoden) kunt u lezen op de pagina Koop een proefwerk over kansrekening...

Oplossing

Elk van de methoden om passagiers over verdiepingen te verdelen is een combinatie van 6 passagiers over 7 verdiepingen, die zowel qua samenstelling als qua volgorde verschillen van andere combinaties. Omdat één of meerdere passagiers dezelfde verdieping kunnen verlaten, kunnen dezelfde passagiers herhaald worden. Daarom is het aantal van dergelijke combinaties gelijk aan het aantal plaatsingen met herhalingen van 7 elementen van 6:

Combinaties

Combinaties van n elementen per k worden ongeordende verzamelingen genoemd die ten minste één element van elkaar verschillen.

Laat meerdere elementen tegelijk uit de algemene bevolking worden gehaald (of de elementen worden opeenvolgend genomen, maar er wordt geen rekening gehouden met de volgorde van hun verschijning). Als resultaat van een dergelijke gelijktijdige ongeordende selectie van elementen uit de algemene populatie van het volume, worden combinaties verkregen die worden genoemd combinaties zonder herhalingen uit elementen van .

Het aantal combinaties van elementen is gelijk aan:

Voorbeeld 6

Er zitten 9 appels in een doos. Op hoeveel manieren kun jij 3 appels uit een doos selecteren?

Oplossing

Elke keuze bestaat uit 3 appels en verschilt alleen qua samenstelling van de anderen, dat wil zeggen dat het combinaties zijn zonder herhaling van 9 elementen:

Aantal manieren waarop je 3 appels uit 9 kunt kiezen:

Laat elementen één voor één selecteren uit de algemene populatie van het volume, en elk geselecteerd element wordt teruggestuurd naar de algemene populatie voordat het volgende wordt geselecteerd. Dit registreert welke elementen verschenen en hoe vaak, maar houdt geen rekening met de volgorde waarin ze verschenen. De resulterende aggregaten worden genoemd combinaties met herhalingen uit elementen van .

Aantal combinaties met herhalingen van elementen door:

Voorbeeld 7

Het postkantoor verkoopt 3 soorten ansichtkaarten. Op hoeveel manieren kun je 6 ansichtkaarten kopen?

Dit is een taak om het aantal combinaties met herhalingen van 3 tot 6 te vinden:

Een set in groepen verdelen

Laat de set van verschillende elementen is op deze manier in groepen verdeeld, dan bevat de eerste groep elementen, de tweede - elementen, de e groep - elementen, en . Deze situatie wordt het verdelen van de set in groepen genoemd.

Het aantal partities in groepen wanneer elementen in de eerste vallen, elementen in de tweede, elementen in k-de groep- elementen, is gelijk aan:

Voorbeeld 8

Een groep van 16 personen moet in drie subgroepen worden verdeeld, waarvan de eerste uit 5 personen moet bestaan, de tweede uit 7 personen en de derde uit 4 personen. Op hoeveel manieren kan dit gedaan worden?

Oplossing

Hier

Aantal divisies in 3 subgroepen:

Het concept van een geometrische verdelingswet van een discrete willekeurige variabele wordt gepresenteerd en een voorbeeld van het oplossen van het probleem wordt overwogen. Er worden formules gegeven voor de wiskundige verwachting en spreiding van een willekeurige variabele verdeeld volgens een geometrische wet.

Plan:

1. Elementen van combinatoriek.

2. Algemene regels van combinatoriek.

4. Toepassing van grafieken (schema's) bij het oplossen van combinatorische problemen.

1. Combinatoriek en zijn oorsprong.

Combinatoriek is een tak van de wiskunde die vragen bestudeert over hoeveel diverse combinaties kan, onder bepaalde voorwaarden, bestaan ​​uit elementen die tot een bepaalde verzameling behoren.

Combinatoriek ontstond in de 16e eeuw. Gokken (kaarten, dobbelstenen) nam destijds een grote plaats in in het leven van de bevoorrechte lagen van de samenleving. Loterijen waren wijdverbreid. Aanvankelijk betrof het vooral combinatorische problemen gokken: op hoeveel manieren kun je een bepaald aantal punten behalen door met 2 of 3 dobbelstenen te gooien of op hoeveel manieren kun je in sommige gevallen 2 koningen krijgen kaartspel. Deze en andere gokproblemen waren dat wel drijvende kracht in de ontwikkeling van combinatoriek en verder in de ontwikkeling van de waarschijnlijkheidstheorie.

Een van de eersten die het aantal verschillende combinaties bij het dobbelen telde, was de Italiaanse wiskundige Tartaglia. Hij stelde tabellen samen (het aantal manieren waarop k punten op r dobbelstenen konden verschijnen). Hij hield er echter geen rekening mee dat hetzelfde aantal punten kan verschijnen op verschillende manieren, zo bevatten zijn tabellen groot aantal fouten.

De theoretische studie van combinatorische kwesties werd in de 17e eeuw uitgevoerd door de Franse wiskundigen Blaise Pascal en Fermat. Ook gokproblemen waren het uitgangspunt van hun onderzoek.

De verdere ontwikkeling van combinatoriek wordt geassocieerd met de namen van J. Bernoulli, G. Leibniz, L. Euler. In hun werk speelden toepassingen op verschillende games echter een grote rol.

Tegenwoordig worden combinatorische methoden gebruikt om transportproblemen op te lossen, met name planningsproblemen, om productieplannen op te stellen en producten te verkopen, enz.

2. Algemene regels van combinatoriek.

Somregel: Als een object A op m manieren kan worden gekozen, en een object B op k manieren, dan kan het object “A of B” op m + k manieren worden gekozen.

Voorbeelden:

1. Laten we aannemen dat er n verschillend gekleurde ballen in een doos zitten. Er wordt willekeurig 1 bal uitgenomen. Op hoeveel manieren kan dit gedaan worden?

Antwoord: n manieren.

Laten we deze n ballen in twee dozen verdelen: de eerste bevat m ballen, de tweede bevat k ballen. Er wordt willekeurig 1 bal uit een willekeurig geselecteerde doos getrokken. Op hoeveel manieren kan dit gedaan worden?

Oplossing: De bal kan op m manieren uit het eerste vak worden verwijderd, en op k manieren uit het tweede. Dan is het totaal aantal manieren m+k=n.

2. Mariene seinpaal.

In de maritieme semafoor komt elke letter van het alfabet overeen met een bepaalde positie van twee vlaggen ten opzichte van het lichaam van de seingever. Hoeveel van zulke signalen kunnen er zijn?

Oplossing: Het totale aantal is de som van de posities wanneer beide vlaggen zich aan weerszijden van het lichaam van de seingever bevinden, en de posities wanneer ze zich aan dezelfde kant van het lichaam van de seingever bevinden. Bij het tellen van het aantal mogelijke posities wordt de somregel toegepast.

Productregel: Als object A op m manieren kan worden geselecteerd, en na elke dergelijke keuze een ander object B kan worden geselecteerd (ongeacht de keuze van object A) op k manieren, dan kunnen paren objecten “A en B” worden geselecteerd in m * k manieren.

Voorbeelden:

1. Hoeveel tweecijferige getallen zijn er?

Oplossing: Het aantal tientallen kan worden aangegeven met een willekeurig getal van 1 tot en met 9. Het aantal enen kan worden aangegeven met een getal van 0 tot en met 9. Als het aantal tientallen 1 is, dan kan het aantal enen een willekeurig getal zijn (van 0 tot 9). tot 9). Er zijn dus tien getallen van twee cijfers, waarbij het aantal tientallen 1 is. We redeneren op dezelfde manier voor elk ander aantal tientallen. Dan kunnen we berekenen dat het er 9 zijn *10 = 90 tweecijferige getallen.

2. Er zijn 2 lades. Eén bevat m veelkleurige kubussen en de andere bevat k veelkleurige ballen. Op hoeveel manieren kun je het “Cube-Ball”-paar kiezen?

Oplossing: De keuze van de bal is niet afhankelijk van de keuze van de kubus, en omgekeerd. Daarom is het aantal manieren waarop een bepaald paar kan worden geselecteerd m*k.

3. Populatie zonder herhaling en steekproef zonder herhaling.

Bevolking zonder herhalingen is een verzameling van een eindig aantal verschillende elementen a 1, a 2, a 3, ..., a n.

Voorbeeld: Set van n veelkleurige stukjes.

Bemonsteringsvolumek (kN) is een groep van m elementen van een gegeven populatie.

Voorbeeld: Een bont lint genaaid uit m veelkleurige restjes geselecteerd uit de gegeven n .

Berichten vann elementen elkk Dergelijke monsters worden monsters genoemd die elk k elementen bevatten, geselecteerd uit de gegeven n elementen van de algemene bevolking zonder herhaling, en van elkaar verschillen, hetzij in de samenstelling van de elementen, hetzij in de volgorde van hun rangschikking.

- aantal plaatsingen vanaf n door k.

Aantal plaatsingen vanaf n door k kan op de volgende manier worden bepaald: het eerste selectieobject kan worden geselecteerd N manieren, dan kan het tweede object worden geselecteerd n -1 manier, enz.

Als we deze formule transformeren, hebben we:

Dat mag niet worden vergeten 0!=1.

Voorbeelden:

1. Er nemen 17 teams deel aan de eerste klasse A-groep van het voetbalkampioenschap. Er worden medailles uitgereikt: goud, zilver en brons. Op hoeveel manieren kunnen ze gespeeld worden?

Oplossing:De winnende teamcombinaties verschillen van elkaar in de samenstelling en volgorde van de elementen, d.w.z. zijn plaatsingen van 17 tot en met 3.

2. De wetenschappelijke vereniging bestaat uit 25 personen. Het is noodzakelijk om een ​​voorzitter, een vice-voorzitter, een wetenschappelijk secretaris en een penningmeester van de vereniging te kiezen. Op hoeveel manieren kan dit gedaan worden?

Oplossing: Combinaties van het managementteam van een bedrijf verschillen van elkaar in de samenstelling en volgorde van elementen, d.w.z. zijn plaatsingen van 25 tot en met 4.

Permutaties zonder herhalingen van Nelementenworden plaatsingen zonder herhalingen genoemd n elementen van n , d.w.z. plaatsingen verschillen alleen van elkaar in de volgorde van de elementen.

Aantal permutaties.

Voorbeelden:

1. Hoeveel verschillende vijfcijferige getallen kunnen worden gemaakt uit de cijfers 1, 2, 3, 4, 5, op voorwaarde dat ze uit verschillende cijfers moeten bestaan?

Oplossing:We hebben permutaties van 5 elementen.2. Op hoeveel manieren kun jij 6 veelkleurige restjes samenvoegen tot een kleurrijk lint?
Oplossing:We hebben permutaties van 6 elementen.

Combinaties zonder herhalingen uit Nelementen doork Dergelijke monsters worden monsters genoemd die elk k elementen bevatten, geselecteerd uit de gegeven n elementen van de algemene bevolking zonder herhaling, en verschillen alleen van elkaar in de samenstelling van de elementen.

- aantal combinaties van n door k

Elementen van elkcombinaties zijn mogelijkmanieren. DanVoorbeelden:

1. Als twintig mensen deelnemen aan de halve finale van een schaakkampioenschap en er slechts drie de finale bereiken, op hoeveel manieren kunnen deze drie dan worden bepaald?

Oplossing:In dit geval is de volgorde waarin deze triple zich bevindt niet significant. Daarom zijn de drielingen die de finale bereikten combinaties van 20 bij 3.

2. Op hoeveel manieren kunt u drie afgevaardigden uit tien personen selecteren voor een conferentie?

Oplossing:In dit geval is de volgorde waarin deze triple zich bevindt niet significant. Daarom zijn drietallen afgevaardigden combinaties van 10 bij 3.

Abstract:

4.Gebruik van grafieken (schema's) bij het oplossen van combinatorische problemen.

In het geval dat het aantal mogelijke keuzes bij elke stap afhangt van welke elementen eerder zijn geselecteerd, kan het proces van het samenstellen van combinaties worden weergegeven als een ‘boom’. Teken eerst zoveel segmenten vanaf één punt als diverse verkiezingen kan in de eerste stap worden gedaan. Teken vanaf het einde van elk segment zoveel segmenten als er bij de tweede stap kunnen worden geselecteerd, als dit element bij de eerste stap is geselecteerd, enz.

Taak:

Bij het samenstellen van teams ruimteschip Er wordt ook rekening gehouden met de kwestie van de psychologische compatibiliteit van reisdeelnemers. Het is noodzakelijk om een ​​ruimteschipbemanning van 3 personen te vormen: een commandant, een ingenieur en een arts. Er zijn 4 kandidaten voor de positie van commandant: een 1, een 2, een 3, een 4 .In plaats van machinist 3:b1, b2, b3. Voor doktersplaats - 3: c 1, c 2, c 3. Uit de inspectie bleek dat de commandanta 1 is psychologisch compatibel met ingenieurs b 1 en b 3 en artsen c 1 en c 3. Commandant een 2 - met ingenieurs b1 en b2. en alle dokters. Commandanteen 3 - met ingenieursb1 en b2 en artsenc1 en c3. Commandant een 4 - met alle ingenieurs en de dokter c 2 . Daarnaast ingenieurb 1 niet compatibel met arts c 3, b 2 - met een arts c1 en b 3 - met een arts c 2. Op hoeveel manieren kan de bemanning van het schip onder deze omstandigheden worden samengesteld?

Oplossing:

Laten we de overeenkomstige “boom” maken.

Antwoord: 10 combinaties.

Zo'n boom is een grafiek en wordt gebruikt om combinatorische problemen op te lossen.

Laten we het aantal permutaties van n elementen in MS EXCEL tellen. Met behulp van formules geven we op het blad alle permutatieopties weer ( Engelse vertaling term: permutatie).

Een permutatie van een reeks van n elementen is de rangschikking van elementen in een bepaalde volgorde.

De elementen van een set kunnen cijfers, letters en andere objecten in het algemeen zijn. Het belangrijkste is dat deze elementen verschillend zijn. Omdat Elk object kan aan een getal worden gekoppeld. Voor permutaties wordt gewoonlijk een eindige reeks gehele getallen gebruikt, bijvoorbeeld (1; 2; 3; 4; 5). Al zijn lettersets ook vaak terug te vinden in de literatuur. Alle verschillende permutaties van een set van drie elementen (a, b, c) zijn dat bijvoorbeeld abc, acb, terug, bca, taxi, cba.

Het aantal permutaties van n elementen is n! (faculteit).

Om de faculteit in MS EXCEL te berekenen is er een functie =FACT(), de Engelse versie van FACT(). Het is duidelijk dat het aantal permutaties zeer snel groeit met n: voor n=7 is het aantal permutaties 5040. In alle eerlijkheid moet worden opgemerkt dat de permutatie-opties zelf vaak niet hoeven te worden gevonden, het belangrijkste is om vind hun nummer.

Opmerking: Permutaties kunnen worden beschouwd als een speciaal geval van plaatsingen voor n=k (zie artikel). Daarom kunt u de functie REST() gebruiken om het aantal permutaties te berekenen. Voor n=7 wordt het aantal permutaties berekend met de formule = PERMANENT(7,7)

Opmerking: Je kunt lezen over permutaties met herhalingen (waarbij elementen worden teruggezet naar de set waaruit ze zijn gehaald nadat je elk element hebt geselecteerd).

Gemaakt in het voorbeeldbestand universele formule om alle permutaties voor een gegeven n weer te geven. Bijvoorbeeld voor n=3.

Taak

6 auto's verschillend merken nemen deel aan survivalraces: LADA Granta, Hyundai Solaris, KIA Rio, Renault Duster, Lada Kalina, Volkswagen Polo. Bepaal het aantal mogelijke opties voor het verdelen van zetels onder alle deelnemers.

We moeten het aantal permutaties van 6 auto's op 6 plaatsen bepalen. Die. n=6. Het blijkt dat er 720 van dergelijke permutaties zijn: =PREST(6,6) of 6! =FEIT(6)

Laten we het voorbeeldbestand gebruiken om alle permutaties te vinden.

Laten we numerieke waarden willekeurig vergelijken met automerken en afkortingen maken voor merknamen: LADA Granta (LG=1), Hyundai Solaris (HS=2), ...

Door een cel in te typen B5 waarde 6, we zullen alle opties bepalen voor het plaatsen van auto's op de plaatsen die ze in de race innamen.

Opmerking: Je kunt lezen over plaatsingen in het artikel, en over combinaties in het artikel.

Opsomming van alle mogelijke permutaties kan nodig zijn om verschillende problemen op te lossen (zie artikel en).

Inversies van permutaties

Voor elke permutatie A 1, A 2, A 3,..., A n van N gehele getallen 1, 2, 3, ..., N, de inversie is het paar ( A i, A j) als voor i< j выполняется A ik> A J. Het omgekeerde getal in een permutatie laat zien hoe "ongesorteerd" de permutatie is in oplopende volgorde.

Het aantal inversies in de permutatie 1, 2, 3, 4 is bijvoorbeeld 0 (een permutatie van 4 gehele getallen wordt gesorteerd in oplopende volgorde van 1 naar 4), en het aantal inversies in de permutatie 4, 3, 1, 2 is 5, omdat.:

• het eerste element (i=1) is 4 en is groter 3 getallen (met j=2, 3, 4), die zich aan de rechterkant bevinden (4>3, 4>1, 4>2), d.w.z. we hebben 3 inversies;
• het tweede element (i=2) is 3 en is groter 2 getallen (met j=3, 4) die zich rechts bevinden (3>1, 3>2), d.w.z. we hebben nog 2 inversies;
• dus het derde element (i=3) is gelijk aan 1 en it minder aantal met j=4, die zich aan de rechterkant bevindt (1<2), то эта пара не является инверсией. Т.е. у перестановки 4, 3, 1, 2 число инверсий равно 3+2+0=5.

In het voorbeeldbestand wordt voor elke permutatie het getal berekend door inversie.

Om het materiaal gemakkelijker te navigeren te maken, zal ik de inhoud van dit onderwerp toevoegen:

Invoering. Sets en selecties.

In dit onderwerp zullen we kijken naar de basisconcepten van combinatoriek: permutaties, combinaties en plaatsingen. Laten we hun essentie en formules ontdekken waarmee u hun hoeveelheid kunt vinden.

Om te werken hebben we wat aanvullende informatie nodig. Laten we beginnen met zo'n fundamenteel wiskundig concept als een set. Het concept van een set werd in detail besproken in het onderwerp "Het concept van een set. Methoden voor het specificeren van sets".

Een heel kort verhaal over de menigte: toon\verberg

Kortom: een set is een verzameling objecten. Schrijf sets tussen accolades. De volgorde waarin de elementen zijn geschreven doet er niet toe; herhalingen van elementen zijn niet toegestaan. De reeks cijfers van het getal 11115555999 is bijvoorbeeld: $\(1,5,9\)$. De reeks medeklinkers in het woord "tijgerwelp" is: $\(t, g, r, n, k\)$. De notatie $5\in A$ betekent dat element 5 tot de verzameling $A=\(1,5,9 \)$ behoort. Het aantal elementen in een eindige verzameling wordt genoemd stroom van deze set en duidt $|A|$ aan. Voor een set $A=\(1,5,9 \)$ die 3 elementen bevat, geldt bijvoorbeeld: $|A|=3$.

Beschouw een bepaalde niet-lege eindige verzameling $U$, waarvan de kardinaliteit $n$, $|U|=n$ is (d.w.z. de verzameling $U$ heeft $n$ elementen). Laten we een concept introduceren als steekproef(sommige auteurs noemen het een tuple). Met een monster van volume $k$ uit $n$ elementen (afgekort als $(n,k)$-sample) bedoelen we een set elementen $(a_1, a_2,\ldots, a_k)$, waarbij $a_i\in U$. Een selectie wordt geordend genoemd als de volgorde van de elementen ervan is opgegeven. Twee geordende monsters die alleen verschillen in de volgorde van de elementen zijn verschillend. Als de volgorde van de steekproefelementen niet significant is, wordt de steekproef ongeordend genoemd.

Merk op dat de definitie van een selectie niets zegt over elementherhalingen. In tegenstelling tot set-elementen kunnen selectie-elementen worden herhaald.

Beschouw bijvoorbeeld de verzameling $U=\(a,b,c,d,e\)$. De set $U$ bevat 5 elementen, d.w.z. $|U|=5$. Een voorbeeld zonder herhalingen zou kunnen zijn: $(a,b,c)$. Deze selectie bevat 3 elementen, nl. de omvang van deze steekproef is 3. Met andere woorden, het is een $(5,3)$-steekproef.

Een voorbeeld met herhalingen kan er als volgt uitzien: $(a,a,a,a,a,c,c,d)$. Het bevat 8 elementen, d.w.z. het volume is 8. Met andere woorden, dit is een $(5,8)$-steekproef.

Laten we nog twee $(5,3)$-voorbeelden bekijken: $(a,b,b)$ en $(b,a,b)$. Als we aannemen dat onze monsters ongeordend zijn, dan is het monster $(a,b,b)$ gelijk aan het monster $(b,a,b)$, d.w.z. $(a,b,b)=(b,a,b)$. Als we ervan uitgaan dat onze monsters zijn besteld, dan is $(a,b,b)\neq(b,a,b)$.

Laten we naar een ander voorbeeld kijken, iets minder abstract:) Stel dat er zes snoepjes in een mandje zitten, en ze zijn allemaal verschillend. Als we het eerste snoepje associëren met nummer 1, het tweede snoepje met nummer 2, enzovoort, dan kan de volgende set worden geassocieerd met de snoepjes in het mandje: $U=\(1,2,3,4, 5,6\)$. Stel je voor dat we willekeurig onze hand in een mand steken om er drie snoepjes uit te halen. De uitgetrokken snoepjes zijn de selectie. Omdat we 3 van de 6 snoepjes nemen, krijgen we een (6,3)-monster. De volgorde waarin de snoepjes in de handpalm worden geplaatst, is volkomen irrelevant, dus dit monster is ongeordend. Nou, en aangezien alle snoepjes verschillend zijn, is de selectie zonder herhaling. In deze situatie hebben we het dus over een ongeordende (6,3)-steekproef zonder herhalingen.

Laten we nu vanaf de andere kant naderen. Laten we ons voorstellen dat we ons in een snoepfabriek bevinden, en deze fabriek produceert vier soorten snoep. De set $U$ in deze situatie is als volgt: $U=\(1,2,3,4 \)$ (elk getal is verantwoordelijk voor zijn eigen soort snoep). Laten we ons nu voorstellen dat al het snoep in één enkele goot wordt gegoten, vlakbij waar we staan. En terwijl we onze handpalmen plaatsen, selecteren we 20 snoepjes uit deze stroom. Een handvol snoepjes is een voorbeeld. Is de volgorde waarin de snoepjes in een handvol worden geplaatst, van belang? Natuurlijk niet, dus het monster is ongeordend. Er zijn slechts 4 soorten snoep en we selecteren twintig stuks uit de algemene stroom - herhaling van variëteiten is onvermijdelijk. Tegelijkertijd kunnen de monsters heel verschillend zijn: het kan zelfs zijn dat we alle snoepjes van hetzelfde type hebben. In deze situatie hebben we dus te maken met een ongeordende (4,20)-steekproef met herhalingen.

Laten we nog een paar voorbeelden bekijken. Laat verschillende 7 letters op de kubussen schrijven: k, o, n, f, e, t, a. Deze letters vormen de verzameling $U=\(k,o,n,f,e,t,a\)$. Laten we zeggen dat we van deze kubussen “woorden” van 5 letters willen maken. De letters van deze woorden (bijvoorbeeld “konfe”, “tenko” enzovoort) vormen (7,5)-selecties: $(k,o,n,f,e)$, $(t,e,n ,k ,o)$, enz. Uiteraard is de volgorde van de letters in zo’n voorbeeld belangrijk. De woorden "nokft" en "kfton" zijn bijvoorbeeld verschillend (hoewel ze uit dezelfde letters bestaan), omdat de volgorde van de letters daarin niet overeenkomt. Er zijn geen herhalingen van letters in dergelijke "woorden", omdat er slechts zeven kubussen zijn. De reeks letters van elk woord is dus een geordend (7,5)-voorbeeld zonder herhalingen.

Nog een voorbeeld: van de vier cijfers 1, 5, 7, 8 maken we allerlei achtcijferige getallen. Bijvoorbeeld 11111111, 15518877, 88881111 enzovoort. De verzameling $U$ is: $U=\(1,5,7,8\)$. De cijfers van elk samengesteld getal vormen een (4,8)-monster. De volgorde van de cijfers in een getal is belangrijk, d.w.z. het monster is besteld. Herhalingen zijn toegestaan, dus we hebben hier te maken met een geordend (4,8)-monster met herhalingen.

Plaatsingen zonder herhalingen van $n$ elementen door $k$

Plaatsing zonder herhalingen van $n$ elementen door $k$ - geordende $(n,k)$-selectie zonder herhalingen.

Omdat de elementen in de betreffende sample niet kunnen worden herhaald, kunnen we niet meer elementen in de sample selecteren dan er in de originele set zitten. Daarom geldt voor dergelijke monsters de volgende ongelijkheid: $n≥ k$. Het aantal plaatsingen zonder herhalingen van $n$ elementen door $k$ wordt bepaald door de volgende formule:

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

Wat betekent het "!"-teken?: toon\verberg

Opname "n!" (lees "en factorial") geeft het product aan van alle getallen van 1 tot n, d.w.z.

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

Per definitie wordt aangenomen dat $0!=1!=1$. Laten we bijvoorbeeld 5 vinden!:

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

Voorbeeld nr. 1

Het alfabet bestaat uit een reeks symbolen $E=\(+,*,0,1,f\)$. Laten we het aantal van zulke woorden van drie tekens in dit alfabet bepalen die geen herhalende letters bevatten.

Met woorden van drie tekens bedoelen we uitdrukkingen als “+*0” of “0f1”. De verzameling $E$ heeft vijf elementen, dus de letters van woorden van drie tekens vormen (5,3)-selecties. De eerste vraag is: zijn deze monsters besteld of niet? Woorden die alleen verschillen in de volgorde van hun letters worden als verschillend beschouwd, dus de volgorde van de elementen in het voorbeeld is belangrijk. Dit betekent dat het monster is besteld. Tweede vraag: zijn herhalingen toegestaan ​​of niet? Het antwoord op deze vraag wordt gegeven door de voorwaarde: woorden mogen geen herhalende letters bevatten. Samenvattend: de letters van elk woord dat aan de voorwaarden van het probleem voldoet, vormen een geordend (5,3)-voorbeeld zonder herhalingen. Met andere woorden, de letters van elk woord vormen een plaatsing zonder herhaling van 5 elementen van 3. Hier zijn voorbeelden van dergelijke plaatsingen:

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

Wij zijn geïnteresseerd in het totaal aantal van deze plaatsingen. Volgens formule (1) zal het aantal plaatsingen zonder herhalingen van 5 elementen van 3 als volgt zijn:

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

Die. je kunt 60 woorden van drie tekens maken, waarvan de letters niet worden herhaald.

Antwoord: 60.

Plaatsingen met herhalingen van $n$ elementen van $k$

Plaatsing met herhalingen van $n$ elementen door $k$ - geordende $(n,k)$-selectie met herhalingen.

Het aantal plaatsingen met herhalingen van $n$ elementen van $k$ wordt bepaald door de volgende formule:

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

Voorbeeld nr. 2

Hoeveel getallen van vijf cijfers kunnen worden gemaakt uit de reeks cijfers $\(5,7,2\)$?

Uit deze reeks getallen kunt u de vijfcijferige getallen 55555, 75222, enzovoort maken. De cijfers van elk dergelijk getal vormen een (3,5)-steekproef: $(5,5,5,5,5)$, $(7,5,2,2,2)$. Laten we ons de vraag stellen: wat voor soort monsters zijn dit? Ten eerste kunnen cijfers in getallen worden herhaald, dus we hebben te maken met voorbeelden met herhalingen. Ten tweede is de volgorde van de cijfers in een getal belangrijk. 27755 en 77255 zijn bijvoorbeeld verschillende nummers. We hebben dus te maken met geordende (3,5)-monsters met herhalingen. We vinden het totale aantal van dergelijke monsters (d.w.z. het totale aantal vereiste vijfcijferige getallen) met behulp van formule (2):

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

Daarom kunnen uit de gegeven cijfers 243 vijfcijferige getallen worden gemaakt.

Antwoord: 243.

Permutaties zonder herhalingen van $n$ elementen

Een permutatie zonder herhalingen van $n$ elementen is een geordende $(n,n)$-selectie zonder herhalingen.

In wezen is permutatie zonder herhaling een speciaal geval van plaatsing zonder herhaling, wanneer de steekproefomvang gelijk is aan de kardinaliteit van de originele set. Het aantal permutaties zonder herhaling van $n$-elementen wordt bepaald door de volgende formule:

\begin(vergelijking)P_(n)=n! \einde(vergelijking)

Deze formule is trouwens gemakkelijk te verkrijgen als je bedenkt dat $P_n=A_(n)^(n)$. Dan krijgen we:

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

Voorbeeld nr. 3

Er liggen vijf porties ijs van verschillende bedrijven in de vriezer. Op hoeveel manieren kun je de volgorde kiezen waarin ze worden gegeten?

Laat het getal 1 overeenkomen met het eerste ijsje, het getal 2 met het tweede, enzovoort. We krijgen de set $U=\(1,2,3,4,5\)$, die de inhoud van de vriezer vertegenwoordigt. De volgorde van eten kan als volgt zijn: $(2,1,3,5,4)$ of als volgt: $(5,4,3,1,2)$. Elke set is een (5,5)-monster. Het zal ordelijk en zonder herhaling zijn. Met andere woorden, elk monster is een permutatie van vijf elementen van de originele set. Volgens formule (3) is het totale aantal van deze permutaties als volgt:

$$ P_5=5!=120. $$

Bijgevolg zijn er 120 bestellingen voor het kiezen van de volgorde van eten.

Antwoord: 120.

Permutaties met herhalingen

Permutatie met herhalingen is een geordende $(n,k)$-steekproef met herhalingen, waarbij element $a_1$ $k_1$ keer wordt herhaald, $a_2$ $k_2$ keer wordt herhaald, enzovoort, tot het laatste element $ a_r$, wat $ k_r$ keer wordt herhaald. In dit geval $k_1+k_2+\ldots+k_r=k$.

Het totale aantal permutaties met herhalingen wordt bepaald door de formule:

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

Voorbeeld nr. 4

Woorden zijn samengesteld op basis van het alfabet $U=\(a,b,d\)$. Hoeveel verschillende woorden kunnen er uit zeven karakters bestaan ​​als in deze woorden de letter “a” twee keer herhaald moet worden; de letter "b" - 1 keer, en de letter "d" - 4 keer?

Hier zijn voorbeelden van zoekwoorden: "aabdddd", "daddabd" enzovoort. De letters van elk woord vormen een (3,7)-voorbeeld met herhalingen: $(a,a,b,d,d,d,d)$, $(d,a,d,d,a,b,d )$ en enz. Elk dergelijk monster bestaat uit twee elementen "a", één element "b" en vier elementen "d". Met andere woorden: $k_1=2$, $k_2=1$, $k_3=4$. Het totale aantal herhalingen van alle symbolen is uiteraard gelijk aan de steekproefomvang, d.w.z. $k=k_1+k_2+k_3=7$. Als we deze gegevens in formule (4) vervangen, krijgen we:

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

Het totale aantal zoekwoorden is dus 105.

Antwoord: 105.

Combinaties zonder herhalingen van $n$ elementen van elk $k$

Een combinatie zonder herhalingen van $n$ elementen door $k$ is een ongeordende $(n,k)$-sample zonder herhalingen.

Het totale aantal combinaties zonder herhalingen van $n$ elementen van $k$ wordt bepaald door de formule:

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

Voorbeeld nr. 5

Het mandje bevat kaarten met gehele getallen van 1 tot en met 10. Er worden 4 kaarten uit het mandje gehaald en de daarop geschreven cijfers worden opgeteld. Hoeveel verschillende sets kaarten kunnen uit het mandje worden getrokken?

In dit probleem is de initiële set dus: $U=\(1,2,3,4,5,6,7,8,9,10\)$. Uit deze set selecteren we vier elementen (d.w.z. vier kaarten uit het mandje). De nummers van de uitgetrokken elementen vormen een (10,4)-selectie. Herhalingen in deze selectie zijn niet toegestaan, omdat de nummers van alle kaarten verschillend zijn. De vraag is: doet de volgorde waarin kaarten worden geselecteerd er toe of niet? Dat wil zeggen: zijn de monsters $(1,2,7,10)$ en $(10,2,1,7)$ gelijk of niet gelijk? Hier moet u zich wenden tot de omstandigheden van het probleem. De kaarten worden eruit gehaald om later de som van de elementen te vinden. Dit betekent dat de volgorde van de kaarten niet belangrijk is, omdat het veranderen van de plaats van de termen de som niet zal veranderen. Het monster $(1,2,7,10)$ en het monster $(10,2,1,7)$ komen bijvoorbeeld overeen met hetzelfde getal $1+2+7+10=10+2+1+ 7 = $ 20. Conclusie: uit de omstandigheden van het probleem volgt dat we te maken hebben met ongeordende monsters. Die. we moeten het totale aantal ongeordende (10,4) monsters zonder herhalingen vinden. Met andere woorden, we moeten het aantal combinaties van 10 elementen van 4 vinden. We gebruiken hiervoor formule (5):

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

Daarom is het totale aantal doorzochte sets 210.

Antwoord: 210.

Combinaties met herhalingen van $n$ elementen van elk $k$

Een combinatie met herhalingen van $n$ elementen van $k$ is een ongeordende $(n,k)$-sample met herhalingen.

Het totale aantal combinaties met herhalingen van $n$ elementen van $k$ wordt bepaald door de formule:

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

Voorbeeld nr. 6

Stel je voor dat we bij een snoepfabriek staan, vlak naast een lopende band waarlangs vier soorten snoep bewegen. We steken onze handen in deze stroom en trekken er twintig stukken uit. Hoeveel verschillende “snoepjescombinaties” kunnen er in een handvol zitten?

Als we aannemen dat het eerste type overeenkomt met het getal 1, het tweede type - het getal 2, enzovoort, dan is de initiële set in ons probleem als volgt: $U=\(1,2,3,4\) $. Uit deze set selecteren we 20 elementen (dat wil zeggen, diezelfde 20 snoepjes van de lopende band). Een handvol snoepjes vormt een (4,20)-monster. Uiteraard zullen er herhalingen van variëteiten zijn. De vraag is: doet de volgorde van de elementen in het monster er toe of niet? Uit de omstandigheden van het probleem volgt dat de volgorde waarin de elementen zijn gerangschikt er niet toe doet. Het maakt voor ons geen verschil of het handje eerst 15 lolly's bevat, en dan 4 chocoladesnoepjes, of eerst 4 chocoladesnoepjes, en dan pas 15 lolly's. We hebben dus te maken met een ongeordende (4,20) steekproef met herhalingen. Om het totale aantal van deze monsters te vinden, gebruiken we formule (6):

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

Het totaal aantal gezochte combinaties bedraagt ​​dus 1771.