# [Help] The number of possible k-sided polygons in an m by n grid of dots

#### 7i5at5

Last edited by a moderator:

#### skipjack

Forum Staff
The "inner pentagon" in my diagram is ignored because it doesn't use any lattice points. This wouldn't, as you say, comply with your last revision of the rules, but your motivation for the rules is unclear, as you keep changing them.

#### DarnItJimImAnEngineer

My gut instinct is that you're going to have to take connectivity into account for k > 4.

I'm guessing your solutions for N3 and N4 bank on counting the number of non-colinear triplets and quadruplets, respectively? If so, the solution for the larger polygons may be fundamentally different.

Incidentally, a brute force computer code should easily be able to do this for max(m,n) up to 100s if not 1000s or more. If this were my project, I would probably try a parametric study of simulations first, look for patterns, follow two or three red herrings, and then give up and table it for a few decades.

#### 7i5at5

That last revision should be the final one - there shouldn't be any other cases left. As long as it forms a simple polygon, it is allowed.

#### DarnItJimImAnEngineer

One last clarification, and I think the rules will be clear for everyone:

1. You have an m by n grid of dots.
2. Pick k dots from the grid
3. Connect the dots to form a k-sided polygon. The connecting line segments cannot intersect each other or pass through another dot. Each dot will only have one line going in and one line going out. See attachment below.
4. Find a function/formula that uses k, m, and n to calculate the total number of distinct k-sided polygons that can be made in this way.
The line segments cannot pass through any other vertex of the polygon, or the line segments cannot pass through any other dot on the m by n grid (other than their own vertices, obviously)?

In other words, would the triangle {(0,0), (0,2), (2,2)} be an acceptable polygon on a 3x3 grid?

#### 7i5at5

One last clarification, and I think the rules will be clear for everyone:

The line segments cannot pass through any other vertex of the polygon, or the line segments cannot pass through any other dot on the m by n grid (other than their own vertices, obviously)?

In other words, would the triangle {(0,0), (0,2), (2,2)} be an acceptable polygon on a 3x3 grid?
No.

#### 7i5at5

Solutions that include cases where {(0,0), (0,2), (2,2)} is acceptable are welcome as well, though. It's still better than nothing.