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⩾1. Jest ich 2n, 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 (nk) ciągów binarnych, w których jest k jedynek. Zatem 2n=(n0)+(n1)+…+(nn)
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−1k−1), a w drugim (n−1k). Z drugiej strony liczba sposobów, na jakie można wybrać k-osobową delegację spośród n-osobowej klasy wynosi (nk). Zatem (nk)=(n−1k−1)+(n−1k)
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 (ni), a chłopców (mk−i). Stąd delegację możemy wybrać na k∑i=0(ni)(mk−i) sposobów. Wiemy jednak, że takich wyborów jest (n+mk). W konsekwencji k∑i=0(ni)(mk−i)=(n+mk)
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+1k+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 (ik) takich wyborów. Musimy przy tym pamiętać, by (i+1)⩾(k+1), bo inaczej nie byłoby z kogo wybierać. Dostajemy więc tożsamość (n+1k+1)=n∑i=k(ik)
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 (2nn) takich wyborów, bo wybór jednej grupy determinuje drugą. Jeśli ustalimy liczbę osób z grupy A, powiedzmy 0⩽k⩽n, to z B musimy wybrać n−k osób. Takich wyborów w A możemy dokonać (nk), natomiast w B jest ich (nn−k). Przy ustalonym k mamy więc (nk)(nn−k) wyborów. Dowodzi to tożsamości: (2nn)=n∑k=0(nk)(nn−k)=n∑k=0(nk)2.