Ile prostokątów można utworzyć na kracie

[MathMaster]

Witam

Mam takie zadanie

Ile różnych prostokątów można utworzyć na kracie wymiaru \(\displaystyle{ n \times n}\) ?

Gdybym uwzględniał sam kształt prostokąta zadanie byłoby banalnie proste. Prostokątów byłoby \(\displaystyle{ n^{2}}\), ale prawdopodobnie muszę uwzględnić również położenie. I teraz zadanie się komplikuje bo ilość położeń jest zależna od kształtu prostokąta, więc nie mam pojęcia jak to zrobić. Przypuszczam, że trzeba użyć kombinacji bez powtórzeń.

Zad. 2

Wykazać, że liczba prostokątów, które dotykają co najmniej jednym bokiem
prawego lub dolnego brzegu \(\displaystyle{ n \times n}\) kraty wynosi \(\displaystyle{ n^{3}}\).

Za te zadanie całkowicie nie mam pomysłu jak się zabrać.

[a4karo]

Wsk. Każdy prostokąt jest jednoznacznie wyznaczony przez lewy dolny i prawy górny wierzchołek. Ile jest takich par punktów?

Ta obserwacja pomoże również rozwiązac zad. 2

[MathMaster]

Nie jestem pewny, ale wydaję mi się, że skoro mamy \(\displaystyle{ n^{2}}\) punktów to liczba tych prostokątów będzie wybranie 2 punktów ze wszystkich \(\displaystyle{ {n^{2} \choose 2}}\), dobrze myślę?

[a4karo]

Chyba nie: powiedziałem, że lewy dolny i prawy gorny, a więc na pewno nie wszystkie

[MathMaster]

No to może następna wskazówka

[a4karo]

Ile jest ponktów na prawo i w górę od \(\displaystyle{ (a,b)}\)?

[MathMaster]

W prawo jest \(\displaystyle{ n-a-1}\)
W górę jest \(\displaystyle{ n-b-1}\)

[a4karo]

NO wlasnie. To teraz wysumuj to po wszystkich \(\displaystyle{ a}\) i \(\displaystyle{ b}\)

[MathMaster]

Przykro mi, ale dalej nie rozumiem, jak mam wysumować, że niby coś takiego?
\(\displaystyle{ n ^{2} \cdot (( \sum_{a=0}^{n-1}a )+( \sum_{b=0}^{n-1}b))}\)

[a4karo]

no nie. Dla każdego \(\displaystyle{ a}\) i \(\displaystyle{ b}\) masz \(\displaystyle{ (n-a-1)(n-b-1)}\) prawych górnych rogów. I te ilości trzeba do siebie dodać

[Hydra147]

Można też powiedzieć, że każdy prostokąt jest jednoznacznie wyznaczony przez dwie proste równoległe do 1. z boków i 2 proste równoległe do 2. Taka obserwacja (moim zdaniem) znacznie ułatwia obliczenia. Ułatwia to też zadanie 2.

[a4karo]

@Hydra147 Fakt, to jest lepszy pomysł

[Hydra147]

A tak w ogóle to jak patrzę na to 2. to wynika z niego pierwsze. Otóż wynik w 1. to suma wyników 2. dla \(\displaystyle{ k=1,2,3,...,n}\) wynosi zatem \(\displaystyle{ \sum_{k=1}^{n} k^{3}= ( \frac{n(n+1)}{2} )^{2}}\).
EDIT:
A co do mojego pomysłu to widziałem go dzisiaj rano w delcie