👤
Rozwiązane

Zad.1
Podać dowód kombinatoryczny następującej równości (równość na zdjęciu)
Wskazówka. Rozważyć kolorowanie spośród obiektów, mając do dyspozycji dwa kolory.
Zad.2
Podać dowód analityczny równości z zadania 1.

Zad1 Podać Dowód Kombinatoryczny Następującej Równości Równość Na Zdjęciu Wskazówka Rozważyć Kolorowanie Spośród Obiektów Mając Do Dyspozycji Dwa Kolory Zad2 Po class=

Odpowiedź :

SAPPHO24680ON

Kombinatoryka

Zad.1.

  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ść?
  2. 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.
  3. 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.

  1. 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]
  2. Przekształcamy prawą stronę równania:
    [tex]RHS = 2^k {n \choose k} = 2^k \frac{n!}{k! (n-k)!}[/tex]
  3. 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]


On Studier: Inne Pytanie