Counting problems

[Steven G]

Suppose you have nxm grid. How many rectangles can you make from this grid?

I solved this by realizing that a rectangle is the intersection obtained by highlighting two vertical lines and two horizontal lines of the grid. The answer I got was (_n+1C₂)(_m+1C₂)

I am just wondering how others would solve this.

 

[Romsek]

why n+1 and m+1 ?

 

[Steven G]

why n+1 and m+1 ?

When I saw that you responded I was thinking Oh no! We never do probability problems the same way. You are a trained engineer, correct. I think we went through that discussion once.

In an nxm grid there are n+1 horizontal lines and m+1 vertical lines.

 

[Romsek]

I only see n horizontal lines and m vertical ones

 

[Dr.Peterson]

I only see n horizontal lines and m vertical ones

That's a matter of definition! Does nxm count the spaces (Jomo) or the lines (Romsek)? Since the problem focuses on rectangles (regions), I'd interpret it Jomo's way. But a mathematician wants careful definitions before attacking a problem.

As for how to solve the problem, combinations is the elegant way; if I hadn't seen it, I'd probably use a series, counting different sizes. (Then after I had an answer, I'd slap my head and realize I could get that answer more easily. Which is how math works in real life.

 

[Romsek]

Yeah, I consider a grid to be of points that become vertices, not the space between them. Jomo's interpretation is equally valid.

Combos is the way to go. There's a fairly common problem where you're given a regular polygon with all the vertices having lines drawn between them and you are asked how many possible triangles there are. A real toughy until you realize it's just choosing any 3 vertices.

 

[lookagain]

I am just wondering how others would solve this.

Rectangles also exist in oblique positions for a sufficiently combined large
number of length and width grid points. You need a different/amended
formula for the total number of rectangles.

 

[Steven G]

I only see n horizontal lines and m vertical ones

You need those special glasses to see the last two lines. I can sell you a pair if you want one.

 

[Steven G]

Then after I had an answer, I'd slap my head and realize I could get that answer more easily. Which is how math works in real life.

That is why I posted the problem so other members can see how I did this. For once I was on target. I have no idea how I thought of this method but it seems like the way to go. I gave this problem to a mathematician friend of mine and he actually solved it my way. Mathematicians think so clearly it amazes me.

 

[Romsek]

That is why I posted the problem so other members can see how I did this. For once I was on target. I have no idea how I thought of this method but it seems like the way to go. I gave this problem to a mathematician friend of mine and he actually solved it my way. Mathematicians think so clearly it amazes me.

lookagain made a good point. There's a whole other set of rectangles to be considered and they are going to be described in a more complicated way.

 

[Dr.Peterson]

The main issue to me here is that the problem needs to be clarified. This is interesting.

Suppose you have nxm grid. How many rectangles can you make from this grid?

I solved this by realizing that a rectangle is the intersection obtained by highlighting two vertical lines and two horizontal lines of the grid. The answer I got was (_n+1C₂)(_m+1C₂)

I am just wondering how others would solve this.

You're thinking of the "grid" as a grid of squares, as a chessboard is 8x8; and you're thinking of "making a rectangle" as forming a rectangle by combining some of those squares, or equivalently drawing a rectangle by drawing along the lines in the grid.

I only see n horizontal lines and m vertical ones

Romsek is thinking of the grid as composed of lines, not squares, but still drawing only along the lines. So it's only the count (the meaning of the variables) that's different.

Rectangles also exist in oblique positions for a sufficiently combined large
number of length and width grid points. You need a different/amended
formula for the total number of rectangles.

lookagain is thinking of a grid as a lattice of points, and of making a rectangle as choosing four of the points as vertices of a rectangle.

Those are two different problems, and two ways of describing size. Quite a lot of uncertainty in a few words.

Now, I think the first time I saw this problem (Jomo's form), about 20 years ago, I had first seen the question, "How many squares can be made on a chessboard?" That, I think, has to be done as a sum over size, though there may be a more elegant way. So it probably took me a moment or two to get out of that way of thinking and see the product-of-combinations approach for the rectangle problem.

Now, lookagain's version seems considerably harder to make a general formula for. That is worth pondering!