Matematyka dyskretna 1/Ćwiczenia 5: Współczynniki dwumianowe

From Studia Informatyczne

Współczynniki dwumianowe

Ćwiczenie 1

Wskaż największy wyraz w \displaystyle n-tym wierszu Trójkąta Pascala i odpowiedź uzasadnij.

Wskazówka

Największym wyrazem w \displaystyle n-tym wierszu jest wyraz środkowy \displaystyle {n \choose {\left\lfloor n/2 \right\rfloor}}={n \choose {\left\lceil n/2 \right\rceil}}. Korzystając ze wzoru na postać zwartą współczynnika dwumianowego, pokaż \displaystyle {n\choose k}<{n\choose k+1} dla \displaystyle k<\left\lfloor n/2 \right\rfloor.

Rozwiązanie

Ponieważ \displaystyle {n\choose k}={n\choose n-k}, dla \displaystyle n\geqslant k\geqslant0, to aby pokazać, że największym wyrazem w \displaystyle n-tym wierszu jest \displaystyle {n\choose{\left\lfloor n/2 \right\rfloor}}={n\choose{\left\lceil n/2 \right\rceil}}, wystarczy pokazać, że


\displaystyle {n\choose k}<{n\choose k+1},


dla \displaystyle k<\left\lfloor \frac{n}{2} \right\rfloor. Nierówność ta jest równoważna kolejno


\displaystyle \aligned \frac{n!}{k!(n-k)!}&<\frac{n!}{(k+1)!(n-k-1)!},\\ \frac{1}{n-k}&<\frac{1}{k+1},\\ k+1&<n-k,\\ k&<\frac{n-1}{2}. \endaligned


Ostatnia nierówność zachodzi dla \displaystyle k<\left\lfloor \frac{n}{2} \right\rfloor, zatem wszystkie poprzednie też zachodzą.

Ćwiczenie 2

Posługując się interpretacją kombinatoryczną pokaż, że


\displaystyle {n\choose0}{n\choose k}+{n\choose1}{n-1\choose k-1}+\ldots+{n\choose k}{n-k\choose0} =2^k{n\choose k}.


Wskazówka

Rozważ liczbę kolorowań \displaystyle k rozróżnialnych obiektów wybranych spośród \displaystyle n, przy użyciu dwu kolorów.

Rozwiązanie

Policzmy kolorowania \displaystyle k rozróżnialnych obiektów wybranych spośród \displaystyle n, przy użyciu dwu kolorów (biały i czarny). Podzbiór \displaystyle k-elementowy \displaystyle n-elementowego zbioru obiektów można wybrać na \displaystyle {n\choose k} sposobów i każdy taki podzbiór możemy pokolorować na \displaystyle 2^k sposobów. Zatem liczba interesujących nas kolorowań to \displaystyle 2^k{n\choose k}.

Policzmy nasze kolorowania inną metodą.

Zauważmy, iż dowolne kolorowanie posiada \displaystyle i obiektów białych i \displaystyle k-i czarnych dla pewnego \displaystyle i\in\left\lbrace 0,\ldots,k \right\rbrace. Zatem każde kolorowanie możemy jednoznacznie otrzymać wybierając najpierw \displaystyle i obiektów spośród wszystkich \displaystyle n (i kolorując je na biało), a później z pozostałych \displaystyle n-i obiektów wybierając \displaystyle k-i (kolorując je na czarno). Możemy to zrobić na \displaystyle {n\choose i}{n-i\choose k-i} sposobów, czyli sumując po wszystkich możliwych wartościach \displaystyle i otrzymujemy \displaystyle \sum_{i=0}^k{n\choose i}{n-i\choose k-i}.

Ćwiczenie 3

Posługując się interpretacją kombinatoryczną pokaż, że


\displaystyle {n\choose 0}^2+{n\choose1}^2+\ldots+{n\choose n}^2={2n\choose n}.


Wskazówka

Rozważ liczbę wyborów \displaystyle n osób z \displaystyle 2n-osobowej grupy złożonej z \displaystyle n mężczyzn i \displaystyle n kobiet.

Rozwiązanie

Rozważmy na ile sposobów możemy wybrać \displaystyle n osób z grupy \displaystyle n mężczyzn i \displaystyle n kobiet. Oczywiście, z jednej strony, sposobów wyboru \displaystyle n spośród \displaystyle 2n osób jest \displaystyle {2n\choose n}. Alternatywnie zauważmy, że wybierając \displaystyle n osób wybieramy \displaystyle i mężczyzn i \displaystyle n-i kobiet dla pewnego \displaystyle i\in\left\lbrace 0,\ldots,n \right\rbrace. Dla ustalonego \displaystyle i możemy to wykonać na \displaystyle {n\choose i}{n\choose n-i}={n\choose i}^2 sposobów, zatem sumarycznie liczba możliwości to \displaystyle \sum_{i=0}^n{n\choose i}^2, co było do pokazania.

Ćwiczenie 4

Posługując się interpretacją kombinatoryczną pokaż, że


\displaystyle {n\choose 1}+2{n\choose 2}+\ldots+n{n\choose n}=n2^{n-1}.


Wskazówka

Rozważ liczbę wyborów z grupy \displaystyle n osób podzbioru z wyznaczonym w nim przywódcą.

Rozwiązanie

Rozważmy na ile sposobów można wybrać z grupy \displaystyle n osób podzbiór z wyznaczonym w nim przywódcą. Z jednej strony możemy najpierw wybrać przywódcę spośród \displaystyle n osób, a później dobrać do niego dowolny podzbiór zbioru pozostałych \displaystyle n-1 osób. Możemy to zrobić na \displaystyle n2^{n-1} sposobów.

Z drugiej strony możemy najpierw wybrać niepusty podzbiór \displaystyle i-elementowy (dla \displaystyle i\in\left\lbrace 1,\ldots,n \right\rbrace) zbioru \displaystyle n osób, a potem wybrać spośród nich przywódcę na jeden z \displaystyle i sposobów. Sumując po wszystkich \displaystyle i możemy wykonać to na \displaystyle \sum_{i=0}^ni{n\choose i} sposobów, co było do pokazania.

Ćwiczenie 5

Posługując się interpretacją kombinatoryczną pokaż, że


\displaystyle 1^2{n\choose 1}^2+2^2{n\choose 2}^2+\ldots+n^2{n\choose n}^n=n^2{2n-2\choose n-1}.


Wskazówka

Rozważ liczbę wyborów z grupy \displaystyle 2n osobowej złożonej z \displaystyle n mężczyzn i \displaystyle n kobiet podzbioru, w którym liczba kobiet i mężczyzn jest równa i ponadto, w którym wyróżnionych jest dwóch przywódców jeden mężczyzna i jedna kobieta.

Rozwiązanie

Dla rozgrzewki rozważmy, na ile sposobów z grupy \displaystyle 2n osób złożonej z \displaystyle n mężczyzn i \displaystyle n kobiet można wybrać podzbiór osób, w którym liczba mężczyzn i kobiet jest równa. Nietrudno zauważyć, iż jest to \displaystyle \sum_{i=0}^n{n\choose i}^2, a z Ćwiczenia 3 wiemy, że \displaystyle \sum_{i=0}^n{n\choose i}^2={2n\choose n}.

Zastanówmy się teraz z kolei na ile sposobów można wybrać

z tej samej \displaystyle 2n osobowej grupy podzbiór, w którym liczba mężczyzn i kobiet jest równa i dodatkowo wśród wybranych jest wyróżnionych dwóch przywódców: jeden mężczyzna i jedna kobieta.

Dla ustalonego \displaystyle i\in\left\lbrace 1,\ldots,n \right\rbrace możemy najpierw wybrać \displaystyle i kobiet i \displaystyle i mężczyzn

na \displaystyle {n\choose i}^2 sposobów, a potem spośród nich wyłonić przywódców na \displaystyle i^2 sposobów. Zatem sumarycznie możemy dokonać wyboru na \displaystyle \sum_{i=1}^ni^2{n\choose i}^2.

Alternatywnie możemy najpierw wybrać przywódcę jednego spośród \displaystyle n mężczyzn

i jednej spośród \displaystyle n kobiet na \displaystyle n^2 sposobów, a potem uzupełnić wybrańców dobierając im \displaystyle i mężczyzn i tyle samo kobiet, dla \displaystyle i\in\left\lbrace 0,\ldots,n-1 \right\rbrace. Z początkowej naszej refleksji możemy to zrobić na \displaystyle {2n-2\choose n-1} sposobów. Podsumowując, interesującego nas wyboru możemy dokonać na \displaystyle n^2{2n-2\choose n-1}, co było do pokazania.



SW 8.CW1.swf

Ćwiczenie 6

Ile prostokątów zawiera się w kratce \displaystyle n\times n? Dla przykładu w kratce \displaystyle 2\times2 jest ich \displaystyle 9.

Wskazówka

Rozważ ile prostokątów w kratce \displaystyle n\times n zawiera się w górnej lewej podkratce \displaystyle m\times m (dla \displaystyle m<n), ale nie zawiera się w górnej lewej podkratce \displaystyle (m-1)\times(m-1).

Rozwiązanie

<flash>file=SW 8.CW2.swf|width=250|height=250</flash>

SW 8.CW2.swf

<flash>file=SW 8.CW3.swf|width=250|height=250</flash>

SW 8.CW3.swf

Policzmy ile prostokątów w kratce \displaystyle n\times n położonych jest w lewej górnej podkratce \displaystyle m\times m i przylega do chociaż jednej z wewnętrznych (czyli dolnej bądź prawej) krawędzi podkratki. Kilka przykładów takich prostokątów przedstawiamy poniżej dla \displaystyle n=5 i \displaystyle m=4:

Prostokąt przylegający do prawej pionowej krawędzi podkratki \displaystyle m\times m i nieprzylegający do dolnej poziomej krawędzi jest jednoznacznie wyznaczony przez wybór \displaystyle 1 pionowej krawędzi spośród \displaystyle m i dwu poziomych krawędzi spośród \displaystyle m.

Zatem jest dokładnie \displaystyle {m\choose 1}{m\choose 2}=\frac{m^2(m-1)}{2} takich prostokątów. Analogicznie jest \displaystyle \frac{m^2(m-1)}{2} prostokątów przylegających do dolnej krawędzi podkratki \displaystyle m\times m i nieprzylegających do prawej. W końcu jest dokładnie \displaystyle m^2 prostokątów leżących w prawym dolnym narożniku podkratki \displaystyle m\times m, gdyż są one jednoznacznie wyznaczone przez wybór \displaystyle 1 poziomej linii spośród \displaystyle m i \displaystyle 1 pionowej linii spośród \displaystyle m.

Zatem w sumie jest


\displaystyle \frac{m^2(m-1)}{2}+\frac{m^2(m-1)}{2}+m^2=m^3,


prostokątów w podkratce \displaystyle m\times m przylegających do chociaż jednej wewnętrznej krawędzi. Sumując po \displaystyle m\in\left\lbrace 1,\ldots,n \right\rbrace otrzymujemy liczbę wszystkich prostokątów w kratce \displaystyle n\times n, czyli jest ich


\displaystyle 1^3+2^3+\ldots+n^3 = \left( \frac{n(n+1)}{2} \right)^2.


Ćwiczenie 7

Udowodnij, że:


\displaystyle (-4)^n{-\frac{1}{2}\choose n}={2n\choose n}.


Wskazówka

Najprościej indukcyjnie.

Rozwiązanie

Dowód przez indukcję względem \displaystyle n. Dla \displaystyle n=1 mamy


\displaystyle (-4)^1{-\frac{1}{2}\choose 1}=(-4)\frac{-\frac{1}{2}}{1}=2={2\choose 1}.


Ponadto:


\displaystyle \aligned {2(n+1)\choose n+1} &=\frac{(2n+1)(2n+2)}{(n+1)^2}{2n\choose n}\\ &=\frac{2(2n+1)}{n+1}(-4)^n{-\frac{1}{2}\choose n}\\ &=(-4)^{n+1}\frac{(-\frac{1}{2}-n)}{n+1}{-\frac{1}{2}\choose n}\\ &=(-4)^{n+1}{-\frac{1}{2}\choose n+1}. \endaligned


Ćwiczenie 8

Udowodnij, że:


\displaystyle f_{n+1}=\sum_{k=0}^{n}{n-k\choose k}


gdzie \displaystyle f_n jest \displaystyle n-tą liczbą Fibonacci'ego

Wskazówka

Dowód indukcyjny.

Rozwiązanie

<flash>file=SW 8.CW4.swf|width=250|height=250</flash>

SW 8.CW4.swf

Dowód indukcyjny względem \displaystyle n. Dla \displaystyle n=0 i \displaystyle n=1 mamy odpowiednio \displaystyle f_1=1= {0\choose0}=1 i \displaystyle f_2=1=1+0={1\choose0}+{0\choose1}. Ponadto:


\displaystyle \aligned f_{n+2}&=f_n+f_{n+1}\\ &=\sum_{k=0}^{n-1}{n-1-k\choose k}+\sum_{k=0}^n{n-k\choose k}\\ &={n\choose 0}+\sum_{k=0}^{n-1}\left({n-1-k\choose k}+{n-(k+1)\choose k+1}\right)\\ &={n\choose0}+\sum_{k=0}^{n-1}{n-k\choose k+1}\\ &={n+1\choose0}+\sum_{k=1}^{n}{n+1-k\choose k}+ 0\\ &=\sum_{k=0}^{n}{n+1-k\choose k}+ {0 \choose n+1}\\ &=\sum_{k=0}^{n+1}{n+1-k\choose k}.  \endaligned