Loading [MathJax]/jax/output/HTML-CSS/jax.js
Poznański Portal Matematyczny

Tożsamości kombinatoryczne

Autor: Piotr Mizerka

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 n1. 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 k1 osób z n1, 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 n1, które zostały. W pierwszym przypadku takich wyborów mamy (n1k1), a w drugim (n1k). Z drugiej strony liczba sposobów, na jakie można wybrać k-osobową delegację spośród n-osobowej klasy wynosi (nk). Zatem (nk)=(n1k1)+(n1k)

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 ki chłopców. Wyborów dziewcząt mamy w tej sytuacji (ni), a chłopców (mki). Stąd delegację możemy wybrać na ki=0(ni)(mki) sposobów. Wiemy jednak, że takich wyborów jest (n+mk). W konsekwencji ki=0(ni)(mki)=(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)=ni=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 0kn, to z B musimy wybrać nk osób. Takich wyborów w A możemy dokonać (nk), natomiast w B jest ich (nnk). Przy ustalonym k mamy więc (nk)(nnk) wyborów. Dowodzi to tożsamości: (2nn)=nk=0(nk)(nnk)=nk=0(nk)2.

Ta strona wykorzystuje pliki cookies

Ta strona wykorzystuje pliki cookies do zapewniania najwyższej wygody korzystania z serwisu. Te same pliki mogą być wykorzystywane przez współpracujące z nami firmy w celach badawczych. Jeśli wyrażasz zgodę na nasze działania, zamknij ten komunikat. Pamiętaj, że zawsze możesz wyłączyć obsługę plików cookies w swojej przeglądarce.

Zamknij