Dowód kombinatoryczny

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
lel1101
Użytkownik
Użytkownik
Posty: 33
Rejestracja: 17 paź 2012, o 21:31
Płeć: Mężczyzna
Podziękował: 7 razy
Pomógł: 1 raz

Dowód kombinatoryczny

Post autor: lel1101 »

Stosując argumentację kombinatoryczną, udowodnić tożsamość: \(\displaystyle{ \sum_{k=0}^{n} {n \choose k} (m-1) ^{n-k}= m^{n}}\)
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

Dowód kombinatoryczny

Post autor: »

Zliczamy funkcje ze zbioru \(\displaystyle{ \{ 1,2, \ldots , n\}}\) w zbiór \(\displaystyle{ \{ 1,2, \ldots , m\}}\).

Z lewej strony najpierw wybieramy \(\displaystyle{ k}\) argumentów, które przejdą na jedynkę, a pozostałych \(\displaystyle{ n-k}\) przechodzi na dowolną liczbę różną od jedynki. Oczywiście \(\displaystyle{ k}\) może przyjmować wartości od \(\displaystyle{ 0}\) (gdy jedynka nie należy do zbioru wartości funkcji) do \(\displaystyle{ n}\) (dla funkcji stale równej jeden).

Q.
lel1101
Użytkownik
Użytkownik
Posty: 33
Rejestracja: 17 paź 2012, o 21:31
Płeć: Mężczyzna
Podziękował: 7 razy
Pomógł: 1 raz

Dowód kombinatoryczny

Post autor: lel1101 »

ja to zrobiłam tak:
\(\displaystyle{ (m+x) ^{n}= \sum_{k=0}^{n} {n \choose k} m ^{n-k}x ^{k}}\)
następnie przyjęłam, że x=1 i wyszło mi:
\(\displaystyle{ (m+1) ^{n}= \sum_{k=0}^{n} {n \choose k} m ^{n-k}}\)
i nie wiem co dalej...
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

Dowód kombinatoryczny

Post autor: »

Wystarczyłoby teraz zamiast \(\displaystyle{ m}\) wstawić \(\displaystyle{ m-1}\), ale oczywiście nie jest to argumentacja kombinatoryczna o którą proszono.

Q.
lel1101
Użytkownik
Użytkownik
Posty: 33
Rejestracja: 17 paź 2012, o 21:31
Płeć: Mężczyzna
Podziękował: 7 razy
Pomógł: 1 raz

Dowód kombinatoryczny

Post autor: lel1101 »

racja
dziękuję
ODPOWIEDZ