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.

Dokaz

Trditev lahko dokažemo z indukcijo naštevilo $n$. Zanimivejša pa je naslednja kombinatorična utemeljitev identitete. Potenco $(x + y)^n$ najprej zapišimo kot produkt $n$ faktorjev oblike $x + y$:

$$\underbrace{(x+y)(x+y)···(x+y)}_{n}.$$

Ko s pomočjo distributivnostnega zakona odpravimo vse oklepaje, dobimo vsoto produktov oblike $a_1a_2...a_n$, kjer posamičen faktor $a_i$ izberemo izmed nedoločenk $x$ in $y$ v $i$-tem oklepaju $(x+y)$ zgornjega produkta:

$$(x+y)^n = \sum_{(a_1,...,a_n) \in \{x,y\}^n} a_1a_2...a_n.$$

Produkt $a_1a_2...a_n$ je torej oblike $x^ry^{n-r}$, pri čemer $r$ pove, koliko od faktorjev $a_i$ je enakih $x$. Ker lahko $r$ oklepajev, iz katerih za $a_i$ vzamemo nedoločenko $x$, izberemo na ${n \choose r}$ načinov, se posamični člen $x^ry^{n-r}$ v razvoju potence binoma $(x+y)^n$ pojavi natanko ${n \choose r}$-krat. S tem je trditev dokazana.

Dokaz

Prvo trditev dobimo, če v binomsko formulo vstavimo $x = y = 1$, drugo pa, če vstavimo $x = 1$ in $y = -1$.

Dokaz

Trditev lahko dokažemo z računskim rokohitrstvom takole:
Najprej formulo za binomske koeficiente podamo v naslednji “neokrajšani” obliki,

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

Nato pa v zgornji formuli za $r$ vstavimo $n-r$, in dobimo naslednjo enakost:

$${n \choose n-r} = \frac{n!}{(n-r)!(n-(n-r))!} = \frac{n!}{(n-r)!r!} = {n \choose r}.$$

S tem je trditev dokazana.
Za nas pa je zanimivejši naslednji kombinatorični dokaz. Naj bo $\mathcal{N}$ poljubna $n$-elementna podmnožica. Definirajmo preslikavo, ki vsaki $r$-elementni podmnožici $A \subseteq \mathcal{N}$ priredimo njen komplement $A^C \subseteq \mathcal{N}$. Ni se težko prepričati, da je takšna preslikava bijekcija med množico $\mathcal{K}(\mathcal{N},r)$ vseh $r$-elementnih podmnožic množice $\mathcal{N}$ in množico $\mathcal{K}(\mathcal{N},n- r)$ vseh $(n-r)$-elementnih podmnožic množice $\mathcal{N}$. Ker je prvih ${n \choose r}$, slednjih pa ${n \choose n-r}$, je trditev s tem dokazana.

Dokaz

Navedimo dva dokaza te trditve. Prvi je povsem računski in temelji na formuli iz trditve 2.7. Računajmo:

$${n \choose r} + {n \choose r+1} = \frac{n^\underline{r}}{r!}+ \frac{n^\underline{r+1}}{(r+1)!} = \frac{(r+1)n^\underline{r} + n^\underline{r+1}}{(r+1)!}=$$ $$= \frac{(r+1)n^\underline{r} +(n-r)n^\underline{r}}{(r+1)!} = \frac{(n+1)n^\underline{r}}{(r+1)!} = \frac{n+1^\underline{r+1}}{(r+1)!}= {n+1 \choose r+1}.$$

Drugi dokaz trditve pa je povsem kombinatoričen in upošteva le dejstvo, da je ${n \choose r}$ enako številu $r$-elementnih podmnožic $n$-elementne množice.
Naj bo $\mathcal{N}$ poljubna $(n+1)$-elementna množica. Brez izgube splošnosti lahko predpostavimo, da je $\mathcal{N} = \{1,2,...,n,n + 1\}$. Množico $(r + 1)$-elementnih podmnožic razdelimo v dve skupini: V prvi naj bodo tiste podmnožice, ki vsebujejo element $n + 1$, v drugi pa preostale. V drugi skupini so tako pristale ravno vse $(r + 1)$-elementne podmnožice množice $\mathcal{N} \setminus \{n+1\}$ – teh je natanko ${n \choose r+1}$
. Preštejmo še one iz prve skupine – imenujmo jo $R_1$. Vsaki podmnožici $A$ iz $R_1$ priredimo množico $A' = A \setminus \{n+1\}$. Ker $A$ po predpostavki vsebuje element $n+1$, je $A'$ $r$-elementna podmnožica množice $\mathcal{N} \setminus \{n+1\}$. Predpis $A \mapsto A'$ tako podaja preslikavo med $R_1$ in $\mathcal{K}(\mathcal{N}\setminus \{n+1\},r)$. Ni težko videti, da je preslikava, podana s predpisom, $A' \mapsto A' \cup \{n+1\}$ inverz preslikave $A \mapsto A'$. Zato je preslikava $A \mapsto A'$ bijekcija, in množici $R_1$ ter $\mathcal{N}\setminus \{n+1\}$ sta enako močni. Ker slednja šteje ${n \choose r}$ elementov, je to hkrati tudi moč množice $R_1$. V obeh skupinah skupaj je torej ${n \choose r} + {n \choose r+1}$ podmnožic. Po drugi strani pa obe skupini podmnožic skupaj tvorita množico vseh $(r+1)$-elementnih podmnožic $(n+1)$-elementne množice $\mathcal{N}$, za katere pa vemo, da jih je ${n+1 \choose r+1}$. Enakost je s tem dokazana.

Dokaz

Naj bo $x$ element unije $\cup^n_{i=1}A_i$. Tedaj je $x$ vsebvan v vsaj eni od množic $A_i$. Pa denimo, da je $x$ vsebovan v natanko $m$ množicah $A_i$. Tedaj se za vsak $k \in \{1,...,n\}$ element $x$ pojavi v natanko ${m \choose k}$ presekih $\cap_{i \in \mathcal{J}}A_i$ za katere je $|\mathcal{J}|=k$. To pa pomeni, da $x$ za vsak $k$ prispeva k desni strani enakosti (*) natanko $(-1)^{k-1}{m \choose k}$, skupaj torej

$$\sum^n_{k=1}(-1)^{k-1}{m \choose k} = 1 + \sum^m_{k=0}(-1)^{k-1}{m \choose k}= 1,$$

kjer smo pri zadnji enakosti uporabili trditev 3.4. S tem je trditev dokazana.

Rešitev

Za $i= 1,...,n$ naj bo $A_i$ množica vseh permtacij v $P_n$, za katere je $i$ fiksna točka. Unija $\cup_{i=1}A_i$ je natanko množica vseh permutacij, ki niso deranžmaji. Nas torej zanima število

$$d_n = |P_n|-|\cup^n_{i=1}A_i| = n!-|\cup^n_{i=1}A_i|.$$

Vzemimo poljubno indeksno množico $\mathcal{J} \in {\mathbb{N}_n \choose k}$ in premislimo, koliko elementov premore presek $\cap_{i \in \mathcal{J}}A_i$. Elementi tega preseka so natanko tiste permutacije $(a_1,...,a_n)$, za katere je $a_i = i$ za vsak $i \in \mathcal{J}$, na preostalih mestih $\mathbb{N}_n \setminus \mathcal{J}$ pa se nahaja poljubna permutacija množice $\mathbb{N}_n \setminus \mathcal{J}$. Zato je moč preseka $\cap_{i \in \mathcal{J}}A_i$ enaka $(n-k)!$ in

$$S_k = \sum _{\mathcal{J} \in {\mathbb{N}_n \choose k}}|\cap_{i \in \mathcal{J}}A_i|= {n \choose k}(n-k)!= \frac{n!}{k!}.$$

Iz načela vključitev in izključitev sledi:

$$|\cup^n_{i=1}A_i|=\sum^n_{k=1}(-1)^{k-1}S_k = n! \sum^n_{k=1}(-1)^{k-1} \frac{1}{k!}$$

Opazimo, da zaporedje $\frac{d_n}{n!}$ zelo hitro konvergira k $e^{-1}$. Verjetnostna interpretacija tega dejstva je, da je verjetnost, da naključno izbrana permutacija nima fiknish točk približno enaka $e^{-1} \approx 0,37$.

Rešitev

Če revoleraše z naravnimi števili med $1$ in $n$, lahko situacijo po odhodu iz salona opišemo s permutacijo $(a_1,...,a_n)$ množice revolverašem, kjer je $a_i$ zaporedna številka lastnika revolverja, ki ga je ob odhodu zagrabil $i$-ti revolveraš. Vseh možnih situacij po odhodu je torej $n!$ in vse so enako verjetne. Situacije, kjer nihče od revolverašev ne zagrabi svojega revolverja, pa ustrezajo natanko deranžmajem. Zato je verjetnost tega dogodka enaka

$$\frac{d_n}{n!}= \sum^n_{k=0}(-1)^k \frac{1}{k!}.$$