Grafy Losowe Omówienie
Table of Contents

Zadania

1.

$|\Omega|=2^n$
$|A|={n \choose 6 }$ (0 dla n<6)
$P(A)=\frac{|A|}{|\Omega|}=\frac{{n\choose 6}}{2^n}$

2.

$|\Omega|=6^n$
$|A|={n \choose 6 } \cdot 5^{n-6}$ (0 dla n<6)
$P(A)=\frac{|A|}{|\Omega|}={n \choose 6}\left(\frac{1}{6}\right)^6 \left(\frac{5}{6}\right)^{n-6}$
Granica to oczywiście 0, co widać na kilka sposobów:

a)

(1)
\begin{align} 0 \le P(A) < \frac{ const \cdot n^6 } {\left(\frac{6}{5}\right)^{n} } \end{align}

licznik rośnie wielomianowo, mianownik wykładniczo, więc całość zbiega do zera.

b)

Niech $a_n= {n \choose 6}\left(\frac{1}{6}\right)^6 \left(\frac{5}{6}\right)^{n-6}$,
$b_n = \frac{a_{n+1}}{a_n} = \frac{5\left(n+1\right)}{6(n-5)}$
$b_{35} = 1$, $0 \le b_{36} < 1$
$\forall_{n>36}\quad b_n<b_{36}$
$\forall_{n>36}\quad a_{n+1}=b_n\cdot a_n<b_{36} \cdot a_n$
Indukcyjnie $\forall_{n>36}\quad 0 \le a_{n+1} <\left(b_{36}\right)^{n-36} \cdot a_{36}$
Prawa strona to stała razy stała mniejsza od jeden do n-tej potęgi, co zbiega do zera.

c)

Dla n>36 $a_n\ge 0$ maleje, więc ma granicę g.
$g = \lim_{n\to\infty} a_{n+1} = \lim_{n\to\infty} a_n \cdot \lim_{n\to\infty} b_n = \frac{5}{6}g$
więc g=0.

d)

zdefiniujmy zbiór zdarzeń elementarnych $\Omega_n, |\Omega_n|=6^n$, oraz jego podzbiory:
$A_n$ - zbiór takich z.el., że liczba sukcesów (szóstek) jest równa 6,
$B_n$ - zbiór takich z.el., że liczba sukcesów nie odbiega od $\frac{5}{6}\cdot n$ o ponad $\varepsilon \cdot n$
gdzie np. $\varepsilon=0.01$.
Z prawa wielkich liczb $\forall_{\varepsilon>0} \lim_{n\to\infty} P(|\frac{s_n}{n}-\frac{5}{6}|<\varepsilon) = 1$
czyli $\lim_{n\to\infty} P(B_n) = \lim_{n\to\infty} \frac{|B_n|}{|\Omega_n|}=1$
(Poza pierwszymi kilkoma n) zdarzenia $A_n$ i $B_n$ są rozłączne, więc $|A_n| \le |\Omega_n| - |B_n|$ .
Z powyższej granicy, granicy $\lim \frac{|\Omega_n|}{|\Omega_n|}=1$, arytmetyki granic i trzech ciągów, wynika, że istnieje granica
$\lim P(A_n) = \lim \frac{|A_n|}{|\Omega_n|}$ i równa jest 1-1, czyli 0, ckd.

3.

Można było nieco skrócić korzystając implicite z założenia ${n\choose -1}=0$, które okazuje się zachowuje sporo własności, w tym ${n\choose k}={{n-1}\choose{k-1}}+{{n-1}\choose k}$.
Przy okazji: $\sum\limits_{i=0}^{n} {n\choose i} 1^i\cdot 1^{n-i} = \left(1+1\right)^n = 2^n$ - szybki i prosty sposób, pozwalający na ciekawe uogólnienia.

4.

Tu łatwiej było udowodnić tzw. 'bajeczką' niż indukcyjnie, tzn. mamy teatrzyk, n chłopców i n dziewcząt i dobieramy im kwiatki i pasiaste czapki, rzucamy w nich pomidorami czerwonymi lub zielonymi, dajemy tygrysom na pożarcie… Czasami takie bajkowe wybory trudno wyrazić formalnie, więc można skorzystać z pośredniego sposobu:
Niech $W(x)=(1+x)^{2n}$
Wtedy współczynnik przy $x^n$ to ${2n}\choose n$ (z wzoru dwumianowego, czyli w zasadzie z definicji dwumianu).
Jednocześnie $W(x) = (1+x)^n \cdot (x+1)^n$

(2)
\begin{align} = \left(\sum\limits_{i=0}^{n} {n\choose i}x^i\right)\cdot\left(\sum\limits_{i=0}^{n} {n\choose i}x^{n-i}\right) \end{align}
(3)
\begin{align} = \sum\limits_{i=0}^{n} \sum\limits_{j=0}^{n} {n \choose i}{n \choose j} x^{i+\left(n-j\right)} \end{align}

czyli współczynnik przy $x^n$ jest równy sumie tych składników, w których i=j

(4)
\begin{align} \sum\limits_{i=0}^{n} {n \choose i}{n \choose i} } \end{align}

ckd. Tym sposobem, zamiast machać rękami o 'wyborach', w dość ścisły sposób mówimy o współczynniku. Poza tym większość jest podobna - dzielimy na dwa nawiasy (na dziewczęta i chłopców) i patrzymy na współczynnik przy $x^n$ (wybieramy n osób).

5.

Każdy wskazany graf jest pełny, więc z ścisłej nierówności warunku wynika, że każde dwa wierzchołki mają inny stopień wyjściowy, czyli $d_{out}$ jest injekcją (funkcją różnowartościową). Graf taki jest prosty, więc stopień wyjściowy musi być liczbą z przedziału N={0,1,…,n-1}. Wierzchołków jest n=|N|, więc $d_{out}$ jest bijekcją z V na N (przyjmuje n różnych wartości z n-elementowego zbioru).
Między wierzchołkami dwóch takich grafów V1, V2 istnieje bijekcja $f(v1)=d_{out2}^{-1}(d_{out1}(v1))$
(złożenie $d_{out1}$ z V1 na N i odwrotności $d_{out2}$ z V2 na N jest bijekcją z V1 na V2).
Bijekcja ta jest izomorfizmem, bo

  • krawędź u->v istnieje
  • wtw gdy $d_{out1}(u)>d_{out1}(v)$ (bo graf 1 spełnia warunek)
  • wtw gdy $d_{out2}(f(u))>d_{out2}(f(v))$ (bo $d_{out2}(f(u))=d_{out1}(u)$ z definicji f)
  • wtw gdy krawędź f(u)->f(v) istnieje (bo graf 2 spełnia warunek)

Po ludzku: każdemu wierzchołkowi z V1 można przyporządkować dokładnie jeden wierzchołek z V2 o tym samym stopniu wyjściowym, przy czym krawędzie w takim przyporządkowaniu będą szły od wierzchołków z większym stopniem do tych z mniejszym, więc jest to izomorfizm.
Zadanie można też udowodnić indukcyjnie, tj. każdy taki graf wielkości n+1 da się w ten sam, jednoznaczny sposób skonstruować z grafu wielkości n.

LaTeX

Żeby nawiasy miały odpowiednie rozmiary, trzeba pisać
\left( \frac{ {n\choose k} }{2^n} \right)

(5)
\begin{align} \left( \frac{{n\choose k}}{2^n} \right) \end{align}

zamiast
(\frac{ {n\choose k} }{2^n})

(6)
\begin{align} (\frac{{n\choose k}}{2^n}) \end{align}

Żeby nie wstawiać ich za każdym można użyć pakietu nath
http://www.ctan.org/tex-archive/macros/latex/contrib/nath/
(zapisz plik nath.sty do tego samego folderu co .tex i dopisz \usepackage{nath})
Nath właśnie automatycznie poprawia nawiasy, zmienia (n \choose k) na
\binom{n}{k}, pozwala pisać \root[3]{n}, nie wymaga \limits po \sum i \lim, i ma parę innych udogodnień.
Nie jest do końca kompatybilny z amsmath (z amsfonts i amssymb nie ma problemu).

Do języka polskiego używam
\usepackage[utf8]{inputenc}
\usepackage{polski}
\usepackage[polish]{babel}
\frenchspacing
i zapisuję pliki w kodowaniu utf8, nie wiem czy to wszędzie działa.

Do mnożenia \cdot zamiast *.
Poza tym przydały się tu \forall, \sum\limits_{i=0}^{n}, \lim_{n\to\infty}, {n\choose k}, \le, \Omega, \varepsilon, \frac{1}{2}.

O ile nie zaznaczono inaczej, treść tej strony objęta jest licencją Creative Commons Attribution-ShareAlike 3.0 License