uzasadnij kombinatorycznie i algebraicznie

[razorr]

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}}\)

[Qń]

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]

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]

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]

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ść