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ć.
Udowodnij kombinatorycznie
- Premislav
- 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
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).
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).