udowodnić tożsamość - dyskretna

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
paio0990
Użytkownik
Użytkownik
Posty: 14
Rejestracja: 19 paź 2011, o 16:34
Płeć: Kobieta
Lokalizacja: Bydgoszcz

udowodnić tożsamość - dyskretna

Post autor: paio0990 »

Mam prośbę, czy mógłby mi ktoś pomóc w rozwiązaniu zadania, w którym należy udowodnić tożsamość

\(\displaystyle{ \sum_{k=0}^{n} k ^{2} {n \choose k} =n(n+1)2 ^{n-2}}\)

Prosiłabym również o wytłumaczenie.
Z góry dziękuję za pomoc.
Ostatnio zmieniony 19 paź 2011, o 19:46 przez Nakahed90, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Użytkownik
Użytkownik
Posty: 9833
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2632 razy

udowodnić tożsamość - dyskretna

Post autor: »

Udowodnić jakkolwiek, czy jakimś konkretnym sposobem (np. interpretacją kombinatoryczną)?

Q.
chlorofil
Użytkownik
Użytkownik
Posty: 548
Rejestracja: 16 cze 2010, o 18:30
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 29 razy
Pomógł: 96 razy

udowodnić tożsamość - dyskretna

Post autor: chlorofil »

No właśnie, najprościej będzie interpretacją kombinatoryczną...
paio0990
Użytkownik
Użytkownik
Posty: 14
Rejestracja: 19 paź 2011, o 16:34
Płeć: Kobieta
Lokalizacja: Bydgoszcz

udowodnić tożsamość - dyskretna

Post autor: paio0990 »

najlepiej byłoby interpretacją kombinatoryczną
Użytkownik
Użytkownik
Posty: 9833
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2632 razy

udowodnić tożsamość - dyskretna

Post autor: »

Można na przykład tak: spośród \(\displaystyle{ n}\)-osobowej grupy chcemy wybrać \(\displaystyle{ k}\)-osobową delegację, a w niej przewodniczącego i sekretarza (przy czym może być tak, że obie funkcje sprawuje jedna osoba).

Z jednej strony możemy najpierw wybrać \(\displaystyle{ k}\) osób na \(\displaystyle{ {n\choose k}}\) sposobów, a potem na \(\displaystyle{ k}\) sposobów wybrać przewodniczącego i na \(\displaystyle{ k}\) sposobów sekretarza, co daje łącznie \(\displaystyle{ {n \choose k} \cdot k^2}\) sposobów. To wyrażenie musimy przesumować po \(\displaystyle{ k}\), bo delegacja może liczyć dowolną ilość osób.

Z drugiej strony możemy najpierw wybrać osoby wyróżnione. Jeśli jedna osoba pełni obie funkcje, to wybieramy ją na \(\displaystyle{ n}\) sposobów, a potem dobieramy dowolny podzbiór pozostałych \(\displaystyle{ n-1}\) osób na \(\displaystyle{ 2^{n-1}}\) sposobów. Jeśli funkcje pełnią inne osoby, to na \(\displaystyle{ n}\) sposobów wybieramy przewodniczącego, na \(\displaystyle{ n-1}\) sekretarza i dobieramy im dowolny podzbiór pozostałych \(\displaystyle{ n-2}\) osób na \(\displaystyle{ 2^{n-2}}\) sposobów. W sumie więc możliwości jest:
\(\displaystyle{ n2^{n-1}+n(n-1)2^{n-2}=2^{n-2}(2n+n(n-1))=2^{n-2}n(n+1)}\)

Q.
paio0990
Użytkownik
Użytkownik
Posty: 14
Rejestracja: 19 paź 2011, o 16:34
Płeć: Kobieta
Lokalizacja: Bydgoszcz

udowodnić tożsamość - dyskretna

Post autor: paio0990 »

Dziękuje bardzo za pomoc.

A miałabym jeszcze jedno pytanie bo znalazłam taki wzór:
\(\displaystyle{ (a+b) ^{n}= \sum_{k=0}^{n} {n \choose k} a ^{k}b ^{n-k}}\)

i czy mógłbyś mi wytłumaczyć jak za jego pomocą udowodnić powyższą tożsamość. Bo pewnie mi się to przyda i dobrze by było gdybym to też zrozumiała.

Z góry dziękuję
Użytkownik
Użytkownik
Posty: 9833
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2632 razy

udowodnić tożsamość - dyskretna

Post autor: »

Wskazówka: spróbuj użyć tożsamości \(\displaystyle{ k {n \choose k} =n {n-1 \choose k-1}}\).

Q.
paio0990
Użytkownik
Użytkownik
Posty: 14
Rejestracja: 19 paź 2011, o 16:34
Płeć: Kobieta
Lokalizacja: Bydgoszcz

udowodnić tożsamość - dyskretna

Post autor: paio0990 »

Kombinuje, kombinuje i nic mi nie wychodzi z tego:/
Użytkownik
Użytkownik
Posty: 9833
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2632 razy

udowodnić tożsamość - dyskretna

Post autor: »

Wykonaj chociaż pierwszy krok, przekształcając sumowane wyrażenie zgodnie z podanym wzorem.

Q.
paio0990
Użytkownik
Użytkownik
Posty: 14
Rejestracja: 19 paź 2011, o 16:34
Płeć: Kobieta
Lokalizacja: Bydgoszcz

udowodnić tożsamość - dyskretna

Post autor: paio0990 »

słuchaj a mógłbyś mnie jakoś naprowadzić bo nie wiem jak się za to zabrać i co z tym zrobić
Użytkownik
Użytkownik
Posty: 9833
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2632 razy

udowodnić tożsamość - dyskretna

Post autor: »

Już wszystko napisałem: przekształć wyrażenie \(\displaystyle{ k^2 {n \choose k}}\) przy pomocy przytoczonego wzoru.

Q.
paio0990
Użytkownik
Użytkownik
Posty: 14
Rejestracja: 19 paź 2011, o 16:34
Płeć: Kobieta
Lokalizacja: Bydgoszcz

udowodnić tożsamość - dyskretna

Post autor: paio0990 »

Wiem że to mam przekształcić ale nie wiem właśnie jak i dlatego pytam
Użytkownik
Użytkownik
Posty: 9833
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2632 razy

udowodnić tożsamość - dyskretna

Post autor: »

Naprawdę nie widzisz co można zrobić z wyrażeniem \(\displaystyle{ k \cdot k \cdot {n \choose k}}\) przy użyciu wzoru \(\displaystyle{ k \cdot {n \choose k} =n \cdot {n-1 \choose k-1}}\)?
Bo jeśli problem zaczyna się na tym poziomie, to przed zabieraniem się za wykazywanie tożsamości takich jak z tego wątku, powinnaś poćwiczyć proste przekształcenia algebraiczne.

Q.
paio0990
Użytkownik
Użytkownik
Posty: 14
Rejestracja: 19 paź 2011, o 16:34
Płeć: Kobieta
Lokalizacja: Bydgoszcz

udowodnić tożsamość - dyskretna

Post autor: paio0990 »

\(\displaystyle{ k \cdot n {n -1\choose k-1}}\)

nie wiem czy o to chodzi, nie miałam w ogóle do czynienia z takimi zadaniami. Na pierwszych zajęciach je dostaliśmy do rozwiązania bez żadnego wytłumaczenia ani nic. :/
No i niestety nikt nie potrafi tego rozwiązać, a ja chciałabym się tego nauczyć i dlatego szukam jakiejś pomocy na forum
Ostatnio zmieniony 20 paź 2011, o 17:17 przez , łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości. Znak mnożenia to \cdot .
Użytkownik
Użytkownik
Posty: 9833
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2632 razy

udowodnić tożsamość - dyskretna

Post autor: »

Ok, mamy zatem:
\(\displaystyle{ \sum_{k=0}^{n} k ^{2} {n \choose k}=\sum_{k=1}^{n} k ^{2} {n \choose k}=\sum_{k=1}^{n} kn {n-1 \choose k-1}=n\sum_{k=1}^{n} k {n-1 \choose k-1}}\)
(w pierwszym kroku zmieniliśmy zakres sumowania, bo zerowy wyraz i tak jest równy zero, a w ostatnim kroku wyłączyliśmy przed znak sumy stałą niezależną od indeksu po którym sumujemy).

Teraz mały trik:
\(\displaystyle{ \sum_{k=1}^{n} k {n-1 \choose k-1}=\sum_{k=1}^{n} (k-1+1) {n-1 \choose k-1}=\sum_{k=1}^{n} (k-1) {n-1 \choose k-1}+\sum_{k=1}^{n} {n-1 \choose k-1}}\)

Zauważmy teraz, że:
\(\displaystyle{ \sum_{k=1}^{n} (k-1) {n-1 \choose k-1}=\sum_{k=2}^{n} (k-1) {n-1 \choose k-1}}\)

Spróbuj znów przekształcić sumowane wyrażenie w analogiczny sposób jak poprzednio.

Q.
ODPOWIEDZ