Tekst źródłowy strony Matematyka dyskretna 1/Ćwiczenia 5: Współczynniki dwumianowe

==Współczynniki dwumianowe==

{{cwiczenie|1|cw 1|
Wskaż największy wyraz w <math>\displaystyle n</math>-tym wierszu Trójkąta Pascala i odpowiedź uzasadnij.

}}

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">  
Największym wyrazem w <math>\displaystyle n</math>-tym wierszu jest wyraz środkowy 
<math>\displaystyle {n \choose {\left\lfloor n/2 \right\rfloor}}={n \choose {\left\lceil n/2 \right\rceil}}</math>. 
Korzystając ze wzoru na postać zwartą współczynnika dwumianowego, 
pokaż <math>\displaystyle {n\choose k}<{n\choose k+1}</math> dla <math>\displaystyle k<\left\lfloor n/2 \right\rfloor</math>.
</div></div>

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  
Ponieważ <math>\displaystyle {n\choose k}={n\choose n-k}</math>, dla <math>\displaystyle n\geqslant k\geqslant0</math>, 
to aby pokazać, że największym wyrazem w <math>\displaystyle n</math>-tym wierszu jest 
<math>\displaystyle {n\choose{\left\lfloor n/2 \right\rfloor}}={n\choose{\left\lceil n/2 \right\rceil}}</math>, 
wystarczy pokazać, że 


<center><math>\displaystyle {n\choose k}<{n\choose k+1},
</math></center>


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


<center><math>\displaystyle \begin{align} \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{align}</math></center>


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

</div></div>

{{cwiczenie|2|cw 2|
Posługując się interpretacją kombinatoryczną pokaż, że


<center><math>\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}.
</math></center>


}}

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">  
Rozważ liczbę kolorowań <math>\displaystyle k</math> rozróżnialnych obiektów wybranych spośród <math>\displaystyle n</math>, 
przy  użyciu dwu kolorów.
</div></div>

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  
Policzmy kolorowania <math>\displaystyle k</math> rozróżnialnych obiektów wybranych spośród <math>\displaystyle n</math>, 
przy  użyciu dwu kolorów (biały i czarny). 
Podzbiór <math>\displaystyle k</math>-elementowy <math>\displaystyle n</math>-elementowego zbioru obiektów można wybrać 
na <math>\displaystyle {n\choose k}</math> sposobów i każdy taki podzbiór możemy pokolorować na <math>\displaystyle 2^k</math> sposobów. 
Zatem liczba interesujących nas kolorowań to <math>\displaystyle 2^k{n\choose k}</math>.

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

{{cwiczenie|3|cw 3|
Posługując się interpretacją kombinatoryczną pokaż, że 


<center><math>\displaystyle {n\choose 0}^2+{n\choose1}^2+\ldots+{n\choose n}^2={2n\choose n}.
</math></center>


}}

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">  
Rozważ liczbę wyborów <math>\displaystyle n</math> osób z <math>\displaystyle 2n</math>-osobowej grupy złożonej z <math>\displaystyle n</math> mężczyzn i <math>\displaystyle n</math> kobiet.

</div></div>

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  
Rozważmy na ile sposobów możemy wybrać <math>\displaystyle n</math> osób z grupy <math>\displaystyle n</math> mężczyzn i <math>\displaystyle n</math> kobiet. 
Oczywiście, z jednej strony, sposobów wyboru <math>\displaystyle n</math> spośród <math>\displaystyle 2n</math> osób jest <math>\displaystyle {2n\choose n}</math>. 
Alternatywnie zauważmy, że wybierając <math>\displaystyle n</math> osób wybieramy <math>\displaystyle i</math> mężczyzn i <math>\displaystyle n-i</math> kobiet 
dla pewnego <math>\displaystyle i\in\left\lbrace 0,\ldots,n \right\rbrace</math>. 
Dla ustalonego <math>\displaystyle i</math> możemy to wykonać na <math>\displaystyle {n\choose i}{n\choose n-i}={n\choose i}^2</math> 
sposobów, zatem sumarycznie liczba możliwości to 
<math>\displaystyle \sum_{i=0}^n{n\choose i}^2</math>, co było do pokazania.
</div></div>

{{cwiczenie|4|cw 4|
Posługując się interpretacją kombinatoryczną pokaż, że


<center><math>\displaystyle {n\choose 1}+2{n\choose 2}+\ldots+n{n\choose n}=n2^{n-1}.
</math></center>


}}

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">  
Rozważ liczbę wyborów z grupy <math>\displaystyle n</math> osób podzbioru z wyznaczonym w nim przywódcą.
</div></div>

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  
Rozważmy na ile sposobów można wybrać z grupy <math>\displaystyle n</math> osób podzbiór z wyznaczonym w nim przywódcą. Z jednej strony możemy najpierw wybrać przywódcę spośród <math>\displaystyle n</math> osób, a później dobrać do niego dowolny podzbiór zbioru pozostałych <math>\displaystyle n-1</math> osób. Możemy to zrobić na <math>\displaystyle n2^{n-1}</math> sposobów.

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

</div></div>

{{cwiczenie|5|cw 5|
Posługując się interpretacją kombinatoryczną pokaż, że


<center><math>\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}.
</math></center>


}}

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">  
Rozważ liczbę wyborów z grupy <math>\displaystyle 2n</math> osobowej złożonej z <math>\displaystyle n</math> mężczyzn i <math>\displaystyle n</math> 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.

</div></div>

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  
Dla rozgrzewki rozważmy, na ile sposobów z grupy <math>\displaystyle 2n</math> osób 
złożonej z <math>\displaystyle n</math> mężczyzn i <math>\displaystyle n</math> 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 <math>\displaystyle \sum_{i=0}^n{n\choose i}^2</math>, 
a z [[#cw_3|Ćwiczenia 3]] 
wiemy, że <math>\displaystyle \sum_{i=0}^n{n\choose i}^2={2n\choose n}</math>.

Zastanówmy się teraz z kolei na ile sposobów można wybrać 
z tej samej <math>\displaystyle 2n</math> 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 <math>\displaystyle i\in\left\lbrace 1,\ldots,n \right\rbrace</math> możemy najpierw wybrać <math>\displaystyle i</math> kobiet i <math>\displaystyle i</math> mężczyzn
na <math>\displaystyle {n\choose i}^2</math> sposobów, 
a potem spośród nich wyłonić przywódców na <math>\displaystyle i^2</math> sposobów. 
Zatem sumarycznie możemy dokonać wyboru na <math>\displaystyle \sum_{i=1}^ni^2{n\choose i}^2</math>.

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

</div></div>

<div class="thumb tright"><div style="width:250px;">
<flash>file=SW 8.CW1.swf|width=250|height=250</flash>
<div.thumbcaption>SW 8.CW1.swf</div></div>
</div>

{{cwiczenie|6|cw 6|
Ile prostokątów zawiera się w kratce <math>\displaystyle n\times n</math>? 
Dla przykładu w kratce <math>\displaystyle 2\times2</math> jest ich <math>\displaystyle 9</math>.

}}

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">  
Rozważ ile prostokątów w kratce <math>\displaystyle n\times n</math> zawiera się w górnej lewej podkratce 
<math>\displaystyle m\times m</math> (dla <math>\displaystyle m<n</math>), 
ale nie zawiera się w górnej lewej podkratce <math>\displaystyle (m-1)\times(m-1)</math>.
</div></div>

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  
<div class="thumb tleft"><div style="width:250px;">
<flash>file=SW 8.CW2.swf|width=250|height=250</flash>
<div.thumbcaption>SW 8.CW2.swf</div></div>
</div>

<div class="thumb tright"><div style="width:250px;">
<flash>file=SW 8.CW3.swf|width=250|height=250</flash>
<div.thumbcaption>SW 8.CW3.swf</div></div>
</div>

Policzmy ile prostokątów w kratce <math>\displaystyle n\times n</math> położonych jest w lewej górnej podkratce 
<math>\displaystyle m\times m</math> 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 <math>\displaystyle n=5</math> i <math>\displaystyle m=4</math>:

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

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

Zatem w sumie jest 


<center>
<math>\displaystyle \frac{m^2(m-1)}{2}+\frac{m^2(m-1)}{2}+m^2=m^3,
</math>
</center>


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


<center>
<math>\displaystyle 1^3+2^3+\ldots+n^3 = \left( \frac{n(n+1)}{2} \right)^2.
</math>
</center>


</div></div>

{{cwiczenie|7|cw 7|
Udowodnij, że: 


<center>
<math>\displaystyle (-4)^n{-\frac{1}{2}\choose n}={2n\choose n}.
</math>
</center>


}}

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">  
Najprościej indukcyjnie.
</div></div>

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  
Dowód przez indukcję względem <math>\displaystyle n</math>. 
Dla <math>\displaystyle n=1</math> mamy


<center>
<math>\displaystyle (-4)^1{-\frac{1}{2}\choose 1}=(-4)\frac{-\frac{1}{2}}{1}=2={2\choose 1}.
</math>
</center>


Ponadto:


<center>
<math>\displaystyle \begin{align} {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{align}</math>
</center>


</div></div>

{{cwiczenie|8|cw 8|
Udowodnij, że:  


<center>
<math>\displaystyle f_{n+1}=\sum_{k=0}^{n}{n-k\choose k}
</math>
</center>


gdzie <math>\displaystyle f_n</math> jest <math>\displaystyle n</math>-tą liczbą Fibonacci'ego

}}

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">  
Dowód indukcyjny.
</div></div>

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  

<div class="thumb tright"><div style="width:250px;">
<flash>file=SW 8.CW4.swf|width=250|height=250</flash>
<div.thumbcaption>SW 8.CW4.swf</div></div>
</div>

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


<center>
<math>\displaystyle \begin{align} 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}. 
\end{align}</math>
</center>


</div></div>