Matematyka dyskretna 1/Ćwiczenia 5: Współczynniki dwumianowe

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

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: