234 (12)

9. R a c h a n• k p r a wd o p o d o b i • A 11 w a

9. RACHUNEK PRAWDOPODOBIEŃSTWA

9.1.2. Podstawowe pojęcia kombinatoryczne

2 _ -

N.

kolejność elementów w tych podzbiorach jest nieistotna

a) lYrmułuęjii (lwi powtórzeń) n-wyra/owa zbioru //•elementowego (w e iV, ) o różnych elementach jest to każdy ciąg //-wyrazowy utworzony z wszystkich elementów tego zbioru. Symbol p_n.

(I) Permutowanic //-elementowego zbioru Z to ustalanie porządku elementów w tym zbiorze, czyli równowartościowe odwzorowanie zbioru 1.2.....nno zbiór Z.

.....»} -z

i — M

lub png/potządkawnnic elementów

€ Z (i = 1.2.....«)\vinnej dowolnej

kolejności.

n •— z.

Inaczej: p_m — to zmiana kolejności elementów zbioru Z na różne możliwe sposoby.

O permutacji zbioru Z mówimy wtedy, gdy chodzi o zmianę kolejności elementów tego zbioru.

(2) Liczba P wszystkich różnych permutacji p zbioru złożonego z // różnych elementów wyraża się wzorem:

P = //!; n € N.

na przykład Z = {a, b, c}, // = 3, P₃ = 3! = 6. Oto wszystkie możliwe permutacje: p₃:{l.2,3} — {a.fo.c}, czyli

1    — a    a    b    b    c    c

2    •— £>VcVaVcVaVZ?

3«c    b    c    a    b    a

Istnieje 6 różnych możliwości (ciągów 3-wyrazo-wych) uporządkowania elementów zbioru Z, czyli p₃= |(a,fc,c),(a, c,b), (fe,a, c), (b, c,a), (c, a, b),

( c. b, a ) J. W każdej z 6 możliwości zbiór Z jest ten sam, występuje tylko inna kolejność elementów.

(3)    Jeżeli w zbiorze //-elementowym Z znajduje się m < n jednakowych elementów, to liczba permutacji takiego zbioru Z jest równa:

Pini) = -Ą; n,me N., m < n / ml    *

na przykład Z = { a, a, b }, n = 3, m = 2, P₃( 2) =    = 3. Oto wszystkie możliwe permuta-

cje tego zbioru: {(a, a, b), (a, b, a), ( b, a,a)\.

(4)    Uogólnienie: Jeżeli w zbiorze //-elementowym Z = { z,.. .z_n } element z_k powtarza się //, razy, z₂ powtarza się n₂ razy, z_k powtarza się n_k razy, to liczba wszystkich różnych //-wyrazowych permutacji z powtórzeniami zbioru //-elementowego Z wyraża się wzorem:

Pl //.,//......n. ) - —;-P'-    9

"^{V 1}    ‘ ^k) «.^! V ' n_kV

",*= ^N+> ⁿt ~ liczba powtórzeń elementu »

/' = 1 ...k, //.+ //,+ ...+ n. = n ^{1 2} *

b) Kombinacja (bez powtórzeń) /fc-clcmcntowa ( k G N ) zbioru Z //-elementowego ( n e /V ^) różnych elementów jest to każdy podzbiór ^-elementowy ( k < n ) utworzony z elementów zbioru Z.

(1)    TWorzenie ^-elementowych kombinacji zbiom //-elementowego Z to tworzenie ^-elementowych podzbiorów (bez istotnej kolejności elementów w podzbiorach) utworzonych zc zbioru Z. Jeśli zbiór Z jest //-elementowy, to można z niego utwo-rzyć podzbiór 0-clcmentowy oraz podzbiory: 1-elc-mentowc, 2-clementowe, itd. In — I )-elemento\ve i podzbiór //-elementowy, czyli cały zbiór Z.

O kombinacji mówimy wtedy, gdy chodzi o wybór k elementów spośród n elementów bez ważnej kolejności elementów w wybranym ż-elemen-towym podzbiorze.

(2)    Liczba C* wszystkich różnych A-elemento-wych kombinacji (bez powtórzeń) zbioru //-elementowego wyraża się wzorem:

C^k=(^,}\ = ——r-; * e N,k < n,n " \*/ *!(//-*)!

na przykład Z = {a,b,c,d,e} n = 5. Podzbiorów 3-elementowych: k = 3(< 5) jest

||j fjj = aftr -¹⁰- WM

Oto te podzbiory 3-elementowe: la, b, c},{a, b, e}, {a, d, e}, {c. d, e}

{b, d, e}, { b, c,e},{b,c,d}

{ a, c, e }, { a, c, d }, { a, b, d }

Uwaga: Na przykład { c, d, e } = { d, e. c } są to te same podzbiory pod względem zawartości elementów (choć różnią się one kolejnością zapisanych elementów), gdyż w zbiorze (podzbiorze) kolejność nic odgrywa roli. Natomiast jako permutacje, czyli ciągi (kolejność ważna), są one różne: (c, d, e ) ^ (t/.r.r).

(3) Jeżeli Z = { z,.....z_n } jest zbiorem //-elemento

wym, to liczba kombinacji /.--elementowych z powtórzeniami, w której jest k, elementów z., k. elementów z,, itd. k_n elementów z„, gdzie A. + L t ...+!/* i k. G W dla i = I...// wyraża się wzorem:

7% *    / // + k — 1 \    / // + k — I V , .    . v u . \