Hogyan tudnám jól megérteni a Kombinatorikát,Permutációt,Variációt. Mi a permutáció és a variáció közt a különbség? Hogy tudnám minnél egyszerűbben kiszámolni a lehetőségeket?

Az a baj nehéz ügyesen megválaszolni. Mert akárhogy is válaszoltak az előttem lévők jól, kvázi leírták a tankönyvet amiből állítólag nem értetted meg. "22es csapdája" Megpróbálom én is, de valszeg ennek is tankkönyvi szaga lesz picit,de hátha.

Az összes lehetséges eset összeszámlálása a közös mindegyikükben, annyi csavarral hogy mindig megvan adva 2 dolog:

1. az eseteket legeneráló folyamat

2. és hogy mi számít egyenlő/azonos esetnek amit így nem különbeztetünk meg és számolunk külön.

(azaz legeneráljuk az összes verziót mintha minden-is számítana, majd ugyanazon "zsákba" tesszük azokat a kimeneteleket amit nem tekintünk különbözőnek , s végül ezen zsákokat számoljuk meg, tehát hogy hány "egyenlőségi csoport" van)

Az egész "leleke" a permutáció fogalma. Ebből (majdnem) minden alapeset levezethető. Sőt, megértve a természetét megértünk más alaptípustól eltérő feladatot is.(később kifejtve)

Őszintén anno nekem is nehezen ment, nem elég hogy a számítas is bonyolultnak tűnim, de a hozzá tartozó elnevezést megjegyezni sem volt piskóta. Kirázott tőle ugyan úgy a hideg,mint magától a számolástól.

Első nézőpont.

Tehát a permutáció kiemelkedik fogalmilag, a kombinació és variáció az igazi testvérek. A permutáció ugyanis nem olyan értelemben ismétlés nélküli vagy ismétléses, mint az utóbbi kettő.

Permutációnál nincs eleve kiválasztás (vagyis kvázi az összes elem a kiválasztott), és mindig számít a sorrend, ha van, ha nincs ismetlődő elem (ami sehogy nem hasonítható össze az imételt kiválasztáshoz)! Ezzel szemben a kombináció/variáció mindig a kiválasztásról szól,akár ismetlés nélküli, akár ismétléses, a kombinació jelzi hogy a sorrend nem számít, a variació jelzi hogy a sorrend számít. Azaz a kettő között a "sorrendiség számítása" a különbség.Innen nézve a permutáció ezek felett áll, úgy is felfoghatjuk, hogy hidként összeköti a két fogalmat. K ----P---- V

Szendvics hasonlat:

K: csak az számít mi van a szendvicsben ( választható szalámi, paradicsom, sajt)

V: számít milyen sorrendben vannak egymásra pakolva a választott elemek

...függetlenül attól hogy többször felhasználható-e sajt, szalámi, paradicsomkarika.

*kiválasztás része:n alapanyagból k választható

*ismétlés része: többször választható-e vagy sem.

Egy kérdés van minden esetben: Anya hányféle szendvicset tud reggelre elkészíteni nekem adott feltételekkel?

Másik nézőpont.

a, kiválasztás / nics kiválasztás = összes kiválasztása

b, sorrend számít/ nem számít

c, ismétléses/ismétlés nélkül

Tehát 3 db két értékű tulajdonság. Innen nézve 2*2*2 azaz 8 alapeset kellene létezzen.

1.kiválasztás van: [K,V] (ismétléses/anélküli) /2*2=4 eset/

2.összes kiválasztás:[P]

DE! itt nincs értelme ismétlésről beszélni olyan értelemben mint a kiválasztásnál, marad a sorrend kerdése /1*2=2 eset/

DE! nincs értelme arra esetet fenntartani hogy hányféle eset van, ha nincs sorrend? természetesen 1 db! /2-1=1 eset/

Tehát 8 helyett ezért van csak 5 eset: 2 K, 2 V, P

Illetve a permutáció esete kettébomlik hogy van ismétlődő elem vagy sem. Hangsúlyozom sokadjára, nem mindegy hogy a halmazból ismételten valaszthatunk, vagy magában a halmazban többször fordul elő egy elem. Ismetléses/visszatevéses választásnál, ha k-t választunk, az olyan mintha ismétlés/visszatevés nélkül választhatunk k db-ot, de minden elem legalább k-szor előfordul, hogy akár k db azonosat is választhassunk bármelyikből, ha már visszatenni/ismételni nem lehet)

Harmadik nézőpont.

A P általanosan egy adott esetnek a sorrendjét adja meg ( attól függően van e halmazban ismétlődő elem)

A K jelenléte/nem jelenléte adja meg hogy van-e kiválasztás/vahy nincs, azaz kvázi az összeset kiválsztjuk. Talán így elsőre furcsa. Kombináció = Kiválasztás ???

Igen, mert ha számít a sorrend is az eseteknél akkor az Variáció, azaz P + K = V

Tehát a P kepviseli az elemismétlődest figyelembe vevő sorrendet az egyes esetekben, a K képviseli a kiválsztással legyártott eseteket.

Innen (is) érzékelhetjük hogy K,V esetnél mindig csak kiválasztási ismétlés meglétevel/hianyaval fogalkoztunk, nem definiáltunk olyan esetet amikor a választott halmazunkban elemismétlés van. Ha megengedett az ismetelt/visszatevéses választás akkor ennek nincs is jelentősége,hisz bármelyik elemet akárhányszor választhatjuk. Érdekesebb az amikor ismétlődő elem van, de nem ismétlős/visszatevős a választás, ami azonos azzal (szemben a visszatevéssel) hogy nincs ismétlődő elem, de minden elemnek egyedileg!! meg van szabva hányszor választhatjuk ki visszatevéssel (azaz nem válaszhatjuk akárhányszor). Bonyolultnak tűnik, nem tűnik se gyakori esetnek, nem hiába nem kapott külön nevet, még altalános képlete se lehet bár ezt csak ismereteim hiányaban mondom. Nem is baj, nem alapeset az tuti.

Folytatás... :D

Tehát azt a zavart el kell hárítani hogy keveredik az ismetlés/visszatevés szóhasználata! Utoljára, az ismetlés más P-nél és más K,V esetében. Ezért jobb ha utóbbi esetben visszatevésről beszélünk, amiből inkább asszocioálunk valasztásra mintsem választhato elemek ismétlődésére.

Permutációból (majdnem) levezethető minden alapeset?

(ahova nem irok ism.et az ism. nelküli most!)

P = n!

P => ism. P = n!/k!

Feltételezzük, hogy a k azonos különbözik, azaz k! sorrendje van, azaz minden esetet ennyiszer számoltunk többször, így visszaozstunk vele.

P => V = n!/(n-k)!

Csak faktoriális trükk. Ha az n-nél kevesebb k db helyre van több elemem, akkor az n*(n-1)*(n-2)*... sor nem ér végig, de a lemaradó szorzat így néz ki:(n-k)*(n-(k-1))*...*2*1=(n-k)!

P + V => K = V/k! = n!/[(n-k)!k!]=definícíó szerint: (n alatt a k)=(n alatt n-k)

A kombináció "olyan variáció" ahol mem számit a sorrend. k elemű halmazokat azonban variáció eseteben k! szorosan számoltunk, így visszaosztunk.

P => K => ism.K = (n+k-1 alatt a k)

Definició szerint kivalasztunk ismétléssel k darabot.Ugy hasonlitjuk össze az eseteket a megszamolás érdekében hogy a választható elemeket sorrendbe rakom, MAJD az összes lehetséges k db kiválasztásban az elemeket ugyanolyan sorrendbe rakom (kihagyva olyan elemeket termeszetesen amiket nem választottunk). Van n-1 db elválasztó lapocskám, ami eredetileg az n db választható elemeket határolta el egymastól. Most fogom ezeket és beteszem a sorrendbe állitott k db kiválasztasokhoz úgy,hogy ugyanúgy határolják az elemeket, maximum egyes határoló lapok egymásmellé kerülnek közvetlen, ha a közöttük lévő elemből nem választottunk ki egyet sem. Így kapunk egy k +(n-1)=n+k-1 elemű eseteket. PL: 1,2,3,4,5 ből 4at: 1,3,3,4 => 1, 1|2, 2|3, 3, 3, 3|4, 4, 4|5. (5+4-1=8 db)

Csinaljuk fordítva!! n+k-1 elemből valasszunk (n-1) elemet amit határolónak jelölünk meg, mely határolók jelzik hogy milyen elemnek tekintjük a közöttük lévő elemeket. Látszik minden kiválasztás megfelel egy esetnek az eredeti kiválasztásban, így számuk azonos.

ism. V = n^k = n*n*... (összesen k-szor összeszorozva) Egyedül az ism. V az ami ebből a szempontból kakukktojás.

Röviden P => ism.P, V => K => ism.K továbbá önállóan ism.V

És akkor általanos amikor nem alapesetről van szó, hanem összetett esetekről.

Ilyen ill. vitatható hogy alap vagy sem, a ciklikus permutáció. Ha az ember érti a permutációt akkor vérszemet kap mikor szembejön a ciklikus permutáció, hogy mi ez mi a @$#?!?!?

De ezt IGAZÁN megérteni azt jelenti, megérthető jóval általánisabb eset is.

Tehát a permutáció igazából függvenyként is felfogható. Amikor azt mondjuk higy 2,1,3 az 1,2,3 elemek egy permutációja/sorrendje akkor azt momdom igazából hogy van egy p() függvény és p(1)=2, p(2)=1,p(3)=3 :) De látható, ez nem akármilyen függbény, ez "párbaállítós", azaz csúnya szóval bijektív függvény. Az 1,2 3 számokból álló halmazt önmagára képezi, de különböző elemekhez különböző elem tartozik.

Ciklikus P

Tipikis az asztal köré ültetéses feladat.

Ha a fenti értelmezést nézzük akkor nem székekre hanem "számokra" (számozott székekre/számozott helyekre)

ültetünk számokat.

Másik trükk, hogy

(elküldtem véletlen)

...tehát, másik trükk, hogy nem magát az ültetéseket hasonlítgatom össze, hanem az ültetés "geometriaját/viszonyát" nézem hogyan variálható.

Azaz n helyre n! féle képpen ülhet ember.

DE! Amellett a feltétel mellett hogy minden széknek a szomszédja kötött, sőt az is kötbe van higy bal vagy jobboldali a szomszédja így a helyeket csak úgy variálhatom, hogy forgatom a székeket az asztal körül (diszkréten), tehát nem az embereket ültetem arréb hanem az alattuk lévő széket cserélgetem. Igazából bármelyik nézőpont jó, a fokusz a geometrián van! A székek egy n csúcsú sokszöget alkotnak, önmagába n féle képpen forgathatom (nem megengedett a tükrözés, azaz a bal szomszed bal, a jobb jobb kell hogy maradjon). Tehát amikor "nem felvserélhetőnek/egyedinek tartottuk a székeket n! féle ültetés volt, amikor pedig mozgathatóak a székek akkor minden esetet annyiszor számoltunk ahányféle képpen a székek variálhatóak, azaz ha visszaosztunk megkapjuk a lépletet. n!/n=(n-1)!

Mi van ha nem számít a bal/jobb?

Akkor tükrözni is lehet, ami újabb n eset, összesen n+n=2n (n csúcsú sokszög önmagába való leképezésére gondoljunk most is) Vigyázat. 1 és 2 szék esetén a forgatás és tükrözés ugyan az, nem két különböző eset. 2n csak n>2 esetén igaz, azaz n>2 esetben az eserek száma n!/(2n), 1 és 2 esetben is 1 az eredmény!

Hogy bonyolíthatjuk? Mi van he nem asztal köré, hanem egy kocka sarkaihoz ültetünk nyolc embert. És az számít hogy ki ül a 3 db élszomszédos csúcsoknál, de nem számít mondjuk hogy milyen sorrendben ülnek körbe egy adott csúcsból nézve? :) Mi van ha a kocka egyik oldala poros, és ez is számít? :D Mivan ha nem emberek hanem számozott golyókat helyezünk a csúcsokhoz,de nincs nyolcas hanek kettő azonos szám van?:DD

Mi vam ha az egyedi golyók közül 1 szinezett, ami nem.kerülhet a pirosra szinezett oldal egyik csúcsához sem? XD Szóval lehet fokozni...