Ez a cikk a matematika egy speciális szakaszára, a kombinatorikára összpontosít. Képletek, szabályok, példák a problémamegoldásra – mindezt itt megtalálod, ha elolvasod a cikket a végéig.
Szóval, mi ez a rész? A kombinatorika bármely objektum megszámlálásának kérdésével foglalkozik. De ebben az esetben a tárgyak nem szilva, körte vagy alma, hanem valami más. A kombinatorika segít megtalálni egy esemény valószínűségét. Például kártyázáskor mekkora a valószínűsége annak, hogy az ellenfélnek van ütőkártyája? Vagy egy ilyen példa - mekkora a valószínűsége annak, hogy egy húsz golyós zacskóból pontosan fehér lesz? Az ilyen jellegű feladatokhoz tudnunk kell legalább az alapokat a matematika ezen részéből.
Kombinatorikus konfigurációk
A kombinatorika alapfogalmait és képleteit tekintve nem tudunk mást, mint figyelmet fordítani a kombinatorikus konfigurációkra. Nemcsak megfogalmazásra, hanem különféle kombinatorikai problémák megoldására is használják. Példák az ilyen modellekre:
- elhelyezés;
- permutáció;
- kombináció;
- számösszetétel;
- osztott szám.
Az első háromról később részletesebben is szó lesz, de ebben a részben a kompozícióra és a felosztásra is figyelünk. Amikor egy bizonyos szám (mondjuk a a) összetételéről beszélnek, az a számnak néhány pozitív szám rendezett összegeként való ábrázolását értik. A felosztás pedig egy rendezetlen összeg.
Sections
Mielőtt közvetlenül a kombinatorika képleteire és a feladatok mérlegelésére térnénk, érdemes odafigyelni arra, hogy a kombinatorikának a matematika többi részéhez hasonlóan megvannak a maga alfejezetei. Ezek a következők:
- felsoroló;
- strukturális;
- extrém;
- Ramsey-elmélet;
- valószínűségi;
- topológiai;
- végtelen.
Az első esetben felsoroló kombinatorikáról beszélünk, a problémák a halmazok elemei által alkotott különböző konfigurációk felsorolását vagy megszámlálását jelentik. Ezekre a halmazokra általában bizonyos korlátozások vonatkoznak (megkülönböztethetőség, megkülönböztethetőség, ismétlés lehetősége stb.). És ezeknek a konfigurációknak a számát az összeadás vagy szorzás szabályával számítjuk ki, amelyről egy kicsit később fogunk beszélni. A strukturális kombinatorika magában foglalja a gráfok és a matroidok elméleteit. Egy extremális kombinatorikai probléma például az, hogy mi a gráf legnagyobb dimenziója, amely kielégíti a következő tulajdonságokat… A negyedik bekezdésben megemlítettük a Ramsey-elméletet, amely a szabályos struktúrák véletlen konfigurációkban való jelenlétét vizsgálja. ValószínűségiA kombinatorika képes megválaszolni a kérdést - mekkora a valószínűsége annak, hogy egy adott halmaznak van egy bizonyos tulajdonsága. Ahogy sejthető, a topológiai kombinatorika módszereket alkalmaz a topológiában. És végül a hetedik pont – a végtelen kombinatorika a kombinatorikai módszerek végtelen halmazokra való alkalmazását vizsgálja.
Hozzáadási szabály
A kombinatorika képletei között találhatunk egészen egyszerűeket is, amelyeket már régóta ismerünk. Példa erre az összegszabály. Tegyük fel, hogy kapunk két cselekvést (C és E), ha ezek kölcsönösen kizárják egymást, a C művelet többféleképpen is elvégezhető (például a), az E művelet pedig b-módon, akkor bármelyik (C) vagy E) a + b módon végezhető el.
Elméletileg ezt elég nehéz megérteni, megpróbáljuk egy egyszerű példával átadni a lényeget. Vegyük egy osztály átlagos tanulólétszámát – mondjuk ez huszonöt. Köztük tizenöt lány és tíz fiú. Naponta egy kísérőt osztanak ki az osztályba. Hányféleképpen lehet ma osztálykísérőt kijelölni? A probléma megoldása meglehetősen egyszerű, az összeadás szabályához fogunk folyamodni. A feladat szövegében nem szerepel, hogy csak fiúk vagy csak lányok lehetnek szolgálatban. Ezért a tizenöt lány vagy a tíz fiú bármelyike lehet. Az összegszabályt alkalmazva egy meglehetősen egyszerű példát kapunk, amellyel egy általános iskolás könnyen megbirkózik: 15 + 10. Kiszámolva azt a választ kapjuk, hogy huszonöt. Vagyis csak huszonöt út létezikrendeljen egy szolgálati órát a mai napra.
Szorzási szabály
A szorzás szabálya is a kombinatorika alapképletei közé tartozik. Kezdjük az elmélettel. Tegyük fel, hogy több műveletet kell végrehajtanunk (a): az első műveletet 1 módon hajtjuk végre, a másodikat 2 módon, a harmadikat 3 módon, és így tovább, amíg az utolsó a-műveletet ugyanazon módon hajtjuk végre. Ekkor mindezek a műveletek (amelyekből összesen van) N módon hajthatók végre. Hogyan számítsuk ki az ismeretlen N-t? A képlet segít nekünk ebben: N \u003d c1c2c3…ca.
Még egyszer, elméletben semmi sem világos, térjünk át a szorzási szabály alkalmazásának egyszerű példájára. Vegyük ugyanazt a huszonöt fős osztályt, amelyben tizenöt lány és tíz fiú tanul. Csak ezúttal két kísérőt kell választanunk. Lehetnek csak fiúk vagy lányok, vagy fiúk egy lánnyal. Rátérünk a probléma elemi megoldására. Az első kísérőt választjuk, ahogy az utolsó bekezdésben eldöntöttük, huszonöt lehetséges lehetőséget kapunk. A második ügyeletes személy a megmaradt személyek közül bármelyik lehet. Huszonöt tanulónk volt, egyet választottunk, ami azt jelenti, hogy a maradék huszonnégy emberből bárki lehet a második ügyeletes. Végül alkalmazzuk a szorzási szabályt, és megállapítjuk, hogy a két kísérő hatszázféleképpen választható ki. Ezt a számot huszonöt és huszonnégy szorzatával kaptuk.
Csere
Most megvizsgálunk még egy kombinatorikai képletet. A cikk ezen részében miBeszéljünk a permutációkról. Azonnal vizsgálja meg a problémát egy példával. Vegyünk biliárdlabdákat, van belőlük n-edik szám. Ki kell számolnunk: hány lehetőség van sorba rendezni, azaz rendezett készletet készíteni.
Kezdjük, ha nincs labdánk, akkor nulla elhelyezési lehetőségünk is van. Ha pedig egy labdánk van, akkor az elrendezés is ugyanaz (matematikailag ez a következőképpen írható fel: Р1=1). Két golyót kétféleképpen lehet elhelyezni: 1, 2 és 2, 1. Ezért Р2=2. Három golyót hatféleképpen lehet elhelyezni (Р3=6): 1, 2, 3; 1, 3, 2; 2, 1, 3; 2, 3, 1; 3, 2, 1; 3, 1, 2. És ha nem három ilyen golyó van, hanem tíz vagy tizenöt? Az összes lehetséges opció felsorolása nagyon hosszú, akkor a kombinatorika jön a segítségünkre. A permutációs képlet segít megtalálni a választ kérdésünkre. Pn=nP(n-1). Ha megpróbáljuk leegyszerűsíteni a képletet, a következőt kapjuk: Pn=n (n - 1) … 21. Ez pedig az első természetes számok szorzata. Az ilyen számot faktoriálisnak nevezzük, és n-nek jelöljük!
Vegyük fontolóra a problémát. A vezető minden reggel sorban építi fel különítményét (húsz fő). Három legjobb barát van a különítményben - Kostya, Sasha és Lesha. Mennyi a valószínűsége, hogy egymás mellett lesznek? A kérdésre adott válasz megtalálásához el kell osztani a „jó” eredmény valószínűségét az eredmények teljes számával. A permutációk száma összesen 20!=2,5 kvintillió. Hogyan lehet megszámolni a „jó” eredmények számát? Tegyük fel, hogy Kostya, Sasha és Lesha egy szuperember. Aztán miCsak tizennyolc tantárgyunk van. A permutációk száma ebben az esetben 18=6,5 kvadrillió. Mindezzel Kostya, Sasha és Lesha önkényesen mozoghatnak egymás között az oszthatatlan hármasukban, és ez még 3!=6 lehetőség. Tehát összesen 18 „jó” csillagképünk van!3! Csak meg kell találnunk a kívánt valószínűséget: (18!3!) / 20! Ami hozzávetőlegesen 0,016. Százalékra átszámítva csak 1,6% lesz.
Szállás
Most egy másik nagyon fontos és szükséges kombinatorikai képletet fogunk megvizsgálni. A szállás a következő számunk, amelyet a cikk ezen részében javasolunk. Egyre bonyolultabbak leszünk. Tegyük fel, hogy a lehetséges permutációkat szeretnénk figyelembe venni, csak nem a teljes halmazból (n), hanem egy kisebbből (m). Ez azt jelenti, hogy n elem permutációját vesszük figyelembe m.
A kombinatorika alapképleteit nem csak megjegyezni, hanem meg is kell érteni. Még annak ellenére is, hogy bonyolultabbá válnak, hiszen nem egy paraméterünk van, hanem kettő. Tegyük fel, hogy m \u003d 1, majd A=1, m \u003d 2, majd A=n(n - 1). Ha tovább egyszerűsítjük a képletet, és átváltunk a faktoriális jelölésekre, egy egészen tömör képletet kapunk: A \u003d n! / (n - m)!
Kombináció
A kombinatorika szinte összes alapképletét példákkal végiggondoltuk. Most pedig térjünk át a kombinatorika alaptanfolyamának mérlegelésének utolsó szakaszára – a kombináció megismerésére. Most m elemet választunk ki a rendelkezésünkre álló n-ből, miközben mindegyiket minden lehetséges módon kiválasztjuk. Akkor miben különbözik ez a szállástól? Mi nemfontolja meg a sorrendet. Ez a rendezetlen készlet egy kombináció lesz.
Azonnal vezesse be a jelölést: C. n-ből m golyót helyezünk el. Nem figyelünk a rendre, és ismétlődő kombinációkat kapunk. Ahhoz, hogy megkapjuk a kombinációk számát, el kell osztanunk az elhelyezések számát m-rel! (m faktoriális). Vagyis C \u003d A / m! Így van néhány módja annak, hogy n golyó közül válasszunk, nagyjából annyit, amennyit szinte mindent kiválaszthatunk. Ennek van egy logikus kifejezése: egy keveset választani ugyanaz, mint szinte mindent kidobni. Ezen a ponton azt is fontos megemlíteni, hogy a kombinációk maximális száma akkor érhető el, ha megpróbáljuk kiválasztani az elemek felét.
Hogyan válasszunk képletet a probléma megoldásához?
Részletesen megvizsgáltuk a kombinatorika alapképleteit: elhelyezés, permutáció és kombináció. Most az a feladatunk, hogy megkönnyítsük a kombinatorika problémamegoldásához szükséges képlet kiválasztását. Használhatja a következő meglehetősen egyszerű sémát:
- Kérdezd meg magadtól: figyelembe veszik-e az elemek sorrendjét a feladat szövegében?
- Ha a válasz nem, akkor használja a kombinációs képletet (C=n! / (m!(n - m)!)).
- Ha a válasz nem, akkor még egy kérdésre kell válaszolnia: minden elem benne van a kombinációban?
- Ha a válasz igen, akkor használja a permutációs képletet (P=n!).
- Ha a válasz nem, akkor használja az allokációs képletet (A=n! / (n - m)!).
Példa
Figyelembe vettük a kombinatorika elemeit, a képleteket és néhány egyéb kérdést. Most menjünk továbbvalós problémára gondolva. Képzeld el, hogy van előtted egy kivi, egy narancs és egy banán.
Első kérdés: hányféleképpen rendezhetők át? Ehhez a permutációs képletet használjuk: P=3!=6 út.
Második kérdés: hányféleképpen lehet kiválasztani egy gyümölcsöt? Ez nyilvánvaló, csak három lehetőségünk van - válasszon kivit, narancsot vagy banánt, de alkalmazzuk a kombinációs képletet: C \u003d 3! / (2!1!)=3.
Harmadik kérdés: hányféleképpen lehet kiválasztani két gyümölcsöt? Milyen lehetőségeink vannak? Kiwi és narancs; kivi és banán; narancs és banán. Vagyis három lehetőség, de ez könnyen ellenőrizhető a kombinációs képlettel: C \u003d 3! / (1!2!)=3
Negyedik kérdés: hányféleképpen lehet kiválasztani három gyümölcsöt? Amint látja, csak egyféleképpen választhat három gyümölcsöt: vegyünk egy kivit, egy narancsot és egy banánt. C=3! / (0!3!)=1.
Ötödik kérdés: hányféleképpen választhatsz legalább egy gyümölcsöt? Ez a feltétel azt jelenti, hogy egy, kettő vagy mindhárom gyümölcsöt vehetünk. Ezért adjuk hozzá a C1 + C2 + C3=3 + 3 + 1=7-et. Vagyis hét módszerünk van arra, hogy legalább egy darab gyümölcsöt vegyünk le az asztalról.
