Rechtecke im Grid |
| 19.05.2019, 16:26 | Ben Gun | Auf diesen Beitrag antworten » |
| Rechtecke im Grid Aus diesem Grid sollen Rechtecke ausgewählt werden. Jedes Rechteck wird durch die linke untere Ecke und die rechte obere Ecke eindeutig festgelegt, z.B. (1, 1) und (2, 3). (s. Anhang) Wie viele Möglichkeiten gibt es solche Rechtecke auszuwählen ? Na ja, es gibt n x m Eckpunkte ... und da könnte ich zwei Eckpunkte auswählen, ohne Reihenfolge, ohne Zurücklegen (Lotto Modell). Aber das ist leider nicht die Lösung. Denn es gibt die Nebenbedingung: Für (x1, y1) und (x2, y2) muss gelten x1 < x2 und y1 < y2. Und das bekomme ich einfach nicht in Griff ! Kann mir jemand einen Ansatz verraten ? |
||
| 19.05.2019, 17:17 | Huggy | Auf diesen Beitrag antworten » |
| RE: Rechtecke im Grid Betrachte zunächst mal eine feste linke untere Ecke. Wieviele Möglichkeiten gibt es, dazu eine rechte obere Ecke auszuwählen? Das ist simpel. Jetzt summiert man über alle möglichen linken unteren Ecken. Dies Doppelsumme ist nicht schwer auszuwerten. |
||
| 19.05.2019, 18:05 | Ben Gun | Auf diesen Beitrag antworten » |
Der Punkt sei (x, y). Dann kann ich (m - x) * (n - y) = (m * n) - (n * x) - (m * y) + (x * y) obere Ecken dazu auswählen. Wir summieren über 0 <= x <= m - 1 und 0 <= y <= n - 1 S = (m * n) * m * n - n * n * (m * (m + 1) / 2) - m * m * (n * (n + 1) / 2) + (m * ( m + 1) / 2) * (n * (n + 1) / 2) Für m = 5 und n = 8 erhalte ich dann 280 Möglichkeiten .... ich hoffe, das ist richtig ? |
||
| 19.05.2019, 18:35 | Leopold | Auf diesen Beitrag antworten » |
Mit der Umindizierung und geht es schneller. Dann ist über und zu summieren, was letztlich als Produkt zweier Summen angesehen werden kann. EDIT In deiner Rechnung scheint ein Fehler zu sein. Es muß statt heißen. Entsprechend bei . |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
