Enumeration of Polygon Dissections with Prescribed Conditions

Overview

The purpose of this research is to enumerate the number of ways of dissecting a convex polygon with arbitrary prescribed conditions on the allowable polygon pieces. It is well known that the number of ways to dissect a polygon into triangles with noncrossing diagonals is the Catalan number. The starting point of my research is to find the number of ways if, in addition to triangles, polygons of more sides can be used as the dissection pieces. By observing the initial patterns I conjecture the formula for dissecting an (n+2)-gon into a (k_1+2)-gon, a (k_2+2)-gon, …, a (k_t+2)-gon and triangles. I discover how the parameters k_i affect the counting formula and prove the conjecture by analyzing the figure formed by the dissection. The more general problem for dissecting a polygon with arbitrary prescribed conditions is also solved. The key point is that we find the relation between the number of dissections with repetitive pieces allowed or not. In fact, one of them is a permutation of the other. Let a_n(k_1^{p_1}, k_2^{p_2},…, k_t^{p_t},1^*) be the number of ways to dissect a (n+2)-gon into pi polygons with (k_i + 2) sides (i = 1, 2,…, t ), and n-\sum_{i=1}^{t}k_ip_i triangles. From the above observation we obtain the general formula a_n(k_1^{p_1}, k_2^{p_2},…, k_t^{p_t},1^*)=\frac{1}{\prod_{i=1}^{t}(p_i!)} \frac{(n+\sum_{i=1}^{t}p_i)!}{(n+1)!}\binom{2n-K+\sum_{i=1}^{t}p_i }{n+\sum_{i=1}^{t}p_i }, where K=\sum_{i=1}^{t}k_ip_i. In other words, the enumeration for the number of ways to dissect a convex polygon into arbitrary prescribed polygons is solved.

Awards (2)

• Second Award of $2,000 $2,000
• American Mathematical Society: Third Award of $500 $500

Competition history

• ISEF 2021 Mathematics · Entry MATH011

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.