Matematyka dyskretna 1/Ćwiczenia 5: Współczynniki dwumianowe: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Linia 1: Linia 1:
 
==Współczynniki dwumianowe==
 
==Współczynniki dwumianowe==
  
{{cwiczenie|ex dwum srodkowy wyraz trojkata||
+
{{cwiczenie|1|cw 1|
 
 
 
Wskaż największy wyraz w <math>\displaystyle n</math>-tym wierszu Trójkąta Pascala i odpowiedź uzasadnij.
 
Wskaż największy wyraz w <math>\displaystyle n</math>-tym wierszu Trójkąta Pascala i odpowiedź uzasadnij.
  
Linia 19: Linia 18:
 
<math>\displaystyle {n\choose{\left\lfloor n/2 \right\rfloor}}={n\choose{\left\lceil n/2 \right\rceil}}</math>,  
 
<math>\displaystyle {n\choose{\left\lfloor n/2 \right\rfloor}}={n\choose{\left\lceil n/2 \right\rceil}}</math>,  
 
wystarczy pokazać, że  
 
wystarczy pokazać, że  
 +
  
 
<center><math>\displaystyle {n\choose k}<{n\choose k+1},
 
<center><math>\displaystyle {n\choose k}<{n\choose k+1},
 
</math></center>
 
</math></center>
 +
  
 
dla <math>\displaystyle k<\left\lfloor \frac{n}{2} \right\rfloor</math>.  
 
dla <math>\displaystyle k<\left\lfloor \frac{n}{2} \right\rfloor</math>.  
 
Nierówność ta jest równoważna kolejno
 
Nierówność ta jest równoważna kolejno
 +
  
 
<center><math>\displaystyle \aligned \frac{n!}{k!(n-k)!}&<\frac{n!}{(k+1)!(n-k-1)!},\\
 
<center><math>\displaystyle \aligned \frac{n!}{k!(n-k)!}&<\frac{n!}{(k+1)!(n-k-1)!},\\
Linia 31: Linia 33:
 
k&<\frac{n-1}{2}.
 
k&<\frac{n-1}{2}.
 
\endaligned</math></center>
 
\endaligned</math></center>
 +
  
 
Ostatnia nierówność zachodzi dla <math>\displaystyle k<\left\lfloor \frac{n}{2} \right\rfloor</math>,  
 
Ostatnia nierówność zachodzi dla <math>\displaystyle k<\left\lfloor \frac{n}{2} \right\rfloor</math>,  
Linia 37: Linia 40:
 
</div></div>
 
</div></div>
  
{{cwiczenie|ex dwum kolorowanie k podzbiorow n elementowego zbioru 2 kolorami||
+
{{cwiczenie|2|cw 2|
 +
Posługując się interpretacją kombinatoryczną pokaż, że
  
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}
 
<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}.
 
=2^k{n\choose k}.
 
</math></center>
 
</math></center>
 +
  
 
}}
 
}}
Linia 70: Linia 74:
 
</div></div>
 
</div></div>
  
{{cwiczenie|ex dwum wybranie n osob sposrod n mezczyzn i n kobiet||
+
{{cwiczenie|3|cw 3|
 +
Posługując się interpretacją kombinatoryczną pokaż, że
  
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}.
 
<center><math>\displaystyle {n\choose 0}^2+{n\choose1}^2+\ldots+{n\choose n}^2={2n\choose n}.
 
</math></center>
 
</math></center>
 +
  
 
}}
 
}}
Linia 94: Linia 99:
 
</div></div>
 
</div></div>
  
{{cwiczenie|ex dwum wybieranie podzbioru z przywodca||
+
{{cwiczenie|4|cw 4|
 +
Posługując się interpretacją kombinatoryczną pokaż, że
  
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}.
 
<center><math>\displaystyle {n\choose 1}+2{n\choose 2}+\ldots+n{n\choose n}=n2^{n-1}.
 
</math></center>
 
</math></center>
 +
  
 
}}
 
}}
Linia 114: Linia 120:
 
</div></div>
 
</div></div>
  
{{cwiczenie|ex dwum wybieranie podzbioru mezczyzn i kobiet z przywodcami||
+
{{cwiczenie|5|cw 5|
 +
Posługując się interpretacją kombinatoryczną pokaż, że
  
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^2{2n-2\choose n-1}.
 
<center><math>\displaystyle 1^2{n\choose 1}^2+2^2{n\choose 2}^2+\ldots+n^2{n\choose n}=n^2{2n-2\choose n-1}.
 
</math></center>
 
</math></center>
 +
  
 
}}
 
}}
Linia 135: Linia 142:
 
można wybrać podzbiór osób, w którym liczba mężczyzn i kobiet jest równa.  
 
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>,  
 
Nietrudno zauważyć, iż jest to <math>\displaystyle \sum_{i=0}^n{n\choose i}^2</math>,  
a z Zadania [[##ex dwum wybranie n osob sposrod n mezczyzn i n kobiet|Uzupelnic ex dwum wybranie n osob sposrod n mezczyzn i n kobiet|]]  
+
a z [[#cw_3|Ćwiczenia 3]]  
 
wiemy, że <math>\displaystyle \sum_{i=0}^n{n\choose i}^2={2n\choose n}</math>.
 
wiemy, że <math>\displaystyle \sum_{i=0}^n{n\choose i}^2={2n\choose n}</math>.
  
Linia 164: Linia 171:
 
</div>
 
</div>
  
{{cwiczenie|ex dwum liczba prostokatow w kratce n na n||
+
{{cwiczenie|6|cw 6|
 
 
 
Ile prostokątów zawiera się w kratce <math>\displaystyle n\times n</math>?  
 
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>.
 
Dla przykładu w kratce <math>\displaystyle 2\times2</math> jest ich <math>\displaystyle 9</math>.
Linia 206: Linia 212:
  
 
Zatem w sumie jest  
 
Zatem w sumie jest  
 +
  
 
<center>
 
<center>
Linia 211: Linia 218:
 
</math>
 
</math>
 
</center>
 
</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
 
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>
 
<center>
Linia 218: Linia 227:
 
</math>
 
</math>
 
</center>
 
</center>
 +
  
 
</div></div>
 
</div></div>
  
{{cwiczenie|ex dwum tozsamosc z 1/2 w indeksie gornym||
+
{{cwiczenie|7|cw 7|
 +
Udowodnij, że:
  
Udowodnij, że:
 
  
 
<center>
 
<center>
Linia 229: Linia 239:
 
</math>
 
</math>
 
</center>
 
</center>
 +
  
 
}}
 
}}
Linia 239: Linia 250:
 
Dowód przez indukcję względem <math>\displaystyle n</math>.  
 
Dowód przez indukcję względem <math>\displaystyle n</math>.  
 
Dla <math>\displaystyle n=1</math> mamy
 
Dla <math>\displaystyle n=1</math> mamy
 +
  
 
<center>
 
<center>
Linia 244: Linia 256:
 
</math>
 
</math>
 
</center>
 
</center>
 +
  
 
Ponadto:
 
Ponadto:
 +
  
 
<center>
 
<center>
Linia 255: Linia 269:
 
\endaligned</math>
 
\endaligned</math>
 
</center>
 
</center>
 +
  
 
</div></div>
 
</div></div>
  
{{cwiczenie|ex dwum sumka z fibonaccimi||
+
{{cwiczenie|8|cw 8|
 +
Udowodnij, że: 
  
Udowodnij, że: 
 
  
 
<center>
 
<center>
Linia 266: Linia 281:
 
</math>
 
</math>
 
</center>
 
</center>
 +
  
 
gdzie <math>\displaystyle f_n</math> jest <math>\displaystyle n</math>-tą liczbą Fibonacci'ego
 
gdzie <math>\displaystyle f_n</math> jest <math>\displaystyle n</math>-tą liczbą Fibonacci'ego
Linia 285: Linia 301:
 
<math>\displaystyle f_1=1= {0\choose0}=1</math>  i <math>\displaystyle f_2=1=1+0={1\choose0}+{0\choose1}</math>.
 
<math>\displaystyle f_1=1= {0\choose0}=1</math>  i <math>\displaystyle f_2=1=1+0={1\choose0}+{0\choose1}</math>.
 
Ponadto:
 
Ponadto:
 +
  
 
<center>
 
<center>
Linia 296: Linia 313:
 
\endaligned</math>
 
\endaligned</math>
 
</center>
 
</center>
 +
  
 
</div></div>
 
</div></div>

Wersja z 09:06, 2 wrz 2006

Współczynniki dwumianowe

Ćwiczenie 1

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

Wskazówka
Rozwiązanie

Ćwiczenie 2

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



Wskazówka
Rozwiązanie

Ćwiczenie 3

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



Wskazówka
Rozwiązanie

Ćwiczenie 4

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



Wskazówka
Rozwiązanie

Ćwiczenie 5

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



Wskazówka
Rozwiązanie

<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 ? Dla przykładu w kratce jest ich .

Wskazówka
Rozwiązanie

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

<div.thumbcaption>SW 8.CW3.swf

Policzmy ile prostokątów w kratce położonych jest w lewej górnej podkratce 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 i :

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

Zatem jest dokładnie takich prostokątów. Analogicznie jest prostokątów przylegających do dolnej krawędzi podkratki i nieprzylegających do prawej. W końcu jest dokładnie prostokątów leżących w prawym dolnym narożniku podkratki , gdyż są one jednoznacznie wyznaczone przez wybór poziomej linii spośród i pionowej linii spośród .

Zatem w sumie jest



prostokątów w podkratce przylegających do chociaż jednej wewnętrznej krawędzi. Sumując po otrzymujemy liczbę wszystkich prostokątów w kratce , czyli jest ich



Ćwiczenie 7

Udowodnij, że:



Wskazówka
Rozwiązanie

Ćwiczenie 8

Udowodnij, że:



gdzie jest -tą liczbą Fibonacci'ego

Wskazówka
Rozwiązanie

Dowód indukcyjny względem . Dla i mamy odpowiednio i . Ponadto:


Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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}