Kombinatoryka
Zad.1.
- Rozważmy historię: mamy [tex]n[/tex] obiektów, chcemy [tex]k[/tex] spośród nich pokolorować jednym z dowolnych dwóch kolorów. Na ile sposobów możemy wykonać taką czynność?
- Z jednej strony możemy:
- najpierw wybrać [tex]k[/tex] obiektów spośród [tex]n[/tex] do pokolorowania [tex]n \choose k[/tex],
- a następnie dla każdego wybrać jeden spośród dwóch kolorów [tex]2^k[/tex]
- co daje nam prawą stronę równania. - Z drugiej strony możemy postępować "od tyłu":
- najpierw wybrać ile spośród [tex]k[/tex] obiektów chcemy pokolorować jednym kolorem [tex]i \le k[/tex],
- następnie policzyć na ile sposobów możemy wybrać te [tex]i[/tex] obiektów do pokolorowania tym kolorem [tex]n \choose i[/tex],
- a wtedy z pozostałych [tex](n-i)[/tex] obiektów na ile sposobów możemy wybrać pozostałe [tex](k-i)[/tex] obiektów do pokolorowania drugim z kolorów [tex]n-i \choose k-i[/tex]
- wybór każdej z możliwych liczby obiektów do pokolorowania pierwszym kolorem [tex]i[/tex] jest równoprawdopodobny, więc finalnie sumujemy po wszystkich wartościach [tex]i[/tex] od [tex]0[/tex] do [tex]k[/tex]
- co daje nam lewą stronę równania.
Zad.2.
- Przekształcamy lewą stronę równania:
[tex]LHS = \sum_{i=0}^k {n \choose i} {n-i \choose k-i} = \sum_{i=0}^k \frac{n!}{i! (n-i)!} \frac{(n-i)!}{(k-i)! (n-k)!} = \frac{n!}{(n-k)!} \sum_{i=0}^k \frac{1}{i! (k-i)!}[/tex] - Przekształcamy prawą stronę równania:
[tex]RHS = 2^k {n \choose k} = 2^k \frac{n!}{k! (n-k)!}[/tex] - Porównując należy więc pokazać, że:
[tex]2^k \frac{1}{k!} = \sum_{i=0}^k \frac{1}{i! (k-i)!}\\2^k = \sum_{i=0}^k \frac{k!}{i! (k-i)!}\\2^k = \sum_{i=0}^k {k \choose i}[/tex]
co kończy dowód.
Dlaczego ostatnia równość kończy dowód?
- spójrzmy na wyrażenie [tex](x+y)^n[/tex]
- z własności dwumianu Newtona jest ono równe:
[tex](x+y)^n = {n \choose 0} x^{n} y^{0} + {n \choose 1} x^{n-1} y^{1} + {n \choose 2} x^{n-2} y^{2} + \ldots + {n \choose n} x^{0} y^{n}[/tex] - innymi słowy:
[tex](x+y)^n = \sum_{i=0}^n {n \choose i} x^{n-i} y^{i}[/tex] - zauważmy teraz, że:
[tex]2^n = (1+1)^n[/tex] - czyli korzystając z dwumianu Newtona:
[tex]2^n = (1+1)^n = \sum_{i=0}^n {n \choose i} 1^{n-i} 1^{i} = \sum_{i=0}^n {n \choose i}[/tex]
