Matematyka dyskretna 1/Ćwiczenia 5: Współczynniki dwumianowe: Różnice pomiędzy wersjami
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.Ć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}