Wie viele Unterrechtecke gibt es auf einem m x n-Gitter?

Die Antwort lautet m(m+1)n(n+1)/4 .

Ein Rechteck wird durch seine zwei Projektionen auf der x-Achse und auf der y-Achse definiert.

Projektion auf der x-Achse: Anzahl der Paare (a, b) derart, dass 1 & lt; = a & lt; = b & lt; = m = m (m + 1) / 2

idem für y-Achse

Gleiche Antwort wie @Thomash, aber mit ein wenig mehr Erklärung, Post für die Nachwelt:

Wenn Sie das in einer Dimension herausfinden können, ist es einfach, es in zwei Dimensionen zu verschieben.

Schauen wir uns ein 1x5 an:

Die Formel dafür ist einfach: sum = n(1 + n)/ 2 . Im Fall von 5 möchten Sie 5 (1 + 5) / 2 = 15.

Um Ihre Antwort zu erhalten, tun Sie das einfach für n und m und multiplizieren Sie sie:

Nehmen wir an, Sie haben m columns und n rows:

Im obigen Raster ist m 4 und n ist 3. Sagen wir, Sie müssen wissen, wie viele Rechtecke Sie bilden können, wenn Sie den oberen linken Punkt auswählen. Wenn Sie die obere linke Ecke auswählen, d. H.

Sie haben 3 Punkt, um rechts zu wählen, und 2 Punkte, um unten zu wählen, daher sind die Gesamtkombinationen: 3*2 = 6 .

Daher kann die Gesamtzahl der Rechtecks, die Sie bilden können, der Gesamtzahl der Rechtecke an jedem Punkt entsprechen, beginnend mit (0, 0) ( top left wird als 0, 0 angenommen) bis (m-1, n-1) .

Wenn Sie versuchen, eine Zusammenfassung zu finden:

Was gleich ist

Sie bekommen also

Da m und n Ihr Fall ist, sind nicht die Anzahl der Punkte, sondern die Anzahl der gebildeten Liniensegmente. Die obige Formel kann umgewandelt werden:

Und es wird

Ich habe eine gute Lösung gefunden Schauen wir uns die Tabellenränder des Rasters an.
Um ein Rechteck zu erstellen, benötigen wir vier Punkte an den Rändern.
2 Punkte horizontal und 2 vertikal

zum Beispiel (n = 4,, m = 5)
Beachten Sie, dass die Auswahl für N + 1 und M + 1 erfolgt Weil wir die Grenzen und nicht die Rechtecke selbst betrachten

Hier ist ein Beispiel für eine Auswahl:

Wir können alle möglichen Optionen berechnen, um 2 horizontale Punkte und 2 vertikale Punkte mithilfe der Binomialformel auszuwählen:

Eine alternative Lösung,

In einem m * n-Gitter haben wir m + 1 Zeilen und n + 1 Zeilen, die sich schneiden.

Wir verwenden die Tatsache, dass ein Rechteck gebildet werden kann, indem ein Schnittpunkt zwischen diesen Linien und einem anderen Punkt gewählt wird, der weder in der horizontalen noch in der vertikalen Linie liegt.

So ist die Anzahl der Möglichkeiten, einen Schnittpunkt zu wählen, (m + 1) (n + 1) . und die Anzahl der Möglichkeiten, den zweiten Punkt zu wählen, ist [die Anzahl der Möglichkeiten, einen Schnittpunkt ohne die Punkte in der gleichen horizontalen und vertikalen Linie zu wählen] ist ((m + 1) (n + 1) - nm-1)

Betrachten wir nun ein 1x1-Gitter, verwenden wir die Tatsache, dass dieses Gitter viermal einzeln durch die vier Punkte gezählt werden kann.

Daher ist die Gesamtzahl der Rechtecke, die gebildet werden können, [(m + 1) (n + 1) ((m + 1) (n + 1) -nm-1)] / 4

, das weiter vereinfacht werden kann zu [(m + 1) (n + 1) (m) (n)] / 4

Die richtige Antwort sollte (m(m+1)n(n+1))/4 minus der Anzahl der Quadrate im rechteckigen Raster sein.