Toźsamości kombinatoryczne.

[dagi]

Udowodnić kombinatorycznie następującą tożsamość :

\(\displaystyle{ {n \choose 2} 2^{n-2} = \sum_{i = 2}^{n} {n \choose i} {i \choose 2}}\)


Będę wdzięczna za wytłumaczenie jak się właśnie robi te dowody kombinatorycznie, bo o ile uzasadnienia algebraiczne w miarę umiem, o tyle uzasadnienia kombinatorycznie nie mam pojęcia :/

????

[tometomek91]

No to chcemy wybrać z pudełka, zawierającego \(\displaystyle{ n}\) kul, dokładnie dwie, a następnie resztę albo pomalować na żółto albo nie malować. Łącznie na wybór i malowanie mamy tyle sposobów ile wynosi lewa strona. Możemy to zrobić też tak, że najpierw wyciągamy pewną ilość kul, powiedzmy \(\displaystyle{ i}\), i z tych wybranych odłożyć na bok dwie, a resztę wybranych pomalować na żółto. Te \(\displaystyle{ n-i}\) pozostałych oczywiście nie ruszamy. Sumując po \(\displaystyle{ i}\) mamy prawą stronę.

[dagi]

To co napisałeś w miarę rozumiem, tylko nie bardzo rozumiem jak udowodnić, że to co opisałeś lewą stroną i to co opisałeś prawą stroną jest sobie równe ?

[tometomek91]

Czyli rozumiemy historyjkę związaną z lewą stroną i historyjkę do prawej strony, problem jest w udowodnieniu, że oba te opowiadanka to ta sama bajka.. No najważniejszy jest morał, który jest taki sam w obu przypadkach: mamy dwie kule odłożone na bok, a resztę albo pomalowane albo nie. Różnią się one tylko sposobem wybierania tych dwóch kul i kul do malowania.

Jeszcze raz
LEWA: wybieramy dwie do odłożenia, a każdą kolejną albo malujemy albo nie - czyli mamy dwie odlożone i część pomalowaną a część nieruszoną.
PRAWA: możemy najpierw wybrać część do malowania, a następnie z tej części dwie odłożyć i, znów kończymy na tym, że mamy dwie odłożone i część pomalowaną a pozostałe nieruszone. Tylko tutaj możemy wybrać tę "część do malowania" albo złozoną z dwóch kul (a nastepnie z tych dwóch wybrać dwie do odłożenia), albo złożoną z trzech kul (i znich dwie na bok) albo z czterech itd. W tym wypadku też kończymy z dwoma kulami na boku i częśćią pomalowaną.