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}}\)
uzasadnij kombinatorycznie i algebraicznie
-
- 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
uzasadnij kombinatorycznie i algebraicznie
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.
Algebraicznie: wskazówka - dwumian Newtona.
Q.
-
- Użytkownik
- Posty: 2959
- Rejestracja: 8 sie 2009, o 23:05
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 281 razy
- Pomógł: 498 razy
uzasadnij kombinatorycznie i algebraicznie
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ę.
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ę.
-
- 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
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}}\)
\(\displaystyle{ {2n \choose 2} = 2 {n \choose 2} + n^{2}}\)
-
- Użytkownik
- Posty: 2959
- Rejestracja: 8 sie 2009, o 23:05
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 281 razy
- Pomógł: 498 razy
uzasadnij kombinatorycznie i algebraicznie
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ść
Algebraicznie: rozpisz te dwumiany z definicji, wspólny mianownik itp. trochę zabawy i powinno dać tożsamość