Udowodnij kombinatorycznie

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
max123321
Użytkownik
Użytkownik
Posty: 3388
Rejestracja: 26 maja 2016, o 01:25
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 975 razy
Pomógł: 3 razy

Udowodnij kombinatorycznie

Post autor: max123321 »

Udowodnij kombinatorycznie, że dla liczb \(\displaystyle{ n,m \ge 0}\) zachodzi tożsamość:

\(\displaystyle{ \sum_{k=0}^{n}\left\{ {k \choose m} \right\}\left( m+1\right)^{n-k}=\left\{ {n+1 \choose m+1} \right\}}\)

,gdzie \(\displaystyle{ \left\{ {n \choose k} \right\}}\) oznacza liczby Stirlinga drugiego rodzaju.

Jak to zrobić? Prawdopodobnie należy wymyślić jakąś historyjkę, która by obrazowała tę równość, ale zupełnie nie mam pomysłu jak to zrobić.
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Re: Udowodnij kombinatorycznie

Post autor: Premislav »

Ponumerujmy sobie elementy zbioru \(\displaystyle{ n+1}\)-elementowego i ustaw je sobie w jakimś rzędzie czy czymś tam. Na \(\displaystyle{ \left\{k \atop m\right\}}\) sposobów dzielisz zbiór pierwszych \(\displaystyle{ k}\) elementów (\(\displaystyle{ k<n+1}\), bo chcemy żeby jeszcze coś stało dalej, bo musimy zrobić jeszcze jeden podzbiór)
na \(\displaystyle{ m}\) niepustych parami rozłącznych podzbiorów, \(\displaystyle{ k+1}\). element wyznacza podzbiór numer \(\displaystyle{ m+1}\), a pozostałych \(\displaystyle{ n+1-(k+1)=n-k}\) elementów „wrzucasz" do powstałych \(\displaystyle{ m+1}\) niepustych podzbiorów na \(\displaystyle{ (m+1)^{n-k}}\) sposobów, gdyż dla każdego z tych pozostałych \(\displaystyle{ n-k}\) elementów masz \(\displaystyle{ m+1}\) podzbiorów do wyboru.
Oczywiście suma po lewej powinna się zaczynać od \(\displaystyle{ k=m}\), żeby ta interpretacja działała, ale wcześniej są same zera, bo \(\displaystyle{ \left\{k \atop m\right\}=0}\) dla \(\displaystyle{ k, m\in \NN,k<m}\).
Formalnie trzeba pokazać, że w ten sposób zliczam każdy podział zbioru \(\displaystyle{ n+1}\)-elementowego na \(\displaystyle{ m+1}\) niepustych podzbiorów dokładnie raz, ale IMHO to dość oczywiste (\(\displaystyle{ k}\) biorę najmniejsze takie, aby elementy zbioru \(\displaystyle{ \left\{ 1, \ldots k+1\right\}}\) należały łącznie do dokładnie \(\displaystyle{ m+1}\) różnych podzbiorów, oczywiście z zasady minimum takie \(\displaystyle{ k}\) istnieje).
ODPOWIEDZ