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

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\geqslant 0$, 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 {\begin{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}}.\end{aligned}}$

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 \choose 0}{n \choose k}+{n \choose 1}{n-1 \choose k-1}+\ldots +{n \choose k}{n-k \choose 0}=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 \choose 1}^{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}^{n}i{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}^{n}i^{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.

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

<div.thumbcaption>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\times 2$ 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>

<div.thumbcaption>SW 8.CW2.swf

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

<div.thumbcaption>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 {\begin{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}.\end{aligned}}$

Ć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>

<div.thumbcaption>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 \choose 0}=1$ i $\displaystyle f_{2}=1=1+0={1 \choose 0}+{0 \choose 1}$. Ponadto:

$\displaystyle {\begin{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 \choose 0}+\sum _{k=0}^{n-1}{n-k \choose k+1}\\&={n+1 \choose 0}+\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}.\end{aligned}}$