Uzasadnić podane przykłady.
: 16 lis 2010, o 19:26
Dostałem zza zadanie wykonać te 5 zadań z mojego nieulubionego działu takiego jak kombinatoryka, w dodatku udowodnić. Nie wiem kompletnie jak się za to wziąć. Proszę o pomoc.
1.Udowodnij równość \(\displaystyle{ \sum_{k=0}^{n} {n \choose k} = 2^{n}}\) Wsk.:Rozważyć ilość wszystkich podzbiorów zbioru n-elementowego.
2.Udowodnij równość \(\displaystyle{ \sum_{r=0}^{k} {n \choose r} {m \choose k-r} = {m+n \choose k}}\) Wsk.: Rozważyć wybór k osób spośród grupy n kobiet i m mężczyzn.
3.Udowodnij równość \(\displaystyle{ \sum_{i=0}^{n} {n \choose i} {n-i \choose k-i} = 2^{k} {n \choose k}}\).Wsk: Rozważyć kolorowanie k spośród n obiektów, mając do dyspozycji dwa kolory.
4.Udowodnij równość \(\displaystyle{ \sum_{k=0}^{n} k {n \choose k} =n2^{n-1}}\) Wsk.Rozważyć pochodną \(\displaystyle{ (1+x)^{n}}\)
5.Udowodnij równość \(\displaystyle{ {n \choose k} {k \choose a}a = {n \choose a} {n-a \choose k-a}}\)
1.Udowodnij równość \(\displaystyle{ \sum_{k=0}^{n} {n \choose k} = 2^{n}}\) Wsk.:Rozważyć ilość wszystkich podzbiorów zbioru n-elementowego.
2.Udowodnij równość \(\displaystyle{ \sum_{r=0}^{k} {n \choose r} {m \choose k-r} = {m+n \choose k}}\) Wsk.: Rozważyć wybór k osób spośród grupy n kobiet i m mężczyzn.
3.Udowodnij równość \(\displaystyle{ \sum_{i=0}^{n} {n \choose i} {n-i \choose k-i} = 2^{k} {n \choose k}}\).Wsk: Rozważyć kolorowanie k spośród n obiektów, mając do dyspozycji dwa kolory.
4.Udowodnij równość \(\displaystyle{ \sum_{k=0}^{n} k {n \choose k} =n2^{n-1}}\) Wsk.Rozważyć pochodną \(\displaystyle{ (1+x)^{n}}\)
5.Udowodnij równość \(\displaystyle{ {n \choose k} {k \choose a}a = {n \choose a} {n-a \choose k-a}}\)