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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Linia 28: Linia 28:
  
  
<center><math>\displaystyle \aligned \frac{n!}{k!(n-k)!}&<\frac{n!}{(k+1)!(n-k-1)!},\\
+
<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},\\
 
\frac{1}{n-k}&<\frac{1}{k+1},\\
 
k+1&<n-k,\\
 
k+1&<n-k,\\
 
k&<\frac{n-1}{2}.
 
k&<\frac{n-1}{2}.
\endaligned</math></center>
+
\end{align}</math></center>
  
  
Linia 254: Linia 254:
  
 
<center>
 
<center>
<math>\displaystyle \aligned {2(n+1)\choose n+1}
+
<math>\displaystyle \begin{align} {2(n+1)\choose n+1}
 
&=\frac{(2n+1)(2n+2)}{(n+1)^2}{2n\choose n}\\
 
&=\frac{(2n+1)(2n+2)}{(n+1)^2}{2n\choose n}\\
 
&=\frac{2(2n+1)}{n+1}(-4)^n{-\frac{1}{2}\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{(-\frac{1}{2}-n)}{n+1}{-\frac{1}{2}\choose n}\\
 
&=(-4)^{n+1}{-\frac{1}{2}\choose n+1}.
 
&=(-4)^{n+1}{-\frac{1}{2}\choose n+1}.
\endaligned</math>
+
\end{align}</math>
 
</center>
 
</center>
  
Linia 296: Linia 296:
  
 
<center>
 
<center>
<math>\displaystyle \aligned f_{n+2}&=f_n+f_{n+1}\\
+
<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}\\
 
&=\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}\left({n-1-k\choose k}+{n-(k+1)\choose k+1}\right)\\
Linia 303: Linia 303:
 
&=\sum_{k=0}^{n}{n+1-k\choose k}+ {0 \choose n+1}\\
 
&=\sum_{k=0}^{n}{n+1-k\choose k}+ {0 \choose n+1}\\
 
&=\sum_{k=0}^{n+1}{n+1-k\choose k}.  
 
&=\sum_{k=0}^{n+1}{n+1-k\choose k}.  
\endaligned</math>
+
\end{align}</math>
 
</center>
 
</center>
  
  
 
</div></div>
 
</div></div>

Wersja z 13:07, 5 cze 2020

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: