udowodnić tożsamość - dyskretna
-
- Użytkownik
- Posty: 14
- Rejestracja: 19 paź 2011, o 16:34
- Płeć: Kobieta
- Lokalizacja: Bydgoszcz
udowodnić tożsamość - dyskretna
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.
\(\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.
Powód: Poprawa wiadomości.
-
- 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
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.
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.
-
- Użytkownik
- Posty: 14
- Rejestracja: 19 paź 2011, o 16:34
- Płeć: Kobieta
- Lokalizacja: Bydgoszcz
udowodnić tożsamość - dyskretna
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ę
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
- Posty: 14
- Rejestracja: 19 paź 2011, o 16:34
- Płeć: Kobieta
- Lokalizacja: Bydgoszcz
udowodnić tożsamość - dyskretna
słuchaj a mógłbyś mnie jakoś naprowadzić bo nie wiem jak się za to zabrać i co z tym zrobić
-
- Użytkownik
- Posty: 14
- Rejestracja: 19 paź 2011, o 16:34
- Płeć: Kobieta
- Lokalizacja: Bydgoszcz
udowodnić tożsamość - dyskretna
Wiem że to mam przekształcić ale nie wiem właśnie jak i dlatego pytam
-
- 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
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.
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.
-
- Użytkownik
- Posty: 14
- Rejestracja: 19 paź 2011, o 16:34
- Płeć: Kobieta
- Lokalizacja: Bydgoszcz
udowodnić tożsamość - dyskretna
\(\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
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 Qń, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości. Znak mnożenia to \cdot .
Powód: Poprawa wiadomości. Znak mnożenia to \cdot .
-
- 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
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.
\(\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.