Ilość prostokątów

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Awatar użytkownika
Hendra
Użytkownik
Użytkownik
Posty: 176
Rejestracja: 18 sty 2015, o 23:42
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 37 razy
Pomógł: 3 razy

Ilość prostokątów

Post autor: Hendra »

Witajcie!
Mam dany prostokąt o wymiarach \(\displaystyle{ 4 \times 8}\). Jest on tym samym podzielony na 32 kwadraty o boku \(\displaystyle{ 1 \times 1}\).
Moim zadaniem jest obliczyć ile jest wszystkich prostokątów na rysunku jak z opisu.
Próbowałem liczyć to "ręcznie", ale niestety metoda jest niezbyt wydajna i łatwo w niej o przeoczenie czegoś. Bardzo prosiłbym o pomoc w znalezieniu bardziej kombinatorycznej metody.
Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 8570
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 306 razy
Pomógł: 3347 razy

Re: Ilość prostokątów

Post autor: kerajs »

Zastanawiałem się na sposobów można umieścić lewy, górny kwadracik prostokąta na planszy \(\displaystyle{ 4 \times 8}\)
dla prostokątów o wymiarach \(\displaystyle{ 1\times 1,1\times 2,...,1\times 8}\) jest to: \(\displaystyle{ 4 \cdot \left( 8+7+...+1\right)}\) możliwości,
dla prostokątów o wymiarach \(\displaystyle{ 2\times 2,2\times 3...2\times 8}\) jest to: \(\displaystyle{ 3 \cdot \left( 7+6+...+1\right)}\) możliwości,
dla prostokątów o wymiarach \(\displaystyle{ 3\times 3,3\times 4,...3\times 8}\) jest to: \(\displaystyle{ 2 \cdot \left( 6+5+...+1\right)}\) możliwości
i dla prostokątów o wymiarach \(\displaystyle{ 4\times 4,4\times 5...4\times 8}\) jest to: \(\displaystyle{ 1 \cdot \left( 5+4+...+1\right)}\) możliwości.
Obracając je o 90 stopni należy dodać jeszcze:
dla prostokątów o wymiarach \(\displaystyle{ 2\times 1,3\times 1,4\times 1}\) jest to: \(\displaystyle{ \left( 3+2+1\right) \cdot 8}\) możliwości,
dla prostokątów o wymiarach \(\displaystyle{ 3\times2,4\times2}\) jest to: \(\displaystyle{ \left( 2+1\right) \cdot 7}\) możliwości
i dla prostokątów o wymiarach \(\displaystyle{ 4\times3}\) jest to: \(\displaystyle{ \left( 1\right) \cdot 6}\) możliwości.

W iloczynie z możliwościami lewy czynnik to ilość możliwych przesunięć prostokąta w poziomie, a prawy w pionie.
ODPOWIEDZ