Matematyka dyskretna 1/Wykład 5: Współczynniki dwumianowe
Zliczanie podzbiorów raz jeszcze
Wiemy już, że dowolny zbiór
-elementowy ma dokładnie podzbiorów. Teraz zajmiemy się pytaniem ile taki zbiór ma podzbiorów o dokładnie elementach. Policzymy zatem liczność rodziny -elemetowych podzbiorów zbioru . Rodzinę tę oznaczać będziemy przez .Współczynnik dwumianowy to liczba -elementowych podzbiorów zbioru -elementowego, tzn. . Wyrażenie czytamy po .
Prawdopodobnie jako pierwszy tej notacji użył Andreas von Ettingshausen w 1826. Jednak liczby te już wcześniej pojawiały się wielokrotnie, choćby w Trójkącie Pascala. Sama nazwa "współczynniki dwumianowe" bierze się stąd, że liczby te pojawiają się w rozwinięciu dwumianu . Zobaczymy to dokładnie w Twierdzeniu 5.7
Przykład
Aby policzyć
skąd wypiszmy wszystkie -elementowe podzbiory -elementowego zbioru . Sa to , , , , , , .
Bezpośrednio z definicji liczb dostajemy:
Obserwacja 5.1
Dla
zachodzi:- ,
- , dla ,
- , dla ,
- , dla .
Dowód
Pierwszy punkt jest natychmiastową konsekwencją faktu, że dowolny zbiór
-elementowy ma tylko jeden -elementowy podzbiór -podzbiór pusty i tylko jeden podzbiór -elementowy - cały zbiór.Drugi punkt jest oczywisty, jako że zbiór
-elementowy nie może mieć podzbiorów o elementach.Dla dowodu trzeciego punktu, zauważmy jedynie, że podzbiorów jednoelementowych jest dokładnie tyle ile elementów w zbiorze.
Wreszcie dla dowodu ostatniego punktu załóżmy, że
. Wtedy funkcja
jest bijekcją. A zatem istotnie .

Nasza następna obserwacja stanowi fundament dla rekurencyjnej procedury obliczania współczynników dwumianowych.
Obserwacja 5.2
Dla
mamy:
Dowód
Podobnie jak przy budowaniu zależności rekurencyjnej przy zliczaniu wszystkich podzbiorów zbioru
-elementowego załóżmy, że . Wtedy, po usunięciu ze zbioru elementu dostajemy -elementowy zbiór . Oczywiście wszystkie -elementowe podzbiory zbioru można podzielić na dwa typy:- albo mają w sobie element ,
- albo go nie mają.
W drugim przypadku są to
-elementowe podzbiory -elementowego zbioru . Jest więc ich dokładnie .Każdy zaś podzbiór pierwszego typu, czyli
takie, że jest jednoznacznie wyznaczony przez swoje pozostałe elementów, czyli dla pewnego . A zatem

Trójkąt Pascala (nazwany na cześć Blaise'a Pascala, który napisał znakomitą rozprawę o współczynnikach dwumianowych) bazuje na własności i ustawia liczby w następujący sposób:
- wiersze trójkąta numerowane są kolejnymi liczbami naturalnymi
,
- w każdym wierszy trójkąta występuje dokładnie
Są to kolejno
... | ... | ... | ... | ... | ||||||
Przesunięcie w wierszach, pozwala wyliczyć
jako sumę dwu liczb stojących bezpośrednio nad :Przykład
Napisz program drukujący trójkąt Pascala, ale z liczbami
modulo , tzn. w miejsce wstaw jedynie resztę lub z dzielenia liczby przez . Zaobserwuj na wydruku powstały fraktal. Wyjaśnij dlaczego tak się dzieje.W trójkącie Pascala współczynniki o tym samym górnym indeksie, np.
tworzą wiersz; natomiast współczynniki o ustalonym dolnym indeksie, np.
tworzą przekątną.
Trójkat Pascala ma zera na obrzeżach, a jego wiersze są symetryczne względem pionowej osi przebiegającej przez środek trójkąta. Jest to konsekwencja Obserwacji 5.1. Współczynniki dwumianowe spełniają bardzo wiele ciekawych zależności. Wymienimy tylko te najważniejsze. Zaczniemy od wzoru w postaci zwartej.
Obserwacja 5.3
Dla dowolnych
Dowód
Podamy dwa dowody: kombinatoryczny i indukcyjny.
Dowód kombinatoryczny. Ustalmy pewien
-elementowy zbiór , i wybierajmy po kolei różnych jego elementów, tzn. utwórzmy injekcję . Z wykładu o zliczaniu zbiorów i funkcji wiemy, ze takich injekcji jest . W wyniku takiego wyboru, dostajemy wszakże pewien uporządkowany ciąg elementów zbioru . Wiele takich ciągów wyznacza ten sam -elementowy podzbiór zbioru . Ciągi takie różnią sie jedynie kolejnością elementów, a zatem jest ich tyle ile permutacji zbioru -elemetowego, czyli . Zatem jest dokładnie
podzbiorów -elementowych zbioru -elementowego.
Dowód indukcyjny. Indukcję poprowadzimy względem górnego indeksu
. Dla mamy tylko jeden interesujący nas współczynnik , i rzeczywiście . Załóżmy zatem, że wszystkie współczynniki w -tym wierszu spełniają wzór z tezy i rozważmy dla . Jeśli to . Załóżmy więc, że . Wtedy:

Przykład
Przykład
Wyobraźmy sobie, że znajdujemy się w mieście zbudowanym na planie prostopadle przecinających się ulic. Powiedzmy, że znajdujemy się w punkcie
i chcemy dojść do punktu , tak jak zaznaczono na rysunku.Łatwo zauważyć, że jest wiele najkrótszych dróg prowadzących z
do . Dla przykładu: możemy pójść razy na północ i potem cały czas na wschód, ale także możemy iść najpierw razy na na wschód i dopiero wtedy skręcić na północ.Ile jest najkrótszych dróg z
do ?Zauważmy, że każda najkrótsza droga biegnie przez dokładnie
skrzyżowań (licząc skrzyżowanie w punkcie i nie licząc skrzyżowania w punkcie ). Na każdym takim skrzyżowaniu musimy podjąć decyzję, czy pójść na wschód czy na północ, przy czym musimy iść dokładnie razy na północ i dokładnie razy na wschód.Zatem liczba najkrótszych dróg z
do to liczba wyborów spośród skrzyżowań, trzech, na których pójdziemy na północ, bądź na których pójdziemy na wschód. A zatem liczba ta wynosi .W ogólności załóżmy, że mamy kratkę
i chcemy narysować najkrótszą łamaną po krawędziach kratki łączącą lewy dolny wierzchołek z prawym górnym. Na ile sposobów możemy narysować taką łamaną?Widzimy, że musimy narysować
odcinków jednostkowych, z których dokładnie jest pionowych i dokładnie jest poziomych. Zatem jest
Przykład
Ile rozwiązań ma równanie
gdzie są liczbami naturalnymi?
Użyjmy kratki rozważanej w poprzednim przykładzie do połączenia przeciwległych jej rogów. W kratce rozmiaru
suma poziomych odcinków daje i jest dokładnie takich odcinków, po jednym na każdym poziomie. Jeśli długości tych odcinków oznaczymy odpowiednio przez , to każda taka droga (łamana) na kratce ustala pewne rozwiązanie naszego równania, i każde rozwiązanie równania wyznacza dokładnie jedna drogę (łamaną). Dla przykładu - animacja obok.Zatem istnieje
rozwiązań naszego równania.W ogólności, równanie
Przykład
Ile rozwiązań ma równanie
gdzie są dodatnimi liczbami naturalnymi?
Zauważmy, że każde rozwiązanie tego równania z warunkami
, można otrzymać z rozwiązania w liczbach naturalnych równania
poprzez podstawienie . Na podstawie poprzedniego przykładu poszukiwanych rozwiązań jest zatem .
Rozważmy obiektów (np. punktów) ustawionych w ciągu jeden przy drugim.
Separatorem nazywamy pionową kreskę położoną pomiędzy dwoma punktami. Zatem pomiędzy
punktami mamy możliwych pozycji dla separatora. Zauważmy, że każde rozwiązanie naszego równania jednoznacznie odpowiada jednemu z możliwych rozmieszczeń separatorów wśród pozycji. Liczba punktów do pierwszego separatora to wartość , liczba punktów pomiędzy pierwszym a drugim separatorem to , itd., liczba punktów za ostatnim -szym separatorem to . Dla przykładu:Na odwrót każde rozwiązanie
Zatem liczba rozwiązań naszego równania to liczba rozmieszczeń naszego równania wyznacza jednoznacznie rozłożenie separatorów: pierwszy kładziemy po punktach, drugi po , itd. separatorów na pozycjach, czyli .Przykład
Rozważmy znów kratkę, tym razem kwadratową, wielkości
, i policzmy na ile sposobów można w jej wnętrzu narysować prostokąt tak, aby wszystkie jego boki były równoległe do krawędzi kratki?Zauważmy, że każdy taki prostokąt jest jednoznacznie wyznaczony przez dwie linie poziome (spośród
) oraz dwie linie pionowe (znów spośród ). Rzeczywiście, dowolny prostokąt wyznacza dwie linie poziome i dwie pionowe (te przylegające do jego boków). I na odwrót dowolny wybór linii pozwoli nam nakreślić jednoznacznie prostokąt w kratce.Poziome linie możemy wybrać na
sposobów i pionowe linie także na sposobów. Zatem prostokąt w kratce możemy narysować na dokładnie
Przechodzimy teraz do kolejnych własności współczynników dwumianowych.
Rozpoczniemy od sumowania liczb na przekątnej trójkąta Pascala. Przekątna taka jest oczywiście nieskończona - sumujemy więc tylko jej początkowy fragment.
Obserwacja 5.4 [reguła sumowania po górnym indeksie]
Dla
mamy
Dowód
Ustalmy
-elementowy zbiór Rozważając jego -elementowe podzbiory zwracamy uwagę na element tego podzbioru, który ma największy indeks. Oczywiście jest , gdyż nie ma -elementowych podzbiorów. Równie łatwo jest zauważyć, że jest dokładnie jeden podzbiór -elementowy w którym jest elementem o najwyższym indeksie, jest to zbiór .Policzmy teraz podzbiory zbioru
, w których jest elementem o największym indeksie, przy czym . Oprócz elementu każdy taki zbiór ma dokładnie elementów wybranych z -elementowego zbioru . Wyboru tych elementów można dokonać na sposobów. Zatem podzbiorów zbioru , w których jest elementem o największym indeksie jest dokładnie . Sumując po wszystkich możliwych , czyli otrzymujemy:

Podobnie możemy sumować liczby położone na linii "prostopadłej" do przekątnych Trójkąta Pascala, czyli liczby postaci
.Obserwacja 5.5 [reguła sumowania równoległego]
Dla
mamy:
Dowód
Tożsamość tę udowodnimy wykorzystując dwukrotnie {regułę symetrii} oraz {regułę sumowania po górnym indeksie}:

Obserwacja 5.6 [tożsamość Cauchy'ego, splot Vandermonde'a]
Dla liczb naturalnych
mamy:Dowód
Policzymy liczbę wszystkich wyborów
osób z grona mężczyzn i kobiet, czyli liczbę na jeszcze jeden sposób. Wybierając osób wybieramy najpierw mężczyzn na sposobów, a potem kobiet na sposobów. Pozostaje teraz zsumować po wszystkich możliwych wartościach parametru .
Dwumiany
Poniższe Twierdzenie o Dwumianie wyjaśnia pochodzenie tajemniczej nazwy "współczynniki dwumianowe". Twierdzenie to często przypisuje się Pascalowi. Tymczasem było ono już znane indyjskiemu matematykowi Pingala w III wieku p.n.e..
Obserwacja 5.7 [Twierdzenie o Dwumianie]
Dla
i
Dowód
Przedstawmy najpierw potęgę
w rozwiniętej formie iloczynu:
Korzystając z rozdzielności mnożenia, wyrażenie to staje się sumą składników.
Każdy taki składnik to iloczyn pewnej liczby -ów i pewnej liczby -ów, przy czym łącznie iloczyn taki ma czynników.
A zatem każdy składnik ma postać . Powstaje on poprzez wybór (spośród ) czynników w iloczynie , z których do składnika postaci wchodzi (a tym samym składników, z których wchodzi ). Tym samym składników postaci jest tyle, ile -elementowych podzbiorów zbioru -elementowego, czyli pojawi się w sumie -krotnie.

Twierdzenie o Dwumianie można też udowodnić za pomocą indukcji, co pozostawiamy jako ćwiczenie.
Przykład
Wniosek 5.8
Dla dowolnego
- ,
- ,
- . (Uwaga: )
Dowód
Wszystkie punkty wynikają trywialnie z Twierdzenia o Dwumianie. (Pierwszy jest oczywisty. Dla dwu pozostałych zauważmy jedynie, że
, .) Jednak drugi i trzeci punkt mają ładną interpretację kombinatoryczną.Istotnie, liczba podzbiorów zbiorów
elementowego to . Z drugiej strony licząc te podzbiory, możemy kolejno zliczać podzbiory -elementowe - jest ich .Nieco dłuższy jest argument kombinatoryczny dla naprzemiennej sumy
. Dla jest to oczywiste. Natomiast dla jest to równoważne stwierdzeniu, że dla -elementowego zbioru- liczba podzbiorów zbioru o parzystej liczbie elementów jest równa liczbie podzbiorów o nieparzystej liczbie elementów.
Załóżmy najpierw, że
jest nieparzyste. Wtedy każdy podzbiór zbioru o parzystej liczbie elementów ma dopełnienie o nieparzystej liczbie elementów, a każdy podzbiór zbioru o nieparzystej liczbie elementów ma dopełnienie o parzystej liczbie elementów. Ta bijektywna odpowiedniość dowodzi, że w istocie jest ich tyle samo.Załóżmy zatem, że
jest parzyste i ustalmy . Zdefiniujmy funkcję , kładąc
Zauważmy, że jest permutacją . Rzeczywiście, dla różnych podzbiorów mamy:
- jeśli i to
- jeśli i to
- jeśli i to i , zatem .
To dowodzi, że
jest injekcją. Dla dowodu surjektywności weźmy dowolne . Jeśli to , jeśli zaś to . Zatem jest permutacją zbioru . Co więcej łatwo zauważyć, że dla o parzystej (nieparzystej) liczbie elementów ma nieparzystą (parzystą) liczbę elementów. To dowodzi, że dla parzystego podzbiorów o parzystej liczbie elementów jest tyle samo co podzbiorów o nieparzystej liczbie elementów.
Uogólniony współczynnik dwumianowy
Wniosek 5.8 pozwala na ustalenie wartość sumy całego wiersza w Trójkącie Pascala i wartość naprzemiennej sumy całego wiersza Trójkąta Pascala. W praktyce często pojawia się konieczność (naprzemiennego) sumowania tylko pewnego fragmentu takiego wiersza.Do tego pomocne mogłyby być sumy postaci:
dla .
Niestety nie jest znana żadna zwarta postać
. Zaskakująca jest natomiast zwarta postać modyfikacji tej sumy polegającej na wymnożeniu każdego składnika przez jego odległość od środka trójkąta. Indukcyjny dowód tak powstałej zależności pozostawiamy jako ćwiczenie.Obserwacja 5.9
Dla
Natomiast naprzemienna częściowa suma
wiersza Trójkąta Pascala ma postać zwartą. Wyprowadzenie takiej postaci odwołuje się do uogólnienia współczynnika dwumianowego na dowolne rzeczywiste indeksy górne, i dowolne całkowite indeksy dolne. Wykorzystuje to poznane już przy okazji rachunku róznicowego pojęcie dolnej silni .Uogólniony współczynnik dwumianowy dla i to:
Zauważmy, że w istocie dla wartości pozostają niezmienione. Oczywiście, dla , interpretacja jako -elementowych liczby podzbiorów zbioru -elementowego pozostaje w mocy. Nie jest natomiast znana sensowna kombinatoryczna interpretacja uogólnionego współczynnika dwumianowego dla pozostałych rzeczywistych wartosci . Odnotujmy tylko, że jest wielomianem -tego stopnia zmiennej . Sporo własności współczynnika dwumianowego przenosi się na wersję uogólnioną. Poniższe zostawiamy bez dowodu jako ćwiczenie.
Obserwacja 5.10
Dla
i mamy- ,
- ,
- ,
- , dla .
Przykład
Z uwagi na to, że w indeksie dolnym mogą występować jedynie liczby całkowite, nie ma sensu reguła symetrii
. Ale nawet dla całkowitych wartości zawodzi:
- jeśli , to ,
- jeśli , to .
Zachowana jest natomiast reguła dodawania.
Obserwacja 5.11
Dla
i
Dowód
Dla ujemnych wartości
wszystkie współczynniki równe są i tożsamość trywialnie zachodzi. Niech teraz i . Oczywiście różnica
jest wielomianem co najwyżej . Może więc, o ile nie jest wielomianem stale równym zero, mieć co najwyżej miejsc zerowych.
Z drugiej strony wiemy już, że ta różnica zeruje się dla wszystkich liczb naturalnych , więc musi być zawsze równa .

Uogólniona reguła dodawania z Obserwacji 5.11 pozwala rozszerzyć Trójkąt Pascala na współczynniki o ujemnych wartościach górnego indeksu.
Kolejne wartości "ujemnej części" możemy wyliczać w następującej kolejności:
Przyjrzyjmy się wartościom dla ustalonego i całkowitych wartości . Zauważalny jest pewien rodzaj symetrii między tymi wartościami. W istocie zachodzi on dla wszystkich rzeczywistych wartości górnego indeksu.
Obserwacja 5.12 [reguła negacji górnego indeksu]
Dla
, :
Dowód
Znaną nam już z Obserwacji 5.5 regułę równoległego sumowania możemy uogólnić za pomocą argumentu podobnego do użytego w dowodzie Obserwacji 5.11.
Obserwacja 5.13
Dla
,
Zauważmy, że rozważana suma jest tylko pozornie nieskończona, gdyż dla wszystkich ujemnych wartości
odpowiednie składniki zerują się. W dalszych ciągu przyjmiemy będziemy również rozważać podobne sumy "nieskończone", ale przy założeniu, że tylko skończenie wiele składników jest niezerowych.Wyposażeni w regułę negacji górnego indeksu wracamy teraz my do naprzemiennej, cześciowej sumy wierszy w Trójkącie Pascala, czyli do
.Obserwacja 5.14
Dla
,
Dowód
Przedstawimy teraz tożsamość, której później użyjemy do zliczenia pewnych, szczególnych permutacji. Zaczniemy od pomocniczej obserwacji.
Obserwacja 5.15 [przestawienie trójmianowe]
Dla
,
Dowód
Zauważmy, że dla
obie strony równości się zerują. Także dla teza jest trywialna. Zatem możemy założyć, że . Wtedy:

Obserwacja 5.16 [reguła odwracania]
Dla funkcji
wtedy i tylko wtedy, gdy
Dowód
Z uwagi na symetrię założeń wystarczy udowodnić tylko jedne implikację. Zakładamy zatem, że
by dostać:
gdzie druga równość wynika ze zmiana kolejności sumowania, trzecia z przestawienia trójmianowego, a ostatnia przez podstawienie .
Z Wniosku 5.8 wiemy, że suma jest niezerowa (i wynosi ) tylko dla . Zatem kontynuując:

Permutacje bez punktów stałych
Nieporządek na zbiorze to permutacja taka, że dla dowolnego , czyli permutacja "bez punktów stałych".
Podsilnia liczby , w skrócie , to liczba nieporządków zbioru -elementowego. Przyjmujemy, że , jako ze jedyna permutacja zbioru pustego - funkcja pusta - w oczywisty sposób nie ma punktów stałych.
Przykład
Zbiór
ma permutacje, ale tylko z nich to nieporządki. Oto ich lista:
Obserwacja 5.17
.
Dowód
Zauważmy najpierw, że liczba permutacji
zbioru -elementowego takich, że dla dokładnie elementów , wynosi . Stąd:
Stosując teraz regułę odwracania, dostajemy:

Współczynniki multimianowe
Współczynniki dwumianowe pojawiały się przy rozwinięciu dwumianu
. Odpowiadały one wyborom dwuwartościowym. Podobnie rozważając trójmian , czy ogólnie , pojawią się współczynniki odpowiadające wyborom odpowiedni trój- i -wartościowym. Wybieranie podzbioru -elementowego ze zbioru -elementowego to podział zbioru na dwie części o odpowiednio i elementach. Naturalnym uogólnieniem, będzie podział zbioru -elementowego na części o odpowiednio elementach, przy czym oczywiście .Współczynnik multimianowy , dla , oraz całkowitych takich, że , to liczba sposobów umieszczenia obiektów w pudełkach z odpowiednio obiektami w pierwszym pudełku, w drugim, itd., oraz w -tym. Jeśli którakolwiek z liczb jest ujemna to współczynnik jest równy . Zauważmy, że z uwagi na symetrię dolnych indeksów, ich kolejność nie jest istotna. Oczywiście to w nowej notacji .
Następna obserwacja wynika wprost z definicji współczynników multimianowych.
Obserwacja 5.18
Dla
, takich, że zachodzi:- ,
- ,
- ,
- ,
- , dla dowolnej permutacji zbioru .
Następna obserwacja wymaga krótkiego uzasadnienia.
Obserwacja 5.19
Dla
takich, że
Dowód
Rozmieszczenie
-obiektów w pudełkach po w każdym, polega na:- wyborze obiektów spośród wszystkich i umieszczeniu ich w pierwszym pudełku - możemy to uczynić na sposobów,
- wyborze obiektów spośród pozostałych i umieszczeniu ich w drugim pudełku - możemy to uczynić na sposobów,
- wyborze obiektów spośród pozostałych
i umieszczeniu ich w trzecim pudełku - możemy to uczynić na
sposobów,- ...
- wyborze obiektów spośród pozostałych i umieszczeniu ich w ostatnim pudełku - możemy to uczynić na sposobów.
Zatem wszystkich możliwych rozmieszczeń zgodnie z wymogami z definicji
współczynnika multimianowego jest dokładnie .
Wniosek 5.20
Dla
takich, że
Dowód
Przykład
Ile liczb możemy ułożyć zapisując w dowolnej kolejności
cyfr: ?Zauważmy, że każda taka liczba powstaje przez wybór dwu pozycji dla cyfry
, jednej dla cyfry , jednej dla cyfry , trzech dla cyfry , jednej dla cyfry , dwu dla cyfry i wreszcie jednej pozycji dla cyfry . Zatem pozycji to nasze obiekty, które rozmieszczamy w siedmiu pudełkach etykietowanych cyframi: . Zatem z definicji współczynnika multimianowego mamy:
Przykład
Rozważmy raz jeszcze podróż w mieście o ulicach na planie siatki. Tym razem jednak...
-wymiarową wersję. Mamy więc do dyspozycji trójwymiarową, prostopadłościenną kratownicę . Na ile sposobów można połączyć przeciwległe wierzchołki prostopadłoscianu najkrótszą możliwą łamaną Zauważmy, że każda najkrótsza możliwa łamana składa się z dokładnie odcinków jednostkowych. Przy czym dokładnie z nich jest poziomych, pionowych i idzie w głąb. Zatem najkrótszych łamanych jest tyle co rozmieszczeń odcinków (obiekty) w pudełkach: "poziomy", "pionowy", "w głąb" tak, by w było ich odpowiednio i . Z definicji współczynnika multimianowego mamy zatem:
łamanych.
Kratka z rysunku o wymiarach
ma zatem: interesujących nas łamanych.Współczynniki multimianowe także zachowują pewną regułę dodawania.
Obserwacja 5.21
Dla
, całkowitych takich, że
Dowód
Ponieważ
, możemy wybrać i ustalić ulubiony obiekt . Możemy go umieścić w jednym z pudełek. Jeśli jednak umieścimy go w pierwszym, to pozostałe obiektów musimy rozłożyć do pudeł zgodnie z warunkami wyjściowymi, ale do pierwszej szuflady mamy włożyć już obiekt mniej ( a nie ). Rozłożenia tego możemy dokonać na . Analogicznie gdy umieścimy w drugim pudle, to pozostałe przedmioty rozkładamy w pudłach odpowiednio po . Po przesumowaniu po numerach pudła, w którym jest dostajemy nasz wzór.
Jako ćwiczenie pozostawiamy dowód następującego uogólnienia wzoru dwumiennego:
Obserwacja 5.22