Krótki abstrakt

W artykule omówimy kilka na pozór nieoczywistych tożsamości. Wykażemy ich poprawność próbując interpretować, jakie obiekty przelicza lewa i prawa strona równości.

Ciągi binarne na dwa sposoby

Przyjrzyjmy się na rozgrzewkę ciągom binarnym długości $n\geqslant 1$. Jest ich $2^n$, ponieważ na każdej z $n$ pozycji mamy dwie możliwości jej uzupełnienia. Z drugiej strony, jeśli ustalimy liczbę jedynek w ciągu, to by wyznaczyć ten ciąg, pozostaje jedynie wybrać, na jakich pozycjach się one znajdą. Mamy więc $n\choose k$ ciągów binarnych, w których jest $k$ jedynek. Zatem

$$2^n={n\choose 0}+{n\choose 1}+…+{n\choose n}$$

Symbol Newtona

Chcemy wybrać delegację $k$ uczniów spośród $n$-osobowej klasy. Każda porządna klasa musi mieć przewodniczącego. Jednak nie musi on koniecznie być wybrany do naszej delegacji. Możemy więc nasz wybór rozbić na dwa rozłączne przypadki: z przewodniczącym i bez. Jeśli przewodniczący jest w naszej delegacji, to pozostaje uzupełnić ją o $k-1$ osób z $n-1$, które zostały do wyboru. W przeciwynym wypadku przewodniczący tak naprawdę w ogóle nie liczy się przy wyborze delegacji, możemy go więc „wyrzucić” z klasy na czas wyboru. Wtedy wybieramy $k$ osób spośród $n-1$, które zostały. W pierwszym przypadku takich wyborów mamy ${n-1}\choose {k-1}$, a w drugim ${n-1}\choose {k}$. Z drugiej strony liczba sposobów, na jakie można wybrać $k$-osobową delegację spośród $n$-osobowej klasy wynosi $n\choose k$. Zatem

$${n\choose k} = {{n-1}\choose{k-1}}+{{n-1}\choose {k}}$$

Podzielmy naszą klasę na dziewcząta i chłopców…

Wyboru takiej delegacji możemy dokonać jeszcze w trochę inny sposób…

Załóżmy, że w naszej klasie jest $n$ dziewcząt i $m$ chłopców. Możemy zażądać, by liczba dziewcząt w delegacji była ustalona, powiedzmy równa $i$. Jeśli wybierzemy $i$ dziewczyn, to musimy wybrać jeszcze $k-i$ chłopców. Wyborów dziewcząt mamy w tej sytuacji $n\choose i$, a chłopców $m\choose {k-i}$. Stąd delegację możemy wybrać na

$$\sum_{i=0}^k{n\choose i}{m\choose {k-i}}$$ sposobów. Wiemy jednak, że takich wyborów jest ${n+m}\choose k$. W konsekwencji $$\sum_{i=0}^k{n\choose i}{m\choose {k-i}}={{n+m}\choose k}$$

Nie każdy ma równy wzrost

Przypuśćmy, że w naszej klasie jest $n+1$ uczniów i każdych dwoje ma różny wzrost. Chcemy wybrać $(k+1)$-osobową reprezentację. Możemy z jednej strony zrobić to na ${n+1}\choose{k+1}$ sposobów. Podejdźmy do tego trochę inaczej…

Ustalmy, jaka będzie najwyższa osoba w naszej grupie. Powiedzmy, że ma ona $(i+1)$-szy wzrost w kolejności od najniższego. Pozostaje wybrać wtedy $k$ uczniów do naszej grupy. Wszyscy oni mają wzrosty spośród $i$ najmniejszych. Mamy więc $i\choose k$ takich wyborów. Musimy przy tym pamiętać, by $(i+1)\geqslant(k+1)$, bo inaczej nie byłoby z kogo wybierać. Dostajemy więc tożsamość

$${{n+1}\choose{k+1}}=\sum_{i=k}^n{i\choose k}$$

Znowu te delegacje

Rozważmy $2n$-elementową grupę osób. Ponumerujmy je od $1$ do $2n$. Możemy wyróżnić dwie mniejsze, $n$-elementowe grupy $A=\{1,…,n\}$ oraz $B=\{n+1,…,2n\}$.

Zastanówmy się teraz nad wyborem $n$-osobowej delegacji spośród naszej $2n$-elementowej grupy. Mamy ${2n}\choose n$ takich wyborów, bo wybór jednej grupy determinuje drugą. Jeśli ustalimy liczbę osób z grupy $A$, powiedzmy $0\leqslant k\leqslant n$, to z $B$ musimy wybrać $n-k$ osób. Takich wyborów w $A$ możemy dokonać $n\choose k$, natomiast w $B$ jest ich $n\choose{n-k}$. Przy ustalonym $k$ mamy więc ${n\choose k}{n\choose{n-k}}$ wyborów. Dowodzi to tożsamości:

$${{2n}\choose n}=\sum_{k=0}^n{n\choose k}{n\choose{n-k}}=\sum_{k=0}^n{n\choose k}^2.$$