Dear Ayush
I have solved this using x -sided polygonsa re fomrd from the vertices of n-sided polygon.
I will assume that the polygons have to be non-self-intersecting.
Number the vertices of the original polygon from 1 to N. Now, there are two possibilities. Either vertex 1 is part of the solution polygon or not.
If vertex 1 is part of the solution polygon, vertex 2 and vertex N cannot be. This means that x-1 vertices have to be chosen out of the remaining N-3 vertices such that no two are adjacent. The number of ways of choosing this is equal to the number of integer solutions of y1+y2+....yx=(N-3)-(x-1) with the additional constraints that y1,yx >= 0; y2,y3...yx-1 >=1. This is equal to the number of whole number solutions of y1+y2+..yx=(N-3)-(x-1)-(x-2). This is just (N-x-1)C(x-1).
If vertex 1 is not part of the solution polygon, we need to choose x vertices out of the remaining N-1 vertices under the same constraints. Following the same logic (or just a change of variables), we get the number of such polygons to be equal to (N-x)C(x).
The total number of polygons is thus (N-x-1)C(x-1)+(N-x)C(x).
Regards
Arun (askIITians forum expert)
