KOMGRAF
148. Bizonyítsa be, hogy n különböző elem összes permutációjának száma nfaktoriális =n(n -1)(n -2)...3*2*1!
Adott n [különböző] elem valamely sorrendjét az adott elemek egy permutációjának nevezzük. Az n elem összes lehetséges sorrendjének a számát, vagyis az n elem permutációinak számát pn-nel jelöljük. A pn meghatározásához vegyünk egy n rekeszes dobozt, és vizsgáljuk meg, hány féleképpen lehet elhelyezni az 1,2,3,...N,n elemeket a megadott n helyre: n féleképp, n -1 féleképp, ... Kétféleképp, egyféleképp. Az első rekeszbe az n elem bármelyike választható; így ez a rekesz n féleképpen tölthető be. A második rekeszbe az első helyre beírt elem már nem választható, így a másodikba az (n -1) elem bármelyike tehető. Ez az első rekesz minden lehetséges kitöltése mellett a második rekesz kitöltésére (n -1) féle lehetőséget ad. Az első két rekesz kitöltésére tehát (n*(n -1)) lehetőség van. A harmadik rekeszbe már csak (n -2) elem közül választhatunk. gy az első három rekeszbe (n*(n -1)*(n -2)) féleképpen tehetők az elemek. Hasonlóan látható be, hogy a következő helyek mindegyike egyel kevesebb módon tölthető be, mint az előző hely. Az (n -2)-edik rekeszbe 3, az (n -1)-edik rekeszbe 2 elem közül választhatunk; az n-edik rekeszbe már csak egy elem marad.
N különböző elem összes permutációjának száma: pn =n*(n -1)*...*3*2*1. Az egyenlőség jobb oldalán az első n természetes szám szorzata áll, ennek rövid jelölése: n faktoriális. Tehát pn =n faktoriális.
149. Bizonyítsa be, hogy a különböző elem k -ad osztáj variációinakszáma n faktoriális / (n -k) faktoriális!
Adott n különböző elem, válasszunk ki közülük k-t (k <=n), és vegyük a kiválasztott k elem egy sorrendjét. gy az n elem egy k-ad osztáj variációját nyerjük. Az összes kiválasztott k -as összes lehetséges sorrendjének a száma az n elem összes k -ad osztály variációinak száma. Ennek bebizonyítására vegyünk egy k rekeszes dobozt! Ebben helyezzük el n elem közül k elemet minden lehetséges módon: n féleképp, (n -1) féleképp, ...,(N -k +1) -féleképp. Az első rekeszbe az n elem bármelyike tehető. A második rekeszbe már csak (n -1) elem közül választhatunk [egy elem ugyanis már az első rekeszben van]. Ez (n -1) féle kitöltési lehetőséget ad a második rekesz számára. Az első két rekeszbe így (n*(n -1)) féleképpen tehetők az elemek. Minden rekeszbe egyel kevesebb elem közül választhatunk, mint az előzőbe. A k-adik rekeszbe (n -k +1) elem közül választunk. A doboz teljes kitöltésére összesen (n*(n -1)*...*(N -k +1)) lehetőség adódik. Ha az eredményt (n -k) faktoriálissal bővítjük, faktoriális jelöléssel is fölírhatjuk: n*(n -1)*...*(N -k +1) =n*(n -1)*...*(N -k +1)*(n -k)*(n -k -1)*...*2*1 /(N -k)*(n -k -1)*...*2*1 =Nfaktoriális /(n -k)faktoriális.
150. Bizonyítsa be, hogy különböző elem k -ad osztály konbinációinak száma =nfaktoriális /kfaktoriális*(n -k)faktoriális.
Adott n különböző elem. Az n elem közül k különböző elemet választunk ki oly módon, hogy a kiválasztás sorrendjére nem vagyunk tekintettel. gy az n elem k -ad osztály konbinációját nyerjük. Ennek meghatározása érdekében nézzük meg, milyen kapcsolat van az n elemből alkotott k -ad osztály variációk száma és az n elemből alkotott k -ad osztály konbinációk között! Egy k-ad osztály konbinációból gy képezhetünk k-ad osztály variációt, hogy a konbináció elemeit permutáljuk. Minden egyes konbináció k faktoriális variációt ad. A konbinációk különböztek egymástól legalább egy elembe, így a kapott variációk is biztos különböznek. Ezek szerint: kfaktoriális*különböző n elem k-ad osztály konbinációja =n*(n -1)*(n -2)*...*(N -k +1) =nfaktoriális /(n -k)faktoriális, innen: különböző n elem k-ad osztály konbinációja =n*(n -1)*...*(N -k +1) /kfaktoriális =nfaktoriális /kfaktoriális*(n -k)faktoriális
159. Határozza meg egy véges halmaz részhalmazainak számát!
Egy n elemű halmaznak 2^n szám különböző részhalmaza van.
Bizonyítása: tekintsük az (a ={{a1,a2,...,An}}) halmazt! Egy részhalmazt megadhatunk oly módon, hogy az a1,a2,...,aN elemekről rendre megmondjuk, hogy benne vannak-e a részhalmazban, vagy sem. Ennek alapján az A halmaz részhalmazait megfeleltetjük 0 és 1 számjegyekből álló n tagu számsorozatoknak: a k-adik helyre aszerint írunk 0-át vagy 1-et, hogy a(k) benne van-e a részhalmazban. Ha nincs benne, 0-át; ha benne van, 1-et írunk. Ez a megfeleltetés kölcsönösen egyértelmű, így pontosan annyi részhalmaza van az A halmaznak, mint ahány 0-ákból és 1-esekből álló n tagu számsorozat van. Minden hely kitöltésére egymástól függetlenül 2 lehetőségünk van [0-át vagy 1-et írhatunk]. gy a lehetőségek száma 2^n.
160. Mit nevezünk gráfnak? Mi az n pont teljes gráf? Mi az egyszerű gráf? Mi az összefüggő gráf?
Ha véges sok adott pont közül egyeseket vonallal összekötünk, akkor a kapott ábrát gráfnak nevezzük. A pontok a gráf pontjai vagy szögpontjai, a vonalak a gráf élei. Ha egy gráfnak n pontja van [n pozitív egész szám], és mindegyik pontból pontosan 1 él vezet a többi ponthoz, akkor a gráfot n pont teljes gráfnak nevezzük.
A gráfokban előfordulhat olyan él is, amelynek mindkét végpontja ugyanaz a pont. Az ilyen él neve hurok. Két csúcsa között több élt is húzhatunk, ezek a többszörös élek.
Egy gráfot egyszerűnek nevezünk akkor, ha nincs benne sem hurok, sem többszörös él.
A gráf összefüggő, ha bármely pontjából bármely másik pontjába élek mentén el lehet jutni.
Megjegyzés küldése