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

#### 7i5at5

Hello. :spin:

This is my first post, so sorry for the potential mistakes below.

A grid of dots has the dimensions m by n, where m is greater than or equal to n. Pick k dots from this grid in such a way that they form a polygon with k sides. In other words, no three dots can be collinear

I want to find a function N(k,m,n) that will determine the total number of possible k-sided polygons using m, n, and k. So far, I have only managed to find the formula for k=3 and k=4, both of which are very long and messy, and doesn't really resemble each other. The formulae's accuracy are also somewhat questionable, but their outputs do correspond to the OEIS sequences A194193, A175383,
A262402, and A296367 so there's that. From k=5 onwards, I am more or less clueless.

Here are the links to a desmos graph containing the N3(k=3) and N4(k=4) formulas:

N3
N4

I'll also attach a PDF containing those formulas for easier readability, and a picture showing the grid and some examples.

Any ideas?

#### Attachments

• 69.8 KB Views: 1
• 18.4 KB Views: 6

#### DarnItJimImAnEngineer

Are you only allowing convex polygons? Because concave polygons with k = 5 or higher can have collinear points (think of a five-pointed star formed from a regular pentagon).

Last edited by a moderator:

#### 7i5at5

Right - sorry - I forgot about that. Concave polygons are allowed too. So ignore the 'no 3-dot collinear' thing, I guess.

Another thing that I didn't mention in my initial post is that some combinations of dots(starting from k=4) can form more than one polygon. I've attached some examples using k=5.

Also - correct me if I'm wrong, but - some combinations(k=5) can have only 3 dots be collinear but not form any pentagon, like:

. o . o .
o . o. o​

So that's something we'll also have to take into account

#### Attachments

• 78.7 KB Views: 0

#### tahirimanov19

Only convex polygons are allowed, I think. And "where m is greater than or equal to n" is irrelevant. One side is always greater than or equal to the other side.
Whats is max(k), given m, n?

#### skipjack

Forum Staff
Is a 5-pointed star acceptable as a polygon?

#### tahirimanov19

So ignore the 'no 3-dot collinear' thing, I guess.
It can't be ignored. Maybe you should post the problem, without your words, or any changes made by you.

#### 7i5at5

Yes, the answers are 4 and 1, respectively.

Whats is max(k), given m, n?
Since k is the number of dots we can pick from the grid (also the number of sides the resulting polygon has), max(k) would be m*n.

#### 7i5at5

It can't be ignored. Maybe you should post the problem, without your words, or any changes made by you.
Sorry for the misunderstanding - my bad - I made mistakes in the initial post.

What the problem wants is:

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.

In my initial post, I gave links to N3 and N4. Those are functions that are specific to k=3 and k=4, respectively. They are separate functions that give the number of triangles and quadrilaterals using m and n. My goal there is to find the similarities between the two, and hopefully use that to make a function that works for all k: N(k,m,n)

I'll be back in about 3 hrs.:spin:

#### Attachments

• 74.6 KB Views: 3