tożsamość udowadniana kombinatorycznie

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
unn4m3nd
Użytkownik
Użytkownik
Posty: 323
Rejestracja: 26 wrz 2010, o 19:48
Płeć: Mężczyzna
Lokalizacja: Pomorze
Podziękował: 118 razy

tożsamość udowadniana kombinatorycznie

Post autor: unn4m3nd »

Podaj dowód kombinatoryczny (tzn. taki, który odwołuje się do znaczenia liczby postaci \(\displaystyle{ {n \choose k}}\) przy wybieraniu k-elementowych pozbiorów ze zbioru n-elementowego) następującej tożsamości
\(\displaystyle{ m^n = \sum_{i=0}^{n} (m-1)^{n-i} {n \choose i}}\)

Totalnie nie wiem jak udowodnić to kombinatorycznie. Jakieś sugestie?
Pozdr.
Awatar użytkownika
Michalinho
Użytkownik
Użytkownik
Posty: 495
Rejestracja: 17 wrz 2013, o 16:13
Płeć: Mężczyzna
Lokalizacja: Chełm
Podziękował: 11 razy
Pomógł: 104 razy

tożsamość udowadniana kombinatorycznie

Post autor: Michalinho »

Mamy zbiór \(\displaystyle{ A=\{a_1, a_2, \ldots, a_m\}}\).
\(\displaystyle{ m^n}\) to liczba n-elementowych ciągów utworzonych z elementów tego zbioru.
Każdy taki ciąg ma pewną liczbę \(\displaystyle{ i}\) wyrazów równych \(\displaystyle{ a_1}\), a pozostałe \(\displaystyle{ n-i}\) ze zbioru \(\displaystyle{ A\setminus \{a_1\}}\) o mocy \(\displaystyle{ m-1}\). Jest ich więc:
\(\displaystyle{ \sum_{i=0}^{n} {n \choose i} (m-1)^{n-i}}\).
ODPOWIEDZ