Rechtecke im Stufendreieck
Wie viele Rechtecke kann man in ein quadratisches Gitter zeichnen, die in einem leiterförmigen Polygon
mit parallelen Seiten zum Gitter enthalten sind?
Mit „Treppe“ ist ein Polygon gemeint, das aus zwei senkrechten Seiten gleicher Länge besteht,
die durch eine Treppe mit n gleichen Stufen verbunden sind.
Der einfachste Weg, dies zu sehen, besteht darin, die Leiter unter der Linie y = x - 1 auf der x-Achse zu platzieren
und zu beachten, dass die Koordinaten a, b, c und d, die die vier Eckpunkte eines beliebigen Rechtecks bilden,
unterschiedliche Zahlen zwischen 0 und n+2 sind.
Es gibt also C(n+3, 4) = (n+3)(n+2)(n+2)n/24 Möglichkeiten (siehe OEIS: A000332).