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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m
Linia 199: Linia 199:
 
Kilka przykładów takich prostokątów przedstawiamy poniżej dla <math>\displaystyle n=5</math> i <math>\displaystyle m=4</math>:
 
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>  
+
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>.
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.  
+
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>.
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  
 
Zatem w sumie jest  

Wersja z 09:08, 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}