uzasadnij kombinatorycznie i algebraicznie

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
razorr
Użytkownik
Użytkownik
Posty: 29
Rejestracja: 17 kwie 2009, o 15:50
Płeć: Mężczyzna
Podziękował: 14 razy
Pomógł: 1 raz

uzasadnij kombinatorycznie i algebraicznie

Post autor: razorr » 6 wrz 2011, o 11:12

mam problem z takim zadaniem:
uzasadnij kombinatorycznie i algebraicznie
\(\displaystyle{ \sum_{k=1}^{n} {n \choose k} (m - 1)^{n-k} = m^{n} - (m-1)^{n}}\)

Gość Specjalny
Gość Specjalny
Posty: 9834
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2629 razy

uzasadnij kombinatorycznie i algebraicznie

Post autor: » 6 wrz 2011, o 11:29

Kombinatorycznie: wystarczy na dwa sposoby policzyć ile jest takich funkcji ze zbioru \(\displaystyle{ \{1,2, \ldots , n\}}\) w zbiór \(\displaystyle{ \{1,2, \ldots m\}}\), w których zbiorze wartości znajduje się jedynka.
Algebraicznie: wskazówka - dwumian Newtona.

Q.

tometomek91
Gość Specjalny
Gość Specjalny
Posty: 2956
Rejestracja: 8 sie 2009, o 23:05
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 281 razy
Pomógł: 495 razy

uzasadnij kombinatorycznie i algebraicznie

Post autor: tometomek91 » 6 wrz 2011, o 11:44

Kombinatorycznie:
Prawa strona to wszystkie suriekcje ze zbioru n elementowego w zbiór m elementowy minuswszystkie suriekcje zbioru n elementowego w zbiór (m-1) elementowy, czyli jest to ilośc suriekcji, które dla co najmniej jednego argumentu przyjmują m-tą wartość.
Lewa strona zlicza wszystkie te suriekcje: wybieramy k argumentów z n na \(\displaystyle{ {n \choose k}}\) sposobów, dla których funkcja przyjmie wartość m-tą, a dla pozostałych (n-k) argumentów przyporządkowujemy jedną z (m-1) wartości, czyli takich funkcji jest \(\displaystyle{ {n \choose k} (m - 1)^{n-k}}\), sumując po k dostajemy prawą stronę.

razorr
Użytkownik
Użytkownik
Posty: 29
Rejestracja: 17 kwie 2009, o 15:50
Płeć: Mężczyzna
Podziękował: 14 razy
Pomógł: 1 raz

uzasadnij kombinatorycznie i algebraicznie

Post autor: razorr » 6 wrz 2011, o 13:18

jakoś ciężko mi to zrozumieć... dlatego jeszcze jedno zadanie o tej samej treści:
\(\displaystyle{ {2n \choose 2} = 2 {n \choose 2} + n^{2}}\)

tometomek91
Gość Specjalny
Gość Specjalny
Posty: 2956
Rejestracja: 8 sie 2009, o 23:05
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 281 razy
Pomógł: 495 razy

uzasadnij kombinatorycznie i algebraicznie

Post autor: tometomek91 » 6 wrz 2011, o 13:49

Zauważ, że \(\displaystyle{ n^2= {n \choose 1} \cdot {n \choose 1}}\). Lewa strona: wybieramy dwa elementy spośród \(\displaystyle{ 2n}\) nierozróżnialnych. Prawa: dzielimy \(\displaystyle{ 2n}\) elementów na dwa zbiory, po n elementów w każdym i teraz albo wybierzemy dwa elementy z pierwszego zbioru na \(\displaystyle{ {n \choose 2}}\) sposobów, albo z drugiego zbioru też na \(\displaystyle{ {n \choose 2}}\) sposobów, albo wybierzemy jeden elment z pierwszego zbioru i jeden element z drugiego zbioru na \(\displaystyle{ {n \choose 1} \cdot {n \choose 1}}\) sposobów, łacznie mamy \(\displaystyle{ {n \choose 2}+{n \choose 2}+{n \choose 1} \cdot {n \choose 1}=2 {n \choose 2} + n^{2}}\) sposobów.
Algebraicznie: rozpisz te dwumiany z definicji, wspólny mianownik itp. trochę zabawy i powinno dać tożsamość

ODPOWIEDZ