Mathematics | Probability theory » A kombinatorikáról

I. tétel KOMBINATORIKA 1. Permutáció Ismétlés nélküli permutáció: Adott n különböző elem. Az elemek egy meghatározott sorrendjét az adott n elem egy ismétlés nélküli permutációjának nevezzük. Az n elem permutációinak számát a P n szimbólummal jelöljük. A permutációk képzését permutálásnak nevezzük. 1.1 tétel Az n elem permutációinak száma P n = n! Az n! (n faktoriális) jelentése a pozitív egész számok sorozata 1-től n-ig, azaz n! = 1 2 . n (P n = nP n-1 ) Ismétléses permutáció: Adott n elem, amelyek között r (r  n) különböző található, ezek a 1 , a 2 , .a r Az a 1 elem k 1 -szer, az a 2 elem k 2 -ször, az a r elem k r -szer fordul elő, és k 1 + k 2 +.+ k r = n Az adott n elem egy meghatározott sorrendjét ezen elemek egy ismétléses permutációjának nevezzük. A szóba jövő ismétléses permutációk számát a P n (k1,k2,kr) szimbólummal jelöljük. 1.2 tétel Rögzített n, r és k 1 , k 2 , ., k r esetén az

ismétléses permutációk száma n! . (k1, k2, .kr) Pn = k 1 ! k 2 ! . k r ! 2. Variációk Ismétlés nélküli variáció: adott n különböző elem. Ha n elem közül k elemet (0 k  n) úgy választunk ki, hogy mindegyik csak egyszer kerül sorra, és a kiválasztás sorrendje is számít, akkor az n elem egy k-adosztályú ismétlés nélküli variációját kapjuk. Az n elem k-adosztályú variációinak számát a V n k szimbólummal jelöljük. 1.3 tétel Az n különböző elem k-adosztályú variációinak száma n! . V n k = (n - k)! = n ( n-1) . (n-k+1) Ha k=n akkor V n k = P n , és 0! = 1. Ismétléses variáció: adott n különböző elem. Ha n elem közül k elemet úgy választunk ki, hogy egy elem többször is sorra kerülhet, és a kiválasztás sorrendje is számít, akkor az n elemet egy k-adosztályú ismétléses variációját kapjuk. Az n elem k-adosztályú ismétléses variációinak számát a V n k(i) szimbólummal jelöljük. 1.4 tétel Az n

különböző elem k-adosztályú ismétléses variációinak száma V n k(i) = nk 3. Kombináció Ismétlés nélküli kombináció: adott n különböző elem. Ha n elem közül k elemet ( 0k n ) úgy választunk ki, hogy mindegyik csak egyszer kerül sorra, és a kiválasztás sorrendje nem számít, akkor az n elem egy k-adosztályú ismétlés nélküli kombinációját kapjuk. Az n elem kadosztályú kombinációinak számát a C n k szimbólummal jelöljük 1.5 tétel Az n különböző elemek k-adosztályú kombinációinak száma n(n-1) .(n-k+1) k! Cnk =  n A fenti kifejezést szokás az   szimbólummal is jelölni (n alatt a k).  k k C n a következő alakban is felírható: n! Cnk = ( n  k )! k ! Ismétléses kombináció: adott n különböző elem. Ha n elem közül k elemet úgy választunk ki, hogy egy elem többször is sorra kerülhet, és a kiválasztás sorrendje nem számít, akkor az n elem egy k-adosztályú ismétléses

kombinációját kapjuk. Az n elem k-adosztályú ismétléses kombinációinak számát a C n k(i) szimbólummal jelöljük. 1. 6 tétel Az n különböző elem k-adosztáylú ismétléses kombinációinak száma  n  k  1 C n k(i) =   k  4. Binomiális tétel A kombinatorika eszközeivel egyszerű módszert nyerhetünk egy kéttagú kifejezés (binom) nedik hatványának polinommá történő alakítására. Ezt mutatja be a következő, az ún binomiális tétel. 1. 7tétel Tetszőleges kéttagú kifejezés (binom) bármely nemnegatív egész kitevőjű hatványa polinommá alakítható a következő módon:  n  0  n 1  n  n  n 1  n n  n  ab    b     a n  k b k  n  1  n k 0 k  a  b n    a n    a n 1b. (nN;a,bR)  n Az   szimbólumot binomiális együtthatónak nevezzük.  k Figyeljük meg,

hogy az összeg n+1 tagból áll, az a és a b kitevőjének az összege minden tagban n. Az a kitevője n-től 0-ig fogy, míg a b kitevője 0-tól n-ig növekszik és megegyezik az n alatti számmal. A binomiális tétel n=1, 2, 3-ra alkalmazva, az algebrából már jól ismert azonosságokhoz jutunk: 1  1 0  1 0 1   a b  a  b  0  1 n= 1 esetén (a +b) 1=   a b  2 2 2  2 1 1  2 0 2  a b    a b    a b  a 2  2ab  b 2 0  2   1  n =2 esetén (a + b)2 =   3  0 n =3 esetén (a + b)3 =   a b 3 0  3  3  3    a 2 b 1    a 1b 2    a 0b 3  a 3  3a 2 b  3ab 2  b 3  1  2  3  0  0 A tétel n =0 esetén is igaz, hiszen (a + b)0 =   a0 b0 = 1 Bizonyítás: Az (a + b)n nem más, mint egy olyan n tényezős sorozat, amelynek minden tényezője (a + b), 1 2 n azaz (a +

b)n = (a  b) (a  b).( a  b) n2 A szorzást elvégezzük úgy, hogy minden tényezőből egy-egy tagot szorzunk össze az összes lehetséges módon, és az így nyert szorzatokat összeadjuk. Például n = 3 esetén: (a + b)3 = (a + b)(a + b)(a + b) Ha mindhárom tényezőből az a-t szorozzuk össze, a3 -t kapjuk. Ha két (a + b) tényezőből a-t, a harmadikból b-t veszünk, a2 b-t kapunk. Ezt azonban háromféleképpen terheljük meg, hiszen a b-t választjuk az 1., a 2 Vagy a 3 Tényezőből Így tehát 3a2 b adódik. Ha egy (a + b) tényezőből választjuk az a-t, a másik kettőből a b-t, akkor ab2 lesz a szorzat. És mivel ezt is háromféleképpen tehetjük meg, 3ab2 -et kapunk. Végül, ha egyik (a + b) tényezőből sem választunk a-t, más szóval mindháromból a b-t szorozzuk össze, b3 lesz a szorzat. Így (a + b)3 = a3 + 3a2 b + 3ab2 + b3 Hasonló módon járunk el 1 2 n (a + b)n =  a  b a  b . a  b , n 2 esetében is. Ha

mindegyik (a + b) tényezőből az a-t szorozzuk össze, an adódik. Ha n-1 tényezőből az a-t, egyből a b-t szorozzuk össze, an-1b lesz a szorzat. De mivel ilyen szorzatot n esetben kapunk, mert a n tényező bármelyikéből választjuk a b-t, tehát nan-1 b lesz az eredmény.  n Ha n-2 tényezőből a-t , kettőből b-t veszünk, an-2b2 lesz a szorzat. Mivel azonban a b-t    2 - féleképpen választjuk ki az n darab (a + b) tényezőből, összesen  n n-2  a b  2 lesz az eredmény. Hasonló módon, ha n-3, n-4 . tényezőből választunk a-t, a többi 3,4, tényezőből b-t,  n  n akkor an-3 b3 , an-4b4 , .szorzathoz jutunk Az együtthatók pedig sorra   ,   ,  3  4 .lesznek, hiszen ennyiféleképpen választjuk ki azokat az (a + b) tényezőket, amelyeknek a b tagja szerepel a szorzatban. Végül, ha egyik tényezőből sem választunk a-t, azaz mindegyikből b-t szorzunk össze, bn adódik. Az így

nyert sorozatok összege, felhasználva, hogy  n  n  n n  és     1  0  n 1  a következő:  n  n  n  a  b n    a n    a n 1b.  b n  0 1   n és ezzel a tételt bizonyítottuk. 5. Binomiális együtthatók tulajdonságai 1.8 tétel Bármely k, n  N és 0kn esetén fennáll a a, szimmetriatulajdonság  n  n       k  n  k b, összegtulajdonság  n  n   n  1        k   k  1  k  1 c,  n  n  n  n         .   2 n  n  0  1   2 izonyítás a, Az állítás helyességéről könnyen meggyőződhetünk, hiszen értelmezésük szerint  n n  n! n! n! és       k   n  k !k !  n  k   n   n

 k  ! n  k  ! k ! n  k  ! Mivel azonban a két összefüggés csupán a nevezőben szereplő tényezők sorrendjében tér el egymástól, így valóban igaz állításunk. b Tudjuk, hogy  n n  n! n! és      k   n  k !k !  k  1  n   k  1 ! k  1 ! Összeadva a két törtet  n  1 !  n  1 n! n! n! k  1  n! n  k  n! n  1        n  k  ! k !  n  k  1 ! k  1 !  n  k  ! k  1 !  n  k  ! k  1 !  n  k  ! k  1 !  k  1 c, Az állítás helyességét a binomiális tétel segítségével könnyen igazolhatjuk. Legyen ugyanis a = 1 és b =1, ekkor a binomiális tétel szerint  n  n  n 1  1 n    1n10    1n 111 .  101n  0 1   n ahonnan  n  n 

n 2 n       .   0  1   n A binomiális együtthatók megismert tulajdonságait jól hasznosíthatjuk a valószínűségszámítási feladatok megoldásában. Kombinatorika: Vnk  n!  n(n  1)    (n  k  1) , (n  k )! Vnk , C  Pk k n C nk  l n! , ahol  k i  n k1! k 2 !.k l ! i 1 p nk1 ,k 2 .kl  Pn = 1 · 2 . (n – 1)· n = n! Vnk ( i )  n k C n0  C nn  1  n  k  1  C nk ( i )   k    n  n(n  1)    (n  k  1) n!     k!(n  k )!  k  k (k  1)    2  1 Binomiális tétel: n  n 1  n  0 n ab   a b , (n  N , a, b  R). n  n  1 a  b n   a n b 0   a n1b1   a n2 b 2       n 0 n 1 n  2  n 0 1

             2 n  n  n  n n Teljes eseményrendszer:  Bi  I és i 1 Bi B j  0, ha i j Disztributív törvények: A(B+C) = AB+AC A+(BC) = (A+B)(A+C) De Morgan-féle képletek: A  B  A B AB  A  B Események valószínűsége: 0  P(A)  1 P() = 0 ha A  B, akkor P(A)  P(B) P(H) = 1 (i, j  1,2., n) P(A+B) = P(A)+P(B)–P(AB) vagy P(AB) = P(A)+P(B)–P(A B) ha AB =  vagy A B =  akkor P( A+B) = P(A)+ P(B) vagy P( AB) = P(A)+ P(B) P(A) = Klasszikus valószínűségi mező: kedvező esetek száma k  összes estek száma n Visszatevéses mintavétel ( Bernoulli-féle képlet): n p k    p k q n k , k  M  , p N  q  1  p,  k  0,1,2,  , n   Általánosítás: p k1 ,k 2 ,,k r  n! p1k1 p 2k2    p rkr , k1!k 2 !  k r ! M   pi  i

, N  Visszatevés nélküli mintavétel:  M  N  M     k  n  k   pk  , (k  0,1,  , n) N   n Általánosítása:  M 1  M 2   M r       k1  k 2   k r   r  p k1 , k 2 ,,k r  ,  M i  N, N  i 1   n  k  n  i 1 i  r  k  n  i i 1 P( AB) P( A  B) vagy P(A| B) = P( B) P( B) P(A| B) = Feltételes valószínűség:  r Szorzási szabály: P( A  B)  P( A  B)  P( B) Valószínűségek általános szorzási szabálya: P( A1  A2      An )  P( A1 )  P( A2  A1 )  P ( A3  A1  A2 )    P( An  A1  A2      An 1 ) n P(A) =  P( A | Bi )P( Bi ) A teljes valószínűség tétele: i 1 P( Bi |A) = Bayes – tétel: P( A | Bi )P( Bi ) n  P( A |

B )P( B ) j1 j P(A| B) = P(A) Független események: Az eloszlásfüggvény: j P(AB) = P(A)P(B) P(a  ξ<b) = F(b)– F(a) F(x) = P(ξ<x) x F(x) =  f (t )dt ' A sűrűségfüggvény: f(x) = F (x),  b A várható érték: M(ξ) = Σ p k x k   xf ( x)dx  a A szórásnégyzet: 2 D (ξ) = M[ξ– M(ξ)] 2 = M(ξ 2 )– [M(ξ)] 2 , 2    D (ξ) =  x p k    x k p k  k 1  k 1  A binomiális eloszlás: n (k=0,1,  , n) P(=k)=   p k q n  k , k   2 M(ξ) = np 2 k D(ξ) = npq   D (ξ) =  x f ( x)dx -   xf ( x)dx      2 2 2 A hipergeometrikus eloszlás:  M  N  M     k  n  k   P(ξ = k) = p k = N   n  M(ξ) = np D(ξ) = M , n  N  , (k = 0, 1, ., n) N,M,n  N , n 1  N n  np(1  p)1   = npq N 1  m

1 A Poisson - eloszlás: P(ξ = k) = p k = M(ξ) = λ, k k! D(ξ) = e  , (k = 0, 1, 2, .)  A normális eloszlás: f ( x) = 1  2  e ( xm)2 2 2 ,R + F(x) = x 1  2 e  (r m)2 2 2  D(ξ) =  M(ξ) = m, Sajátos eset a standard normális eloszlás: m=0, σ =1;  xm F(x)=    x   1    x  ,    Csebisev – egyenlőtlenség: D 2   1 vagy P(|ξ- M(ξ)|  tD())  2 , t>1 P(|ξ- M(ξ)|  ε)  2 t  A nagy számok törvénye:   pq  pq k vagy P  n  p     1  2 P   p     2  n   n n  n  Kétdimenziós eloszlások: Együttes eloszlásfüggvény: F(x,y)=P(   x;  y ), x y Együttes sűrűségfüggvény: f(x,y)=   f (u , v)dvdu x, y   R . 2 x, y   R     A covariancia: cov  ,   M

  M    M    M    M  M  . , M     xi y j pi , j A korrelációs együttható: cov ,  R ,   D D  2 dt