Druga lekcija: Izbori

Pritisnite F11

Iz varnostnih razlogov je mogoče celozaslonski način vključiti samo s pritiskom na gumb F11 na tipkovnici.

Ko ste enkrat v celozaslonskem načinu, ga izključite spet s pritiskom na F11.

Druga lekcija: Izbori

Avtor: Primož Potočnik

Sodelujoče organizacije

Izvedbo projekta je omogočilo sofinanciranje Evropskega sklada za regionalni razvoj in Ministrstva za visoko šolstvo, znanost in tehnologijo. Pri tehnični izvedbi projekta so sodelovali: Fakulteta za matematiko in fiziko Univerze v Ljubljani, Društvo matematikov, fizikov in astronomov Slovenije ter DMFA-založništvo.

2 Druga lekcija: Izbori

Razdelek pričnimo z naslednjim zgledom. Pri igri loto se v bobnu nahaja $39$ kroglic, oštevilčenih s števili $1, 2, ..., 39$ . Organizator igre iz bobna zaporedoma sedemkrat izvleče po eno kroglico. Na koliko načinov lahko to stori?

Odgovor je odvisen od tega, kako razumemo besedo “način”. Osnovni dilemi pri razumevanju naloge sta, ali naj kroglico, ki smo jo v posameznem koraku izvlekli, vrnemo v boben in ali je za nas vrstni red izvlečenih kroglic pomemben. Ti dve dilemi mora seveda razrešiti tisti, ki nam je nalogo zastavil. Od njegovega odgovora je odvisno, kako bomo nalogo reševali.

Kadar je za zastavljalca naloge vrstni red pomemben, bomo preštevali urejene izbore, ki jim zaradi zgodovinskoh razlogov rečemo tudi variacije.

Če kroglice vračamo v boben, bomo govorili o variacijah s ponavljanjem, sicer pa o variacijah brez ponavljanja. če pa vrstni red ni pomemben, bomo šteli neurejene izbore, ki jih imenujemo tudi kombinacije. Podobno kot prej govorimo o kombinacijah s ponavljanjem in brez ponavljanja – odvisno od tega, ali kroglice vračamo v boben ali ne.

V nadaljevanju si bomo vsako od štirih možnih interpretacij naloge ogledali nekoliko podrobneje. Za lažjo izražavo bomo rezultat vlečenja kroglic imenovali žreb. Množico $39$ kroglic označimo z $\mathcal{N} = \{1, 2, ..., 39\}$ .

2.1 Urejeni izbori s ponavljanjem

Denimo, da izvlečene kroglice v boben vračamo, vrstni red izvlečenih kroglic pa je pomemben. Tedaj lahko rezultat žreba enolično predstavimo z urejeno sedmerico elementov množice kroglic $\mathcal{N}$ , pri čemer urejeno sedmerico $(a_1, ..., a_7)$ razumemo kot tisti žreb, pri katerem v $i$ -tem poskusu izvlečemo kroglico $a_i \in \mathcal{N}$ . To nas napelje na idejo, da urejeni izbor s ponavljanjem definiramo na naslednji način.

Definicija 2.1
Naj bo $N$ poljubna množica z $n$ elementi in $r$ poljubno naravnoštevilo. Urejeni $r$ -terici $(a_1, a_2, ..., a_r)$ elementov množice $N$ rečemo urejeni izbor elementov množice $N$ dolžine $r$ . Če želimo poudariti, da so lahko nekateri izmed elementov $a_i$ med seboj tudi enaki, dodamo, da gre za urejeni izbor s ponavljanjem. Množico vseh takšnih izborov označimo s simbolom $\bar{V}(N,r)$ .

Opomba

Ker množica $\bar{V}(N,r)$ vsebuje vse urejene $r$ -terice elementov množice $N$ , je enaka kartezičenmu produktu $r$ kopij množice $N$ . Od tod (in z upoštevanjem načela produkta) neposredno sledi naslednja trditev.

Trditev 2.2
Najbo $N$ poljubna množica z $n$ elementi in $r$ poljubno naravno število. Tedaj množica $\bar{V}(N,r)$ premore $n^r$ izborov.

Opomba

Urejenemu izboru $n$ -elementne množice dolžine $r$ v literaturi imenujejo tudi variacija s ponavljanjem $n$ elementov reda $r$ .

2.2 Urejeni izbori brez ponavljanja

Še naprej si mislimo, da je vrstni red izvlečenih kroglic pomemben, le da tokrat izbranih kroglic v boben ne vračamo. Tako kot prej si žreb, v katerem v $i$ -tem koraku izberemo kroglico $a_i$ , predstavimo z urejeno sedmerico $(a_1, ..., a_7)$ elementov $a_i \in \mathcal{N}$ . Ker kroglic ne vračamo, so elementi $a_i$ paroma različni. Po drugi strani pa vsaka sedmerica paroma različnih elementov množice $\mathcal{N}$ predstavlja kak žreb. Možnih žrebov je torej toliko, kot je različnih sedmeric paroma različnih kroglic v bobnu. Povedano povzemimo v naslednjo formalno definicijo urejenega izbora brez ponavljanja.

Definicija 2.3
Urejeni $r$ -terici paromara zličnih elementov množice $N$ rečemo urejeni izbor elementov množice $N$ dolžine $r$ brez ponavljanja. Množico vseh takšnih izborov označimo s simbolom $\mathcal{V}(N,r)$ .

Urejenih izborov brez ponavljanja je seveda nekoliko manj kot vseh urejenih izborov. Preden jih preštejemo, vpeljimo naslednji funkciji naravnih števil $n$ in $r$ :

$n^\underline{r} = n(n-1)···(n-r+1), n!= n^\underline{r} = n(n-1)···1$

in dodatno de?nirajmo še $n^\underline{0} = 0! = 1$ za vsak $n \in \mathbb{N}_0$ . Simbolu $n^\underline{r}$ rečemo padajoča potenca števila $n$ , simbolu $n!$ pa n fakulteta (tudi faktoriela).

Trditev 2.4
Naj bo N poljubna množica z $n$ elementi in $r$ poljubno naravno število. Tedaj množica $\mathcal{V}(N,r)$ premore n^\underline{r} izborov.

Dokaz

Formalni dokaz trditve je najlažje izpeljati z indukcijo na dolžino izbora $r$ . Če je $r = 1$ , je tipični izbor oblike $(a)$ , kjer je $a$ element množice $N$ . Ker je elementov množice $N$ ravno $n$ , je toliko tudi izborov. Formula torej drži za $r = 1$ .

Pa denimo, da za neki $k$ formula drži za vse $r \le k$ . Dokažimo, da velja tudi za $r = k + 1$ . Res! Označimo elemente množice $N$ s simboli $a_1, ..., a_n$ . Izbore iz $\mathcal{V}(N,k+1)$ razvrstimo v $n$ skupin, $\mathcal{R}_1, ..., \mathcal{R}_n$ , pri čemer v skupino $\mathcal{R}_i$ razvrstimo vse izbore, ki imajo na prvem mestu element $a_i$ . Če izboru $(a_i, x_1, ..., x_k)$ iz množice $\mathcal{R}_i$ odrežemo prvo komponento, dobimo “ostanek” $(x_1, ..., x_k)$ , ki je izbor iz $\mathcal{V}(N \setminus \{a_i\},k)$ . Pri tem se vsak izbor iz $\mathcal{V}(N \setminus \{a_i\},k)$ pojavi natanko enkrat kot “ostanek” izbora iz skupine $\mathcal{R}_i$ . Zato je v vsaki skupini $\mathcal{R}_i$ natanko toliko izborov, kot je izborov v množici $\mathcal{V}(N \setminus\{a_i\},k)$ ; teh pa je, kot zagotavlja indukcijska predpostavka, $n-1^k$ . Vseh iskanih izborov je tako $n(n-1)^\underline{k} = n^\underline{k+1} = n^\underline{r}$ . S tem je indukcijski korak dokazan.

Za razliko od urejenih izborov s ponavljanjem, kjer je bila dolžina izbora lahko poljubno velika, je dolžina urejenega izbora brez ponavljanja omejena s številom elementov, ki jih izbiramo. Z drugimi besedami,

$\mathcal{V}(N,r) = \emptyset$ brž ko je $r >|N|$ .

Urejenim izborom elementov množice $N$ brez ponavljanja najdaljše dopustne dolžine (torej dolžine $r = |N|$ ) rečemo tudi permutacija množice $N$ . Iz trditve 2.4 neposredno sledi naslednje:

Trditev 2.5
Število vseh permutacij $n$ -elementne množice je enako

$n^\underline{n} =n!$ .

Opomba

Permutacijo $(a_1, ..., a_n)$ množice $N$ lahko razumemo tudi kot linearno ureditev elementov množice $\mathcal{N}$ , pri kateri je $a_1$ “prvi” element, ki mu “sledi” element $a_2$ in tako dalje, vse do “zadnjega” elementa $a_n$ . Če pa so elementi množice $N$ že vnaprej podani z nekim vrstnim redom (npr. če je $N = \{1, 2, ..., n\}$ ) pa lahko na permutacijo $(a_1, ..., a_n)$ pogledamo tudi kot na bijektivno preslikavo iz množice $N$ vase, ki $i$ -temu elementu množice $N$ priredi element $a_i$ .

2.3 Neurejeni izbori brez ponavljanja

Mislimo si sedaj, da vrstni red izbranih kroglic ni pomemben, izbranih kroglic pa ne vračamo v boben. V tem primeru lahko izid žreba enolično podamo z množico sedmih izžrebanih kroglic. Možnih izidov žreba je torej toliko, kot je vseh sedem elemntov podmnožic množice kroglic $\mathcal{N}$ . To nas napelje na naslednjo definicijo.

Definicija 2.6
Naj bo $N$ poljubna množica z $n$ elementi in $r$ poljubno nenegativno celo število. Tedaj $r$ -elementni podmnožici množice $N$ rečemo neurejeni izbor elementov množice $N$ brez ponavljanja dolžine $r$ . Množico vseh takšnih izborov označimo s simbolom $\mathcal{K}(N,r)$ njihovo število pa s simbolom

${n \choose r}=|\mathcal{K}(N,r)|,$

ki mu pravimo binomski simbol (tudi binomski koeficient) in ga preberemo “n nad r”.

Trditev 2.7
Za poljubni nenegativni celi števili $n$ in $r$ velja enakost

${n \choose r} = \frac{n^\underline{r}}{r!}.$

Dokaz

Naj bo $N$ poljubna $n$ -elementna množica in $r$ poljubno nenegativno celo število. Za $r = 0$ , trditev preide v stavek, da poljubna množica premore natanko eno podmnožico z $0$ elementi. Ker je prazna množica edina $0$ -elementna množica, je slednje očitno pravilno. Predpostavimo torej lahko, da je $r \ge 1$ .

Trditev bomo dokazali tako, da bomo ponovno prešteli vse urejene izbore brez ponavljanja iz množice $\mathcal{V}(N,r)$ . Za $A \in \mathcal{K}(N,r)$ definirajmo naslednjo množico urejenih izborov:

$\mathcal{R}_A = \{(a_1, ..., a_r) :\{a_1, ..., a-r\} = A\}.$

Opazimo, da je $\mathcal{R}_A$ natanko množica vseh permutacij množice $A$ , zato je $|\mathcal{R}_A|=r!$ . Ker se vsak izbor iz $\mathcal{V}(N,r)$ pojavi v natanko eni od množic $\mathcal{R}_A$ (namreč tisti, za katere je množica njegovih komponent enaka $A$ ), je število vseh takšnih izborov enako ${n \choose r}r!$ . Iz trditve 2.4 tedaj sledi enakost

${n \choose r}r! = n^\underline{r}.$

Delimo še z $r!$ in dobimo formulo iz trditve.

2.4 Neurejeni izbori s ponavljanjem

Nazadnje se lotimo še različice naloge, kjer vrstni red izbranih kroglic ni pomemben, izžrebane kroglice pa vračamo v boben. V tem primeru izida žreba žal ne moremo podati z množico izžrebanih kroglic, saj množica ne dopušča večkratnih pojavitev svojih elementov. Zato za opis žreba potrebujemo matematično strukturo, ki ima podobne lastnosti kot množica, dopušča pa večkratno pripadnost kakega elementa. Takšnemu objektu pravimo multimnožica. Formalno je multi množico najlažje opisati kot preslikavo, ki vsakemu potencialnemu elementu priredi njegovo kratnost v multimnožici. Pri tem za elemente, ki jih v multimnožici ni, rečemo, da v njej nastopajo s kratnostjo $0$ .

Definicija 2.8
Multimnožica z elementi v množici $N$ je poljubna preslikava

$\mu: N \to \mathbb{N}_0.$

Pri tem številu $\mu(a), a \in N$ , rečemo kratnost elementa $a$ v multimnožici $\mu$ , vsoti

$\sum_{a \in N}\mu(a)$

pa moč multimnožice $\mu$ .

Neformalno pa lahko multimnožice podajamo tudi kot množice, pri čemer dopuščamo, da se nekateri elementi multimnožice pojavijo več kot enkrat. Pri tem red elementov, tako kot pri množicah, ni pomemben. Na primer, multimnožico $\mu: \{a,b,c,d\}\to \mathbb{N}_0$

$\mu(a) = 1, \mu(b) = 2, \mu(c) = 0, \mu(c) = 3$

lahko podamo tudi z naštevanjem elementov

$\mu = [b,c,c,a,c,b] = [c,b,c,b,a,c] = ... ali \mu = [a^1,b^2,c^3]$

Moč multimnožice $\mu$ je $6$ .

Neurejene izbore s ponavljanjem lahko sedaj opišemo v jeziku multimnožic.

Definicija 2.9
Naj bo $N$ množica moči $n$ . Multimnožici moči $r$ z elementi v množici $N$ rečemo neurejeni izbor elementov množice $N$ dolžine $r$ s ponavljanjem. Množico vseh takšnih multimnožic označimo s simbolom

$\bar{\mathcal{K}}(N,r),$

njihovo število pa s

$\bar{\mathcal{K}}(n,r).$

Trditev 2.10
Za poljubni nenegativni števili $n$ in $r$ velja

$\bar{\mathcal{K}}(n,r) = {n+r-1 \choose n-1} = {n+r-1 \choose r}.$

Dokaz

Vzemimo n-elementno množico $N = \{a_1,...,a_n\}$ . Trditev dokažemo na strog matematičen način tako, da najdemo bijektivno preslikavo iz množice $\bar{\mathcal{K}}(N,r)$ v množico $\bar{\mathcal{K}}(NN_{n+r-1},n-1)$ .
Naj bo $\mu: N \to \mathbb{N}_0$ multimnožica moči $r$ . Za $k \in {1,...,n- 1}$ definirajmo

$b_k = \mu(a_1)+...+ \mu(a_k)+ k$

in jih združimo v množico $B_{\mu} = \{b_1,b_2,...,b_{n-1}\}$ . Dokažimo najprej, da je $B_\mu$ elementna podmnožica množice $\mathbb{N}_{n+r-1}$ in da premore $n-1$ elementov.
Ker je

$b_{k+1} = b_k + \mu(a_{k+1})+1$

za vsak $k \ge 1$ , je zaporedje števil $b_k$ strogo naraščajoče. Ker je $b_1 = \mu(a_1) + 1 \ge 1$ , so števila $b_k$ pozitivna. Po drugi strani pa je

$b_{n-1} = \mu(a_1)+...+\mu(a_{n-1})+ n-1 \le \sum_{k=1}^n \mu(a_k)+ n-1 = r+n-1. (*)$

Zato je res $B_{\mu}$ element množice $\mathcal{K}(\mathbb{N}_{n+r-1},n- 1)$ . Dokažimo zdaj, da je preslikava

$\Phi: \bar{\mathcal{K}}(N,r) \to \mathcal{K}(\mathbb{N}_{n+r-1},n-1), \Phi(\mu) = B_{\mu},$

bijekcija. Surjektivnost dokažemo tako, da vzamemo poljubno $(n - 1)$ -elementno podmnožico $B \subseteq \mathbb{N}_{n+r-1}$ , uredimo njene elemente $b_k$ po velikosti, $b_1 < b_2 < ... < b_{n-1}$ , in rešimo sistem enačb izhajajoč iz prvega enačaja formule (*) na neznanke $\mu(a_k)$ . Dobimo:

$\mu(a_1) = b_1 - 1$ , $\mu(a_k) = b_k - b_{k-1}-1$ za $k \ge 2$ .

Za tako določeno multimnožico $\mu \in \bar{\mathcal{K}}(N,r)$ očitno velja $B_µ = B$ . S tem je surjektivnost preslikave $\Phi$ dokazana. Injektivnost sledi iz dejstva, da so števila $b_k$ v formuli (*) natanko določajo vrednosti $\mu(a_k)$ .

2.5 Ponovno o igri loto

Na koncu poglavja se vrnimo k naši začetni nalogi o številu možnih žrebov sedmih kroglic. Pri vseh štirih različicah naloge preštevamo izbore elementov množice z $n = 39$ elementi dolžine $r = 7$ .

Če je vrstni red izvlečenih kroglic pomemben, kroglice pa vračamo v boben, štejemo urejene izbore s ponavljanjem. Teh je – v skladu s trditvijo 2.2 – natanko

$39^7 = 137231006679.$

Če je vrstni red izvlečenih kroglic pomemben, kroglic pa ne vračamo v boben, štejemo urejene izbore brez ponavljanja. Teh je – v skladu s trditvijo 2.4 – natanko

$39^\underline{7} = 77519922480.$

Če vrstni red izvlečenih kroglic ni pomemben, kroglice pa vračamo v boben, štejemo neurejene izbore s ponavljanjem. Teh je – v skladu s trditvijo 2.10 – natanko

${39+7-1 \choose 7} = {45 \choose 7} = 45379620.$

Nazadnje si oglejmo še interpretacijo naloge, ki ustreza dejanskim pravilom igre loto, torej, ko vrstni red izvlečenih kroglic ni pomemben in kroglic ne vračamo v boben. Tedaj štejemo neurejene izbore brez ponavljanja, ki jih je – v skladu s trditvijo 2.7 – natanko

${39 \choose 7} = \frac{39^\underline{7}}{7!} = 15380937.$