\(\displaystyle{ \sum_{k=0}^{n} {n\choose k}^2={2n\choose n}}\) co nawet ma jakąś interpretację kombinatoryczną
Ja znam taką interpretację (pochodzi ona z z książki "Markowe wykłady" tylko nie wiem z jakiej części matematyka dyskretna albo teoria liczb...). Dwie osoby mają kolekcję
\(\displaystyle{ n}\) znaczków. Chcą się wymienić. Na ile sposobów mogą to zrobić. Strona prawa to przypadek w którym uczestnicy wybierają
\(\displaystyle{ k}\) znaczków ze swojej kolekcji co każdy z nich może zrobić na
\(\displaystyle{ {n \choose k}}\) sposobów a ponieważ jest ich dwóch to wszystkich sposobów jest
\(\displaystyle{ {n \choose k} ^2}\) i to sumujemy po wszystkich
\(\displaystyle{ k}\) (zaczynając od
\(\displaystyle{ k=0}\) co odzwierciedla wymianę pustą). Strona lewa polega na wyłożeniu na stół przez każdego uczestnika swojej
\(\displaystyle{ n}\) elementowej kolekcji i wybraniu losowo
\(\displaystyle{ n}\) spośród
\(\displaystyle{ 2n}\) znaczków, co robimy na
\(\displaystyle{ {2n \choose n}}\) sposobów. Wybrane znaczni trafiają do jednego a znaczki które zostały do drugiego co odpowiada wymianie.