Có bao nhiêu hình chữ nhật phụ trên lưới m x n

Question

Cho một lưới m x n, có bao nhiêu hình chữ nhật phụ duy nhất tồn tại trên lưới như vậy?

Ví dụ:

1 x 1 lưới có 1 hình chữ nhật phụ.

1 x 2 lưới có 3 hình chữ nhật phụ.

Tôi đang tìm một công thức chung có thể được sử dụng để tính toán trực tiếp số hình chữ nhật con hiện có.

Answer 1

Câu trả lời là m(m+1)n(n+1)/4.

hình chữ nhật được xác định bởi hai phép chiếu của nó trên trục x và trên trục y.

chiếu trên trục x: số lượng các cặp (a, b) sao cho 1 < = a < = b < = m = m (m + 1)/2

idem cho trục y

Answer 2

Câu trả lời giống như @Thomash được cung cấp, nhưng với một chút giải thích thêm, đăng cho hậu thế:

Nếu bạn có thể hình dung điều này trong một chiều, thật dễ dàng di chuyển nó thành hai chiều.

Hãy nhìn vào một 1x5:

5 1x1 squares 
+4 1x2 squares 
+3 1x3 squares 
+2 1x4 squares 
+1 1x5 squares = 15 squares. 

Công thức này rất đơn giản: sum = n(1 + n)/ 2. Trong trường hợp của 5, bạn muốn 5 (1 + 5)/2 = 15.

Vì vậy, để có được câu trả lời của bạn, chỉ cần làm điều này cho n và m, và nhân chúng:

sumN = n(1+n)/2 
sumM = m(1+m)/2 
totalRectangles = nm(1+n)(1+m)/4 

Answer 3

Đối điều này cho phép giả sử bạn đã m cột và n hàng:

. . . . 
. . . . 
. . . . 

Trong lưới trên, m là 4 và n là 3. Hãy nói rằng bạn cần phải biết có bao nhiêu hình chữ nhật, bạn có thể hình thành nếu bạn chọn điểm trên bên trái . Nếu bạn chọn top trái góc ví dụ:

* . . . 
. . . . 
. . . . 

Bạn phải có 3 điểm để lựa chọn ở bên phải và 2 điểm để lựa chọn ở phía dưới, do đó tổng hợp là: 3*2 = 6.

Vì vậy tổng số hình chữ nhật bạn có thể tạo thành sẽ tương ứng với tổng số hình chữ nhật tại mỗi điểm bắt đầu từ (0, 0) (top left giả định là 0, 0) đến (m-1, n-1).

Nếu bạn cố gắng tìm tổng kết về điều này:

[(m-1)*(n-1) + (m-2)*(n-1) + (m-3)*(n-1) ... + (n-1)] + 
[(m-1)*(n-2) + (m-2)*(n-2) ... + 1*(n-2)] + 
[(m-1)*(n-3) + (m-2)*(n-3) ... + 1*(n-3)] + 
... 

Đó là bằng

(n-1)*(1 + 2 + .. + m-1) 
+ 
(n-2)*(1 + 2 + .. + m-1) 
+ 
. 
. 
+ 
1*(1 + 2 + ... + m-1) 

Vì vậy, bạn sẽ có được

(1 + 2 + ... + n-1) * (1 + 2 + 3 ... + m-1) 
= mn(n-1)(m-1)/4 

Kể từ m và n là trường hợp của bạn không được số điểm nhưng số lượng các đoạn đường được hình thành. Công thức trên có thể được chuyển đổi:

m = m + 1 
& 
n = n + 1 

Và nó trở thành

(n+1)(m+1)mn/4 

Answer 4

Tôi tìm thấy một giải pháp tốt đẹp,
Cho phép xem xét biên giới bảng của lưới điện.
Và để tạo hình chữ nhật, chúng ta cần bốn điểm trên đường viền.
2 điểm ngang và 2 dọc

ví dụ (n = 4, m = 5)
Lưu ý rằng sự lựa chọn là cho N + 1 và M + 1 Bởi vì chúng ta nhìn vào biên giới và không phải là hình chữ nhật mình

Dưới đây là một ví dụ về một lựa chọn:

Chúng ta có thể tính toán tất cả những lựa chọn có thể chọn 2 điểm ngang và 2 điểm dọc bằng cách sử dụng công thức nhị thức:

Answer 5

Câu trả lời chính xác nên được (m(m+1)n(n+1))/4 trừ đi số vuông trong lưới hình chữ nhật.

Answer 6

Giải pháp thay thế,

Trong lưới m * n, chúng tôi có các đường m + 1 và n + 1 giao nhau.

Chúng tôi sử dụng thực tế, có thể tạo hình chữ nhật bằng cách chọn điểm giao nhau giữa các đường này và một điểm khác không nằm trong đường ngang hoặc dọc.

Vì vậy, số cách để chọn điểm giao nhau là (m + 1) (n + 1). và sau đó là số cách để chọn điểm thứ hai là [đó là số cách để chọn điểm giao cắt trừ các điểm trong cùng một đường ngang và dọc) là ((m + 1) (n + 1) -nm -1)

Bây giờ, hãy xem xét lưới 1x1, chúng tôi sử dụng thực tế lưới này có thể được tính 4 lần mỗi lần duy nhất bởi 4 điểm.

Do đó tổng số các hình chữ nhật có thể được hình thành là [(m + 1) (n + 1) ((m + 1) (n + 1) -nm-1)]/4

có thể được đơn giản hóa hơn nữa thành [(m + 1) (n + 1) (m) (n)]/4