Dowód tożsamości kombinatoryczej
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
Dowód tożsamości kombinatoryczej
Zad.Przeprowadzić kombinatoryczny dowód tożsamości \(\sum_{k=1}^{n} k {n \choose k}=n2^{n-1}\)
-
Przemo10
- Stały bywalec
- Posty: 631
- Rejestracja: 12 wrz 2011, 17:15
- Podziękowania: 2 razy
- Otrzymane podziękowania: 218 razy
- Płeć:
Spośród \(n\) osób \(k\) osób idzie do kina. Może być to zarówno \(0\) osób jak i \(n\) osób. Ponadto spośród osób idących do kina jedna osoba kupuje bilety. Na ile sposobów możesz to zrobić ?
Prawa strona: wybieramy 1 osobę kupującą bilety spośród \(n\)- osób oraz wybieramy wszystkie możliwe podzbiory pozostałych \(n-1\) osób. Oczywiście takich podzbiorów będzie \(2^{n-1}\). Stąd prawa strona to \(n \cdot 2^{n-1}\)
Lewa strona. Spośród \(n\) osób wybieramy \(k\) osób, które pojdą do kina. Następnie wybieramy osobę kupującą bilety. Sumujemy po wszystkich możliwościach wyboru \(k\) osób. Stąd lewa strona.
Prawa strona: wybieramy 1 osobę kupującą bilety spośród \(n\)- osób oraz wybieramy wszystkie możliwe podzbiory pozostałych \(n-1\) osób. Oczywiście takich podzbiorów będzie \(2^{n-1}\). Stąd prawa strona to \(n \cdot 2^{n-1}\)
Lewa strona. Spośród \(n\) osób wybieramy \(k\) osób, które pojdą do kina. Następnie wybieramy osobę kupującą bilety. Sumujemy po wszystkich możliwościach wyboru \(k\) osób. Stąd lewa strona.