Matematyka dyskretna 1/Ćwiczenia 5: Współczynniki dwumianowe: Różnice pomiędzy wersjami
mNie podano opisu zmian |
|||
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.
Ćwiczenie 2
Posługując się interpretacją kombinatoryczną pokaż, że
Ćwiczenie 3
Posługując się interpretacją kombinatoryczną pokaż, że
Ćwiczenie 4
Posługując się interpretacją kombinatoryczną pokaż, że
Ćwiczenie 5
Posługując się interpretacją kombinatoryczną pokaż, że
<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 .
<flash>file=SW 8.CW3.swf|width=250|height=250</flash>
<div.thumbcaption>SW 8.CW3.swfPoliczmy 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:
Ćwiczenie 8
Udowodnij, że:
gdzie jest -tą liczbą Fibonacci'ego
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}