Kombinatórika tétel, szerintetek ez így jó, lesz vagy van amit elrontottam?

A szöveg egy kicsit hosszú lesz, fejből leírom amit tudok.

Illetve a kérdésem végén lesz pár fogalom, amit nem teljesen értek.

Viszont aki válaszol annak előre is megköszönöm.

A tétel címe: Leszámlálási alapfogalmak (permutációk, variációk és kombinációk (ismétlés nélkül és ismétléssel)

példával, kiszámításuk , binomiális együtthatók közti egyszerű összefüggések, a binomiális tétel)

Leszámlálási probléma az nem más, mint hogy definálok valamilyen matematikai módon egy halmazt, és nekem meg kell mondanom, hogy hány eleme van ennek a halmaznak.

6 alapesetet különböztetünk meg:

Az első eset az n elem k-ad osztályú ismétlés nélküli variációja. Ez azt jelenti, hogy van n különböző elemem és ebből előállítok egy k hosszú sorrendet, azaz kiválasztok n különböző elemből k darabot (n >= k), majd sorba rendezem őket, tehát számít a sorrend és az ismétlés nem megengedett.

Jelölése: V(n,k) ez azt mondja meg, hogy n elemnek hány k-ad osztályú ismétlés nélkül variációja van

Például, ha van egy futó verseny, ahol 100 (n) versenyző indul, és az első 10 (k) befutó sorrendjére vagyok kíváncsi, akkor ez egy ismétlés nélküli variáció, tehát 100 elem 10-ed osztályú ismétlés nélküli variációja.

Az ismétlés nélküli variáció száma: n*(n-1)*(n-2)*...(n-k+1), ez egy k tényezős szorzat, melynek az 1. tényezője n, a 2. n-1 és a k-adik tényező az n-k+1

Amikor egy leszámlálási problémát szeretnénk megoldani, akkor mindig zárt alakban keressük a megoldást, ezért az n! faktoriális bevezetésével az ismétlés nélküli variáció számát fel lehet írni másképp, hogy zárt alakot kapjunk.

Az n! az azt jelenti, hogy 1-től n-ig összeszorozzuk a pozitív egész számokat, azaz 1*2*3*4*...*n

Azonban ha n = 0, akkor n! az 1, vagyis 0! = 1.

A ismétlés nélküli variáció száma tehát zárt alakban n!/(n-k)!

Számának bizonyítása:

Ugye n különböző elemből kell kiválasztanom k darabot, hogy ismétlés nem megengedett, vagyis egy k hosszú sorrendet kell előállítanom.

A k hosszú sorrend 1. eleme n féle lehet, mivel az n elem közül bármelyiket választhatjuk, ez n esetet jelent. A k hosszú sorrend 2. eleme n-1 féle lehet, mivel bármelyik elemet választhatjuk, kivéve azt amit az 1. elemnek választottunk, mivel ismétlés nem megengedett, ez n-1 alesetet jelent. A 3. elem n-2 féle lehet, mivel bármit választhatunk, kivéve az első 2 elemnek választott dolgot. És így tovább, tehát esetek száma megegyezik a variációk számával, ezért n*(n-1)*(n-2)*...(n-k+1) az ismétlés nélküli variációk száma.

n elem k-ad osztályú ismétléses variációja azt jelenti, hogy n különböző típusból egy k hosszú sorrendet előállítok, vagyis k elemet kiválasztok és sorba rendezem, tehát számít a sorrend, viszont itt az ismétlés az korlátlanul megengedett.

Jelölése: Vism(n,k)

Száma pedig n^k.

Például ha van egy olyan versenyem, ahol a verseny résztávokból áll és minden résztávnak van egy győztese, akkor ha van n versenyzőm és k db résztávom, akkor ez egy ismétléses variáció, mivel aki az 1. résztávot megnyeri, az megnyerheti a 2.-at és 3.-at is, tehát ismétlés itt megengedett.

Számát hasonlóan lehet bizonyítani az ismétlés nélküli esethez, itt az 1. elemem n féle lehet, viszont a 2. elemem is n féle lehet, mivel ismétlés megengedett, így tovább, a k hosszú sorrendem minden eleme n féle lehet, vagyis az ismétléses variáció száma: n^k.

n elem ismétlés nélküli permutációja alatt egy n hosszú sorrendet értünk, vagyis n különböző elemből kell kiválasztani n db-ot, azaz az összeset, majd ezeket sorba rendezzük, azaz számít a sorrend.

Jelölése: Pn

Száma pedig: n!

Például ha van 5 különböző golyóm, akkor ezeket hány féleképpen lehet sorba rendezni, vagy másik példa, ha van 5 emberem, akkor ez az 5 ember hány féle képpen ülhet le egymás mellé.

Számának bizonyítása:

Az ismétlés nélküli permutáció igazából egy ismétlés nélküli variáció, ahol n = k, vagyis n elemből n-et, az összeset ki kell választani.

Az ismétlés nélkül variáció száma n!/(n-k)!, az ismétlés nélküli permutáció pedig egy V(n,n), tehát k = n, vagyis n!/(n-n)!, ami n!/0!, ugye 0! az 1, tehát n!/1, ami n!, tehát ezért n! az ismétlés nélküli permutációnak a száma.

Ha valamiről nem mondjuk, hogy ismétlés nélküli, vagy ismétléses, akkor mindig az ismétlés nélküli esetre gondolunk.

Tegyük fel, hogy n = k1+k2+k3+...+kl, vagyis egy n számot l darab pozitív egész szám összegeként állítunk elő. Ekkor ennek az n számnak az ismétléses permutációja egy olyan n hosszú sorrend, melyben l féle elem fordul elő, az 1. elem k1-szer, a 2. az k2-ször, és így tovább, az i-edik az ki-szer.

Vagyis az ismétléses permutáció az az, amikor n elemből kiválasztok n-et, azaz az összeset, sorba rendezem ezeket, tehát számít a sorrend, azonban az n elem között lehetnek egymással megegyező elemek.

Erre példa az órarend készítés, vagy az, ha mondjuk van 5 golyóm, ebből 2 piros, 2 kék és 1 zöld és ezeket sorba kell rendezni.

Száma: n!/(k1!*k2!*...kl!)

Számának bizonyítása:

Ugye az azonos elemek felcserélésével ugyanazt a sorrendet kapjuk vissza, pl. a golyós példánál, ha 2 piros golyót felcsérelek, akkor az ugyanannak a sorrendnek számít.

Különböztessük meg az azonos elemeket, mondjuk indexeléssel, ekkor n különböző elemet kapunk, ugye n különböző elem permutációjának száma n!

Egy konkrét sorrendet úgy kapunk meg, hogy vesszük az egyes elemek permutációit és ezekkel korrigáljuk azt az esetet amikor mindegyik elem különbözik.

Vagyis az n!-ban meg kell számolnunk a k1!*k2!*...*kl!-t.

n elem ismétlés nélküli kombinációja alatt azt értjük, hogy van n különböző elemünk és ebből k darabot kiválasztunk, úgy hogy a sorrend egyáltalán nem számít.

Vagyis az ismétlés nélküli kombináció az csak abban különbözik az ismétlés nélküli variációtól, hogy a kombináció esetében nem számít a sorrend.

Jelölése: C(n,k), ahol (n >= k)

Például a lottó húzás az egy ismétlés nélküli kombináció.

Definíció szerint (n alatt k) = n!/(k!*(n-k)!), ezt binominális együtthatónak is nevezik.

A C(n,k) azaz az ismétlés nélküli kombináció száma az (n alatt k)

Számának bizonyítása:

Bármely ismétlés nélküli kombináció megkapható úgy, hogy az alaphalmaz minden eleméről eldöntjük, hogy ki van-e választva, azaz minden ismétlés nélküli kombináció kódolható egy n hosszú 0/1-es sorozattal, melyben k db 1-es és n-k db 0 fordul elő.

Pl.:

0 1 2 3 4 ... n

0 0 1 0 1 0

Ekkor a 2-t, 4-t kiválasztottam és a 0-t, 1-et, 3-at, n-t nem választottam ki. Vagyis egy ilyen 0/1-es sorozatban k darab dolgot kiválasztok és n-k darab dolgot pedig nem választok ki.

Az ilyen 0/1-es sorozatok ismétléses permutációinak a száma az: n!/(k!*(n-k)!) ami nem más mint (n alatt k)

Azaz minden ismétlés nélküli kombináció az igazából egy ismétléses permutáció.

A binominális együtthatót, azt (n alatt k)-val jelöljük és az igaz, hogy:

(n alatt k) = (n alatt n-k)

Mivel (n alatt k) = n!/(k!*(n-k)!)

(n alatt n-k) pedig ugyanez, csak k helyére mindenhova (n-k)-t írunk, azaz n!/((n-k)!*((n-(n-k))!) amit ha felbontunk akkor: n!/((n-k)!*(k!)) kabpunk és ez ugyan az mint az (n alatt k)

A binominális együtt ható (n alatt k) felírható (n-1 alatt k)+(n-1 alatt k-1) alakban is.

Ezt úgy lehet bizonyítani, hogy meg kell néznünk, hogy az n elemű alaphalmaznak hány k elemű részhalmaza van, ha kijelölünk egy elemet. Ekkor 2 féle k elemű részhalmazt tudunk megkülönböztetni, egy olyan típust ami tartalmazza a kijelölt elemet és egy olyat ami nem tartalmazza a kijelölt elemet. Ahány féle képpen n-1 elemből k-1-et kitudunk választani annyi féle olyan k elemű részhalmaz van, ami a kijelölt elemet tartalmazza, és ahány féle képpen n-1 elemből k darabot ki tudunk választani, annyi olyan k elemű részhalmazunk van, ami a kijelölt elemet nem tartalmazza.

A binominális tétel:

(a+b)^n = (n alatt 0)*a^n*b^0 + (n alatt 1)*a^(n-1)*b^1 +...+(n alatt n-1)*a*b^(n-1) + (n alatt n)*a^0*b^n = szumma (i = 0-tól n-ig) a^(n-i)*b^i

A binominális tételt n szerinti teljes indukcióval lehet bizonyítani.

Az alapeset az n = 1.

(a+b)^1 = (1 alatt 0)*a^1*b^0 + (1 alatt 1)*a^0*b^1 = a+b, tehát az n=1 alapeset igaz

Tegyük fel, hogy (n-1)-re már tudjuk, ekkor:

(a+b)^n = (a+b)*(a+b)^(n-1) = (a+b)*((n-1 alatt 0)*a^(n-1)*b^0 + (n-1 alatt 1)*a^(n-2)*b^1 +... + (n-1 alatt n-1)*a^0*b^n-1

Mivel mindegyik tagnál a kitevők különbsége n-1, így ha beszorozzuk a+b-vel, akkor a kitevők különbsége n lesz, vagyis ilyen alakú lesz:

szumma(i=0-tól n-ig) a^(n-i)*b^i*(n-1 alatt i)+(n-1 alatt i-1)

ez pedig nem más mint:

szumma(i=0-tól n-ig) a^(n-i)*b^i*(n alatt i)

A binominális tétel következménye:

(n alatt 0)+(n alatt 1)+...(n alatt n) = (1+1)^n = 2^n

(n alatt 0) - (n alatt 1) + (n alatt 2) - (n alatt 3)+....+-(n alatt n) = (1-1)^n = 0^n = 0

Azaz a binominális együtthatók váltakozó előjelű összege az 0.

n elem ismétléses kombinációja az azt jelenti, hogy n különböző típusból kiválasztok k darabot (n >= k), ahol a sorrend nem számít, viszont ismétlés az korlátlanul megengedett.

Jelölése: Cism(n,k)

Pl.: n gombóc fagyit kérek kehelybe

Száma: (n+k-1 alatt k)

Számának bizonyítása:

Célunk n = a1+a2+a3+..ak felbontások megszámolása, ahol minden ai egy természetes szám.

Ez kódolható egyes számrendszerben, azaz:

pl. 7 gombóc fagyit kérek 6 típusból:

3+0+1+0+0+2

egyes számrendszerbe úgy kódolom, hogy ahol összeadás jel van oda 0-át írok, ahol 0 van oda nem írok semmit, ahol pedig szám oda pedig annyi 1-est amennyi a szám, vagyis a 3+0+1+0+0+2 egyes számrendszerben kódolva:

11100100011

Ez egy olyan 0/1-es sorozat melyben k db 1-es és n-1 db 0 fordul elő, és ilyen 0/1-es soroknak a permutációja az (n+k-1 alatt k)

Ez a tétel, amit nem teljesen értek, csak bemagoltam belőle azaz ismétléses kombináció és az ismétléses permutáció bizonyítása, illetve hogy mi is az a leszámlálási probléma, mit jelent az, hogy valamilyen matematikai módon definiálok egy halmazt.

Illetve az, hogy ezeknél miért az van, hogy n különböző típusból kell választani, nem pedig elemből? (ezt külön kiemelte a tanárom)

Ezek lennének a kérdéseim, illetve még annyi, hogy mindent jól írtam le, nem írtam valamit hibásan, esetleg még van olyan amit beletennétek ebbe a tételbe?