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óinak
szá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 cscsa között több
élt is hzhatunk, 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.